ZOJ2725_Digital Deletions

题意是这样的，一开始给你一串数字，两个人轮流操作，操作可以分为两种。

1、每次修改一个数字，使其变为一个小于当前的非负数。

2、移除中间的某一个0以及0右边的所有数字。

使得所有数字消失的游戏者获胜。

题目有一个很关键的条件，最多只有6为，其实我们可以这样考虑这个问题。

对于每一位，最多有11种状态，0到9以及空。

所以我们可以用6个11进制表示所有的状态，这样算来时间上是可以承受的。

然后的话，就是典型的记忆化搜了，对于每一个数，枚举每一种后继的状态，然后用基本的博弈知识判断该状态是必胜还是必败。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define maxn 2000200

 using namespace std;

 int f[maxn],dig[],cur,k,n;

 char s[];

 int dfs(int x)

 {

     if (x<=) return -;

     if (f[x]!=) return f[x];

     int tot,d;

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

     {

         tot=x,d=(x/dig[i])%;

         if (d==) break;

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

         {

             tot-=dig[i];

             if (dfs(tot)==-) return f[x]=;

         }

         if (d==)

         {

             if (dfs(tot/dig[i+])==-) return f[x]=;

         }

     }

     return f[x]=-;

 }

 int main()

 {

     memset(f,,sizeof f);

     dig[]=dig[]=;

     for (int i=; i<; i++) dig[]+=dig[i]=dig[i-]*;

     dig[]*=,dig[]=dig[]*;

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

     {

         for (cur=,n=strlen(s)-,k=; n>=; k++,n--)

             cur+=dig[k]*(s[n]-''+);

         if (dfs(cur)==) printf("Yes\n");

             else printf("No\n");

     }

     return ;

 }

巴特西

ZOJ2725_Digital Deletions

最新文章

热门文章