Codeforces Round 602(div.1) 比赛总结
cunzai_zsy0531
·
·
个人记录
A
由于保证有解，所以可以先设定一个解，比如前面 k-1 个 ()，后面就是一大堆 (((((()))))) 这样的。
接着按位从左到右考虑，如果这一位和设定的解不一样，那么就从后面找一个一样的 reverse 一下就行了。
B
离线之后从大到小（相同权值先加入编号小的）加入数，平衡树支持插入和查询第 k 小就做完了。
注意一定不能再写 splay 了，以后的平衡树都写 fhqtreap。
C
二分答案（边长），check 的时候做这样一件事：先考虑每个点能不能作为中心点，然后对每个 X 查距离 mid 范围内有没有中心点，这个可以使用二位前缀和实现。所以总的复杂度是 O(nm\log n)，可以通过。
D
无fft的生成函数入门题。
首先可以写出一个 dp 式子：设 dp_{i,j} 表示已经考虑了前 i 位，移动后的数组的值减去原数组的值的差为 j 的方案数，则
dp_{i,j}=\left\{\begin{aligned}{}
k\cdot dp_{i-1,j},h_i=h_{i+1}\\
dp_{i-1,j-1}+dp_{i-1,j+1}+(k-2)\cdot dp_{i-1,j},h_i\neq h_{i+1}
\end{aligned}\right.
这样考虑 dp 数组的生成函数 F(z)=\sum\limits_{i=-\infty}^{\infty}a_iz^i=z^{-1}+(k-2)+z，设 h_i\neq h_{i+1} 的数有 t 个，那么最后要求的就是 dp_0\cdot k^{n-t}\cdot (z^{-1}+(k-2)+z)^t 的正系数之和。
考虑怎么算后面那个东西：首先枚举一个 k-2 项的次数 i，这样式子就变成了 (k-2)^i\cdot (z+z^{-1})^{t-i}，后面这个东西的正系数的和是 \binom{t}{i}\sum_{2j>i}\binom{i}{j}=\binom{t}{i}\cdot \frac{2^i-[2|i]\binom{i}{\frac{i}{2}}}{2}，可以快速计算，所以这题就做完了。