2024-11-20总结

糖果堆

先排序。 赛时打表发现，似乎糖果是划分为若干个区间，每个区间前后匹配的：

1233214554

那么考虑 dp，设 \(f_i\) 表示 \(1\sim i\) 的答案，那么可以 \(f_i=\min(f_j,g_{j,i})\)，其中 \(g\) 是这段区间前后匹配的代价，两者都可以 \(O(n^2)\) 计算。

然后发现这样似乎没有什么优化想法，但是如果我们多开一个 \(dp_i\) 表示 \(1\sim i\) 划分为的段数，输出 \(dp_n\) 之后就会惊奇的发现，大样例 1 似乎只有 \(2\) 段！

这是为什么呢？虽然不理解，但是经过多次打表发现，糖果只会划分为一段或者前后两段，每段前后匹配。枚举分割点可以做到 \(O(n^2)\)。

似乎还是优化不了。但是我们猜这个划分点或许有单调性或者单峰性？打表后发现，大概长这样：

26210 26212 26208 26218 26217 ... 26211 3100 3102 3104 3108 3116 ...

前面是乱序的，而后面突然就变得有序了？

赛时不会做，于是口胡了一下，写了模拟退火。

赛后考虑证明：

1. 取模不优，因为 \(a_i,a_j<m\)，所以 \(a_i+a_j-m<a_i,a_j\)，所以肯定是尽量不取模
2. 交叉匹配不优于包含，因为取模不优。
3. 所以最后一定是划分为前面全部相加小于 \(m\) 两两匹配，后面相加大于等于 \(m\) 两两匹配，这样是最优的。

二分分界点即可。

最短路

很经典的化边为点。考虑模操作的意义，实际上就是建一个有向环，每条边权为 \(1\)，那么 \((a+b)\bmod m\) 就是 \(-a\) 到 \(b\) 的距离。

\(i\to -a:0,b\to i:0,i\to i+1:1\)，跑最短路。

因为 \(m\) 很大，但有用的点很少，连续的无用点可以缩为一条边。\(O(n\log n)\)。

游戏

考虑推 \(SG\) 函数。我们发现对于同一个 \(i\)，\(s_{i,j}\) 的值事实上并不多，只有三种：

所以直接维护 \(S\) 和 \(x\) 即可。

回文串

考虑哈希判定回文串。

那么我们需要二分答案，然后移动中心点，每次需要维护中心点左右边的哈希值。

拆开贡献 \(B^{i}\) 和 \(B^{-j}\)，那么我们需要用两个权值树状数组，一个维护比她大的 \(B^{-j}\) 的和，用来计算答案，另一个维护比她小的数的个数，那么滑动窗口时删除最左边的数就是找到后面比她小的数的个数 \(v_{i-x}\)，答案减去 \(v_{i-x}B^{x-i}\) 就行了。