CF2123D.Binary String Battle

Alice 和 Bob 得到一个长度为 $n$ 的二进制字符串 $s$，以及一个整数 $k$（$1\leq k < n$）。

如果 Alice 能够将 $s$ 的所有字符都变成 $0$，则 Alice 获胜。如果 Alice 无法在有限步内获胜，则 Bob 获胜。

Alice 和 Bob 轮流操作，Alice 先手。

• 在 Alice 的回合，她可以选择 $s$ 中任意一个长度为 $k$ 的子序列 $^{\text{∗}}$，然后将该子序列中的所有字符都变为 $0$。
• 在 Bob 的回合，他可以选择 $s$ 中任意一个长度为 $k$ 的子串 $^{\text{†}}$，然后将该子串中的所有字符都变为 $1$。

注意，只要在游戏过程中（包括 Alice 和 Bob 的回合之间），字符串全部变为 $0$，Alice 就立即获胜。

请判断在双方都采取最优策略的情况下，谁会获胜。

$^{\text{∗}}$ 字符串 $s$ 的子序列是 $s$ 中若干字符组成的集合，这些字符不必相邻。

$^{\text{†}}$ 字符串 $s$ 的子串是 $s$ 中一段连续的字符，这些字符必须相邻。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2\leq n \leq 2\cdot 10^5$，$1\leq k < n$）。

每个测试用例的第二行包含一个长度为 $n$ 的二进制字符串 $s$。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出一行，如果 Alice 能在最优策略下获胜，则输出 "Alice"；否则输出 "Bob"。

输出不区分大小写。例如，"aLiCe"、"alice"、"ALICE" 和 "alICE" 都会被识别为 "Alice"。

在第三个样例中，Alice 可以选择由 $s_2$ 组成的子序列，将 $s$ 变为 $000000$，她立即获胜。

在第四个样例中，可以证明 Alice 无法保证在有限步内将 $s$ 变为 $0000$。

由 ChatGPT 4.1 翻译