D - Distant Control - 题解

标签与难度

标签: 贪心, 思维题, 字符串, 构造, 博弈论思想 难度: 1400

题目大意喵~

你好呀，指挥官！我们有一排 $n$ 个机器人朋友，编号从 1 到 $n$。它们有的开着('1')，有的关着('0')，就像一串二进制码一样呢。

我们有一个神奇的遥控器，但它有点小脾气，只能执行两种操作，都和一个固定的数字 $a$ 有关：

1. 关机操作: 找到 连续的 $a$ 个 都处于开机状态的机器人，把它们全部关掉 (从 '1' 变成 '0')。
2. 开机操作: 找到 连续的 $a+1$ 个 都处于关机状态的机器人，把它们全部打开 (从 '0' 变成 '1')。

我们可以执行任意多次操作（也可以一次都不做）。我们的任务是，找出经过一番操作后，最多能有多少个机器人处于开机状态，喵~？

解题思路分析

这道题看起来像是在问我们如何通过一系列操作来达到一个最优状态，也就是让开机的机器人数量最大化，对吧？那我们当然是希望尽可能多地执行“开机操作”，少做（或者不做）“关机操作”啦！

“开机操作”可以让 $a+1$ 个机器人打开，净增加了 $a+1$ 个 '1'。而“关机操作”会让我们失去 $a$ 个 '1'。一增一减，这其中一定有什么奥秘，喵！

让我们来仔细分析一下这两个操作的关系。

我们的目标是最大化 '1' 的数量，所以最理想的情况就是把所有机器人都变成 '1'，也就是让答案等于 $n$。那么问题就变成了：我们有没有可能把所有机器人都变成 '1' 呢？

这就像点燃一堆篝火，需要一个“火种”。一旦有了火种，火焰就可能蔓延开来，把所有木柴都点燃！在这里，“开机操作”就是我们的“火种”，它可以增加 '1' 的数量。

寻找“火种”

有两种可能的方式来启动这个“全部开机”的连锁反应：

1. 直接火种: 初始状态下，如果已经存在一个长度至少为 $a+1$ 的连续 '0' 段（比如 ...00...0...，长度 $\ge a+1$），我们就可以直接执行“开机操作”，把它们变成 '1'。这一下就增加了 $a+1$ 个 '1'，多棒呀！

2. 间接火种: 如果没有现成的长 '0' 段怎么办呢？别灰心，我们还可以“创造”一个！“关机操作”可以把一段长度为 $a$ 的 '1' 变成 '0'。虽然这会暂时减少 '1' 的数量，但如果我们能巧妙地利用它，就能创造出奇迹，喵~

   想象一下这个场景：...011...1...，其中 '1' 的部分长度恰好是 $a$。如果我们对这段 '1' 执行“关机操作”，它就会变成 ...000...0...。看呐！原来的那个 '0' 和我们新创造的 $a$ 个 '0' 连在了一起，形成了一个长度为 $a+1$ 的 '0' 段！这不就创造出了一个“直接火种”了嘛？

   那么，什么时候可以通过“关机操作”来创造火种呢？只要我们有一段长度至少为 $a$ 的连续 '1'，并且整个序列中至少还有一个 '0' 存在，那么这段 '1' 的边界必然会和 '0' 相邻（或者通过其他 '1' 间接相邻）。我们总能找到一个地方，通过关掉 $a$ 个 '1' 来和旁边的 '0' 合并，从而凑出 $a+1$ 个连续的 '0'。

连锁反应的开始

一旦我们通过上述两种方式之一，成功地执行了一次“开机操作”，我们就拥有了更多的 '1'。这些新生成的 '1' 可能会和旁边的 '1' 合并，形成更长的 '1' 段。这样一来，我们就更有可能拥有长度 $\ge a$ 的 '1' 段，从而可以执行“关机操作”来创造更多的“火种”。

这个过程就像一个永动机！

• 用 0...0 (长度 $a+1$) -> 1...1 (增加 '1')
• 用 1...1 (长度 $a$) -> 0...0 (创造 '0'，准备下一步的增加)

