题目链接:https://vjudge.net/contest/299140#problem/G
题目大意:
爱丽丝和鲍勃在玩一个奇怪的游戏。游戏规则是:

1 最初有N堆石头。
2 在每轮游戏中,玩家可以选择任何一堆石头,并将其分成石头个数不相等的两堆。
5 如果玩家不能这样做,他/她将输掉比赛。

艾丽斯开始比赛,他们轮流交替。

输入
输入以整数t(≤1000)开始,表示测试用例的数量。
每种情况都以包含整数n(1≤n≤100)开始。下一行包含n个整数,其中第i个整数表示第i堆中的单元数。您可以假定每堆中的单元数在1到10000之间。

输出
对于每个案例,打印案例编号和“Alice”或“Bob”,具体取决于游戏的获胜者。

思路:直接sg函数。根据sg定理:

当前状态的SG函数等于各个子状态SG函数的异或和
sg[0]=0
sg[1]=0
sg[2]=0
sg[3]=mex{sg[1, 2], s[2, 1]}={sg[1]^s[2]}
//因为[1, 2]和[2, 1]状态重复。
所以只枚举一个状态就可以了
......................

直接枚举分成2堆时的分法就行了求出sg函数就行了。这里必须递推,递归一直RE。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

int sg[10010];
bool vis[20010];

int get_sg(int len)
{
    for(int i=3;i<=len;i++)
    {
        memset(vis, 0, sizeof(vis));
        for(int j=1;j*2<i;j++)//只枚举一个状态
        {
            vis[sg[j]^sg[i-j]]=true;
        }
        for(int j=0;j<20010;j++)//求mex
        {
            if(!vis[j])
            {
                sg[i]=j;
                break;
            }
        }
    }
}

int main()
{
    int t, CUT=0;
    memset(sg, -1, sizeof(sg));
    sg[1]=sg[2]=0;
    get_sg(10000);
    scanf("%d",&t);
    while(t--)
    {
        CUT++;
        int n, ans=0, a;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a);
            ans^=sg[a];
        }
        if(ans)
        {
            printf("Case %d: Alice\n",CUT);
        }
        else
        {
            printf("Case %d: Bob\n",CUT);
        }
    }

    return 0;
}