题目题解

问题理解

给定长度为 $n$ 的二进制字符串 $s$ 和整数 $k$（$1 \le k < n$）。
Alice 先手，每轮：

• Alice 选择任意长度为 $k$ 的子序列（不一定连续），将其全部设为 $0$。
• Bob 选择任意长度为 $k$ 的子串（连续段），将其全部设为 $1$。

若某一时刻字符串全为 $0$，Alice 立即获胜。双方最优，判断谁获胜。

---

第一步：Alice 直接获胜的条件

设 $cnt$ 为字符串中 $1$ 的个数。
若 $cnt \le k$，则 Alice 可以在第一回合选择所有 $1$ 作为子序列（长度恰好为 $cnt$，若不足 $k$ 可补 $0$ 凑够 $k$），将所有 $1$ 变为 $0$，立即获胜。
因此：

$$\text{若 } cnt \le k \quad \Rightarrow \quad \text{Alice 胜}. $$

---

第二步：Bob 的胜利条件

Bob 获胜当且仅当他能保证在 Alice 的每个回合开始前，字符串中至少有 $k+1$ 个 $1$。
因为这样 Alice 每次最多只能翻转 $k$ 个 $1$，而 Bob 能通过操作将至少 $k$ 个位置变回 $1$，从而保持 $1$ 的数量 $\ge k+1$。

---

第三步：当 $n \ge 2k$ 时 Bob 获胜

若 $n \ge 2k$，Bob 有策略保证每次操作后 $1$ 的数量 $\ge k+1$。

策略：
在 Bob 的回合，他先任意选择一个已有的 $1$ 作为“保留位”（位置 $p$），然后选择一个长度为 $k$ 且不包含 $p$ 的子串。
由于 $n \ge 2k$，$p$ 的左侧或右侧至少有 $k$ 个位置，因此这样的子串一定存在。
Bob 将该子串全部设为 $1$，这样：

• 该子串贡献 $k$ 个 $1$，
• 保留位 $p$ 本身就是 $1$（未被影响），

因此总 $1$ 的数量 $\ge k+1$。

由于 Bob 能在每轮保持 $1$ 的数量 $\ge k+1$，Alice 永远无法将全部 $1$ 清零，因此 Bob 获胜。

---

第四步：当 $n < 2k$ 时 Alice 获胜

若 $n < 2k$，Alice 有获胜策略。

关键观察：
当 $n < 2k$ 时，任意长度为 $k$ 的子串必然覆盖位置 $\lfloor (n+1)/2 \rfloor$（中间位置）。
特别地，所有长度为 $k$ 的子串都包含第 $\lceil n/2 \rceil$ 个位置（取整后固定）。

Alice 的策略：
她始终保留中间位置（记为 $pos$）的值为 $1$，直到最后一回合。
在每轮她的回合，她选择任意 $k$ 个 $1$（不包括 $pos$）变为 $0$。
由于 $n < 2k$，除了 $pos$ 外，剩余位置数 $n-1 < 2k-1$，但 Alice 总能找到 $k$ 个 $1$ 吗？需要确保 $1$ 的数量足够。

更精确的论证：
设 $x$ 为当前 $1$ 的数量。若 $x > k$，Alice 可以翻转 $k$ 个 $1$（避开 $pos$），使 $x$ 减少 $k$。
随后 Bob 操作：他只能选择包含 $pos$ 的子串（因为所有长度为 $k$ 的子串都包含 $pos$），且 $pos$ 当前为 $1$，因此 Bob 最多只能将其他 $k-1$ 个位置变为 $1$。
因此，Bob 操作后，$1$ 的数量增加最多 $k-1$。
所以每轮净减少至少 $1$ 个 $1$。

由于 $x$ 有限且严格递减，最终 $x$ 会降至 $\le k$，此时 Alice 可以在下一轮直接清零获胜。

---

最终结论

综合以上：

$$\text{结果} = \begin{cases} \text{Alice}, & \text{if } cnt \le k \text{ 或 } n < 2k, \\ \text{Bob}, & \text{otherwise}. \end{cases} $$

等价于：

• 若 $cnt \le k$，Alice 胜。
• 否则，若 $n < 2k$，Alice 胜。
• 否则 Bob 胜。

---

算法步骤

1. 读入 $n, k$ 和字符串 $s$。
2. 统计 $1$ 的个数 $cnt$。
3. 若 $cnt \le k$ 或 $n < 2k$，输出 "Alice"；否则输出 "Bob"。

---

时间复杂度

• 统计 $cnt$：$O(n)$。
• 总复杂度 $O(\sum n) \le 2 \times 10^5$，满足要求。

---

代码实现

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

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    
    int cnt = 0;
    for (char c : s) {
        if (c == '1') cnt++;
    }
    
    if (cnt <= k || n < 2 * k) {
        cout << "Alice\n";
    } else {
        cout << "Bob\n";
    }
}

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

---

验证样例

测试用例	$n$	$k$	$s$	$cnt$	$cnt \le k$	$n < 2k$	结果
1	5	2	11011	4	否	5 < 4? 否	Bob
2	7	4	1011011	5		7 < 8 是	Alice
3	6	1	010000	1	是	—
4			1111	4	否	4 < 2 否	Bob
5	8	3	10110110	5		8 < 6 否
6		4	111111	6		6 < 8 是	Alice

与题目输出一致。

---

总结

本题的关键在于：

1. 若 $1$ 的数量 $\le k$，Alice 直接获胜。
2. 若 $n \ge 2k$，Bob 可以通过保留一个 $1$ 并翻转不包含它的子串，保持 $1$ 的数量 $\ge k+1$，从而获胜。
3. 若 $n < 2k$，Alice 可以每轮净减少 $1$ 的数量，最终获胜。