只要我们能启动这个循环，我们就能不断地把 '0' 变成 '1'，直到整个序列都变成 '1' 为止。这个过程是不可阻挡的！

结论

所以，解题的关键就变成了一个非常简单的问题：我们能不能找到最初的那个“火种”？

• 条件一: 字符串中是否存在一个长度 $\ge a+1$ 的连续 '0' 段？
• 条件二: 字符串中是否存在一个长度 $\ge a$ 的连续 '1' 段？

只要满足上述任意一个条件，我们就能启动连锁反应，最终把所有 $n$ 个机器人都打开。这种情况下，答案就是 $n$。

如果这两个条件都不满足，那就意味着我们既不能直接开机，也不能通过关机来创造开机的条件。我们一个操作也做不了，只能保持现状。那么答案就是初始状态下 '1' 的数量。

所以，我们的算法超级简单，喵~

1. 扫一遍字符串，找出最长的连续 '1' 的长度 max_ones 和最长的连续 '0' 的长度 max_zeros。
2. 如果 max_ones >= a 或者 max_zeros >= a+1，那么答案就是 n。
3. 否则，答案就是字符串里 '1' 的初始个数。

代码实现

这是我根据上面的思路，精心为你准备的代码哦~ 注释超详细的，希望能帮到你，喵！

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

// 为了让代码更整洁，把处理单个测试用例的逻辑放到一个函数里，喵~
void solve() {
    int n;
    int a;
    std::cin >> n >> a;
    std::string s;
    std::cin >> s;

    // 标志位，判断是否可以启动“连锁反应”
    bool can_make_all_ones = false;

    // 单次遍历来检查是否存在足够长的 '1' 或 '0' 段
    int consecutive_ones = 0;
    int consecutive_zeros = 0;

    for (char c : s) {
        if (c == '1') {
            consecutive_ones++;
            consecutive_zeros = 0; // 连续的 '0' 中断了
        } else { // c == '0'
            consecutive_zeros++;
            consecutive_ones = 0; // 连续的 '1' 中断了
        }

        // 检查是否满足启动条件
        // 条件1: 连续的 '1' 数量达到 a
        // 条件2: 连续的 '0' 数量达到 a+1
        if (consecutive_ones >= a || consecutive_zeros >= a + 1) {
            can_make_all_ones = true;
            break; // 已经找到火种，可以提前结束循环啦！
        }
    }

    if (can_make_all_ones) {
        // 如果可以启动连锁反应，最终就能把所有机器人都打开
        std::cout << n << std::endl;
    } else {
        // 如果无法启动，就只能保持原样，计算初始的 '1' 的数量
        int initial_ones = 0;
        for (char c : s) {
            if (c == '1') {
                initial_ones++;
            }
        }
        std::cout << initial_ones << std::endl;
    }
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(N)$。对于每个测试用例，我们最多只需要完整遍历一次长度为 $N$ 的字符串。如果提前找到了“火种”，甚至会更快结束。总时间复杂度是所有测试用例的 $N$ 之和，即 $O(\sum N)$。
• 空间复杂度: $O(1)$。我们只需要几个变量来存储当前的连续计数和总数，不需要与 $N$ 成正比的额外空间，非常节省内存呢，喵~

知识点总结

这道题的核心是观察和思维转换。它告诉我们，在面对一个看似复杂的操作序列问题时，可以先思考：

1. 最终目标是什么？ (最大化 '1' 的数量，理想情况是全为 '1')
2. 达到目标的“瓶颈”或“关键步骤”是什么？ (能够执行“开机操作”)
3. 如何创造执行关键步骤的条件？ (通过“关机操作”来构造出满足条件的 '0' 段)

一旦发现了这个“连锁反应”或者“点火”的机制，问题就从一个动态的过程模拟，简化成了一个静态的初始条件检查。这是解决很多构造题和思维题的常用技巧哦！希望你也能掌握这种化繁为简的魔法，加油，喵~！