hdu 3032 sg打表找规律 *

时间：2022-06-17 20:46:50

有n堆石子，alice先取，每次可以选择拿走一堆石子中的1~x(该堆石子总数) ，也可以选择将这堆石子分成任意的两堆。alice与bob轮流取，取走最后一个石子的人胜利。

打表代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 const int N=;

 int sg[N];

 //注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍

 //n是集合s的大小 S[i]是定义的特殊取法规则的数组

 int s[];

 int SG_dfs(int x)

 {

     int i;

     if(sg[x]!=-)

         return sg[x];

     bool vis[];

     memset(vis,,sizeof(vis));

     for(int i=x-;i>=;i--)     //第一种取法

         vis[SG_dfs(i)]=;

     for(i=;i<=x/;i++)     //分开取法

     {

         int ans=;

         ans^=SG_dfs(i);

         ans^=SG_dfs(x-i);

         vis[ans]=;

     }

     int e;

     for(i=;;i++)

         if(!vis[i])

         {

             e=i;

             break;

         }

     return sg[x]=e;

 }

 int main()

 {

     int t,n;

     scanf("%d",&t);

     memset(sg,-,sizeof(sg));

     while(t--)

     {

         scanf("%d",&n);

         int x;

         for(int i=;i<n;i++)

         {

             scanf("%d",&x);

             SG_dfs(x);

             printf("sg[%d]=%d\n",x,sg[x]);

         }

         for(int i=;i<=;i++){

             printf("%d: %d\n",i,sg[i]);

             //if(i%10==0)

                 //system("pause");

         }

         printf("\n");

     }

     return ;

 }

之后异或一下即可，2333

相关文章