题解 CF1672H¶
感觉这道题很有趣，记录一下。
看官方答案没太看懂，根据灵神的解答想明白了怎么证明。
首先可以证明每次移除的都是一个完整的 alternative substring。移除不完整的没有任何好处。
首先我们考虑所有的 00，11 的个数（允许重叠）。比如 000 里有两个 00。
如果场上有 k 个 00，0 个 11，那么很显然需要 k+1 次操作。
如果场上有 k 个 00，t 个 11，那么我们考虑：
- 如果移除的是一个偶数长度的 alt string，那么移出后 00 和 11 各减少 1 个。
- 如果移除的是一个奇数长度的 alt string，那么移出后 00 或 11 减少 1 个（其实是减少 2 个，但是前后又拼出 1 个）
- 如果 00 和 11 的个数都不为 0，那么一定存在一个偶数长度的 alt string。这是因为考虑任意两个 00 11，它们中间必须有至少一个偶数长度的 alt string，否则不可能从 0 变成 1 （奇数长度的 alt string 首尾是一样的）
基于以上三点我们不难发现，答案应该是 max(#00, #11) + 1。