70分 WA15~20 求调

#include<bits/stdc++.h>
using namespace std;
int T;
int n,fa1[100001],fa2[100001];
int size10[100001],size11[100001];
int size20[100001],size21[100001];
int l1[100001],r1[100001];
int l2[100001],r2[100001];
int main()
{
  cin>>T;
  while(T--)
  {
  	string s;
  	int ans=0;
  	char s1[100001],s2[100001];
  	bool t1[100001],t2[100001];
  	memset(fa1,0,sizeof fa1);
  	memset(fa2,0,sizeof fa2);
  	memset(size10,0,sizeof size10);
  	memset(size20,0,sizeof size20);
  	memset(size11,0,sizeof size11);
  	memset(size21,0,sizeof size21);
  	memset(l1,0,sizeof l1);
  	memset(l2,0,sizeof l2);
  	memset(r1,0,sizeof r1);
  	memset(r2,0,sizeof r2);
  	cin>>n;
  	cin>>s;
  	for(int i=0;i<n;i++) s1[i]=s[i];
  	cin>>s;
  	for(int i=0;i<n;i++) s2[i]=s[i];
  	cin>>s;
  	for(int i=0;i<n;i++) t1[i]=s[i]-'0';
  	cin>>s;
  	for(int i=0;i<n;i++) t2[i]=s[i]-'0';
  	for(int i=1;i<n;i++)
  	{
  		if(t1[i] and t1[i-1])
  		{
  			fa1[i]=fa1[i-1];
  			r1[fa1[i]]=i;
  		}
  		else
  		{
  			fa1[i]=i;
  			l1[fa1[i]]=i;
  			r1[fa1[i]]=i;
  		}
  		if(t2[i] and t2[i-1])
  		{
  			fa2[i]=fa2[i-1];
  			r2[fa2[i]]=i;
  		}
  		else
  		{
  			fa2[i]=i;
  			l2[fa2[i]]=i;
  			r2[fa2[i]]=i;
  		}
  	}
  	for(int i=0;i<n;i++)
  	{
  		if(s1[i]=='1') size11[fa1[i]]++;
  		else size10[fa1[i]]++;
  		if(s2[i]=='1') size21[fa2[i]]++;
  		else size20[fa2[i]]++;
  	}
  	for(int i=0,j=0;i<n and j<n;)
  	{
  		if(not(l1[fa1[i]]>r2[fa2[j]] or r1[fa1[i]]<l2[fa2[j]]) and size10[fa1[i]]>0 and size20[fa2[j]]>0)
  		{
  			ans++;
  			size10[fa1[i]]--;
  			size20[fa2[j]]--;
  			if(s1[i]=='0')
  			{
  				if(i==l1[fa1[i]] and l1[fa1[i]]<r1[fa1[i]]) l1[fa1[i]]++;
  				i++;
  			}
  			if(s2[j]=='0')
  			{
  				if(j==l2[fa2[j]] and l2[fa2[j]]<r2[fa2[j]]) l2[fa2[j]]++;
  				j++;
  			} 
  		}
  		else if(not(l1[fa1[i]]>r2[fa2[j]] or r1[fa1[i]]<l2[fa2[j]]) and size11[fa1[i]]>0 and size21[fa2[j]]>0)
  		{
  			ans++;
  			size11[fa1[i]]--;
  			size21[fa2[j]]--;
  			if(s1[i]=='1')
  			{
  				if(i==l1[fa1[i]] and l1[fa1[i]]<r1[fa1[i]]) l1[fa1[i]]++;
  				i++;
  			}
  			if(s1[j]=='1')
  			{
  				if(j==l2[fa2[j]] and l2[fa2[j]]<r2[fa2[j]]) l2[fa2[j]]++;
  				j++;
  			} 
  		}
  		else
  		{
  			if(i<j) i++;
  			else j++;
  		}
  		while(i<n and size10[fa1[i]]+size11[fa1[i]]<=0) i++;
  		while(j<n and size20[fa2[j]]+size21[fa2[j]]<=0) j++;
  	}
  	cout<<ans<<endl;
  }
  return 0;
}