参考http://blog.csdn.net/yizhangbiao/article/details/51992022
http://blog.csdn.net/luomingjun12315/article/details/45555495
必胜点和必败点的概念： P点：必败点，换而言之，就是谁处于此位置，则在双方操作正确的情况下必败。 N点：必胜点，处于此情况下，双方操作均正确的情况下必胜。必胜点和必败点的性质：
1、所有终结点是 必败点 P 。（我们以此为基本前提进行推理，换句话说，我们以此为假设） 2、从任何必胜点N 操作，至少有一种方式可以进入必败点 P。 3、无论如何操作，必败点P 都只能进入 必胜点 N。 hdu2147 题意n*m的表格，起点为（1，m）终点为左下角，两人轮流移动棋子，每次可向左，向下，左下（斜对角）移动，不能移动着输 从左下开始 m/n有一个为偶数则先手必胜SG函数：
解题模型：
1.把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。
即sg(G)=sg(G1)^sg(G2)^...^sg(Gn)。
2.分别考虑没一个子游戏，计算其SG值。
SG值的计算方法：（重点）
1.可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);
2.可选步数为任意步，SG(x) = x;
3.可选石子为一系列不连续的数，用getSG()计算
sg(G)=sg(G1)^sg(G2)^...^sg(Gn)， sg(G)=0,即P-Position,即先手比败。首先定义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}个，mex{sg[0]}={0}，故sg[1]=1;
x=2时，可以取走2-f{1}个石子，剩余{1}个，mex{sg[1]}={1}，故sg[2]=0；
x=3时，可以取走3-f{1,3}个石子，剩余{2,0}个，mex{sg[2],sg[0]}={0,0}，故sg[3]=1;
x=4时，可以取走4-f{1,3,4}个石子，剩余{3,1,0}个，mex{sg[3],sg[1],sg[0]}={1,1,0},故sg[4]=2;
x=5时，可以取走5-f{1,3,4}个石子，剩余{4,2,1}个，mex{sg[4],sg[2],sg[1]}={2,0,1},故sg[5]=3； 模板代码//f[N]:可改变当前状态的方式，N为方式的种类，f[n]存储可以移动的石子数，f[N]要在getSG之前先预处理 //SG[]:0~n的SG函数值 //S[]:为x后继状态的集合 int f[N],SG[MAXN],S[MAXN]; void getSG(int n){ int i,j; memset(SG,0,sizeof(SG)); //因为SG[0]始终等于0，所以i从1开始 for(i = 1; i <= MAXN; i++){ //每一次都要将上一状态 的 后继集合 重置 memset(S,0,sizeof(S)); for(j = 0; f[j] <= i && j <= N; j++) S[SG[i-f[j]]] = 1; //将后继状态的SG函数值进行标记 for(j = 0;j<=MAXN; j++) if(!S[j]){ //查询当前后继状态SG值中最小的非零值 SG[i] = j; break; } } }所以说当我们面对由n个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的SG值的方法，就可以把这些SG值全部看成Nim的石子堆，
然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了！（Nim其实就是n个从一堆中拿石子的游戏求SG的变型，总SG=n个sg的异或）。
hdu1848
题目大意：取石子问题，一共有3堆石子，每次只能取斐波那契数个石子，先取完石子者胜利，问先手胜还是后手胜？
算法思想：可选步数为一系列不连续的数（斐波那契数），可用getSG函数求得。 最终结果是所有SG值异或的结果 。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int f[1010],sg[1010],s[1010]; void getsg(int n) { int i,j; memset(sg,0,sizeof(sg)); for(int i=1;i<=n;i++) { memset(s,0,sizeof(s)); for(int j=0;f[j]<=i&&j<=n;j++) { s[sg[i-f[j]]]=1; } for(int j=0;j<=n;j++) { if(s[j]==0) //求mes{}中未出现的最小的非负整数 { sg[i]=j; break; } } } } int main() { int n,m,p; f[0]=f[1]=1;//预处理f[n] for(int i=2;i<=16;i++) { f[i]=f[i-1]+f[i-2]; } getsg(1000); while(scanf("%d%d%d",&m,&n,&p)!=EOF&&(m+n+p)) { if(sg[n]^sg[m]^sg[p]) cout<<"Fibo"<<endl; else cout<<"Nacci"<<endl; } return 0; }poj 2960
这道题题意： 我就按着样例格式来说吧： 先输入一个K，表示取数集合的个数。（K为0，则结束） 后面跟k个数,表示取数集合的数（就是每次只能取这几个数量的物品） 然后会跟一个M,表示有M次询问。 然后接下来M行，每行先有一个N，表示有多少堆物品。 N后跟着N个数，表示每堆物品数量。 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int f[110],a[110]; int sg[10010],s[10010]; void getsg(int n) { int i,j; memset(sg,0,sizeof(sg)); for(int i=1;i<=10010;i++) { memset(s,0,sizeof(s)); for(int j=0;f[j]<=i&&j<n;j++) { s[sg[i-f[j]]]=1; } for(int j=0;j<=10010;j++) { if(s[j]==0) { sg[i]=j; break; } } } } int main() { int k,m,n; while(scanf("%d",&k)!=EOF&&k) { for(int i=0;i<k;i++) { scanf("%d",&f[i]); } sort(f,f+k); getsg(k); scanf("%d",&m); while(m--) { int ans=0; scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%d",&a[i]); ans^=sg[a[i]]; } if(!ans) printf("L"); else printf("W"); } printf("\n"); } return 0; }
