博弈的题目，打表找规律还是相当有用的一个技巧。
这个游戏在原始的Nim游戏基础上又新加了一个操作，就是游戏者可以将一堆分成两堆。
这个SG函数值是多少并不明显，还是用记忆化搜索的方式打个表，规律就相当显然了。
#include <cstdio>
#include <cstring> const int maxn = ;
int sg[maxn * ];
bool vis[maxn * ]; int mex(int v)
{
if(sg[v] != -) return sg[v];
memset(vis, false, sizeof(vis));
for(int i = ; i < v; i++) vis[mex(i)] = true;
for(int i = ; v - i >= i; i++) vis[mex(i) ^ mex(v - i)] = true;
for(int i = ; ; i++) if(!vis[i]) { sg[v] = i; return i; }
} int main()
{
memset(sg, -, sizeof(sg));
sg[] = ;
for(int i = ; i < maxn; i++)
printf("%d %d\n", i, mex(i)); return ;
}
打表
#include <cstdio> inline long long SG(long long x)
{
if(x == ) return ;
if(x % == ) return x + ;
if(x % == ) return x - ;
return x;
} int main()
{
//freopen("in.txt", "r", stdin); int T; scanf("%d", &T);
while(T--)
{
int n; scanf("%d", &n);
long long ans = , x;
for(int i = ; i < n; i++)
{
scanf("%lld", &x);
ans ^= SG(x);
}
printf("%s\n", ans ? "Alice" : "Bob");
} return ;
}
代码君