C题 | Inverted World

解题思路：

对于任意一个元素，其最终状态只和它的操作次数的奇偶性有关。操作奇数次会取反，偶数次则不变。也就是说，对于任意一位最多操作一次，即可符合题意。

符合题意的最终字符串仅有两种形式：0101...... 和 1010......，我们只需对每个与最终字符串不同的位（异位）操作一次即可。由于我们可以直接操作一个区间，因此可以合并一些操作成为一个操作区间（合异位）。

我们可以贪心地合异位。把异位单独拎出来放到一个数组里，从左到右遍历：

假设当前这一位是 x，查找先前已经进行过的以 !x 结尾的操作区间：

• 如果找到了，那当前位就可以并入这个操作区间，然后这个操作区间就变成以 x 结尾了；
• 如果没找到，说明前面进行过的所有操作都是以 x 结尾的，因此该位只能作为一个新的操作区间的起点。

这样可以保证每个数都被唯一包含在一个操作区间内，且区间总数量最小。

怎么实现呢？非常简单，只需要开两个 int 分别记录以 0 结尾和以 1 结尾的操作区间数量即可。

时空复杂度 。

示例代码：

int ans(vector<int>&a) {
	int cnt[2] = {0}; // cnt[i]: 以i结尾的字符串数量
	for (auto x : a) {
		if (cnt[!x]) --cnt[!x];
		++cnt[x];
	}
	return cnt[0] + cnt[1];
}

void solve() {
	int n;
	string s;
	cin >> n >> s;
	for (auto&x : s) x -= '0'; // 字符转int
	
	vector<int> a[2];
	for (int i = 0; i < n; ++i) // 根据两种最终字符串 提取异位
		a[s[i]^(i&1)].push_back(s[i]);
	
	cout << min(ans(a[0]), ans(a[1])) << endl;
}