CF思维题(cf round 1019 div.2 b题)

CF思维题(cf round 1019 div.2 b题)

Problem - B - Codeforces

题目大意：
给出一个$01$字符串，其中字符串的长度是$n(1\le n\le 2\times 10^5)$

现在有两个按钮$0,1$，开始时手在按钮$0$上。我们每次可以做出两次操作：

• 按下手上的按钮，输出按钮上面的数字($0$或$1$)
• 将手上的按钮换成另一个按钮

定义操作次数为：使用上述两种操作，选择其一，输出完整个字符串所需要的操作次数

现在可以改变字符串，我们可以任选两个索引$l,r$，并反转子串$S_{lr}$，我们就可以在新字符串上操作

问最小操作次数是多少？

解法：

考虑反转字符串的特性：

首先对于反转一个字符串中的子串，只有在反转处会改变连接状态，对于反转位置之前，中间，之后的地方，字符串的连接状态没有改变。例如，对于下面这个字符串，我们想要反转区间$[L,R]$

$\mathrm{010111...}L...0110...R...10011$

显然，这里的操作次数最多只会减少$2$，原因是反转只改变了反转连接处的连接关系

对于一个字符串来说，我们不妨假设每一个字符串的前面都加上了一个虚开头$0$，这样做的好处不言而喻。对于以$1$开头的字符串，这样操作说明了$0$和$1$之间需要发生转换，同时在统计$01$段时方便了后续的思考。读者不妨考虑一下

统计字符串中$01$，$10$段的数量

若$cnt(01)\ge 2||cnt(10)\ge 2$，我们总是能通过反转使得操作次数减少$2$

我们还要统计字符串需要转换按钮的次数$m$

若不满足上面条件，但是$m\ge 2$，我们可以使得操作次数减少$1$

例如$10$，$010$等

代码如下：

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

void solve() {
	int n;
	string str;
	cin >> n >> str;
	char prev = '0';
	int m = 0, c01 = 0, c10 = 0;
	for (int i = 0; i < str.size(); i ++) {
		char cur = str[i];
		if (cur != prev) {
			m ++;
			if (prev == '0') c01 ++;
			else c10 ++;
		}
		prev = cur;
	}
	int res = n + m;
	if (c01 >= 2 || c10 >= 2) {
		res -= 2;
	} else if (m >= 2) {
		res -= 1;
	}
	cout << res << endl;
}

int main() {
	int t;
	cin >> t;
	while (t --) {
		solve();
	}
	return 0;
}