1）游戏规则
通常的Nim游戏的定义是这样的：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。
（三）练习题：
problem one： HDU 4848 Fibonacci again and again
分析：
nim 博弈的简单变形，只需要预处理出（1,1000）的数的SG函数的值即可。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int f[30];
int sg[maxn+1];
int vis[maxn+1];
void init(){
f[0]=1,f[1]=1;
for(int i=2;i<20;i++)
f[i]=f[i-1]+f[i-2];
}
void solve(){
init();
memset(sg,0,sizeof(sg));
for(int i=1;i<=1000;i++){
memset(vis,0,sizeof(vis));
for(int j=1;j<maxn&&f[j]<=i;j++)
vis[sg[i-f[j]]]=1;
for(int j=0;;j++){
if(!vis[j]){
sg[i]=j;
break;
}
}
}
}
int main()
{
int n,m,p;
solve();
while(~scanf("%d%d%d",&n,&m,&p)){
if(n==0&&m==0&&p==0)
break;
if(sg[n]^sg[m]^sg[p])
puts("Fibo");
else
puts("Nacci");
}
return 0;
}
problem two：HDU 1907 John
分析：
nim博弈，注意全部为1的情况。
代码如下：
Code Render Status : Rendered By HDOJ C++ Code Render Version 0.01 Beta
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 50;
int a[maxn];
int main()
{
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int s=0,num=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
s^=a[i];
if(a[i]>1) num++;
}
if((s&&num)||(!s&&!num))
puts("John");
else
puts("Brother");
}
return 0;
}
problem there ：HDU 3032 Nim or not Nim?
分析：
nim博弈的变形，每次可以从一堆取若干，或者把一堆变成两堆。打表找SG函数的规律。
代码如下：
打表找规律的代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 1000010;
int a[maxn];
int sg[maxn];
int get(int x){
int vis[1000];
memset(vis,0,sizeof(vis));
if(sg[x]!=-1) return sg[x];
for(int i=x-1;i>=0;i--)
vis[get(i)]=1;
for(int i=1;i<=x/2;i++){
int ans = 0;
ans^=get(i);
ans^=get(x-i);
vis[ans]=1;
}
for(int i=0;;i++){
if(!vis[i]){
sg[x]=i;
break;
}
}
return sg[x];
}
int main()
{
memset(sg,-1,sizeof(sg));
sg[0]=0;
int n;
while(~scanf("%d",&n)){
for(int i=0;i<20;i++){
printf("sg( %d ) = %d\n",i,get(i));
}
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int get(int x){
if(x==0) return 0;
if(x%4==0)
return x-1;
if(x%4==3)
return x+1;
return x;
}
int main()
{
int t,n,x;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
int ans = 0;
for(int i=0;i<n;i++){
scanf("%d",&x);
ans^=get(x);
}
if(ans) puts("Alice");
else puts("Bob");
}
return 0;
}
原文：http://blog.csdn.net/bigbigship/article/details/44652361