AT_arc208_a.[ARC208A] Bitwise OR Game
普及+/提高
通过率:0%
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
有 N 堆石子,第 i(1≤i≤N) 堆有 Ai 颗石子。
Alice 和 Bob 将用这些石子玩如下的游戏:
- 从 Alice 开始,两名玩家轮流进行操作。
- 每当一个玩家进行操作时,他需要选择一个非空石堆,并从其中移出一个或更多石子。操作的玩家操作时不能改变所有石堆石子个数的按位 OR。
首先不能操作的玩家输。
两名玩家都使用最佳策略,求哪名玩家获胜。
有 T 组数据,你需要分别求解。
::::info[什么是按位 OR?]
非负整数 A,B 的按位 OR,AORB,定义如下:
- 将 AORB 以二进制形式写出,2k(k≥0) 处的二进制位上为 1 当且仅当 A,B 的二进制形式的 2k 处中至少一个为 1,否则为 0。
例如,3OR5=7(二进制下为 011OR101=111)。
一般地,k 个非负整数 p1,p2,p3,⋯,pk 的按位 OR 定义为 (⋯((p1ORp2)ORp3)OR⋯OR⋯pk),可以证明它的值和 p1,p2,p3,⋯,pk 的顺序无关。
::::
输入格式
第一行一个整数 T,表示数据组数。
对于每组数据,第一行一个整数 N。
第二行 N 个整数 A1,A2,⋯,AN。
输出格式
对于每组数据,如果 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≤105
- 2≤N≤2×105
- N 的和最大为 2×105。
- 1≤Ai≤109
- 所有输入值均为整数。
样例解释
对于第一组数据:
初始时,所有石堆石子个数的按位 OR 为 3OR4OR6=7。
Alice 可以执行的操作如下:
- 从第一堆中移出两颗石子。
- 从第二堆中移出一颗或更多石子。
- 从第三堆中移出一颗或更多石子。
如果 Alice 从第一堆中移出一颗石子,所有石堆石子个数的按位 OR 将变为 2OR4OR6=6。因此,Alice 不能执行此操作。
如果 Alice 从第三堆中取出六颗石子,Bob 在下一步中将无法执行任何操作。因此,两名玩家都执行最优策略时的赢家是 Alice。
由 @chenxi2009 翻译。
输入解题思路,AI测评打分。不知道怎么写?