题目大意
详细题目传送门
两个 \(01\) 串，可以对两个串中任意相邻的字符进行交换，没有代价可以进行任意多次。可是两个串有的位置的字符是定死的，无法被交换，求任意次操作后最多让两个串的多少个位置 \(01\) 相等。即 \(\sum [a_i=b_i]\)。
\(n\leq 10^5\)
思路
首先根据冒泡排序的性质，假设 \([l,r]\) 内的所有字符都可以被交换，那么这里的所有字符可以排成任意一个排列。
然后我们就可以将本题转成将两个串分成一些连通块，上下排列，每个块内可以按照任意顺序进行排列，求最多相等。
感觉就像是可以贪心的样子。先去考虑能不能假定固定一个串，只动第二个。发现明显不行，如果是形如
\[\textcolor{red}{AAA}\textcolor{blue}{BBBBB}\textcolor{green}{CCCC} \]\[\textcolor{red}{A}\textcolor{blue}{BBBB}\textcolor{green}{CCCCCCC} \]的情况，我们可能会需要将第二个串的一些数字运到第一个串的红色位置才是匹配最优秀的。所以两个串必须联动。
因为是 NOIP 的第一题，应该不会出一些动规类的东西，所以还是向贪心方向考虑。发现任意一个字符只要匹配上了就赚了，不存在让位情况。考虑证明：
反证法对于一个数字 \(A\)，假设在可以匹配的情况下不去进行匹配，而是让位，则必然浪费一个位置无法进行匹配。如果让别的数字 \(B\) 也在这里匹配则若匹配成功就必有 \(A=B\)。又根据上文冒泡排序性质我们可以构造出一个排列使 \(B\) 移动到匹配位，让 \(A\) 移动到 \(B\) 原位，则与直接用 \(A\) 匹配无异。
若不去匹配 \(A\) 一开始能够匹配的位置，而是换了一个不同字符的在上面，则这个位置就无法贡献答案。即便 \(A\) 能够在后面匹配，也只是回到起点，而原本能够匹配的不同字符也有可能无法匹配上，答案一定不优。
这样我们就可以发现可以按从左到右的位进行考虑。对于当前两个字符所属的连通块，如果还有能够匹配的字符，就移动过来，将两个连通块匹配的这个的这个字符数量各自减 \(1\)，让答案加 \(1\) 即可。
代码
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
const ll MAXN=2e5+5;
string a,b,p,q;
ll T,n;
ll id[2][MAXN],num[2][MAXN][2];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
memset(num,0,sizeof(num));
memset(id,0,sizeof(id));
cin>>n;
cin>>a>>b>>p>>q;
a=" "+a,b=" "+b,p=" "+p,q=" "+q;
ll tot=0;
for(int i=1;i<=n;++i){
if(i==1||p[i]=='0'){
tot++;
num[0][tot][a[i]-'0']++;
id[0][i]=tot;
if(p[i]=='0'&&p[i+1]!='0'){
tot++;
}
continue;
}
num[0][tot][a[i]-'0']++;
id[0][i]=tot;
}
tot=0;
for(int i=1;i<=n;++i){
if(i==1||q[i]=='0'){
tot++;
num[1][tot][b[i]-'0']++;
id[1][i]=tot;
if(q[i]=='0'&&q[i+1]!='0'){
tot++;
}
continue;
}
num[1][tot][b[i]-'0']++;
id[1][i]=tot;
}
ll ans=0;
for(int i=1;i<=n;++i){
if(num[0][id[0][i]][0]&&num[1][id[1][i]][0]){
ans++;
num[0][id[0][i]][0]--;
num[1][id[1][i]][0]--;
}else if(num[0][id[0][i]][1]&&num[1][id[1][i]][1]){
ans++;
num[0][id[0][i]][1]--;
num[1][id[1][i]][1]--;
}
}
cout<<ans<<endl;
}
return 0;
}