AT_arc208_a.[ARC208A] Bitwise OR Game

普及+/提高

通过率:0%

AC君温馨提醒

该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

有 NN 堆石子,第 i(1≤i≤N)i(1\le i\le N) 堆有 AiA_i 颗石子。

Alice 和 Bob 将用这些石子玩如下的游戏:

  • 从 Alice 开始,两名玩家轮流进行操作。
  • 每当一个玩家进行操作时,他需要选择一个非空石堆,并从其中移出一个或更多石子。操作的玩家操作时不能改变所有石堆石子个数的按位 OR\text{OR}。

首先不能操作的玩家输。

两名玩家都使用最佳策略,求哪名玩家获胜。

有 TT 组数据,你需要分别求解。

::::info[什么是按位 OR\text{OR}?]
非负整数 A,BA,B 的按位 OR\text{OR},AOR⁡BA\operatorname{OR}B,定义如下:

  • 将 AOR⁡BA\operatorname{OR}B 以二进制形式写出,2k(k≥0)2^k(k\ge 0) 处的二进制位上为 11 当且仅当 A,BA,B 的二进制形式的 2k2^k 处中至少一个为 11,否则为 00。

例如,3OR⁡5=73\operatorname{OR}5=7(二进制下为 011OR⁡101=111011\operatorname{OR}101=111)。
一般地,kk 个非负整数 p1,p2,p3,⋯ ,pkp_1,p_2,p_3,\cdots,p_k 的按位 OR\text{OR} 定义为 (⋯((p1OR⁡p2)OR⁡p3)OR⁡⋯OR⁡⋯pk)(\cdots((p_1\operatorname{OR}p_2)\operatorname{OR}p_3)\operatorname{OR}\cdots\operatorname{OR}\cdots p_k),可以证明它的值和 p1,p2,p3,⋯ ,pkp_1,p_2,p_3,\cdots,p_k 的顺序无关。
::::

输入格式

第一行一个整数 TT,表示数据组数。

对于每组数据,第一行一个整数 NN。

第二行 NN 个整数 A1,A2,⋯ ,ANA_1,A_2,\cdots,A_N。

输出格式

对于每组数据,如果 Alice 获胜则输出一行 Alice,如果 Bob 获胜则输出一行 Bob。

输入输出样例

  • 输入#1

    4
    3
    3 4 6
    3
    7 7 7
    3
    9 3 5
    10
    1 9 1 3 7 9 10 9 7 3

    输出#1

    Alice
    Bob
    Bob
    Alice

说明/提示

数据范围

  • 1≤T≤1051\le T\le 10^5
  • 2≤N≤2×1052\le N\le 2\times 10^5
  • NN 的和最大为 2×1052\times 10^5。
  • 1≤Ai≤1091\le A_i\le 10^9
  • 所有输入值均为整数。

样例解释

对于第一组数据:

初始时,所有石堆石子个数的按位 OR\text{OR} 为 3OR⁡4OR⁡6=73\operatorname{OR}4\operatorname{OR}6=7。

Alice 可以执行的操作如下:

  • 从第一堆中移出两颗石子。
  • 从第二堆中移出一颗或更多石子。
  • 从第三堆中移出一颗或更多石子。

如果 Alice 从第一堆中移出一颗石子,所有石堆石子个数的按位 OR\text{OR} 将变为 2OR⁡4OR⁡6=62\operatorname{OR}4\operatorname{OR}6=6。因此,Alice 不能执行此操作。

如果 Alice 从第三堆中取出六颗石子,Bob 在下一步中将无法执行任何操作。因此,两名玩家都执行最优策略时的赢家是 Alice。

由 @chenxi2009 翻译。

输入解题思路,AI测评打分。不知道怎么写?

首页