题解：AT_cf17_final_e Combination Lock

Havefunn · 2026-10-21 19:38:05 · 题解

题目

给定长度为 m 的字符串和 n 个区间操作。每次可将区间内字符循环递增。判断能否通过若干次将字符串变为回文串。

思路

首先将回文的要求转化一下。设 k=m/2，可以定义对称位置差值为 d_i = (S_{m-i+1} - S_i) \bmod 26。目标是使所有 d_i=0。

然后构建差分数组 b_i = (d_i - d_{i-1}) \bmod 26。可以发现，原串上的任意区间操作 [l, r]，由于对称位置的加减抵消，等价于仅在差分数组中对两点 b_{\min(l, m-l+2)} 和 b_{\min(r+1, m-r+1)} 进行一加一减。

由于操作不限次数，这相当于在两点间连边，允许自由转移值。可转化为用并查集维护连通块：

• 初始状态：计算所有 b_i 并初始化并查集。
• 合并转移：遍历所有操作 [l, r]，利用映射 idx(x) = \min(x+1, m-x+1)，将点 idx(l-1) 与 idx(r) 合并。
• 判定条件：累加每个连通块内的 b_i。若所有连通块均满足 \sum b \equiv 0 \pmod{26}，则可通过内部转移归零。

最后根据连通块的和是否全为 0 输出即可。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
string str;
const int N=1e5+5;
int t,n,m;
int fa[N],sum[N],d[N],b[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int idx(int x){
    return min(x+1,m-x+1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>t;
    while(t--){
        cin>>str>>n;
        m=str.size();
        str=" "+str;
        int k=m/2;
        d[0]=d[k+1]=0;
        for(int i=1;i<=k;i++)
            d[i]=(str[m-i+1]-str[i]+26)%26;
        for(int i=1;i<=k+1;i++){
            b[i]=(d[i]-d[i-1]+26)%26;
            fa[i]=i;
            sum[i]=0;
        }
        for(int i=1;i<=n;i++){
            int l,r;
            cin>>l>>r;
            int u=find(idx(l-1)),v=find(idx(r));
            if(u!=v)
                fa[u]=v;
        }
        for(int i=1;i<=k+1;i++)
            sum[find(i)]=(sum[find(i)]+b[i])%26;
        int flag=1;
        for(int i=1;i<=k+1;i++){
            if(fa[i]==i&&sum[i]!=0){
                cout<<"NO\n";
                flag=0;
                break;
            }
        }
        if(flag)
            cout<<"YES\n";
    }
    return 0;
}