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