SRM 624 D2L3: GameOfSegments, 博弈论，Sprague?Grundy theorem，Nimber - c++编程基础

TOP

SRM 624 D2L3: GameOfSegments, 博弈论，Sprague?Grundy theorem，Nimber

2015-07-20 17:54:57 来源: 作者: 【大中小】浏览:2次

Tags：SRM 624 D2L3: GameOfSegments 博弈论 Sprague Grundy theorem Nimber

这道题目需要用到博弈论中的经典理论，Sprague–Grundy theorem，下面将相关理论做一个总结：

Impartial Game：公平游戏，双方除了谁先开始游戏外，其余都相同。

Nim：一类经典的Impartial Game，很多游戏都可以等价于Nim。

Nimber（Grundy numbers）：可以理解为标识一个游戏状态的数。在游戏进行过程种，每个状态都应一个唯一的Nimber。

Sprague-Grundy定理：对一个 Impartial Game 的状态，其等效游戏的 Nimber 数，就等于所有其后继状态 Nimber 数的 Mex 函数值。

Mex：对一个集合S，若G为S的补集，则 Mex{S} = min {G}。

根据 Sprague-Grundy定理，要求当前游戏状态的Nimber数，则需要求出其所有后继状态的Nimbers，然后对这些Nimbers取Mex值。而且当存在多个“子Impartial Game”同时进行时，这一定理尤其有用，对每个“子游戏”状态的Nimber数进行异或操作，就是该状态的Nimber数。

代码如下：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include
                 #include 
                 
                   #include 
                  
                    #include 
                   
                     #include 
                    
                      #include 
                     
                       #include 
                      
                        #include 
                       
                         using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) typedef pair
                        
                          pii; typedef long long llong; typedef pair
                         
                           pll; #define mkp make_pair #define FOREACH(it, X) for(__typeof((X).begin()) it = (X).begin(); it != (X).end(); ++it) /*************** Program Begin **********************/ class GameOfSegments { public: int winner(int N) { int Nimbers[1001]; Nimbers[0] = Nimbers[1] = 0; for (int i = 2; i <= N; i++) { set 
                          
                            options; for (int j = 0; j <= i - 2; j++) { options.insert(Nimbers[j] ^ Nimbers[i - j - 2]); } int r = 0; while (options.count(r)) { ++r; } Nimbers[i] = r; } return (Nimbers[N] > 0 ? 1 : 2); } }; /************** Program End ************************/

参考：

http://www.cnblogs.com/fishball/archive/2013/01/19/2866311.html

http://www.cnblogs.com/hsqdboke/archive/2012/04/20/2459796.html

http://www.cnblogs.com/hsqdboke/archive/2012/04/21/2461034.html


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：POJ 2018 Best Cow Fences	下一篇：POJ 1200 Crazy Search(hash).

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: