真题汇总

NOIP2020 移球游戏

构造题

10pts：首先就是只有 \((2+1)\) 个柱子的情况（我模拟赛时没想到qwq）。

我们的目的是构造出两根上面都是颜色 \(1\) 和都是颜色 \(2\) 的柱子，然后将 \(2\) 号柱子上的 \(m\) 个分到这两根柱子上去。

这种情况两根上的东西一定就是原来 \(1\) 号的，那么第一步就是要将其分开。分开要腾出两个柱子，而 \(2\) 号柱子是满的，所以我们就可以把 \(2\) 号柱子当作垫脚的先放一部分到 \(3\) 号里去，这样 \(2\) 号就腾出位置来了。

具体的：若 1 中有 cnt 个颜色为 1 的，把 2 顶端的 cnt 个放到 3 号上去。再对 1 号进行出栈，颜色是 1 的全放到 2 号，颜色是 2 的全都放到 3 号。再将 2 号顶端的 cnt 个放回 1，3 号顶端的 m-cnt 个放回 1，3 号剩下垫脚的放回 2。再将 1 号顶端的 m-cnt 个颜色为 2 的放到 3。最后将 2 号的 m 个按颜色分到 1，3 上去。

tips：上面的都是废话，不如自己手模一下。

40pts：

策略就是对于每个规模为 \(n\) 的问题，将所有颜色为 \(n\) 的放到一个柱子上，缩小问题规模为 \(n-1\)。

一个想法：类似于两根柱子一样对于 \(i\) 和 \(n\) 两两在那边搞？不太行，因为颜色为 \(n\) 的个数不足 \(m\) 个，若放在那就会使得没有空的柱子可用。所以我们就要把所有颜色为 \(n\) 的球移到所有柱子上方。发现 10pts 中的转移中就有那么一种状态，即颜色为 \(n\) 的都在上面，颜色不为 \(n\) 的都在下面。但是我们拿来垫脚的那根柱子上是不能有颜色 \(n\) 的，那么一开始优先处理出这个用来垫脚的柱子即可。记录 \(id\)，将柱子的角色转化用 swap id 解决，这样就避免了将球从一个柱子全都移到另一个空柱子上的浪费。复杂度为 \(O(t \times n^2m)\)，\(t\) 为常数。

其实这种方法是可以过的，因为每次问题规模都在减小，奈何人傻常数大（其实可以加上一些策略的化简可以通过，由于我这里的每个步骤都是照搬 10pts 中的，所以有 5~6 的大常数）。

100pts：

其实也是构造题的套路：分治。40pts 中我们每次处理一个颜色的问题，瓶颈在于要把每根柱子的目标颜色移到该柱子上方。这是由于个数不足不能独立操作造成的。但是如果对颜色进行区分，设当前处理区间为 \([l,r]\)，颜色编号为 \([l,mid]\) 的类比为 \(1\)，编号为 \([mid+1,r]\) 的类比为 \(2\)。同样对于柱子的编号 \([l,mid]\) 的为左边柱子，\([mid+1,r]\) 的为右边柱子。对于一个左边柱子和一个右边柱子，无论如何我们都可以弄出一个都是颜色 \(1\) 的柱子或者一个都是颜色 \(2\) 的柱子出来。每一次操作都会完成一个柱子，那么对于规模为 \(n\) 的问题我们就可以在 \(n\) 次操作内使得左边柱子上的颜色编号都为 \(1\)，右边都为 \(2\)，递归解决即可。复杂度 \(O(t \times n m \log n)\)。

CSP-S2019 树的重心

感觉这道题很典。

40 分就是枚举那条边断了，跑两棵树的重心即可。

考虑树的重心的两种求法：一种是找出最大儿子最小的那个点，这偏向于遍历+统计的过程；另一种就是题面中提到的 \(\text{max son} \le \frac{siz}{2}\)。这确是在树的基本形态不变的情况下可以直接求的。那么显然我们要充分利用后者。设点 \(i\) 的 \(\text{max son}\) 为 \(g_i\)。

我们令原树的重心为 \(rt\)，那么对于一个断边后成为重心的节点 \(x(x \not= rt)\) 而言，有性质：断的这条边不会在 \(x\) 的子树里。感性理解就是若 \(x\) 中的边断了，重心 \(rt\) 就会远离 \(x\) 而不是靠近并成为 \(x\)。似乎枚举边后我们没有一个快速的统计方式去进行寻找和统计，那就不妨从“一个点被统计出发”考虑断掉的子树大小为多少会使得该点成为重心。

设断掉的子树大小为 \(S\)，方向明了可以推知：

1. \(x\) 不为 \(rt\)，\(2 \times g_x \le n-S,2 \times (n-S-siz_x) \le n-S\)，可得知 \(S \in [n-2siz_x,n-2g_x]\)。所以 \(x\) 成为重心的条件为 \(S \in [n-2siz_x,n-2g_x] \land \text{S不在x子树中}\)。
2. \(x\) 为 \(rt\)（若 \(rt\) 在断边后仍然为重心)，设最大子树为 \(mx\)，次大为 \(se\)：
   1. 在 \(mx\) 子树中断的边：\(2 \times siz_{se} \le n-S\)；
   2. 在其他子树中断的边：\(2 \times siz_{mx} \le n-S\)；

以上使用树状数组维护。注意其中如何挖去子树中的贡献：进去一次出来一次之差。

NOIP2020 字符串匹配

枚举 \((AB)\)，调和级数时间复杂度内利用前缀和 \(O(n \log n) + O(n C)\) 统计答案。有些卡常且不能用模哈希。
这一做法出来的有些晚，主要因为思考的时候从循环节出发直接思考算法而不是基于问题本身开始考虑。

发现在 \((AB)\) 向后扩展的过程中，对于 \(C = (A^iT)\)，\(i\) 为奇数或 \(i\) 为偶数时值时一样的。所以求出扩展的个数即可 \(O(1)\) 统计。思考如何统计个数。倍增与调和级数无异，常数小一些而已。发现 KMP 中的最小循环节 \(i-nxt_i\)，可求出对于串 \(i\) 由最小循环节 \(j\) 组成，那么只要求出最小循环节 \(j\) 往右的可以向右扩展的最右处即可。注意预处理中的卡常。

CSP-S2019 划分

贪心好题！

考虑 \(f_{i,j}\) 表示前 \(i\) 个数，最后一段为 \([j,i]\) 的最小价值。这会有 36pts。

最后一段长度越小越优。证明：对于长度确定的 \(a + b = len, a \le b\)，那么 \(b\) 越小 \(a^2 + b^2\) 越小（由均值不等式）。

记录 \(d_i\) 为 \(i\) 结尾最优情况下最后一段的长度。\(f[i] \gets f[j] + (pre[i] - pre[j])^2\) 时 \(pre[i]-pre[j] \ge d[j]\)，即 \(pre[i] \ge pre[j]+d[j]\)。我们维护符合条件最大的 \(j\) 即可。

注意数据范围，最后一个 sub 要开 __int128。