Swap Game

题意翻译

Alice 和 Bob 两个人在玩游戏。 有一个长度为 $n$ 的序列 $a$，Alice 和 Bob 两人轮流完成一个操作，Alice 先开始。 每个人可以将数列的第一个数减 $1$，并将它与后面序列的一个数进行交换，如果一个人操作之前发现当前序列中的第一个数为 $0$，这个人就输了。 问如果两人都足够聪明，最后谁会赢？ 输入输出格式及数据规模见原题面。 Translated by @[CLCK](https://www.luogu.com.cn/user/323183)

题目描述

Alice and Bob are playing a game on an array $ a $ of $ n $ positive integers. Alice and Bob make alternating moves with Alice going first. In his/her turn, the player makes the following move: - If $ a_1 = 0 $ , the player loses the game, otherwise: - Player chooses some $ i $ with $ 2\le i \le n $ . Then player decreases the value of $ a_1 $ by $ 1 $ and swaps $ a_1 $ with $ a_i $ . Determine the winner of the game if both players play optimally.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ $ (1 \leq t \leq 2 \cdot 10^4) $ — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ $ (2 \leq n \leq 10^5) $ — the length of the array $ a $ . The second line of each test case contains $ n $ integers $ a_1,a_2 \ldots a_n $ $ (1 \leq a_i \leq 10^9) $ — the elements of the array $ a $ . It is guaranteed that sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, if Alice will win the game, output "Alice". Otherwise, output "Bob". You can output each letter in any case. For example, "alIcE", "Alice", "alice" will all be considered identical.

输入输出样例

输入样例 #1

3
2
1 1
2
2 1
3
5 4 4

输出样例 #1

Bob
Alice
Alice

说明

In the first testcase, in her turn, Alice can only choose $ i = 2 $ , making the array equal $ [1, 0] $ . Then Bob, in his turn, will also choose $ i = 2 $ and make the array equal $ [0, 0] $ . As $ a_1 = 0 $ , Alice loses. In the second testcase, once again, players can only choose $ i = 2 $ . Then the array will change as follows: $ [2, 1] \to [1, 1] \to [1, 0] \to [0, 0] $ , and Bob loses. In the third testcase, we can show that Alice has a winning strategy.

题目大意：
Alice 和 Bob 在玩一个游戏。游戏在一个由 n 个正整数组成的数组 a 上进行。Alice 和 Bob 交替进行操作，Alice 先开始。每次操作，玩家可以将数组的第一个元素减 1，然后与数组中的任意一个其他元素交换位置。如果在进行操作前数组的第一个元素已经是 0，那么这个玩家就输了。要求判断如果两人都采取最优策略，最终谁会赢。

输入输出数据格式：
输入包括多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 2 × 10^4）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 10^5）——数组 a 的长度。
每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 10^9）——数组 a 的元素。
所有测试用例的 n 之和不超过 2 × 10^5。

对于每个测试用例，如果 Alice 会赢得游戏，输出 "Alice"。否则，输出 "Bob"。
输出时每个字母的大小写不限，例如 "alIcE"、"Alice"、"alice" 都会被认为是相同的。

输入输出样例：
输入样例 #1
```
3
2
1 1
2
2 1
3
5 4 4
```
输出样例 #1
```
Bob
Alice
Alice
```
说明：
在第一个测试用例中，Alice 只能选择 i = 2，使得数组变为 [1, 0]。然后 Bob 也会选择 i = 2，使得数组变为 [0, 0]。因为 a_1 = 0，Alice 输了。
在第二个测试用例中，玩家只能选择 i = 2。数组的变化如下：[2, 1] → [1, 1] → [1, 0] → [0, 0]，Bob 输了。
在第三个测试用例中，可以证明 Alice 有必胜策略。题目大意： Alice 和 Bob 在玩一个游戏。游戏在一个由 n 个正整数组成的数组 a 上进行。Alice 和 Bob 交替进行操作，Alice 先开始。每次操作，玩家可以将数组的第一个元素减 1，然后与数组中的任意一个其他元素交换位置。如果在进行操作前数组的第一个元素已经是 0，那么这个玩家就输了。要求判断如果两人都采取最优策略，最终谁会赢。 输入输出数据格式： 输入包括多个测试用例。第一行包含一个整数 t（1 ≤ t ≤ 2 × 10^4）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 n（2 ≤ n ≤ 10^5）——数组 a 的长度。 每个测试用例的第二行包含 n 个整数 a_1, a_2, ..., a_n（1 ≤ a_i ≤ 10^9）——数组 a 的元素。 所有测试用例的 n 之和不超过 2 × 10^5。 对于每个测试用例，如果 Alice 会赢得游戏，输出 "Alice"。否则，输出 "Bob"。 输出时每个字母的大小写不限，例如 "alIcE"、"Alice"、"alice" 都会被认为是相同的。 输入输出样例： 输入样例 #1 ``` 3 2 1 1 2 2 1 3 5 4 4 ``` 输出样例 #1 ``` Bob Alice Alice ``` 说明： 在第一个测试用例中，Alice 只能选择 i = 2，使得数组变为 [1, 0]。然后 Bob 也会选择 i = 2，使得数组变为 [0, 0]。因为 a_1 = 0，Alice 输了。 在第二个测试用例中，玩家只能选择 i = 2。数组的变化如下：[2, 1] → [1, 1] → [1, 0] → [0, 0]，Bob 输了。 在第三个测试用例中，可以证明 Alice 有必胜策略。