C题 | Inverted World

解题思路：

当处理完毕时，s要么是形如101010...的字符串，要么是形如010101...的字符串。以一种为例（另一种处理方法完全copy这一种），若s原来是1110011，处理完毕后是1010101，会发现需要反置原字符串第2，5，6位，对应字符为101，我们只需要处理它们，其他不需要考虑，相当于是把101的所有字符反置，我们要求最小化的操作次数。

string need_reverse(int mode, string s) {//通过输入的字符串得到需要反置的字符串
	string ret;

	for (int i = 0; i < s.size(); i++)
		if (((i + mode) & 1) && s[i] != '1' )
			ret.push_back(s[i]);
		else if ((((i + mode) & 1) == 0) && s[i] != '0')
			ret.push_back(s[i]);

	return ret;
}

不断推理，最后会发现这个问题等价于是对于这个待处理字符串，把所有字符1看成+1，所有0看成-1，然后求这个序列的最大子段和以及最小字段和，并取两者绝对值较大值。

int get_ans(string t) {//根据需要反置的字符串处理得到最终答案，本质是求最大子段和以及最小子段和并返回绝对值较大者
	int mx = 0, current_mx = 0, mn = 0, current_mn = 0;
	int now;

	for (char i : t) {
		if (i == '1') now = 1;
		else now = -1;

		current_mx = max(current_mx + now, now);
		mx = max(mx, current_mx);

		current_mn = min(current_mn + now, now);
		mn = min(mn, current_mn);
	}

	return max(abs(mx), abs(mn));
}

完整示例代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

string need_reverse(int mode, string s) {//通过输入的字符串得到需要反置的字符串
	string ret;

	for (int i = 0; i < s.size(); i++)
		if (((i + mode) & 1) && s[i] != '1' )
			ret.push_back(s[i]);
		else if ((((i + mode) & 1) == 0) && s[i] != '0')
			ret.push_back(s[i]);

	return ret;
}

int get_ans(string t) {//根据需要反置的字符串处理得到最终答案，本质是求最大子段和以及最小子段和并返回绝对值较大者
	int mx = 0, current_mx = 0, mn = 0, current_mn = 0;
	int now;

	for (char i : t) {
		if (i == '1') now = 1;
		else now = -1;

		current_mx = max(current_mx + now, now);
		mx = max(mx, current_mx);

		current_mn = min(current_mn + now, now);
		mn = min(mn, current_mn);
	}

	return max(abs(mx), abs(mn));
}

void solve() {
	int n;
	string s;

	cin >> n >> s;
	string t = need_reverse(0, s);
	int ans = get_ans(t);
	t = need_reverse(1, s);
	ans = min(ans, get_ans(t));

	cout << ans << endl;
}

signed main() {
	int T = 1;
	//cin >> T;
	while (T--)
		solve();

	return 0;
}