problem
Binary Addition Accepts: 851 Submissions: 3320
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
你有两个无限长0101串S, TS,T，分别记作S_0S_1\dotsS
0
S
1
…和T_0T_1\dotsT
0
T
1
…。其中SS和TT从nn位之后都是00，也就是当i\geq ni≥n，有S_i=T_i=0S
i
=T
i
=0。
你可以对SS串进行操作：
修改SS串的某一位，从00变成11或者从11变成00。
将SS当成二进制数加11，也就是记s=\sum_{i\geq 0} S_i2^is=∑
i≥0
S
i
2
i
，将SS变成s+1s+1二进制表示的形式，其中低位在最前面。
问最少的步数将SS变成TT。
Input
第一行一个正整数T(1\leq T\leq 10^4)T(1≤T≤10
4
)表示数据组数。
对于每组数据，第一行一个整数nn，接下来两行长度为n(1\leq n\leq 10^5)n(1≤n≤10
5
)的0101串SS和TT，表示SS和TT的前nn位。
保证\sum n\leq 10^6∑n≤10
6
。
Output
对于每组数据，输出一个整数，表示步数。
Sample Input
Copy
3
5
11111
00000
5
10100
01010
5
00000
00001
Sample Output
2
3
1
Hint
第一组数据中，可以选择先加一变成 “000001”，然后将S5变成 ‘0’。
第二组数据中，先加一变为 “01100”，然后直接修改。
第三组数据中，直接修改。
solution
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 2000010;
int ps[maxn],pt[maxn],sf[maxn],n,ans;
char s[maxn], t[maxn];
int main(){
int T; cin>>T;
while(T--){
int n; cin>>n;
scanf("%s",s+1);
scanf("%s",t+1);
s[n+1] = '0';
t[n+1] = '0';
for(int i = 1; i <= n; i++){
ps[i] = ps[i-1]+(s[i] == '0');
pt[i] = pt[i-1]+(t[i] == '1');
}
sf[n+1] = 0;
sf[n+2] = 0;
for(int i = n; i >= 1; i--){
sf[i] = sf[i+1]+(s[i]!=t[i]);
}
ans = sf[1];
for(int i = 1; i <= n; i++){
int tmp = (s[i+1]=='1')+(t[i+1]=='0');
tmp += ps[i]+pt[i]+sf[i+2]+1;
ans = min(ans, tmp);
}
cout<<ans<<"\n";
}
return 0;
}