题解 CF2252B Always Changing

JuRuoOIer · 2026-08-10 08:38:08 · 题解

题解 CF2252B Always Changing

同场其他题

题意

给定长为 n 的 01 串 s，求至少删除多少个字符，能使其 01 交替出现，且删除的 0 和 1 个数相差不超过 1。

数据范围：多测，\sum n\le 2\times 10^5。

做法

:::info[我毫无头绪。] 一个比较 naive 的想法是将所有连续段变成一个字符。显然这是必要的，但是可能还不满足条件。 :::

先看提示。

此时得到的串已经是一个符合条件的 01 串了，所以在中间删除一段时要求该段两侧字符相同，所以删除的段的长度必为偶数，删除的 0 和 1 的个数必然相等，即白删了。

所以只有从头尾删是有可能改变删去的 0 和 1 的个数之差的，至多改变多少取决于头尾是不是此前删除数量较少的字符，判断即可。

单组复杂度 O(n)。