2020 年百度之星·程序设计大赛 - 复赛 1002 Binary Addition

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;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/107901814