考场回忆版代码,不知道为啥小样例没过,大样例和考场上一样没有通过 #7 和 #10,获得了 80pts。
代码:
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read() {
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9') {
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9') {
x=x*10+ch-48;
ch=getchar();
}
return x*f;
}
int T,n,s1[MAXN],s2[MAXN],t1[MAXN],t2[MAXN];
string str;
int main() {
T=read();
while(T--){
n=read();
cin>>str; for(int i=0;i<n;i++) s1[i+1]=str[i]-'0';
cin>>str; for(int i=0;i<n;i++) s2[i+1]=str[i]-'0';
cin>>str; for(int i=0;i<n;i++) t1[i+1]=str[i]-'0';
cin>>str; for(int i=0;i<n;i++) t2[i+1]=str[i]-'0';
s1[n+1]=-2,s2[n+1]=2,t1[n+1]=0,t2[n+1]=0;
int s1_sum0=0,s1_sum1=0,s2_sum0=0,s2_sum1=0;
int s1_res0=0,s1_res1=0,s2_res0=0,s2_res1=0;
int ans=0;
for(int i=1;i<=n+1;i++){
if(s1[i]==0) s1_sum0++;
if(s1[i]==1) s1_sum1++;
if(s2[i]==0) s2_sum0++;
if(s2[i]==1) s2_sum1++;
if(t1[i]==0&&t2[i]==0){
if(s1[i]==0) s1_sum0--;
if(s1[i]==1) s1_sum1--;
if(s2[i]==0) s2_sum0--;
if(s2[i]==1) s2_sum1--;
int ans2=(s1[i]==s2[i]);
int ans3=min(s1_sum0,s2_res0); s1_sum0-=ans3,s2_res0=0;
int ans4=min(s1_sum1,s2_res1); s1_sum1-=ans4,s2_res1=0;
int ans5=min(s2_sum0,s1_res0); s2_sum0-=ans5,s1_res0=0;
int ans6=min(s2_sum1,s1_res1); s2_sum1-=ans6,s1_res1=0;
int ans0=min(s1_sum0,s2_sum0); s1_sum0=s2_sum0=0;
int ans1=min(s1_sum1,s2_sum1); s1_sum1=s2_sum1=0;
ans+=(ans0+ans1+ans2+ans3+ans4+ans5+ans6);
continue;
}
if(t1[i]==0){
if(s1[i]==0) s1_sum0--,s1_res0++;
if(s1[i]==1) s1_sum1--,s1_res1++;
int ans3=min(s1_sum0,s2_res0); s1_sum0-=ans3,s2_res0=0;
int ans4=min(s1_sum1,s2_res1); s1_sum1-=ans4,s2_res1=0;
int ans0=min(s1_sum0,s2_sum0); s1_sum0=0,s2_sum0-=ans0;
int ans1=min(s1_sum1,s2_sum1); s1_sum1=0,s2_sum1-=ans1;
ans+=(ans0+ans1+ans3+ans4);
continue;
}
if(t2[i]==0){
if(s2[i]==0) s2_sum0--,s2_res0++;
if(s2[i]==1) s2_sum1--,s2_res1++;
int ans5=min(s2_sum0,s1_res0); s2_sum0-=ans5,s1_res0=0;
int ans6=min(s2_sum1,s1_res1); s2_sum1-=ans6,s1_res1=0;
int ans0=min(s1_sum0,s2_sum0); s1_sum0-=ans0,s2_sum0=0;
int ans1=min(s1_sum1,s2_sum1); s1_sum1-=ans1,s2_sum1=0;
ans+=(ans0+ans1+ans5+ans6);
continue;
}
}
printf("%d\n",ans);
}
return 0;
}