题意:有N堆石子，每堆有s[i]个，Alice和Bob两人轮流取石子，可以从一堆中取任意多的石子，也可以把一堆石子分成两小堆
Alice先取，问谁能获胜
思路：首先观察这道题的数据范围 1 ≤ N ≤ 10^6, 1 ≤ 【Si】 ≤ 2^31 - 1，很明显数据量太大，所以只能通过打表找规律
打表后发现，如果x%4==0 sg[x]=x-1 ;如果 x%4==3 sg[x]=x+1;如果 其他情况 sg[x]=x;
代码：
打表代码：
#include <iostream>
#include <cstring>
using namespace std; int sg[]; int get(int n)
{
if(n<) return ;
if(sg[n]!=-) return sg[n];
bool visit[];
memset(visit,false,sizeof(visit));
for(int i=;i<=n/;i++)
visit[get(i)^get(n-i)]=true;
for(int i=;i<=n;i++)
{
visit[get(n-i)]=true;
}
int k;
for(int i=;i<=;i++)
{
if(visit[i]==false)
{
return sg[n]=i;
}
}
} int main()
{
memset(sg,-,sizeof(sg));
sg[]=;sg[]=;
for(int i=;i<=;i++)
{
get(i);
}
for(int i=;i<=;i++)
cout<<i<<" "<<sg[i]<<endl;
return ;
}
AC代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int main()
{
int t;
cin>>t;
while(t--)
{
int n,x,ans=;
cin>>n;
for(int i=;i<=n;i++)
{
scanf("%d",&x);
if(x%==)
ans=ans^(x-);
else if(x%==)
ans=ans^(x+);
else
ans=ans^x;
}
if(ans)
cout<<"Alice"<<endl;
else
cout<<"Bob"<<endl;
}
return ;
}