程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SRM 624 D2L3: GameOfSegments, 博弈論，Sprague–Grundy theorem，Nimber

SRM 624 D2L3: GameOfSegments, 博弈論，Sprague–Grundy theorem，Nimber

編輯：C++入門知識

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 ************************/