526互联

取石子

发布时间 2023-08-08 16:56:34作者: nyliyuzhong

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

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

  1. 从某堆石子中取走一个；
  2. 合并任意两堆石子。

不能操作的人输。

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

输入格式

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

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

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

输出格式

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

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

数据范围

1≤T≤100,
1≤N≤50,
1≤ai≤1000

输入样例：

3
3
1 1 2
2
3 4
3
2 3 5

输出样例：

YES
NO
NO

 

 

 

代码

#include <cstdio>
#include <cstring>
#include<iostream>

using namespace std;

const int N = 55, M = 50050;

int f[N][M];

int dp(int a, int b)
{
int &v = f[a][b];
if (v != -1) return v;
// 简单情况
if (!a) return v = b % 2;
// 一般情况
// 上一次取完后 b中只有1堆 且只有1个石子 b=1+1-1=1 这堆并入a中
if (b == 1) return dp(a + 1, 0);
// 有a 从a中取1个
if (a && !dp(a - 1, b)) return v = 1;
// 有b 从b中取1个 or 合并b中2个
if (b && !dp(a, b - 1)) return v = 1;
// 合并a中2个
if (a >= 2 && !dp(a - 2, b + (b ? 3 : 2))) return v = 1;
// 合并a中1个b中1个
if (a && b && !dp(a - 1, b + 1)) return v = 1;

return v = 0;
}

int main()
{
memset(f, -1, sizeof f);

int T;
cin >> T;
while (T -- )
{
int n;
cin >> n;
int a = 0, b = 0;
for (int i = 0; i < n; i ++ )
{
int x;
cin >> x;
if (x == 1) a ++ ;
// b==0时 加1堆+加x石子=0 + 1+x-1=x
// b!=0时 加1堆+加x石子=原来的+x+1
else b += b ? x + 1 : x;
}

if (dp(a, b)) puts("YES");
else puts("NO");
}

return 0;
}