好不容易放了一次假，终于得空整理一下有关组合游戏的东西了。
尼姆博弈：有m堆物品，每次选择一堆，拿走至少一件，两位选手，轮流取物品，哪位选手拿走了最后一件，哪位选手就得胜。
我们先来认识一下SG函数
SG为0值的点为必败点
尼姆博弈分为两种状况
一：每次取物的数量范围是【1，m】(m是这堆物品的总数量)
此时，不用计算SG值，每堆的物品数就是就是它所对应的SG值
如下题 HDU2176 取(m堆)石子游戏题目链接
题意：中文~~~~
一道典型的尼姆博弈题目
现给出AC代码
#include<stdio.h>
int main()
{
int m;
int ans;
int data[200000+20];
int i ;
while(scanf("%d",&m)&&m)
{
for(i = 0; i < m; i++)
{
scanf("%d",&data[i]);
}
ans = data[0];
for(i = 1; i < m; i++)//将每堆的数目直接进行异或
{
ans ^= data[i];
}
if(ans== 0)//对于异或值为0，是必败点
{
printf("No\n");
}
else
{
int end = 0;
printf("Yes\n");
for(i = 0; i < m; i++)
{
end = ans ^ data[i];//end是按照最优的方法取完石子后，剩下的石子
if(end < data[i])
{
printf("%d %d\n",data[i],end);
}
}
}
}
return 0;
}
二.m堆物品，每次取的数目i必须属于某一个集合
此时，SG值不再是当前堆的物品数，而需要通过计算求得
如下题 HDU1848 Fibonacci again and again题目链接
题意：共有 三堆石子，两人轮流取石子，但是每次取石子的个数必须属于斐波那契数列，取完最后一个石子的一方获胜。
先普及一下斐波那契数列
F[0]=1,F[1]=2,F[i]=F[i-1]+[i-2],此时要求得每一点的sg值
现给出AC代码
#include<stdio.h>
int F[1010];
int f[1010];
int ct;
int mex(int x)
{
int g[1010]={0};//bool数组表示那些值被作为某个节点的SG值使用过
int t,i;
int j;
for (i=0; i<ct; i++)//此处的ct为存储可取数目的数组的长度
{
t=x-F[i];//数组fib为操作数集合，t为x当前遍历的后继
if (t<0) break;
if (f[t]==-1) f[t]=mex(t);//若t点未赋SG值，递归查找
g[f[t]]=1;//bool数组中，这个SG值赋为true
}
for (j=0; ; j++)//遍历bool数组
if (!g[j]) return j;//第一次遇到一个未被作为SG值的数时，返回答案。
}
int main()
{
int i,j;
int ans;
int n,m,p;
F[0]=1;
F[1]=2;
i = 1;
while(F[i]<1050)
{
F[i+1]= F[i]+F[i-1];
i++;
}
ct = i;
memset(f,-1,sizeof(f));
f[0]=0;
for(i = 1; i <= 1000; i++)
{
f[i]=mex(i);
}
while(scanf("%d%d%d",&n,&m,&p)&&n+m+p)
{
ans = 0;
ans^=f[n];
ans^=f[m];
ans^=f[p];
if(ans)
printf("Fibo\n");
else
printf("Nacci\n");
}
return 0;
}
再来看下一道 HDU1536 S-Nim题目链接
题意：首先给出一些数字，然后给出一组事件堆，两个玩家，要求轮流从组中取得石子，去玩最后一个石子的人获胜
现给出AC代码
#include <iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAX = 110;
const int MMAX=10000+10;
int k,m,l;
int F[MAX],num;
int sg[MMAX];
int mex(int x)
{
bool g[101];//bool数组表示那些值被作为某个节点的SG值使用过
int t;
memset(g,0,sizeof(g));//初值全为0
for (int i=0; i<k; i++)//此处的k为存储可取数目的数组的长度
{
t=x-F[i];//数组F为操作数集合，t为x当前遍历的后继
if (t<0) break;
if (sg[t]==-1) sg[t]=mex(t);//若t点未赋SG值，递归查找
g[sg[t]]=true;//bool数组中，这个SG值赋为true
}
for (int i=0;i<101 ; i++)//遍历bool数组
if (!g[i]) return i;//第一次遇到一个未被作为SG值的数时，返回答案。
}
int main()
{
int ans;
while(scanf("%d",&k)&&k)
{
for(int i = 0; i < k; i++)
{
scanf("%d",&F[i]);
}
sort(F,F+k);
memset(sg,-1,sizeof(sg));
sg[0]=0;
scanf("%d",&m);
while(m--)
{
/*for(int i = 1; i < MMAX; i++)//注掉的部分没有错，但是会超时
{
sg[i]=mex(i);
}*/
ans = 0;
scanf("%d",&l);
while(l--)
{
scanf("%d",&num);
if(sg[num]==-1)
{
sg[num]=mex(num);
}
ans ^= sg[num];
}
if(ans)printf("W");
else printf("L");
}
printf("\n");
}
return 0;
}
通过对比，可知，在这两道题目中，求SG值得mex函数是相同的。