bzoj 3895 取石子

Description

Alice和Bob两个好朋含友又开始玩取石子了。游戏开始时，有N堆石子
排成一排，然后他们轮流操作（Alice先手），每次操作时从下面的规则中任选一个：
·从某堆石子中取走一个
·合并任意两堆石子
不能操作的人输。Alice想知道，她是否能有必胜策略。

Input

第一行输入T，表示数据组数。
对于每组测试数据，第一行读入N。
接下来N个正整数a1，a2…an，表示每堆石子的数量。

Output

对于每组测试数据，输出一行。
输出YES表示Alice有必胜策略，输出NO表示Alice没有必胜策略。

Sample Input

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

Sample Output

YES
NO
NO

HINT

100%的数据满足T<=100, N<=50. ai<=1000

题解

这题我觉得就是瞎搞就可以了。

我们可以通过石子的堆数和每一堆的个数计算出剩余的操作数，显然操作数为奇先手必胜，为偶先手必败。

若将=1的石子堆单独考虑，对于若干堆>1的石子，操作数为$\sum_{i=1}^nx_i$

那么我们可以记f[a][b]表示有a堆=1的石子，>1的石子操作数为b的状态（1表示先手必胜，0表示先手必败），然后进行记搜，对于a!=0的情况分类讨论。

#include <cstdio>
#include <cstring>
using namespace std;
int T,n,x,f[100][51000];
bool dp(int a,int b)
{
    if (!a) return b&1;
    if (b==1) return dp(a+1,0);
    if (f[a][b]!=-1) return f[a][b];
    if (a&&b&&!dp(a-1,b+1)) return f[a][b]=1;
    if (a>=2&&!dp(a-2,b+2+(b?1:0))) return f[a][b]=1;
    if (a&&!dp(a-1,b)) return f[a][b]=1;
    if (b&&!dp(a,b-1)) return f[a][b]=1;
    return f[a][b]=0;
}
main()
{
    scanf("%d",&T);
    memset(f,-1,sizeof(f));
    while (T--)
    {
        scanf("%d",&n);
        int a=0,b=0;
        for (int i=1;i<=n;++i)
        {
            scanf("%d",&x);
            if (x==1) a++;
            else b+=x+1;
        }
        b--;
        puts(dp(a,b)?"YES":"NO");
    }
}