题解-P10050【IOI2021】修改DNA

· · 题解

这是一道 IOI2021 的题目，不过比较简单。大家不要被其来源吓住了，其实，这道 IOI 题大家应该都做过了。

放一个官方中文题面：https://ioi.te.lv/locations/ioi21/contest/day2/DNA/zh_CN.pdf。

前置知识：

言归正传，开始分析。

\text{ans} = \begin{cases} -1 &&\text{if}&& 无解（无论怎么交换，都无法做到一一对应，如对应字母数量不同） \\ 0 &&\text{if}&& 原本就相同 \\ 1 &&\text{if}&& 有且仅有两个字母不同，且交换后两字符串将相同 \\ 2 &&\text{if}&& 三个字母均不同，且交换后两字符串将相同 \end{cases}

其实 \texttt{Subtask\;1} 的结论可以衍伸，比如字母差异为 4 时仅需要 3 次即可修改完成。不懂为什么数据中没有 G。我鸟嘌呤这么没牌面吗？

代码如下：

#include<bits/stdc++.h>
#include<stdexcept>
using namespace std;
//#define int long long
#ifdef int
const int inf=0x7f7f7f7f7f7f7f7f;
#else
const int inf=0x7f7f7f7f;
#endif
int sum[100009][3][3];
inline int bm(const char c) {
    switch(c){
        case 'A':return 0;
        case 'T':return 1;
        case 'C':return 2;
        default:throw("ERROR! The string is wrong!");
    }
}
int n;
void init(string a,string b){
    n=a.size();
    for(int k=1;k<=n;k++){      //注意，这里sum数组下标从1开始，与string不同（为减少特判，防止下标为负的情况） 
        for(int i=0;i<3;i++)for(int j=0;j<3;j++)sum[k][i][j]=sum[k-1][i][j];
        sum[k][bm(a[k-1])][bm(b[k-1])]++;
    }
}
int get_distance(int x,int y){
    int s[3][3],ret=0,t;
    for(int i=0;i<3;i++)for(int j=0;j<3;j++)s[i][j]=sum[y+1][i][j]-sum[x][i][j];
    for(int i=0;i<3;i++)for(int j=i+1;j<3;j++)
        t=min(s[i][j],s[j][i]),ret+=t,s[i][j]-=t,s[j][i]-=t;            //处理所有的不匹配 
    if(s[0][1]!=s[1][2] or s[1][2]!=s[2][0] or s[1][0]!=s[2][1] or s[2][1]!=s[0][2])return -1;      //不存在 
    return ret+2*(s[0][1]+s[1][0]);
}
#ifndef ONLINE_JUDGE
int q,x,y;
string a,b;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0),cerr.tie(0);
    cin>>n>>q;
    cin>>a>>b;
    init(a,b);
    for(int i=1;i<=q;i++){
        cin>>x>>y;
        cout<<get_distance(x,y)<<endl;
    }
}
#endif