1.light oj 1296 :传送门
规则,n堆，每次可以从一堆取1到n/2个。
分析：
打表找sg规律，发现
if n&1 sg(x)=sg(x/2);
else sg(x)=x/2;
代码如下：
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 1000;/*打表。。。int sg[maxn];int get_sg(int x){if(sg[x]!=-1) return sg[x];int vis[maxn];memset( vis,0,sizeof(vis));for(int i=1;i<=x/2;i++)vis[get_sg(x-i)]=1;for(int i=0;;i++){if(!vis[i])return sg[x]=i;}}void init(){memset(sg,-1,sizeof(sg));sg[0]=1;for(int i=1;i<maxn;i++) sg[i]=get_sg(i);}*/int get_sg(int x){if(x&1) return get_sg(x>>1);else return x>>1;}int main(){int t,n,x,cas=1;scanf("%d",&t);while(t–){scanf("%d",&n);int ans = 0;for(int i=0;i<n;i++){scanf("%d",&x);ans^=get_sg(x);}printf("Case %d: ",cas++);if(!ans) puts("Bob");else puts("Alice");}return 0;}
2.light oj 1199 传送门
规则：
n堆石头，每次可以把其中的一堆分为数目不相等的两堆，谁不能移则输。
分析：
每次的操作是相互独立的，，
则sg[x] = mex(sg[1]^sg[x-1],sg[2]^sg[x-2],…,sg[(x-1)/2]^sg[x-(x-1)/2]);
代码如下：
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 1e4+10;int sg[maxn];int get_sg(int x){if(sg[x]!=-1) return sg[x];int vis[maxn];memset(vis,0,sizeof(vis));int half = x/2 – (x%2==0);for(int i=1;i<=half;i++)vis[get_sg(x-i)^get_sg(i)]=1;for(int i=0;;i++){if(!vis[i]) return sg[x]=i;}}void init(){memset(sg,-1,sizeof(sg));sg[0]=0;sg[1]=0;sg[2]=0;for(int i=1;i<maxn;i++)sg[i]=get_sg(i);}int main(){init();int n,x,t,cas=1;scanf("%d",&t);while(t–){scanf("%d",&n);int ans = 0;for(int i=0;i<n;i++){scanf("%d",&x);ans^=sg[x];}printf("Case %d: ",cas++);if(!ans) puts("Bob");else puts("Alice");}return 0;}
3.lightoj 1253 传送门
分析
当n个数不全都是1时就是nim；
否者判断n的奇偶性
代码如下：
#include <cstdio>int main(){int j,i,t,n,x,res;bool flag;scanf("%d",&t);for(j=1;j<=t;++j){res=0;flag=true;scanf("%d",&n);for(i=0;i<n;++i){scanf("%d",&x);if(x!=1) flag=false;res=res^x;}if(flag&&n%2||!flag&&res==0) printf("Case %d: Bob\n",j);else printf("Case %d: Alice\n",j);}return 0;}
你可以很有个性，但某些时候请收敛。
