HDU 1404 (博弈) Digital Deletions

时间：2021-11-06 16:17:45

首先如果第一个数字是0的话，那么先手必胜。

对于一个已知的先手必败状态，凡是能转移到先手必败的状态一定是必胜状态。

比如1是必败状态，那么2~9可以转移到1，所以是必胜状态。

10,10*，10**，10***，10****也都可以删除1后面那个0，转移到1，所以也是必胜状态。

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 const int maxn = ;

 int sg[maxn + ];

 void init()

 {

     char s[], s1[];

     for(int i = , j; i <= maxn; i++) if(!sg[i])//先手必败点

     {//所有能转移到先手必败的状态都是先手必胜状态

         sprintf(s, "%d", i);

         int n = strlen(s);

         for(j = ; j < n; j++)

         {//每一位都加上1

             strcpy(s1, s);

             while(++s1[j] <= '') sg[atoi(s1)] = ;

         }

         int m = i, b = ;

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

         {//在后面添0

             m *= ;

             for(int k = ; k < b; k++) sg[m + k] = ;

             b *= ;

         }

     }

 }

 int main()

 {

     init();

     char s[];

     while(scanf("%s", s) == )

     {

         if(s[] == '') { puts("Yes"); continue; }

         int n = , l = strlen(s);

         for(int i = ; i < l; i++) n = n *  + s[i] - '';

         printf("%s\n", sg[n] ? "Yes" : "No");

     }

     return ;

 }

代码君

相关文章