A

哈哈，写过的题，看过的性质还能忘，这辈子有了。

一个性质，如果要将 \(A\) 序列通过相邻位置 \(+1\) 或 \(-1\) 操作（总和不变，相当于传递）变为序列 \(B\)，设 \(sa_i=\sum\limits_{j=1}^ia_j\)，\(sb_i=\sum\limits_{j=1}^ia_j\)。

那么最少操作次数为：

理解一下，从左到右考虑，首先 \(a_1\) 要变成 \(b_1\)，需要 \(|a_1-b_1|\) 次操作，\(a_2\) 变成 \(a_2+a_1-b_1\)；\(a_2\) 要变成 \(b_2\)，需要 \(|a_2+a_1-b_1-b_2|\) 次操作，以此类推就是上式。

然后简单 DP，考场当然想到了，然后没有上面的东西不会转移，哈哈。设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 个位置，\(a_i\) 变成了 \(j\)，前缀和为 \(k\) 的最小上式。

这样转移要 \(O(m)\)，感觉是 \(O(nm^3)\) 的是吧。但是你发现枚举到 \(i\) 时，\(a_i\) 的上限是 \(\lfloor\frac{m}{i}\rfloor\)，不然前面的数就无法比它大了。所以 \(\sum\lfloor\frac{m}{i}\rfloor\approx m\log m\)。

总复杂度为 \(O(nm^2\log m)\)，有更好的 \(O(nm^2)\)，我不会。

B

可持久线段树维护哈希+二分加速比较字典序

我的题解

C

简单 DP + 根号分治

我的题解

D

期望题

我的题解

E

不会了哥。

当时看了半天，发现自己平衡树就写了个模板题，能写个寄吧，然后鸽了。然后就考了。

等我训完平衡树凯旋归来，薄纱这道题！

F

树形 DP + 背包

我的题解

总结

算是复习了之前的题，\(7\) 道写过 \(6\) 道就离谱。