http://acm.hdu.edu.cn/showproblem.php?pid=3980
这题简单题,但是还是脑残的wa了好几次,把珠子看成是石子,每次取完后都会有两个石子堆得子局面,这两个子局面取异或和,然后求sg值即可
#include <iostream> #include <cstdio> #include <cstring> using namespace std; int n,m; int sg[1010]; int get_sg(int len) { if(len<=0) return 0; if(sg[len]!=-1) return sg[len]; bool vis[1010]={0}; for(int i=1;i+m-1<=len;i++) { int a=get_sg(i-1); int b=get_sg(len-m-i+1); vis[a^b]=1; } for(int i=0;;i++) if(!vis[i]) return sg[len]=i; } int main() { int ca,cas=1; scanf("%d",&ca); while(ca--) { scanf("%d %d",&n,&m); printf("Case #%d: ",cas++); if(m==1) { if(n&1) puts("aekdycoin"); else puts("abcdxyzk"); continue; } memset(sg,-1,sizeof(sg)); if(n>=m&&(!get_sg(n-m))) printf("aekdycoin\n"); else printf("abcdxyzk\n"); } return 1; }