博弈论

参考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("
");
    }
    return 0;
 }