设为首页 加入收藏

TOP

HDU 2188 悼念512汶川大地震遇难同胞――选拔志愿者(巴什博弈论)
2015-07-20 17:41:18 来源: 作者: 【 】 浏览:2
Tags:HDU 2188 悼念 512 汶川 地震 遇难 同胞 选拔 志愿者 巴什 博弈论

题目地址:HDU 2188

裸的巴什博弈模型。

当n=m+1时,由于一次最多只能取m个,所以无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜,所以当一方面对的局势是n%(m+1)=0时,其面临的是必败的局势。所以当n=(m+1)*r+s,(r为任意自然数,s≤m)时,如果先取者要拿走s个物品,如果后取者拿走x(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。

代码如下:

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              using namespace std; int main() { int t, n, m; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); if(n%(m+1)==0) puts("Rabbit"); else puts("Grass"); } return 0; } 
            
           
         
        
       
      
     
    
   
  


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇[LeetCode]Search Insert Position 下一篇HDU 5011 Game(博弈论)

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·用 C 语言或者限制使 (2025-12-25 08:50:05)
·C++构造shared_ptr为 (2025-12-25 08:50:01)
·既然引用计数在做 GC (2025-12-25 08:49:59)
·Java 编程和 c 语言 (2025-12-25 08:19:48)
·. net内存管理宝典这 (2025-12-25 08:19:46)