题解：AT_cf17_final_e Combination Lock

· · 题解

简单题，场切了（感觉 T2 < T1），写一篇题解。

因为要一段同时加一（最后看模 26 意义下的结果），所以容易联想到差分。

这样原题就转变为每次可以进行 a_l \leftarrow a_l + 1，a_{r + 1} \leftarrow a_{r + 1} - 1 操作，最后结果的对称的数的和必须是 26 的倍数（你分别考虑长度为奇数和偶数的情况，发现都满足对称的数的和必须是 26 的倍数）。

而这个操作相当于可以任意互相调整 l 和 r + 1 处的数，所以想到用并查集合并，这样并查集上的每个联通块的任意两个数都可以互相调整。

我们考虑到最后需要满足对称的数的和必须是 26 的倍数，考虑再将对称的数所在的联通块^1再次合并，表示这里面的两个数的和必须是 26 的倍数，考虑有解的必要条件，就是再次合并后的剩下的联通块的和一定是 26 的倍数（因为都可以两两配对，如果不能，说明与其配对的点必定在另一联通块^2，但是这两个点连了边，矛盾）。

其实考试大概到这里就可以写代码了，因为样例都是对的，即使是错的，写这个也浪费不了多少时间。

考虑充分性，我们对于每个联通块^2分别考虑。

可以把联通块^1视为点，然后取的图的生成树，然后从叶子考虑，把连接叶子与父亲点的两个内部点分别设为叶子联通块^1的值和叶子联通块^1的值的相反数，父亲点的值加上叶子联通块^1的值，把叶子里的其他内部点设为 0，删去叶子及父亲点连接叶子的边的内部点，这样会出现新的叶子节点，然后做到最后的根一定是所有点之和（因为每次父亲的值会加上叶子的值），为 26 的倍数，就构造完了。

这里还有个需要想清楚的问题，就是外一某次父亲点只剩一个点，删除之后，父亲点就没有其他点了，是不是就不一定能满足父亲点的和的限制了？

:::info[解答] 若父亲点是根，肯定没问题，如果不是根，那说明这一个点在第二次合并时连接了两个点，这是不可能的，因为一个点在第二次合并时只会连接其对应点，不会再连其他的点。 :::

至此，就做完了。

:::info[赛事代码]{open}

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int T, n, m, l, r, p[N], sum[N];
char s[N];
int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if(x != y) {
        p[x] = y;
        sum[y] += sum[x];
    }
}
void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    for(int i = 1; i <= n + 1; i ++) {
        p[i] = i;
        sum[i] = s[i] - s[i - 1]; 
    }
    scanf("%d", &m);
    while(m --) {
        scanf("%d%d", &l, &r);
        merge(l, r + 1);
    }
    for(int i = 1, j = n + 1; i < j; i ++, j --) merge(i, j);
    for(int i = 1; i <= n + 1; i ++)
        if(find(i) == i && (sum[i] % 26)) {
            printf("NO\n");
            return;
        }
    printf("YES\n");
}
int main()
{
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    scanf("%d", &T);
    while(T --) solve();
    return 0;
}

:::

P.S. 此题被搬到模拟赛 T2 -> 提高级模拟赛：青紫黑黑