题解：P11361 [NOIP2024] 编辑字符串

#include<bits/stdc++.h>
using namespace std;
int t,n;
char a[1145140],b[1145140],c[1145140],d[1145140];
int loca[1145140],locb[1145140];//a[i]与b[i]当前位置为第几块
int blocka[1145140][3],blockb[1145140][3];//记录第某一块的字符0的总数与1的总数 
int main(){
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	cin>>t;
	while(t--){
		int ans=0;//记录答案 
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)cin>>b[i];
		for(int i=1;i<=n;i++)cin>>c[i];
		for(int i=1;i<=n;i++)cin>>d[i];
		//输入
		int cnta=1;//cnta记录当前为第几块 
		for(int i=1;i<=n;i++){
			if(c[i]=='1'){
				loca[i]=cnta;//记录当前位置属于哪个块 
				blocka[cnta][a[i]-'0']++;//块内对应字符个数+1 
			}
			if(c[i]=='0'&&c[i-1]=='1'){
				cnta++;//此块已经结束，开一个新块 
			}
		}
		int cntb=1;//b[i]与a[i]同理进行处理 
		for(int i=1;i<=n;i++){
			if(d[i]=='1'){
				locb[i]=cntb;
				blockb[cntb][b[i]-'0']++;
			}
			if(d[i]=='0'&&d[i-1]=='1'){
				cntb++;
			}
		}
		
		for(int i=1;i<=n;i++)if(c[i]=='0'&&d[i]=='0'&&a[i]==b[i])ans++;//当两位置锁定且相同时ans++
		
		for(int i=1;i<=n;i++){
			if(c[i]=='1'&&d[i]=='0'){
				if(blocka[loca[i]][b[i]-'0']!=0){//若当前块存在与锁定字符相同的字符时，将此字符填入 
					blocka[loca[i]][b[i]-'0']--;
					ans++;
				}
			}
			if(c[i]=='0'&&d[i]=='1'){
				if(blockb[locb[i]][a[i]-'0']!=0){//同理
					blockb[locb[i]][a[i]-'0']--; 
					ans++;
				}
			}
		}
		
		for(int i=1;i<=n;i++){
			if(c[i]=='1'&&d[i]=='1'){
				if(blocka[loca[i]][1]!=0&&blockb[locb[i]][1]!=0){
					blocka[loca[i]][1]--;
					blockb[locb[i]][1]--;
					ans++;
				}
				else if(blocka[loca[i]][0]!=0&&blockb[locb[i]][0]!=0){
					blocka[loca[i]][0]--;
					blockb[locb[i]][0]--;
					ans++;
				}
			}
		}
		cout<<ans<<endl;
		
		for(int i=1;i<=n;i++)loca[i]=0,locb[i]=0;
		//多测不清空，亲人两行泪 
		for(int i=1;i<=cnta;i++)blocka[i][0]=0,blocka[i][1]=0;
		//多测不清空，亲人两行泪 
		for(int i=1;i<=cntb;i++)blockb[i][0]=0,blockb[i][1]=0;
		//多测不清空，亲人两行泪
		//重要的事情说三遍 
	}
	return 0;
}