题解：AT_cf17_final_e Combination Lock

· · 题解

原题是 https://www.luogu.com.cn/problem/AT_cf17_final_e。

感觉 T2 比 T1 简单是真的。但是不知道为什么一个是紫一个是青。首先可以注意到如果我们考虑去做差分，那么其实一次操作 [l,r]，就是在 l 处 +1，然后在 r+1 处减一，上述操作都是在 \bmod 26 的环境下进行的。

考虑图论建模，注意到说其实对于 l 和 r+1 这种，本质就是一个值的转移，并不会影响 l 和 r+1 的和，因此考虑图论建模，即考虑把 l 和 r+1 给连接一起来，考虑用并查集来处理即可。

这样一来，同一个连通块内部的差分值可以任意转移，而每个连通块的差分和始终不变。于是问题就转化成了，能否在保持各个连通块差分和不变的前提下，将差分数组调整成某个回文串对应的差分数组？

然后就是考虑那个回文的问题，手玩一下，我们记录 d_i=a_i-a_{i-1}，然后 m 为整体的字符串的长度，然后回文应该是要满足 a_i=a_{m+1-i}，为了方便，我们把 a_{m+1} 记录为 0，观察得到对于两个 i 和 m+1-i，那么可以注意到 d_i=-d_{m+2-i} 的，也就是说二者加起来是要等于 0 的。考虑继续建模，具体的，就是把 i 和 m+2-i 连接起来，那么现在整体的图就变成了多个连通块的形式，注意到说连接 l 和 r+1 的边，是不会影响和的，后者也是不会影响和的，所以说如果要让答案合法，那么其实就是要把每个连通块内的和都变为 0，用并查集维护一下，然后判断和即可。

注意这里全部都是在 \bmod 26 的前提下进行的。

:::info[Code]

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e5+10;

int n,fa[MAXN],siz[MAXN],sum[MAXN];
string s;
namespace DSU{
    inline int sfind(int x){
        if (fa[x]!=x)fa[x]=sfind(fa[x]);
        return fa[x];
    }
    inline void merge(int x,int y){
        x=sfind(x),y=sfind(y);
        if (x==y)return;
        if (siz[x]<siz[y])swap(x,y);
        fa[y]=x,siz[x]+=siz[y];
    }
}
namespace yixing{
    inline void Main(){
        cin>>s>>n;
        int m=s.size();
        s=" "+s;
        for (int i=1;i<=m+1;i++)fa[i]=i,siz[i]=1,sum[i]=0;
        for (int i=1;i<=n;i++){
            int l,r;cin>>l>>r;
            DSU::merge(l,r+1);
        }
        for (int i=1;i<=m+1;i++)DSU::merge(i,m+2-i);
        sum[DSU::sfind(1)]+=s[1]-'a';
        for (int i=2;i<=m;i++)sum[DSU::sfind(i)]+=s[i]-s[i-1];
        sum[DSU::sfind(m+1)]+='a'-s[m];
        for (int i=1;i<=m+1;i++)if (fa[i]==i&&sum[i]%26!=0)return cout<<"NO\n",void();
        cout<<"YES\n";
    }
}
int main(){
    freopen("string.in","r",stdin);
    freopen("string.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while (T--)yixing::Main();
    return 0;
}

:::