Moe's CF Life

喵~ 主人，今天我们来玩一个关于二进制字符串的游戏好不好呀？Alice 和 Bob 两位老朋友又在对决啦，我们要帮他们分出胜负，喵！

D. Binary String Battle

题目大意喵

Alice 和 Bob 有一个长度为 n 的二进制字符串 s 和一个整数 k。他们轮流操作，Alice 先手。

Alice 的回合：她可以选择字符串中任意 k 个字符（也就是一个长度为 k 的子序列），把它们全都变成 '0'。
Bob 的回合：他可以选择字符串中任意一个长度为 k 的连续子串，把它们全都变成 '1'。

Alice 的目标是把整个字符串都变成 '0'。只要她在她的回合结束后，字符串变成了全 '0'，她就立刻获胜啦！如果 Alice 没办法在有限的回合内获胜，那 Bob 就赢了。

我们要判断，在双方都采取最优策略的情况下，谁会赢呢？

解题思路大揭秘！

这是一个典型的博弈论问题哦，喵~ 不过主人别怕，我们不需要去模拟整个复杂的游戏过程。只要抓住双方的优劣势和制胜关键，就能像猫咪抓老鼠一样，一下子找到答案！

我们可以分几步来分析，就像猫咪走路一样，一步一步，优雅又准确~

第一步：Alice 能不能一回合就获胜？

Alice 的目标是清空所有的 '1'。她一次可以清空 k 个 '1'。那么最简单的情况就是，如果整个字符串里 '1' 的数量本来就很少，少于等于 k 个，那 Alice 不就可以在她的第一个回合，选中所有的 '1'，然后 piu 的一下把它们都变成 '0' 了吗？

结论 1：如果字符串中 '1' 的总数 ones <= k，Alice 直接获胜！

第二步：Bob 有没有稳赢的法宝？

如果 Alice 不能一回合获胜（也就是 ones > k），那我们就要看看 Bob 能不能阻止她了。Bob 的武器是把一个长度为 k 的子串变成全 '1'。这是一个非常强大的防御（或者说反击）手段。

想象一下，如果字符串里已经存在一个长度为 k 的全 '0' 子串，会发生什么？

轮到 Alice 操作，她很努力地在字符串的别处把 k 个 '1' 改成了 '0'。但是，那个长度为 k 的全 '0' 子串，她动它干嘛呀？它本来就是 '0' 嘛。所以这个全 '0' 子串会完好无损地保留下来。
轮到 Bob 了！他看到了这个完美的长度为 k 的全 '0' 子串，眼睛一亮，直接发动技能，把这个子串变成了 111...1（k 个 '1'）。
这样一来，不管 Alice 之前多么努力地消除 '1'，Bob 只要一招，就能确保场上至少有 k 个 '1'。而 Alice 一回合最多也只能消除 k 个 '1'。这意味着，Alice 永远无法把 '1' 的数量降到 0。她永远也赢不了。

结论 2：如果 ones > k 并且字符串中存在一个长度至少为 k 的连续 '0' 子串，Bob 获胜！

第三步：真正的战场！

好啦，现在我们来到了最复杂的情况：ones > k （Alice 不能秒杀）并且 max_zeros < k （Bob 没有现成的 '0' 块可以用）。

这时候，胜负的关键就在于 n 和 k 的大小关系了。这决定了整个战场的“地形”，喵~

情况 A: 2 * k <= n
- 这意味着字符串 n 足够长，至少是 k 的两倍。Bob 可以采取一个“两端开花”的策略。他可以同时关注字符串的头部 s[0...k-1] 和尾部 s[n-k...n-1]。因为 2k <= n，这两个区域是完全分开，互不重叠的。
- Alice 一回合只有 k 次操作机会。她就像一个只有 k 支箭的弓箭手，面对 Bob 的两个城堡。她顶多只能重创其中一个城堡，但另一个城堡就顾不上了。
- Bob 就可以在 Alice 操作完后，检查一下哪个城堡（头部或尾部）的 '0' 更多（也就是防守更薄弱），然后直接把那个城堡变成全 '1'。
- 这样，Bob 总能保证场上至少有 k 个 '1'，Alice 还是赢不了。所以，Bob 获胜。
情况 B: 2 * k > n
- 这意味着字符串 n 相对于 k 来说比较短。k 的长度超过了 n 的一半。
- 这时候，Bob 的“两个城堡”策略就失效了，因为 s[0...k-1] 和 s[n-k...n-1] 会发生重叠！任何一个长度为 k 的子串都会覆盖字符串的“中心”区域。Bob 的所有操作都变得互相牵制。
- 反观 Alice，她的优势就体现出来了。k 很大，她的操作范围非常广。任何一个 Bob 想要固守的长度为 k 的区域，它之外的区域长度为 n-k。而 2k > n 等价于 n-k < k。
- 这意味着，Alice 一次操作 (k 个位置) 的能力，是大于任何 k 子串之外的区域大小 (n-k) 的。她可以轻松地清除掉任何一个 Bob 想要固守的区域之外的所有 '1'，甚至还有余力去削弱那个区域内部。
- 在这种情况下，Alice 掌握了主动权，她可以一步步蚕食 Bob 的 '1'，Bob 无法有效防守。最终，Alice 会把 '1' 的数量减少到 k 以下，然后一举获胜。所以，Alice 获胜。

总结一下策略喵

所以，我们的判断逻辑是这样的：

先看 ones 是否 <= k，如果是，Alice 赢。
如果不是，再看 max_zeros 是否 >= k，如果是，Bob 赢。
如果也不是，最后看 2 * k 是否 > n，如果是，Alice 赢。
否则（也就是 2 * k <= n），Bob 赢。

把这些判断写成代码，问题就解决啦！是不是很简单呀，喵~

参考代码

这是根据上面的思路写出的 C++ 代码，主人可以参考一下哦。

cpp

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

void solve() {
    int n;
    long long k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;

    // 第一步：统计 '1' 的数量
    int ones = 0;
    for (char c : s) {
        if (c == '1') {
            ones++;
        }
    }

    // 结论 1: Alice 能不能一回合获胜？
    if (ones <= k) {
        std::cout << "Alice\n";
        return;
    }

    // 第二步：Bob 有没有稳赢的法宝？
    // 统计最长的连续 '0' 子串
    int max_zeros = 0;
    int current_zeros = 0;
    for (char c : s) {
        if (c == '0') {
            current_zeros++;
        } else {
            max_zeros = std::max(max_zeros, current_zeros);
            current_zeros = 0;
        }
    }
    max_zeros = std::max(max_zeros, current_zeros);

    // 结论 2: Bob 是否有必胜策略？
    if (max_zeros >= k) {
        std::cout << "Bob\n";
        return;
    }

    // 第三步：真正的战场
    // 注意这里要用 long long 防止 k 很大时 2*k 溢出
    if (2LL * k > n) {
        // 情况 B: Alice 获胜
        std::cout << "Alice\n";
    } else {
        // 情况 A: Bob 获胜
        std::cout << "Bob\n";
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D. Binary String Battle ​

题目大意喵 ​

解题思路大揭秘！ ​

第一步：Alice 能不能一回合就获胜？ ​

第二步：Bob 有没有稳赢的法宝？ ​

第三步：真正的战场！ ​

总结一下策略喵 ​

参考代码 ​

相关知识点 ​