题意:链接方法: SG函数，SG表?解析:这题的题意给你构建的情况就已经非常的好了。N个棋子之间互不影响，代表着N个局面互不影响。然后呢，每个局面的棋子能走的点都是这个局面的子游戏，将所有的子游戏进行mex运算就能得到每个局面的sg值。但是发现这样打出来的sg表是错误的，因为我们没有考虑一些必败态。经画图分析等发现，如果先手先走，走到了点(x,y)如果走到了x==y||x==0||y==0的情况，那么先手直接GG。显然先手是不会这么走的，则所有的人除非在不得已的情况下才会走这些点。所以我们不妨把他们的sg值赋0。这些点是不会存在于这个游戏中的，，除非初始棋子在这些点上。考虑了这些条件就OK了。代码:;int t,n;int ssgg[M][M];struct node{int x,y;}pt[N];int sg(int x,int y){if(x==0||y==0)return 0;if(x==y)return ssgg[x][y]=0;if(ssgg[x][y]!=-1)return ssgg[x][y];bool v[10010];memset(v,0,sizeof(v));for(int k=1;;k++){if(x-k<=0&&y-k<=0)break;if(x-k>0&&x-k!=y)v[sg(x-k,y)]=1;if(y-k>0&&y-k!=x)v[sg(x,y-k)]=1;if(x-k>0&&y-k>0)v[sg(x-k,y-k)]=1;}for(int i=0;;i++)if(!v[i])return ssgg[x][y]=ssgg[y][x]=i;}int main(){scanf(“%d”,&t);memset(ssgg,-1,sizeof(ssgg));while(t–){scanf(“%d”,&n);int flag=0;for(int i=1;i<=n;i++){scanf(“%d%d”,&pt[i].x,&pt[i].y);if(pt[i].x==0||pt[i].y==0||pt[i].x==pt[i].y)flag=1;}if(flag){puts(“^o^”);continue;}int ans=0;for(int i=1;i<=n;i++){ans^=sg(pt[i].x,pt[i].y);}if(ans==0)puts(“T_T”);else puts(“^o^”);}}
版权声明：本文为博主原创文章，未经博主允许不得转载。
那么，不如我们礼貌地保持相对距离，不至于太冷，不至于太痛。
