题解：P8521 [IOI 2021] 修改 DNA

· · 题解

先判断什么时候无解，显然是 a 中某种字符出现次数和 b 中某种字符出现次数不相等，这样才会出现无解的情况。这个直接用前缀和做即可。

考虑将 a 和 b 每一位配对起来。如果一个位置 a,b 的字符相等则不用管它；如果存在两个位置配对起来的结果正好相反，则这两个位置可以直接抵消，对答案的贡献为 1。

将上述两种情况的点删去，剩下的序列只能是这两种情况：

k\text{个}\;\;\; k\text{个} \;\;\;k\text{个}\\ \overbrace{A\cdots A}\overbrace{C\cdots C}\overbrace{T\cdots T}\\ \underbrace{T\cdots T} \underbrace{A\cdots A} \underbrace{C\cdots C}\\ k\text{个}\;\;\; k\text{个}\;\;\;k\text{个} \\

或者：

k\text{个}\;\;\; k\text{个} \;\;\;k\text{个}\\ \overbrace{T\cdots T} \overbrace{A\cdots A} \overbrace{C\cdots C}\\ \underbrace{A\cdots A}\underbrace{C\cdots C}\underbrace{T\cdots T}\\ k\text{个}\;\;\; k\text{个}\;\;\;k\text{个} \\

我们注意到，这样对答案的贡献是 2k，直接加进去就行了。

代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ll long long
using namespace std;

ll read(){
    ll x=0,f=1;char ch=getchar_unlocked();
    while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar_unlocked();}
    while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar_unlocked();}
    return f*x;
}

const int N = 1e5+5;
int n,q,s[N][5][5],sa[N][5],sb[N][5],kk[305],cp[5][5];

void init(string a,string b){n=a.size();
    memset(kk,0,sizeof(kk));memset(s,0,sizeof(s));
    memset(sa,0,sizeof(sa));memset(sb,0,sizeof(sb));
    kk['A']=0,kk['T']=1,kk['C']=2;a=" "+a,b=" "+b;
    for(int i=1;i<=n;i++){
        for(int x=0;x<3;x++){
            sa[i][x]=sa[i-1][x];sb[i][x]=sb[i-1][x];
            for(int y=0;y<3;y++)s[i][x][y]=s[i-1][x][y];
        }sa[i][kk[a[i]]]++,sb[i][kk[b[i]]]++;
        s[i][kk[a[i]]][kk[b[i]]]++;
    }
    // for(int x=0;x<3;x++){
    //     for(int i=0;i<n;i++)printf("%d ",sa[i][x]);puts("");
    //     for(int i=0;i<n;i++)printf("%d ",sb[i][x]);puts("");puts("");
    // }
}

int get_distance(int l,int r){int ans=0;l++,r++;
    for(int x=0;x<3;x++)for(int y=0;y<3;y++)cp[x][y]=0;
    for(int x=0;x<3;x++){
        // printf("%d %d %d\n",x,sa[r][x]-sa[l-1][x],sb[r][x]-sb[l-1][x]);
        if(sa[r][x]-sa[l-1][x]!=sb[r][x]-sb[l-1][x])return -1;
    }
    for(int x=0;x<3;x++)for(int y=0;y<3;y++)cp[x][y]=s[r][x][y]-s[l-1][x][y];
    for(int x=0;x<3;x++)for(int y=x+1;y<3;y++){
        int mm=min(cp[x][y],cp[y][x]);ans+=mm,cp[x][y]-=mm,cp[y][x]-=mm;
    }int mx=0;for(int x=0;x<3;x++)for(int y=x+1;y<3;y++)if(cp[x][y]>mx)mx=cp[x][y];
    ans+=mx*2;return ans;
}

#ifndef ONLINE_JUDGE
int main(){
    cin>>n>>q;string a,b;
    cin>>a>>b;init(a,b);
    while(q--){
        int l,r;cin>>l>>r;
        cout<<get_distance(l,r)<<endl;
    }
    return 0;
}
#endif