题解：P10753 [COI 2023] Bliskost

· · 题解

建议难度评为 \color{orange}橙 或 \color{yellow}黄。

题意

给定两长度为 n 的字符串 s,t，判断它们是否相近（指可以通过若干次操作使得 s,t 相等），并给定 Q 次修改，每次修改 s 的一个字符，然后再判断是否相近。

对于每次操作，选择一个字符串 s 和位置 p，将 s_p 和 s_{p+1} 在字母表上前移一位。

思路

可以发现，将所有操作集中到一个字符串可以使 s,t 相等时，那么 s,t 相近。
注意到，对于 s_1，通过操作使其变成 t_1 的操作次数为 t_1-s_1，次数对 26 取模。令这个次数为 a_1，那么 s_2 便已经进行了 a_1 次操作，需再进行 t_2-s_2-a_1 次操作。以此类推，可求出 a_n。
第 n 位是字符串的最后一位，它不可能进行操作，所以当且仅当 a_n=0 时，两字符串相近。对于每次修改，可根据其与 n 的位置差直接修改 a_n，进行 O(1) 判断是否相近。

时间复杂度 O(n+Q)。

代码

#include<bits/stdc++.h>
#define int long long
#define F(i,l,r) for(register int i=(l); i<=(r); ++i)
using namespace std;
const int N= 1e6 +50;

int n,Q;
int a[N];
string s,t;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>Q>>s>>t;
    F(i,1,n){
        a[i]=(t[i-1]+26-s[i-1])%26;
        a[i]-=a[i-1];
        if(a[i]<0) a[i]+=26;
    }
    a[n]%=26;
    cout<<(a[n]?"ne\n":"da\n");
    F(i,1,Q){
        int p;char c; cin>>p>>c;
        int t=c-s[p-1];
        s[p-1]=c;
        a[n]+=t*((n-p)&1?1:-1);
        a[n]%=26;
        cout<<(a[n]?"ne\n":"da\n");
    }

    return 0;
}