CF2092F Andryusha and CCB 题解
蒟蒻君HJT
·
·
题解
可能唯一难度是位置的题目。调和级数板题放 D 题一万个人能过。
设字符串为 z_1z_2\cdots z_n，记 s_i=z_1z_2\cdots z_i。
考虑长度为 i 的前缀 s_i。假设划分为 k 段，每段漂亮值为 r。由于 k-1 的划分点可能是在相同/不同数字之间，因此前 i 个数字中，相邻位置不同的对数应该在 [rk,rk+k-1] 之间，换句话说，确定 k 之后，可能成为答案的 r 也随之确定了。
我们将所有满足 z_i\neq z_{i-1} 的 i 保存为数列 a_1,a_2,\cdots a_c。枚举 r(r\geq 1)，k=1 时，能贡献到的最短前缀显然是 s_{a_r}，最长前缀是 s_{a_{r+1}-1}。
但是 k=2 的时候怎么做呢？最长前缀是 s_{a_{2(r+1)}-1} 是显然的。最短前缀考虑从 k=1 的情况递推过来。第一段最少截断到 s_{a_r}，最多截断到 s_{a_{r+1}-1}，因此：
-
如果 a_{r+1}=a_r+1，在截断的时候 a_{r+1} 一定会被破坏掉，第二段想拥有 r 的漂亮值，只能包括 a_{r+2},a_{r+3}\cdots a_{2r+1}，最短前缀为 s_{a_{2r+1}}。
-
如果 a_{r+1}>a_r+1，在截断的时候 a_{r+1} 不一定会被破坏掉，第二段想拥有 r 的漂亮值，可以包括 a_{r+1},a_{r+2}\cdots a_{2r}，最短前缀为 s_{a_{2r}}。
对于 k 更大的情况可以依次类推下去，最多枚举到 k=\lfloor \frac{c}{r}\rfloor 就足够了。每次在枚举在符合要求的前缀范围执行一次区间加即可维护答案（差分一下）。另外注意一下 r=0 的情况还没算，随便怎么处理下都行。
有人可能会问了，如果不同的 r 对应相同的 k 贡献到了同一个前缀，那答案不就算重了？这不会成为问题，因为题解的开头已经证明了对于某个前缀，当 k 确定时，r 不可能有多解。
提交记录