题解：P10753 [COI 2022-2023] Bliskost

LinkCatTree · 2025-01-01 09:59:40 · 题解

考虑如果字符串 s 和 t 是相近的，两个字符串会满足什么特征。由于每次会对相邻两个字符进行操作，这两个字符的下标必为一奇一偶，因此字符串奇偶两位上字符之和的差也不会变（字符之和：我们把 \text{a} 看做 0，把 \text{b} 看作 1……以此得到的所有数字的总和）。因此我们的出：s 奇偶位上字符之和之差与 t 奇偶位上字符之和之差相同。我们可以 \mathcal{O}(n) 计算一开始的差，然后对于每个询问 \mathcal{O}(1) 维护，总时间复杂度 \mathcal{O}(n+q)。

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
int n,q,sum1,sum2;
char s[N],t[N];

int main() {
    freopen("tmp.in","r",stdin);
    scanf("%d%d%s%s",&n,&q,s+1,t+1);
    for(int i=1;i<=n;i++)
        if(i&1) sum1+=s[i]-'a';
        else sum1-=s[i]-'a';
    ((sum1%=26)+=26)%=26;
    for(int i=1;i<=n;i++)
        if(i&1) sum2+=t[i]-'a';
        else sum2-=t[i]-'a';
    ((sum2%=26)+=26)%=26;
    if(sum1!=sum2) printf("ne\n");
    else printf("da\n");
    while(q--) {
        int p; char op[3];
        scanf("%d%s",&p,op+1);
        if(p&1) sum1+=op[1]-s[p];
        else sum1-=op[1]-s[p];
        s[p]=op[1],((sum1%=26)+=26)%=26;
        if(sum1!=sum2) printf("ne\n");
        else printf("da\n");
    }
    return 0;
}