Nim游戏SG版本

题意：有n堆石子，每次可以从第1堆石子里取1颗、2颗或3颗，可以从第2堆石子里取奇数颗，可以从第3堆及以后石子里取任意颗……。推广到一般情况给定n堆，就是只能在指定的集合里取出对应数量的石子数，比如集合s={1，2，4}就是每次只能从一堆里取走1或2或4颗石子。

分析：想一下前面的一个nim问题，是从一堆中取出指定集合石子数，要求必胜，怎么做，根据前面推导nim解法的过程，我们不妨还是先从0开始考虑，当堆里面的数只有0个时，记M=0，那么此时我已经不能拿了，所以我输记为N，当M=1时看集合里有没有小于等于1的数，如果没有还是N，当M=2，3，4时都先考虑有没有集合里的数。

下面我们将这个问题抽象到图上，而当前状态则被当作棋子，就是结点，每次只能移动集合里面的数。这里面有一个函数mex，也就是相当于状态转换，网上给出了详细的解锁，但好像将原理讲的不是很清楚，其实状态转换就是将当前的状态是否能转换到对手必输的状态，就是Y态，也就是P，如果当前状态可转换的子状态都为对手必赢状态，那么当前状态为先手必输状态，就是N态。所以只需要迭代一下就可以了，但是因为集合里面数不连续，所以只能一开始从0开始找，找到第一个没有出现在子集和中的值，那就是它的SG值，这个SG值可以相当于它的状态，每次子集为0就是N，不为0就是Y，Y可以转换成N，而N只能转换成Y。

最后如果是n堆，就把n堆每个堆的SG值都XOr，为0就是N，不为0就是Y。

下面是mex计算SG值的两种方法。

打表法：

//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//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{}中未出现的最小的非负整数{if(hash[j]==0){sg[i]=j;break;}}}
}

DFS：

//注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//n是集合s的大小 S[i]是定义的特殊取法规则的数组
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=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;
}

两种方法都是网上找的模板，可以直接使用。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！