\(\text{20240301}\) 字符串练习题解
一定要写冬令营的题吗？遗憾的。
P9717
给了一个 \(n\) 个数的首尾相接的字符串，求若干个操作后能形成的不同的字符串大小。
- 一次操作定义为：将字符串内所有的 \(\text{01}\) 同时改成 \(\text{10}\)，如图。
通过这张图我们似乎发现了一个规律，这里的 \(\text{1}\) 似乎在旋转？于是我们得出：
- 定义 \(x\) 串为长度大于等于 \(1\) 的全为 \(x\) 的串
- 对于一个 \(\text{0}\) 串，如果其左边不和某个 \(\text{1}\) 串相邻，变换后会整体往左移动一位；对于 \(\text{1}\) 串恰恰相反；
- 如果一个 \(\text{0}\) 串接在一个 \(\text{1}\) 串后面，那么相当于两个串相撞，变换后长度都会减 \(1\)。
- 当不存在串时，就会绕圈。在此之前每一个字符串都是不相同的
这样可以将它分为两部分。找到一个起点位置，使得每个前缀中 \(\text{1}\) 串长度和不小于 \(\text{0}\) 串长度和，如何求出请右转这里，那么就可以求出每个 \(\text{0}\) 连续串会在什么时侯寄掉，并求出所有 \(\text{0}\) 连续段消失后的序列。
最后求一次结尾串的最小周期长度，这样可以算出剩余的次数。
Gym104901H
令 \(suf_{s, i}\) 表示 s 从第 i 个字符开始的后缀。令 \(g_i = lcp_{s,suf_{s, i}}\)。
对每个下标，求如果必须改掉第 \(i\) 个字符，\(\sum g_j\) 的值最大是多少。
考虑修改第 \(i\) 个字符会对如何。
- \(1 \le i \le g_j\) 或 \(j \le i < j + g_j\)，则它会变成 \(i\)。
- 否则，恰好是其中一个字符串末尾才有影响
-
- 比如 \(i = g_j + 1\)，那么只能变成 \(s_{i+g_i}\) 才能让值增加。新 g 值的计算可以用哈希 & 二分等方式实现。
- 在后面同理。
汝可画图知之。
因此维护每个位置变成每个字符对答案产生的贡献（离线维护区间加等差数列），最后离线把答案算出来即可。注意由于字符集很大，只记录对答案有影响的字符。
\(O(n \log n)\)。
代码写不出不放了。