题解：AT_cf17_final_e Combination Lock

zhangwenyuxuan · 2026-10-21 09:14:30 · 题解

注意，以下的所有计算都在模 26 意义下进行。

首先可以把字符串转化成 0 到 25 的数，每次操作相当于将区间 [l,r] 中的每个数 x 变成 x+1。

显然可以考虑查分，设 a_i=s_{i+1}-s_i，那么上面的操作相当于 a_l 加 1，a_{r+1} 减 1。而题目要求我们判断是否可以变成回文，发现 s 回文的充要条件是任意 a_{i}+a_{|s|-i+2}=0。

观察发现，一个操作相当于规定 a_l 和 a_{r+1} 的和一定，大小可以任意分配。考虑连边，将所有 l 和 r+1 连起来，得到若干个连通块，一个连通块内部和一定，大小任意分配。

但只连这些边，限制依然不好处理，考虑把每个点和它在回文串中对应的点也连边。此时，每个连通块的和为 0 显然是可以变成回文串的一个必要条件，现在证明它的充分性。

现在，一个连通块中有若干对点，每对点中至少一个可以任意分配，先任选一对，通过改变其中一个大小，使得它们和为 0，多余的值流动到剩下的点上。容易发现，此时剩下点的和依旧为 0。重复以上过程，直到剩余最后一对点，它们的和一定为 0，满足条件。

综上所述，每个连通块中所有数的和为 0，是可以变成回文的充要条件。

:::info[参考代码]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int t,n,sz,a[N],b[N],fa[N],sum[N];
string s;
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
    fa[find(x)]=find(y);
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>s>>n;
    sz=s.size();
    for(int i=1;i<=sz;i++){
        a[i]=s[i-1]-'a';
    }
    a[sz+1]=0;
    for(int i=0;i<=sz;i++){
        b[i]=a[i+1]-a[i];
        fa[i]=i;
        sum[i]=0;
    }
    for(int i=0;i*2<=sz;i++){
        merge(i,sz-i);
    }
    for(int i=1;i<=n;i++){
        int l,r;
        cin>>l>>r;
        merge(l-1,r);
    }
        for(int i=0;i<=sz;i++){
        sum[find(i)]+=b[i];
    }
    int ans=1;
    for(int i=0;i<=sz;i++){
            if(sum[i]%26!=0){
            ans=0;
        }
    }
    cout<<(ans?"YES\n":"NO\n");
    return 0;
}

:::