分析

我们可以分类讨论。

• 首先如果 这显然不需要进行操作。
• 如果 , 我们可以进行一次操作将两个配对，可以证明这个操作是最优的。
• ， ， 同理我们可以两次操作配对。
• 那么最后剩下的就是四个一组的。根据鸽巢原理我们一定可以在 次操作之内配对。

那么我们现在只需要记录这四种情况有多少个，然后由前到后考虑就可以了，总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1000;
char A[N],B[N];
int get(char ch) {if(ch=='A')return 1;if(ch=='G')return 2;if(ch=='C')return 3;if(ch=='T')return 0;}
int c[4][4],n,ans;
int main() {
    scanf("%s%s",A+1,B+1);n = strlen(A+1);for(int i = 1;i <= n;i++) {
        if(get(A[i])==get(B[i])) continue;c[get(A[i])][get(B[i])]++;
    }
    for(int i = 0;i < 4;i++) for(int j = 0;j < 4;j++) {
        int Min = min(c[i][j],c[j][i]);c[i][j]-=Min;c[j][i]-=Min;ans+=Min;
    }
    for(int i = 0;i < 4;i++) for(int j = 0;j < 4;j++) for(int k = 0;k < 4;k++) {
        int Min = min(min(c[i][j],c[j][k]),c[k][i]);c[i][j]-=Min;c[j][k]-=Min;c[k][i]-=Min;ans+=Min*2;
    }
    for(int i = 0;i < 4;i++) ans += c[i][3] * 3;
    cout << ans << endl;return 0;
}