HDU-6839 Binary Addition 题解

题目大意

给你两个01串s和t，串n之后的位置可以看做都是0，你可以对s进行两种操作，修改s的第i位，或者将s看做二进制，在二进制的情况下加一，求使s变成t的最小操作步数。

解题思路

比赛的时候完全没思路。

比完之后看到官方题解，才有的思路。。

枚举后缀，先将后缀全部变成1，然后进行加一。

如果第i+1位s是1，就需要先将这一位变成0，然后因为加一，这一位变成1。

如果第i+1为t是0，就还需要将加出来的第i+1位变成0。

在加一之后，后缀全部变成0，所以还需要将后缀变成t一样。

i+2之后的就直接改即可。

完整代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

const int N = 1e5 + 5;
int s0[N], t1[N], dis[N];
char s[N], t[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T; cin >> T;
	while (T--) {
		int n; cin >> n;
		cin >> s + 1 >> t + 1;
		s[n + 1] = t[n + 1] = '0';
		for (int i = 1; i <= n; i++) 
			s0[i] = s0[i - 1] + (s[i] == '0'), 
			t1[i] = t1[i - 1] + (t[i] == '1');
		dis[n + 1] = dis[n + 2] = 0;
		for (int i = n; i >= 1; i--)
			dis[i] = dis[i + 1] + (s[i] != t[i]);
		int ans = dis[1];
		for (int i = 1; i <= n; i++) {
			int tmp = (s[i + 1] == '1') + (t[i + 1] == '0');
			tmp += s0[i] + t1[i] + 1 + dis[i + 2];
			ans = min(ans, tmp);
		}
		cout << ans << endl;
	}
}