题目描述

Alice 和 Bob 两个好朋友又开始玩取石子了。

游戏开始时，有 N 堆石子排成一排，然后他们轮流操作（Alice 先手），每次操作时从下面的规则中任选一个：

从某堆石子中取走一个；
合并任意两堆石子。
不能操作的人输。

Alice 想知道，她是否能有必胜策略。

输入格式
第一行输入 T，表示数据组数。

对于每组测试数据，第一行读入 N；

接下来 N 个正整数 a1,a2,⋯,aN ，表示每堆石子的数量。

输出格式
对于每组测试数据，输出一行。

输出 YES 表示 Alice 有必胜策略，输出 NO 表示 Alice 没有必胜策略。

数据范围
1≤T≤100,
1≤N≤50,
1≤ai≤1000

算法1

(数学) $O(1)$

这道题先是课上听了记忆化搜索，然后一直觉得搜索时是有问题的，有一类情况没有考虑到。就是B类 REMOVE石头的时候，其中一个为2. 此时应该A+1, B-3的。但是代码里只要考虑B-1，A不变的非2情况。一直想为什么不用加这个可能也是对的，分析了3个小时在没分析出来，希望有大佬日后看到可以给我解答。

不过发现了下述性质

首先把所有石子堆分为2类。一类是只有1个石头的堆。一类是>1个石头的堆。
我们维护有1个石头的堆的堆数，ONES。维护>1个石头的堆 SUM数 为 石子总数+堆数-1， OTHERS。

假设第二类的OTHERS <=2 （即要么全是第一类，要么第二类就一个2个石头的堆）。我们可以枚举发现，有3个1 是先手必输的， 6个1 是必输的。 3 * k 个1 都是必输的（可数学归纳）

if (others <= 2) {
    System.out.println(ones % 3 == 0 ? "NO": "YES");
} 

我们还可以证明如果没有第一类。 OTHERS为奇数则先手必胜。（算法提高课已证）

下面就是考虑既有第一类 又有第二类，且第二类OTHERS > 2的情况。

先说结论

else {
    System.out.println((ones % 2 == 1 || others % 2 == 1) ? "YES" : "NO");
}

可以证明第一类石子的堆数为偶数并且第二类SUM数为偶数则先手必败。
最小情况， OTHERS = 4 ，ONES = 0; （根据算法提高课的证明，OTHERS += 2 依然为偶数，则还是必败）
如果ONES += 2；
先手有几种选择。

1. （移除第一类石堆）ONES - -. 那么后手可以通过再一次ONES– 使得 ONES 回到之前已证的必败态。

2. （第一类石堆和第二类石堆合并）ONES - -, OTHERS++。 那么后手可以通过再一次该操作回到ONES = 0, OTHERS=偶数+2的已证必败态。

3. （2个第一类合并）ONES-=2, OTHERS += 3. 那么后手可以对第二类做基本操作（合并或者移除非2的石堆，因为OTHERS >=4必然可以找到这个操作）使得OTHERS–。 回到双偶数的必败态。

4. （第二类的基本操作） OTHERS- -。那么后手就要分情况讨论。
   4.1 OTHERS == 3, 那么后手就合并2个第一类，得到ONES = 0, OTHER=6的情况，回到已证必败态。
   4.2 OTHERS != 3 ， 那么后手就用第二类基本操作，使得OTHERS–， 回到之前 OTHERS >= 4, ONES = 2 的更小的双偶必败态。

递推得证。

同理如果先手看到的局面是这2个数里至少有一个是奇数的，他只要给通过一种方式给后手构造出一种双偶数的局面，他就可以保持自己必胜。
1. ONES 为奇， OTHERS 为奇，使用ONES MERGE 进OTHERS， ONES–, OTHERS++. 变成双偶数
2. ONES 为奇， OTHERS 为偶，使用REMOVE ONES STONE， ONES–。 变成双偶数
3. ONES 为偶， OTHERS为奇，使用OTHERS基本操作，OTHERS–。 变成双偶数。

由上述可以得知一旦拿到双偶数，则任何操作都是必败。可以证明在有第一类 又有第二类，且第二类OTHERS > 2的情况，先手2个数有一个为奇数 则必胜。

时间复杂度 O(1)

JAVA 代码

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int ones = 0, others = -1;
            for (int i = 0; i < n; i++) {
                int x = sc.nextInt();
                if (x == 1) ones++;
                else others += x + 1;
            }
            if (others <= 2) {
                System.out.println(ones % 3 == 0 ? "NO": "YES");
            } else {
                System.out.println((ones % 2 == 1 || others % 2 == 1) ? "YES" : "NO");
            }
        }
    }
}