T1 蓝切了，T2 绿只得了 20 分……
题意分析
给定字符串 $s_1,s_2$ 和标记数组 $t_1,t_2$，$t_i[j]$ 表示 $s_i$ 的第 $j$ 位是否可以参与交换。
同一字符串内任意两个可以参与交换的相邻的字符可以交换，让你求出最多有多少位是相同的。
我们其实可以使用一个很简单的贪心来求解。
首先，对于第 $i$ 位，如果能够通过交换使得 $s_1[i]=s_2[i]$，那么交换一定是不劣的（即最优）。
原因也很简单，具体而言就是对于第 $i$ 号位，你换了，最多让后面少换一个，但是你不换后面最多也只能换一个。
令 $cnt_i[j]$ 表示 $s_i$ 当前能够进行交换的 $j$ 的数量，$j\in{0,1}$，令 $ans$ 为最终答案，初始值为 $0$。
那么我们就可以进行一个分讨：
- $t_1[i]=t_2[i]=0$： $s_1,s_2$ 的第 $i$ 号位都不能换，若 $s_1[i]=s_2[i]$ 就计数，否则跳过。
- $t_1[i]=0,t_2[i]=1$：$s_1[i]$ 不能交换，我们考虑将 $s_2[i]$ 换成 $s_1[i]$；那么我们看看 $cnt_2[s_1[i]]$ 是否大于 $0$，是就代表 $s_2[i]$ 能够交换为 $s_1[i]$，令 $cnt_2[s_1[i]]\leftarrow cnt_2[s_1[i]]-1$ 并计数即可；否则跳过。
- $t_1[i]=1,t_2[i]=0$：$s_2[i]$ 不能交换；同理，$cnt_1[s_2[i]]>0$ 时令其自减并计数，否则跳过。
- $t_1[i]=t_2[i]=1$：随便换；如果都能换成 $0$ 就都换成 $0$，否则如果能都换成 $1$ 就换成 $1$；方法同理可得。
那么如何求 $cnt_i$ 呢？
其实也很简单，可以视作被 $t_i[j]=0$ 的 $j$ 分为了一段一段，在 $t_i[j]=0$ 时找到最小的 $j’$ 满足 $t_i[j’]=0$ 然后统计区间 $[j+1,j’-1]$ 即可。
总时间复杂度：$\mathcal O(n)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
const int N=1e5;
int n;
char s1[N+1],s2[N+1],t1[N+1],t2[N+1];
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
int T;
scanf("%d",&T);
while(T--){
scanf("%d%s%s%s%s",&n,s1,s2,t1,t2);
int cnt1[2]={},cnt2[2]={};
int ans=0;
for(int j=0;t1[j]=='1';j++)cnt1[s1[j]-'0']++;
for(int j=0;t2[j]=='1';j++)cnt2[s2[j]-'0']++;
for(int i=0;i<n;i++){
if(t1[i]=='0'){
if(t2[i]=='0'){
if(s1[i]==s2[i])ans++;
}else{
if(cnt2[s1[i]-'0']>0)ans++,cnt2[s1[i]-'0']--;
}
}else{
if(t2[i]=='0'){
if(cnt1[s2[i]-'0']>0)ans++,cnt1[s2[i]-'0']--;
}else{
if(cnt1[0]&&cnt2[0])ans++,cnt1[0]--,cnt2[0]--;
else if(cnt1[1]&&cnt2[1])ans++,cnt1[1]--,cnt2[1]--;
}
}
if(t1[i]=='0'){
cnt1[0]=cnt1[1]=0;
for(int j=i+1;t1[j]=='1';j++)cnt1[s1[j]-'0']++;
}
if(t2[i]=='0'){
cnt2[0]=cnt2[1]=0;
for(int j=i+1;t2[j]=='1';j++)cnt2[s2[j]-'0']++;
}
}printf("%d\n",ans);
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
