51NOD 1068 Bash游戏 V3-白红宇

51NOD 1068 Bash游戏 V3

阅读量：4684 次

发布时间：2019-06-09

本文共 1063 字，大约阅读时间需要 3 分钟。

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次拿的数量只能是2的正整数次幂，比如(1,2,4,8,16….)，拿到最后1颗石子的人获胜。假设A B都非常聪明，拿石子的过程中不会出现失误。给出N，问最后谁能赢得比赛。

例如N = 3。A只能拿1颗或2颗，所以B可以拿到最后1颗石子。（输入的N可能为大数）

这是个博弈题。。我们可以先打个表看看

打表的过程如下

#include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std;const int N=1000000;int n; int dfs(int x,int pre){ if(x==0) return 0; for(int i=1;i<=n;i*=2) { if(x-i<0) break; if(dfs(x-i,i)==0) return 1; } return 0; }int main(){ while(scanf("%d",&n)!=EOF) { int flag=0; for(int i=1;i<=n;i*=2) { if(dfs(n-i,i)==0) { flag=1; break; } } if(flag) printf("n=%d：A ",n); else printf("n=%d：B ",n); } }

打完表我们可以知道B赢得情况是只有n能被3整除的时候。然后就很好做辣

#include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           using namespace std;const int N=10000;char s[N];int main(){ int T,n; scanf("%d",&T); while(T--) { scanf("%s",s); n=0; int m=strlen(s); for(int i=0;i

转载于:https://www.cnblogs.com/NaCl/p/9580111.html

你可能感兴趣的文章