P8521 [IOI2021] 修改 DNA

· · 题解

题目链接：P8521 [IOI2021] 修改 DNA。

说句闲话，我最开始做这题的时候这题是 P10050 来着？

upd 24/07/09：修改了一处小错误。

科普一下，生物体中常见的碱基有 5 种，分别是腺嘌呤（A）、鸟嘌呤（G）、胞嘧啶（C）、胸腺嘧啶（T）和尿嘧啶（U），其中碱基 A、G、C 和 T 存在于 DNA 中。注意，本题中 DNA 序列只含有字符 A、T 和 C。

本题虽然是交互题，但实际上是一道传统题。

为了方便，我们把 A、T 和 C 分别替换为 0,1,2。

int change(char c){
    if(c=='A') return 0;
    else if(c=='T') return 1;
    else return 2;
}

注意到本题求修改次数的是同一个区间，那么对于任意 k，我们需要把 a_k 改为 b_k。定义一个区间的的修改矩阵 s 为一个 3\times3 的矩阵，并且 s_{i,j} 为某一个区间内需要将 i 改为 j 的个数（0\leqslant i,j\leqslant 2）。

那么我们可以在 init 函数中把修改矩阵求出来。这里使用类似前缀和的思路存储。

void init(string a,string b) {
    int len=a.length();
    For(k,1,len){
        F(i) F(j) S[k][i][j]=S[k-1][i][j];
        S[k][change(a[k-1])][change(b[k-1])]++; // 类似前缀和 
    }
}

我们采取这样的思路修改：能两两交换就交换（如样例二），剩下多出来的考虑三个轮换修改。

对于每一组询问，我们先求出这个区间的修改矩阵。然后进行两两交换。此时 s_{i,j} 和 s_{j,i} 中必有一个为 0。若 s_{1,0} 为 0，则仅当 s_{0,1}=s_{1,2}=s_{2,0} 时，可以将 0 与 1 交换位置，再将 0 与 2 交换位置，交换次数为 s_{0,1}+s_{2,0}=2\times s_{0,1}。s_{0,1} 为 0 同理。

int get_distance(int x,int y){
    int ans=0;
    F(i) F(j) s[i][j]=S[y+1][i][j]-S[x][i][j]; // 求出修改矩阵 
    F(i){
        For(j,i+1,3){
            int m=min(s[i][j],s[j][i]);
            ans+=m;s[i][j]-=m;s[j][i]-=m; // 抵消 
        }
    }
    // 轮换修改 
    if(s[0][1]!=s[1][2] || s[1][2]!=s[2][0] || s[1][0]!=s[2][1] || s[2][1]!=s[0][2]) return -1; 
    if(s[0][1]!=0) return ans+2*s[0][1];
    else return ans+2*s[1][0];
}

代码如下：

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

#define For(i,a,b) for(int i=a; i<=b; i++)
#define F(i) For(i,0,2)
int change(char c){if(c=='A'){return 0;}else if(c=='T'){return 1;}else{return 2;}}

int S[100002][3][3];//ATC
int s[3][3];

void init(string a,string b) {
    int len=a.length();
    For(k,1,len){
        F(i) F(j) S[k][i][j]=S[k-1][i][j];
        S[k][change(a[k-1])][change(b[k-1])]++; // 前缀和 
    }
}

int get_distance(int x,int y){
    int ans=0;
    F(i) F(j) s[i][j]=S[y+1][i][j]-S[x][i][j]; // 求出修改矩阵 
    F(i){
        For(j,i+1,3){
            int m=min(s[i][j],s[j][i]);
            ans+=m;s[i][j]-=m;s[j][i]-=m; // 抵消 
        }
    }
    // 轮换修改 
    if(s[0][1]!=s[1][2] || s[1][2]!=s[2][0] || s[1][0]!=s[2][1] || s[2][1]!=s[0][2]) return -1; 
    if(s[0][1]!=0) return ans+2*s[0][1];
    else return ans+2*s[1][0];
}

/*
int main(){
    int n,q;string a,b;cin>>n>>q>>a>>b;
    init(a,b);
    while(q--){
        int x,y;cin>>x>>y;
        cout<<get_distance(x,y)<<endl;
    }
    return 0;
}
*/