主要思路
首先仔细剖析出题目意思：我们要规定一个路径，要被经过\(k\)，然后再到路径的两头延伸出不大于 \(k\) 的分支，且每个分支独占一颗子树，求方案数。
那么我们可以先把 \(1\) 定为根，然后算出以点 \(u\) 为端点、分支在子树内的方案数 \(f_u\)，然后再算向父亲侧的方案数 \(g_u\)，再枚举 \((u, v)\)：
BZOJ3527:「ZJOI2014」力
主要思路
首先知道：
\[E_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2} – \sum_{j = i + 1}^{n}\frac{q_j}{(i – j)^2} \]
现在要求所有的。我们可以考虑分成前后两个部分分别计算。先考虑前面的部分：
\[a_i = \sum_{j = 1}^{i – 1}\frac{q_j}{(i – j)^2}\]
我们发现这一部分还是很好计算的：当多项式指数为\(i\)时，对应\(a_i\)，发现\(q_j\)和\((i – j)^2\)的下标相加恰好为\(i\)。正好是卷积的形式。后面那一个部分也可以直接这样算。
「杂题集」- 2019年12月9日
最近都在学些科技，做些板子题。现在搜集一些个人觉得比较好的题目作为12月的第一个杂题集吧。
子集
首先，我们先考虑奇数长度段的情况（\(\{a_n\}\)已经排序）：确定中位数为\(a_{mid}\)，则我们发现答案为 左侧所有减去中位数的和 和 右侧所有减去中位数的和 的和，并除以元素个数。欲使价值最大，那么显然右侧需要靠近右端点进行选择， 而左侧需要靠近中位数进行选择。这个时候我们可以考虑使用二分答案来进行优化：简化对长度的枚举复杂度。
AC 自动机 | Aho-Corasick Automaton
CSP-S2 江西重赛小结
在全国复赛结束之后的两天都在疯狂地补文化课。周二的中午，回班偷看了一下手机就发现一堆未接电话。打开微信的时候就已经看到有人在抱怨江西省重新考试的事情了。
“我日。”
下午就踏上了去青山湖校区的地铁，正好赶上了竞赛课。
拿到题目，第一题 SB 题，特判将月份调大即可。第二题化简和式，我花了比较长的时间才彻底化简。第三题有点懵，第四题打了个暴力，第五题想了一会\(\Theta(n^2)\)就搞出来了\(\Theta(n)\)。写完这些之后我又回去改第三题，重新写了一遍代码就过了样例。可惜因为数组没有开两倍，我的这一部分努力化为了泡影。
简单总结，我并不认为这次 CSP-S2 的成绩能代表我的真实水平：首先，这套题远低于全国卷的难度；其次，数组开小这种傻逼事情有一定的偶然因素。所以，我认为全国卷的难度更能体现江西的水平。
各位全国冬令营再见，我们到时候再来一决高下。
P2125:图书馆书架上的书题解
主要思路
这道题是数学推理的好题。
我们考虑把所有的移动全部作为单向移动，设\(x_i\)为\(i\)向\(i – 1\)移动书本的数量。显然，如果我们要把书向右移动，那么我们就把\(x_{i + 1}\)减去相应的值即可。