AT_arc163_e [ARC163E] Chmin XOR Game

题目描述

Alice 和 Bob 用一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots,A_N)$ 进行游戏。

两人轮流操作，从 Alice 开始。无法继续操作的人判负。

• 选择一个非负整数 $X$，使得存在某个整数 $i$ 满足 $A_i > A_i \oplus X$。
• 对于所有 $1 \le i \le N$，用 $\min(A_i, A_i \oplus X)$ 替换 $A_i$。

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

其中，$\oplus$ 表示按位异或运算。

给定 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入通过标准输入给出，格式如下：

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

其中，第 $i$ 个测试用例如下格式：

$N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出 $T$ 行。

第 $i$ 行输出第 $i$ 个测试用例的结果。如果 Alice 获胜，输出 Alice；如果 Bob 获胜，输出 Bob。

样例 1

输入

5
2
3 1
5
1 1 1 1 1
4
0 0 0 0
4
8 1 6 4
5
3 8 7 12 15

输出

Bob
Alice
Bob
Bob
Alice

说明/提示

数据范围

• $1 \le T \le 100$
• $1 \le N \le 100$
• $0 \le A_i \le 10^9$

样例解释 1

第 1 个测试用例，可能的游戏过程如下：

• Alice 选择 $X=3$。对于 $i=1$，有 $3 > 3 \oplus 3 (=0)$，因此该选择有效。
• $A=(3,1)$ 变为 $A=(0,1)$。
• Bob 选择 $X=1$。对于 $i=2$，有 $1 > 1 \oplus 1 (=0)$，因此该选择有效。
• $A=(0,1)$ 变为 $A=(0,0)$。
• Alice 无法再选择合适的 $X$，游戏结束。

此时 Bob 获胜。

第 2 个测试用例，可能的游戏过程如下：

• Alice 选择 $X=1$。对于 $i=1$，有 $1 > 1 \oplus 1 (=0)$，因此该选择有效。
• $A=(1,1,1,1,1)$ 变为 $A=(0,0,0,0,0)$。
• Bob 无法再选择合适的 $X$，游戏结束。

此时 Alice 获胜。

由 ChatGPT 4.1 翻译