CF1988B Make Majority 题解

题意简述

给定一个长度为 $n$ 的 01 序列 $a$。每次操作可以选择一个区间 $[l,r]$，统计区间内 $0$ 的个数 $c_0$ 和 $1$ 的个数 $c_1$：

• 若 $c_0 \ge c_1$，则将区间替换为一个 $0$；
• 若 $c_0 < c_1$，则将区间替换为一个 $1$。

问能否通过若干次操作使得最终序列变为 $[1]$。

核心分析

目标是把整个序列合并成单个 $1$，这意味着我们需要尽量减少 $0$ 的数量。

关键观察 1：先合并连续的 $0$

考虑任意一段连续的 $0$（形如 000...0，两端或一端有 $1$ 隔开）：

• 如果我们单独对这一段连续的 $0$ 做一次操作，显然 $c_0 \ge c_1$（因为 $c_1=0$），所以它一定会变成一个 $0$。
• 这相当于把「一段连续 $0$」压缩成一个 $0$，且该操作不会影响 $1$ 的个数。

因此，我们可以先执行这样的操作，把原序列中每一段连续的 $0$ 都压缩成一个单独的 $0$。此时序列中不会出现相邻的两个 $0$。

关键观察 2：判断最终可能性

压缩后，令整个序列中 $0$ 的个数为 $c_0$（也就是原序列中连续 $0$ 的段数），$1$ 的个数为 $c_1$。

现在考虑能否通过后续操作使整个序列合并成 $[1]$：

• 如果 $c_0 \ge c_1$： 无论选择什么区间，区间内 $0$ 的个数永远 $\ge 1$ 的个数（因为我们可以把 $0$ 和 $1$ 配对，而 $0$ 多了至少一个），所以任何合并操作都会倾向于产生 $0$。最终无论如何都无法消除所有的 $0$，故答案为 No。

• 如果 $c_0 < c_1$： 我们直接选择整个序列 $[1,n]$ 进行一次操作。此时区间内 $c_1 > c_0$，合并结果恰好为 $1$，序列变为 $[1]$。故答案为 Yes。

因此，判定条件仅取决于：压缩后 $0$ 的个数是否严格小于 $1$ 的个数。

统计方法

遍历一遍字符串：

• 遇到 '1'，c1 加一；
• 遇到 '0'，如果它是某个连续 $0$ 块的开头（即 $i=0$ 或前一个字符是 '1'），则 c0 加一。

最后比较 $c_0$ 与 $c_1$ 即可。

复杂度

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(1)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n, c0 = 0, c1 = 0;
        string a;
        cin >> n >> a;

        for (int i = 0; i < n; i++) {
            if (a[i] == '1') {
                c1++;
            } else {
                if (i == 0 || a[i-1] == '1') {
                    c0++;
                }
            }
        }

        if (c0 >= c1) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
        }
    }
    return 0;
}