题解：AT_cf17_final_e Combination Lock

Rainesxiao · 2026-10-21 18:54:24 · 题解

思路

本文中所有运算都是在模 26 意义下的。

首先，对于回文串，可以将左半部分对应位置的值减去右半部分的值，同时将区间操作右边的部分压到左边，这样问题就变成一个序列，有 m 种区间加 1 操作，问能否变为全 0。

可以想到差分，由于一加一减和不变，因而可以想到用并查集将 l 和 r+1 连通，如果最后的连通块和为 0，则可以全变为 0（简单证明：加一减一是等价的，所以 l 和 r+1 之间的转移是双向的，一定可以将连通块中所有数全部加到一个数上，这个数取模为 0）。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int> 
const int N=1e5+5,mod=26;
char s[N];
int val[N],T,n,m,tot,b[N<<1],del[N],tt[N];
pii a[N];
int fa[N*30],siz[N*30],ff[N*30];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) fa[y]=x,siz[x]=(siz[x]+siz[y])%mod;
}
vector<pii> t[N];
void solve(){
    tot=0;
    cin>>s>>m;n=strlen(s);
    for(int i=1;i<=n;i++) val[i]=s[i-1]-'a';
    for(int i=1;i<=n/2;i++) val[i]=(val[i]+mod-val[n-i+1])%mod;val[n/2+1]=0;
    for(int i=1;i<=n/2+1;i++) del[i]=(val[i]+mod-val[i-1])%mod;
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        if((n&1)&&l==n/2+1) l++;
        if((n&1)&&r==n/2+1) r--;
        if(l>r) continue;
        if(r<=n/2) a[++tot]={l,r};
        else if(l>n/2) a[++tot]={n-r+1,n-l+1};
        else if(l<n-r+1) a[++tot]={l,n-r};
        else if(l>n-r+1) a[++tot]={n-r+1,l-1};
    }
    sort(a+1,a+tot+1),tot=unique(a+1,a+tot+1)-a-1;
    for(int i=1;i<=n/2+1;i++) fa[i]=i,siz[i]=del[i];
    for(int i=1;i<=tot;i++){
        merge(a[i].first,a[i].second+1);
    }   
    for(int i=1;i<=n/2+1;i++) if(siz[find(i)]){cout<<"NO\n";return;}
    cout<<"YES\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}