SG函數：

??????? 首先定義mex(minimal excludant)運算，這是施加于一個集合的運算，表示最小的不屬于這個集合的非負整數。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。

??????? 對于任意狀態 x ， 定義 SG(x) = mex(S),其中 S 是 x 后繼狀態的SG函數值的集合。如 x 有三個后繼狀態分別為?SG(a),SG(b),SG(c)，那么SG(x) = mex{SG(a),SG(b),SG(c)}。?這樣 集合S 的終態必然是空集，所以SG函數的終態為 SG(x) = 0,當且僅當 x 為必敗點P時。

【實例】取石子問題

有1堆n個的石子，每次只能取{ 1, 3, 4 }個石子，先取完石子者勝利，那么各個數的SG值為多少？

SG[0]=0，f[]={1,3,4},

x=1 時，可以取走1 - f{1}個石子，剩余{0}個，所以 SG[1] = mex{ SG[0] }= mex{0} = 1;

x=2 時，可以取走2 - f{1}個石子，剩余{1}個，所以 SG[2] = mex{ SG[1] }= mex{1} = 0;

x=3 時，可以取走3 - f{1,3}個石子，剩余{2,0}個，所以 SG[3] = mex{SG[2],SG[0]} = mex{0,0} =1;

x=4 時，可以取走4- ?f{1,3,4}個石子，剩余{3,1,0}個，所以 SG[4] = mex{SG[3],SG[1],SG[0]} = mex{1,1,0} = 2;

x=5 時，可以取走5 - f{1,3,4}個石子，剩余{4,2,1}個，所以SG[5] = mex{SG[4],SG[2],SG[1]} =mex{2,0,1} = 3;

以此類推.....

?? x????????0? 1? 2? 3? 4? 5? 6? 7? 8....

SG[x]????0? 1? 0? 1? 2? 3? 2? 0? 1....

由上述實例我們就可以得到SG函數值求解步驟，那么計算1~n的SG函數值步驟如下：

1、使用 數組f 將 可改變當前狀態 的方式記錄下來。

2、然后我們使用 另一個數組 將當前狀態x 的后繼狀態標記。

3、最后模擬mex運算，也就是我們在標記值中 搜索 未被標記值 的最小值，將其賦值給SG(x)。

4、我們不斷的重復 2 - 3 的步驟，就完成了 計算1~n 的函數值。

void getsg(int n) {bool mex[11111];for(int i=0;i<n;i++){memset(mex,false,sizeof(mex));for (int j = 1; j <= k; ++j)//k為fa數組元素個數{if (i - fa[j] >= 0){mex[sg[i - fa[j]]] = true;}}for(int j=0;j<=n;j++)if(mex[j]==false){sg[i]=j;break;}} }

?

總結

以上是生活随笔為你收集整理的sg函数模板的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。