题解：CF2038G Guess One Character

lgx57 · 2024-11-19 09:55:37 · 题解

一道很有意思的题目。

结论：问 1，11，10 的个数。

我们可以把连续的 0 和 1 都缩成 1 个 0 或 1。经过这样的操作后，整个字符串变成了 0 和 1 交替的样子。

于是可以想到计算出 1 的段数。设 x 为 1 的个数，xx 为 11 的个数，容易得到 1 的段数为 len=x-xx。

再设 10 的个数为 yy，然后分成 2 种情况讨论：

1. 若 len>yy 那么这个字符串一定是 0101 \cdots 01 或 10101 \cdots 01，无论怎么样都是 1 结尾。（不然这个 1 一定会对 10 的数量产生贡献）
   2. 否则，这个字符串一定以 0 结尾。

然后就做完了。