给一个 \(01\) 字符串，需要使它变为非降的，可以执行以下操作：
- 选择一个下标 \(i, (1 \leq i \leq n)\) ，\(\forall j \geq i\) 的数位翻转。
经典的按无后效性翻转问题。
考虑从前往后，得到一个全 \(0\) 串。若开始存在 \(1\) ，则答案减 \(1\) 。
- 如果存在 \(1\) ，遇到 \(1\) 便翻转后缀。最后一定会有一段连续 \(1\) 的后缀，导致多翻转一次，于是答案为 \(cnt - 1\) 。
- 如果不存在 \(1\) ，答案为 \(0\) 。
- 于是答案为 \(max(cnt - 1, 0)\) 。
直观考虑显然是用前缀和，这是对的。
但是“一维后缀翻转”问题具有性质： \(a_{i}\) 翻转后与 \(a_{i + 1}\) 的关系不变。
- 若 \(a_{i + 1} \neq a_{i}\) ，此时 \(a_i\) 为 \(1\) ，将它的后缀翻转，若 \(a_{i + 1} \neq a_{i}\) ，翻转后 \(a_{i + 1}\) 为 \(1\) 。
于是可以设边界 \(s_{0} = 0\) ，记录 \(cnt = \sum_{i=1}^{n}[a_i \neq a_{i - 1}]\) 。答案为 \(max(cnt - 1, 0)\) 。
view
#include <bits/stdc++.h>
void solve() {
int n; std::cin >> n;
std::string s; std::cin >> s; s = "0" + s;
int cnt = 0; for (int i = 1; i <= n; i++) cnt += (s[i] != s[i - 1]);
std::cout << std::max(cnt - 1, 0) << '\n';
}
signed main() {
int _ = 1; std::cin >> _;
while (_--) solve();
return 0;
}