ps：思路仅供参考，并非题解，有错误请指出

首先有一个基本的贪心策略：我们从前往后扫，按照某种相邻交换方式把两个串能匹配尽量先进行匹配一定是最优的。

所以大体思路就出来了：

我们将每一个字符串能交换到这一位的0/1的个数预处理出来。

然后从前往后扫一遍，观察这一位上两个字符串是否都存在0/1，若是，则答案+1。

具体如何预处理呢？

因为我们是从前往后扫的，所以，我们只需要将一段可以交换的区间的头更新0/1个数即可，然后再在统计答案时将个数顺延到下一位即可。

可能本人讲的有点抽象，将代码放上来以便大家更好的理解。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int T,n,ans;
int num1[N][2],num2[N][2],a[N],b[N],t1[N],t2[N];
char s[N];
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		ans=0;
		for(int i=0;i<=n+1;i++){
			num1[i][0]=num1[i][1]=0;
			num2[i][0]=num2[i][1]=0;
		}
		scanf("%s",s+1);
		for(int i=1;i<=n;i++){
			a[i]=s[i]-'0';
		}
		scanf("%s",s+1);
		for(int i=1;i<=n;i++){
			b[i]=s[i]-'0';
		}
		scanf("%s",s+1);
		for(int i=1;i<=n;i++){
			t1[i]=s[i]-'0';
		}
		scanf("%s",s+1);
		for(int i=1;i<=n;i++){
			t2[i]=s[i]-'0';
		}
		for(int i=n;i>=1;i--){
			num1[i][0]+=(a[i]==0);
			num1[i][1]+=(a[i]==1);
			if(t1[i]&&t1[i-1]&&i>1){
				num1[i-1][0]=num1[i][0];
				num1[i-1][1]=num1[i][1];
				num1[i][1]=num1[i][0]=0;
			}
		}
		for(int i=n;i>=1;i--){
			num2[i][0]+=(b[i]==0);
			num2[i][1]+=(b[i]==1);
			if(t2[i]&&t2[i-1]&&i>1){
				num2[i-1][0]=num2[i][0];
				num2[i-1][1]=num2[i][1];
				num2[i][1]=num2[i][0]=0;
			}
		}
		for(int i=1;i<=n;i++){
			if(num1[i][0]&&num2[i][0]){
				ans++;
				num1[i][0]--;
				num2[i][0]--;
			}
			else if(num1[i][1]&&num2[i][1]){
				ans++;
				num1[i][1]--;
				num2[i][1]--;
			}
			else if(num1[i][0]&&num2[i][1]){
				num1[i][0]--;
				num2[i][1]--;
			}
			else{
				num1[i][1]--;
				num2[i][0]--;
			}
			num1[i+1][1]+=num1[i][1];
			num1[i+1][0]+=num1[i][0];
			num2[i+1][1]+=num2[i][1];
			num2[i+1][0]+=num2[i][0];
		}
		printf("%d\n",ans);
	}
	return 0;
}

本文只是想针对T1思路进行一个拓展，并无恶意，如有违规行为请联系我删帖QWQ