P8521 [IOI 2021] 修改 DNA

题目背景

滥用本题评测将被封号

由于技术限制，请不要使用 C++ 14 (GCC 9) 语言提交本题。

这是一道交互题，你只需要实现代码中要求的函数。

你的代码不需要引用任何额外的头文件，也不需要实现 main 函数

题目描述

Grace 是一名生物学家，在新加坡的一个生物信息学公司工作。她的一部分工作是分析不同有机体的 DNA 序列。DNA 序列是包含字符 A、T 和 C 的字符串。注意在本题中，DNA 序列不包含字符 G。

定义一次修改是把 DNA 序列中的两个元素交换位置的操作。例如，通过交换加粗的字符 A 和 C，一次修改可以把 ACTA 转化为 AATC。

两个序列的修改距离是把一个序列转化为另一个序列所用的最少修改次数。如果不能通过修改把一个序列转化为另一个序列，那么这两个序列的修改距离为 $-1$。

Grace 正在分析两个 DNA 序列 $a$ 和 $b$，每个都由 n 个元素组成，下标从 $0$ 到 $n-1$。你的任务是帮助 Grace 回答以下形式的 $q$ 个问题：子串 $a[x\dots y]$ 和 $b[x\dots y]$ 的修改距离是多少？这里，DNA 序列 $s$ 的子串 $s[x\dots y]$ 定义为 $s$ 的下标从 $x$ 到 $y$（包括 x 和 y）的连续字符序列。也就是说，$s[x\dots y]$ 是序列 $s[x]s[x+1]\dots s[y]$。

输入格式

你要实现以下函数：

void init(string a, string b)

• $a,b$：长度为 $n$ 的字符串，表示两个待分析的 DNA 序列。
  恰好调用此函数一次，且发生在任何对 get_distance 的调用之前。

int get_distance(int x, int y)

• $x,y$：待分析的子串的开始和结束下标。
  此函数应返回子串 $a[x\dots y]$ 和 $b[x\dots y]$ 的修改距离。
  恰好调用此函数 $q$ 次。

输出格式

无

输入输出样例 #1

输入 #1

6 3
ATACAT
ACTATA
1 3
4 5
3 5

输出 #1

2
1
-1

说明/提示

对于所有数据：

• $1\le n,q\le 100000$
• $0\le x\le y\le n-1$
• $a$ 和 $b$ 的每个字符都是 A、T 和 C 之⼀

子任务	分值	特殊限制
$1$	$21$	$y-x\le 2$
$2$	$22$	$q\le 500$，$y-x\le 1000$，$a$ 和 $b$ 的每个字符是 A 或 T
$3$	$13$	$a$ 和 $b$ 的每个字符是 A 或 T
$4$	$28$	$q\le 500$，$y-x\le 1000$
$5$	$16$	没有额外的约束条件

样例解释

如果评测程序调用 get_distance(1, 3)，那么该调用应返回 $a[1\dots 3]$ 和 $b[1\dots 3]$（也就是序列 TAC 和 CTA）之间的修改距离。通过 $2$ 次修改可以把 TAC 转化为 CTA：TAC $\to$ CAT，然后是 CAT $\to$ CTA。无法通过比 $2$ 次更少的修改完成该转化。

因此，该调用应返回 $2$。

如果评测程序调用 get_distance(4, 5)，那么该调用应返回序列 AT 和 TA 之间的修改距离。 通过一次修改可以把 AT 转化为 TA，而且显然至少需要一次。

因此，该调用应返回 $1$。

最后，如果评测程序调用 get_distance(3, 5)，由于无法通过修改将序列 CAT 转化为 ATA，因此该调用应返回 $-1$。

C++实现

#include<bits/stdc++.h>
#include<stdexcept>
using namespace std;
#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

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容