CF1472D Even-Odd Game

在新年假期期间，Alice 和 Bob 玩如下游戏，使用一个包含 $n$ 个整数的数组 $a$： - 两位玩家轮流操作，Alice 先手。 - 每一回合，玩家可以选择数组中的任意一个元素并将其移除。 - 如果 Alice 选择的是偶数，那么她将该数加到自己的得分中。如果选择的是奇数，Alice 的得分不变。 - 同理，如果 Bob 选择的是奇数，那么他将该数加到自己的得分中。如果选择的是偶数，Bob 的得分不变。 当数组中没有剩余数字时，游戏结束。得分较高的玩家获胜。如果两位玩家得分相等，则判为平局。 例如，如果 $n=4$，$a=[5,2,7,3]$，游戏可能如下进行（也有其他可能）： - 第一步，Alice 选择 $2$ 并获得 $2$ 分。她的得分现在是 $2$。数组 $a$ 变为 $[5,7,3]$。 - 第二步，Bob 选择 $5$ 并获得 $5$ 分。他的得分现在是 $5$。数组 $a$ 变为 $[7,3]$。 - 第三步，Alice 选择 $7$，得分不变。她的得分仍为 $2$。数组 $a$ 变为 $[3]$。 - 最后一步，Bob 选择 $3$ 并获得 $3$ 分。他的得分现在是 $8$。数组 $a$ 为空。 - 最终，Bob 的得分更高，因此他获胜。 你需要判断，如果两位玩家都采取最优策略，谁将获胜。注意，数组中可能有重复数字。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的元素个数。 下一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示用于游戏的数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行： - 如果 Alice 在最优策略下获胜，输出 "Alice"； - 如果 Bob 在最优策略下获胜，输出 "Bob"； - 如果最优策略下平局，输出 "Tie"。

由 ChatGPT 4.1 翻译