自动搬运

查看原文

来自洛谷，原作者为

	wangbinfeng 今天搞完大概就永远不会碰 OI 了，大家祝好！

搬运于2025-08-24 22:39:48，当前版本为作者最后更新于2024-01-05 08:58:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

---

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

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

前置知识：

• 前缀和 、生物学 DNA（腺嘌呤 A、胸腺嘧啶 T、胞嘧啶 C、鸟嘌呤 G）、英语理解能力。

言归正传，开始分析。

• $\texttt{Subtask\;1.}$ 每次查询最多只有三个字符，则答案如下：

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

• $\texttt{Subtask\;2.}$ 只有两个字母。通过 $\texttt{Subtask\;1}$ 我们可以清晰的发现，每次交换可以修复一个不匹配的情况，因此计算不匹配的数量即可。时间复杂度为 $\Theta \left(qm^2\right)$。此处，$m=y-x+1$，下面同理。
• $\texttt{Subtask\;3.}$ 相较于 $\texttt{Subtask\;2}$ 仅增加了数据范围。因此，可以再 init() 函数中预处理出所有的不匹配数量。显然可以使用前缀和。时间复杂度为 $\Theta \left(n+q\right)$。
• $\texttt{Subtask\;4.}$ 较于 $\texttt{Subtask\;3}$ 仅增加了一个字母。先修改两个字母（需要 $1$ 次），时间复杂度为 $\Theta \left(qm^2\right)$，再修改三个字母（需要 $2$ 次），时间复杂度也为 $\Theta \left(qm^2\right)$。故总时间复杂度显然为 $\Theta \left(qm^2\right)$。
• $\texttt{Subtask\;5.\;\&\;Full\;Solution.}$ 相较于 $\texttt{Subtask\;4}$ 仅增加了数据范围，考虑 $\texttt{Subtask\;3}$ 的做法。用前缀和统计不匹配，然后用常数时间复杂度修改即可。时间复杂度为 $\Theta \left(n+q\right)$。

其实 $\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