题解：AT_cf17_final_e Combination Lock

· · 题解

因为 A 到 Z 循环变，所以可以当成模 26 意义下的区间加 1。

对于区间加可以做个差分，l 到 r 加 1 就变成了 l 处 +1，r+1 处 -1。

计算一下回文字符串的差分。

比如 abcba，差分是 1\ 1\ 1\ -1\ -1。

为了方便算，假设最后是个 0，差分就是 1\ 1\ 1\ -1\ -1\ -1。

设字符串长度是 m，会发现差分数组的第 i 项和第 m+2-i 项加起来是 0。

就可以把 i 和 m+2-1 配对，这一对的权值就是差分数组的第 i 和 m+2-i 项的和。

如果在 l 处 +1，在 r+1 处 -1，就是把 l 所在的那一对 +1，r+1 所在的那一对 -1。

可以用并查集把 l 对应的那对和 r+1 对应的那对合并。

最后在同一个集合的所有对的权值和必须是 0，这样就可以在集合内一直靠 +1 和 -1（模 26 意义下其实就是 +25）调整，最后变得全是 0。

当然有一种特殊情况，你想，如果 m+2-i=i 的话，它需要自己加自己等于 0，这个时候其实它是 13 或者 0 都可以。

所以如果存在 m+2-i=i 的地方，有它的那一块的和不一定是 0，也可以是 13。

复杂度： O((|S| + n) \cdot \alpha)