題意：有n堆石子，每次可以從第1堆石子里取1顆、2顆或3顆，可以從第2堆石子里取奇數(shù)顆，可以從第3堆及以后石子里取任意顆……。推廣到一般情況給定n堆，就是只能在指定的集合里取出對應(yīng)數(shù)量的石子數(shù)，比如集合s={1，2，4}就是每次只能從一堆里取走1或2或4顆石子。

分析：想一下前面的一個(gè)nim問題，是從一堆中取出指定集合石子數(shù)，要求必勝，怎么做，根據(jù)前面推導(dǎo)nim解法的過程，我們不妨還是先從0開始考慮，當(dāng)堆里面的數(shù)只有0個(gè)時(shí)，記M=0，那么此時(shí)我已經(jīng)不能拿了，所以我輸記為N，當(dāng)M=1時(shí)看集合里有沒有小于等于1的數(shù)，如果沒有還是N，當(dāng)M=2，3，4時(shí)都先考慮有沒有集合里的數(shù)。

下面我們將這個(gè)問題抽象到圖上，而當(dāng)前狀態(tài)則被當(dāng)作棋子，就是結(jié)點(diǎn)，每次只能移動集合里面的數(shù)。這里面有一個(gè)函數(shù)mex，也就是相當(dāng)于狀態(tài)轉(zhuǎn)換，網(wǎng)上給出了詳細(xì)的解鎖，但好像將原理講的不是很清楚，其實(shí)狀態(tài)轉(zhuǎn)換就是將當(dāng)前的狀態(tài)是否能轉(zhuǎn)換到對手必輸?shù)臓顟B(tài)，就是Y態(tài)，也就是P，如果當(dāng)前狀態(tài)可轉(zhuǎn)換的子狀態(tài)都為對手必贏狀態(tài)，那么當(dāng)前狀態(tài)為先手必輸狀態(tài)，就是N態(tài)。所以只需要迭代一下就可以了，但是因?yàn)榧侠锩鏀?shù)不連續(xù)，所以只能一開始從0開始找，找到第一個(gè)沒有出現(xiàn)在子集和中的值，那就是它的SG值，這個(gè)SG值可以相當(dāng)于它的狀態(tài)，每次子集為0就是N，不為0就是Y，Y可以轉(zhuǎn)換成N，而N只能轉(zhuǎn)換成Y。

最后如果是n堆，就把n堆每個(gè)堆的SG值都XOr，為0就是N，不為0就是Y。

下面是mex計(jì)算SG值的兩種方法。

打表法：

//f[]：可以取走的石子個(gè)數(shù) //sg[]:0~n的SG函數(shù)值 //hash[]:mex{} int f[N],sg[N],hash[N]; void getSG(int n) {int i,j;memset(sg,0,sizeof(sg));for(i=1;i<=n;i++){memset(hash,0,sizeof(hash));for(j=1;f[j]<=i;j++)hash[sg[i-f[j]]]=1;for(j=0;j<=n;j++) //求mes{}中未出現(xiàn)的最小的非負(fù)整數(shù){if(hash[j]==0){sg[i]=j;break;}}} }

DFS：

//注意 S數(shù)組要按從小到大排序 SG函數(shù)要初始化為-1 對于每個(gè)集合只需初始化1遍 //n是集合s的大小 S[i]是定義的特殊取法規(guī)則的數(shù)組 int s[110],sg[10010],n; int SG_dfs(int x) {int i;if(sg[x]!=-1)return sg[x];bool vis[110];memset(vis,0,sizeof(vis));for(i=0;i<n;i++){if(x>=s[i]){SG_dfs(x-s[i]);vis[sg[x-s[i]]]=1;}}int e;for(i=0;;i++)if(!vis[i]){e=i;break;}return sg[x]=e; }

兩種方法都是網(wǎng)上找的模板，可以直接使用。

?

總結(jié)

以上是生活随笔為你收集整理的Nim游戏SG版本的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。