题解

思路

具体数值只通过奇偶性影响 Alice 的和。设奇数有 $o$ 个、偶数有 $e$ 个。完整博弈可按 $o\bmod4$ 分类，偶数只在余数为 1 时通过回合节奏影响结果。

做法

统计 $o,e$：

• $o\bmod4=0$ 或 $3$：Alice 获胜；
• $o\bmod4=2$：Bob 获胜；
• $o\bmod4=1$：当且仅当 $e$ 为奇数时 Alice 获胜。

按结果输出 Alice 或 Bob。

正确性证明

双方取偶数不会改变 Alice 和的奇偶，只会改变轮次；取奇数时，只有 Alice 取到的奇数数量会翻转她的和。

把奇数按每四个一组考虑，双方各取两个，Alice 取得的奇数数量增加 2，胜负状态不变。因此只需讨论剩余 $0,1,2,3$ 个奇数。直接进行极小规模博弈：剩 0 个时 Alice 的奇数数为偶；剩 3 个时 Alice 可保证取得 0 或 2 个；剩 2 个时 Bob 可迫使 Alice 取得 1 个；剩 1 个时，偶数回合数量为奇数才可让 Bob 取走该奇数。恰得到上述四类条件，故判定正确。

复杂度分析

每组测试只需统计奇偶，时间复杂度为 $O(n)$，额外空间复杂度为 $O(1)$。

子任务说明

• $n\le16$ 时展开完整极大极小游戏树。
• 全为奇数时 Alice 恰取 $\lceil n/2\rceil$ 个数，直接判断其奇偶。
• 满数据使用奇偶计数分类。