C++(clang++11) 解法, 执行用时: 30ms, 内存消耗: 4072K, 提交时间: 2020-12-01 11:34:26

#include<bits/stdc++.h>
using namespace std;
int t,n,a,x,y;
bitset<501201>f[51],vis[51];
bool dfs(int x,int y){
	if(x==0&&y==0)return 0;
	if(y==1)x++,y=0;
	if(!vis[x][y]){
		if(x){
			f[x][y]=!dfs(x-1,y);
			if(y)f[x][y]=f[x][y]||!dfs(x-1,y+1);
			if(x>1)f[x][y]=f[x][y]||!dfs(x-2,y+(bool)y+2);
		}if(y)f[x][y]=f[x][y]||!dfs(x,y-1);
		vis[x][y]=true;
	}return f[x][y];
}int main(){
	for(scanf("%d",&t);t--;){
		x=y=0,scanf("%d",&n);
		while(n--){
			scanf("%d",&a);
			if(a==1)x++;
			else y+=(bool)y+a;
		}puts(dfs(x,y)?"YES":"NO");
	}return 0;
}

Python3 解法, 执行用时: 119ms, 内存消耗: 4624K, 提交时间: 2022-11-21 17:33:37

t = int(input())
for i in range(t):
    n = int(input())
    A = [*map(int, input().split())]
    a = A.count(1)
    b = n + sum(A) - 2 * a - 1
    if b<=2:
        if a%3:
            print("YES")
        else:
            print("NO")
    else:
        if a%2==1 or b%2==1:
            print("YES")
        else:
            print("NO")