← 返回题目列表

AtCoder · pakencamp_2024_day3_1_h

H. 大型异或游戏

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

配点 : 100 点

問題文

N 整数。i 第二张牌有 A_i 。

爱丽丝和鲍勃 使用 N 卡玩游戏。最初,所有卡片都堆在一起。让爱丽丝先玩,轮流重复以下步骤,直到牌堆中没有牌为止。

  • 卡片堆中 1 选择一张牌,将其从牌堆中取出,并将其置于你的手上。

最后,分数是你手上所有牌上写的整数的异或。得分较高的人获胜。如果分数相同,则视为平局。

如果双方表现最优,则判断是否打平,如果不打平,则判定谁胜。

Q 会给出若干测试用例,请针对每个测试用例求出答案。

什么是异或? 整数 a, b 的异或 a \oplus b 定义如下。 当
  • a \oplus b 以二进制表示法 2^k \, (k \geq 0) 中的位数为a, b 以二进制表示法 2^k 数字中只有一位是 1 如果 1,否则 输出为 0 。
例如,3 \oplus 5 = 6 (以二进制表示法 排序到 011 \oplus 101 = 110)。
一般 k 整数 给出了 p_1, \dots, p_k 的异或是 (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) ,即 可以证明 p_1, \dots, p_k 不依赖于顺序。
“最佳行动”是什么意思?

“表现最佳”是指按照以下方式行事。

  • 如果无论对手如何行动都有可能让自己获胜,那么就以能让自己获胜的方式行动。
  • 另一方面,如果无论对方如何行动,都可以防止自己失败,那么自己就会以不会失败的方式行事。
  • 否则,随机执行该操作。

制約

  • 1 \leq Q \leq 2 \times 10^{5}
  • 1 \leq N \leq 2 \times 10^{5} (1 \leq i \leq N)
  • 0 \leq A_i \leq 10^{18} (1 \leq i \leq N)
  • N 的总和是 2 \times 10^{5} 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

Q
case_{1}
case_{2}
\vdots
case_{Q}

在这里,case_{i} 是 您也可以写 i 个测试用例。

每个测试用例均按以下格式给出。 打印

N
A_{1} A_{2} \ldots A_{N}

出力

对于每个测试用例,如果结果是平局, Draw 如果爱丽丝赢了 Alice 如果鲍勃获胜 输出 Bob 。 在第


入力例 1

3
1
1
2
100 100
3
20090926 20250401 33550336

出力例 1

Alice
Draw
Bob

1 测试用例可以考虑以下操作。

爱丽丝 将 1 卡放入你的手牌。爱丽丝的分数是 在 1 中,Bob 的分数是 0 爱丽丝获胜。 将

2 测试用例可以考虑以下操作。

爱丽丝 将 100 卡放入你的手牌。接下来,鲍勃 100 卡放入你的手牌。爱丽丝的分数是 在 100 中,Bob 的分数是 100 ,结果是平局。