← 返回题目列表

Codeforces · 2241/F

F. 有点奇怪

中文机器翻译题面 查看原题

Alice 和 Bob 得到了一个二进制 $$$^{\text{*}}$$$ 字符串 $$$s$$$,长度为 $$$n$$$。他们决定在上面玩一个游戏,轮流玩,爱丽丝先走。

在每一步中,玩家必须选择一个 子序列 字符串 $$$y$$$ 的$$$^{\text{†}}$$$ 具有 奇数 反转次数$$$^{\text{‡}}$$$ 并将其删除。无法采取行动的玩家就输了。

假设双方都发挥最佳状态,确定谁赢得了比赛。

$$$^{\text{*}}$$$二进制字符串是仅由字符 $$$\texttt{0}$$$ 和 $$$\texttt{1}$$$ 组成的字符串。

$$$^{\text{†}}$$$序列 $$$a$$$ 是字符串 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得。

$$$^{\text{‡}}$$$二进制字符串 $$$s$$$ 中的反转是一对索引 $$$(i, j)$$$,使得 $$$i \lt j$$$ 和 $$$s_i = \texttt{1}$$$ 和 $$$s_j = \texttt{0}$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。每个测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 二进制字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的二进制字符串$$$s$$$。保证 $$$s$$$ 的每个字符都是 $$$\texttt{0}$$$ 或 $$$\texttt{1}$$$。

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

输出

对于每个测试用例,如果 Alice 赢得了游戏,则打印 $$$\texttt{Alice}$$$,否则打印 $$$\texttt{Bob}$$$。

示例

输入
复制

3
5
10101
4
0100
6
011001

输出
复制

Alice
Alice
Bob

注意

对于第一个测试用例,Alice 可以选择整个字符串,因为它有奇数个反转。现在,鲍勃只剩下一根空弦,他无法采取行动。因此,爱丽丝获胜。

对于第二个测试用例,Alice 可以选择索引 $$$1$$$、$$$2$$$ 和 $$$4$$$ 处的字符形成的子序列,即 $$$\texttt{010}$$$。然后 Bob 留下索引 $$$3$$$ 处的字符,即 $$$\texttt{0}$$$,它有 $$$0$$$ 反转(偶数)。因此,Bob 无法选择具有奇数个反转的子序列,因此 Alice 获胜。

对于第三个测试用例,可以证明无论 Alice 的第一步如何,Bob 都可以保证获胜。