以前写的关于博弈基础知识的博客:基础博弈论【巴什博弈、威佐夫博弈、尼姆博弈、反尼姆博弈】https://blog.csdn.net/ljw_study_in_CSDN/article/details/88356973

先复习一些概念:
* 先手必胜为N-position,后手必胜为P-position。
* 必败点(P态):前一个选手(Previous player)将取胜的位置称为必败点。
* 必胜点(N态) :下一个选手(Next player)将取胜的位置称为必胜点。
* 现在关于P,N的求解有三个规则
(1):最终态都是P(游戏规则是:最后不能进行操作的人输)
(2):按照游戏规则,到达当前态的前态都是N的话,则当前态是P
(3):按照游戏规则,到达当前态的前态至少有一个P的话,则当前态是N

———————————————————————————————————————————————————————

hdu 1730 Northcott Game

尼姆博弈。

为什么是Nim博弈呢?通常的Nim游戏的定义是这样的:有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。
先手从某一堆中取x个石子然后后手取y个石子,直到这一堆中没有石子和黑棋走x步然后白棋走y步直到黑白棋相遇(如果黑白棋子相遇,那先手必输,因为先手如果移动,后手紧跟移动,直至先手不能动,故先手必输)是不是极其相似呢?
假如把每一行都看成一个堆,而每个堆中的石子数为两个棋子距离差-1,所以我们只需要对每一堆的“石子数”进行异或计算即可。

#include <bits/stdc++.h>
using namespace std;
int n,m,a,b,x,sum;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m)
    {
        sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a>>b;
            x=abs(a-b)-1;
            sum=sum^x;
        }
        if(sum)printf("I WIN!\n");
        else printf("BAD LUCK!\n");
    }
    return 0;
}

hdu 1850 Being a Good Boy in Spring Festival

求尼姆博弈先手必胜的方法数。

只要选择的一堆石子数大于其他所有石子堆异或值,则先手必胜,因为可以把选择的那堆石子数减少到与其他所有石子堆异或值相等,从而使所有石子堆异或值为0,使后手开始选择时面临的是必败状态。

#include <bits/stdc++.h>
using namespace std;
int n,sum,ans,a[110];
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        sum=0;ans=0;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            sum=sum^a[i];
        }
        for(int i=1;i<=n;i++)
            if((sum^a[i])<a[i])ans++;
        printf("%d\n",ans);
    }
    return 0;
}

hdu 1907 John

反尼姆博弈。

尼姆博弈是最先取光石子的人赢,而反尼姆博弈是最先取光石子的人输。

做法:将所有的石子堆异或,设为sum,反尼姆博弈中先手必胜有两种可能:
①sum!=0且存在a[i]>1
②sum=0且所有a[i]=1(因为每个石子堆只有一个石子且可以证明石子堆个数必为偶数,所以显然总是后手最先取光石子,也就是后手必败,先手必胜)

#include <bits/stdc++.h>
using namespace std;
int t,n,x,sum,cnt;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;
        sum=0;cnt=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            sum=sum^x;
            if(x==1)cnt++;//统计只有1个石子的石子堆个数
        }
        if((sum!=0&&cnt<n)||(sum==0&&cnt==n))printf("John\n");
        else printf("Brother\n");
    }
    return 0;
}

hdu 2147 kiki's game

打表NP态,找规律。

从右上角向左下角打表NP态,N态(设为0)表示先手必胜,P态(设为1)表示后手必胜,初始位置a[1][m]=1。
递推到某个位置时,如果它的右边、上边、右上边均为N态,则它为P态;如果它的右边、上边、右上边中只要有一个是P态,则它为N态(先手可以把对手的必胜态P态转化为自己的必胜态N态)。

打表代码(不能AC):

#include <bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m,a[N][N];
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m&&(n||m))
    {
        memset(a,0,sizeof(a));
        a[1][m]=1;
        for(int i=1;i<=n;i++)
            for(int j=m;j>=1;j--)
                if(a[i][j+1]==0&&a[i-1][j]==0&&a[i-1][j+1]==0)a[i][j]=1;
        if(a[n][1]==0)printf("Wonderful!\n");//先手胜
        else printf("What a pity!\n");//后手胜
    }
    return 0;
}

不能AC的原因是超内存(Memory Limit Exceeded),所以要打表前几项找规律。
显然可以看出后手胜的概率较低,那么就找后手胜的规律。

1 1 后手胜

1 2 先手胜
2 1 先手胜
2 2 先手胜

3 1 后手胜
1 3 后手胜
3 2 先手胜
2 3 先手胜
3 3 后手胜

4 1 先手胜
1 4 先手胜
4 2 先手胜
2 4 先手胜
4 3 先手胜
3 4 先手胜
4 4 先手胜

规律:当n和m均为奇数时,后手胜,否则先手胜。

AC代码:

#include <bits/stdc++.h>
using namespace std;
int n,m;
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n>>m&&(n||m))
    {
        if((n&1)&&(m&1))printf("What a pity!\n");
        else printf("Wonderful!\n");
    }
    return 0;
}

hdu 1848 Fibonacci again and again

裸的打表SG函数,求sg函数的模板题。

将输入的三个值对应的sg函数进行异或,异或值为0则后手胜,否则先手胜。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
bool vis[N];
int a,b,c,f[N],sg[N];//f[]表示每次能取的数
void get_sg()//打表sg函数
{
    memset(sg,0,sizeof(sg));//sg[0]=0
    for(int i=1;i<=N;i++)//从1开始遍历,得到sg[i]对应的值
    {
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=15&&f[j]<=i;j++)//遍历能取的数f[j]
            vis[sg[i-f[j]]]=1;//标记i取了f[j]后对应的sg值
        for(int j=0;j<=N;j++)
            if(vis[j]==0){sg[i]=j;break;}//第一个未标记的非负数即为sg[i]
    }
}
int main()
{
    ios::sync_with_stdio(false);
    f[1]=1;f[2]=2;
    for(int i=3;i<=15;i++)//f[15]=987<1000,f[16]=1597>1000
        f[i]=f[i-1]+f[i-2];
    get_sg();
    while(cin>>a>>b>>c&&(a||b||c))
    {
        if(sg[a]^sg[b]^sg[c])printf("Fibo\n");
        else printf("Nacci\n");
    }
    return 0;
}

hdu 1536 S-Nim

这题和上题差不多,还是直接打表sg函数。 记得排序一下 f 数组(f[i]表示每次能取的数)。

还有一个比较玄学的细节:vis标记数组写成了int类型会导致TLE,改成bool类型就AC了。

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
bool vis[N];//这里的vis一定要定义成bool类型,定义成int类型会超时!
int n,m,k,x,sum,f[N],sg[N];
void get_sg()
{
    memset(sg,0,sizeof(sg));
    for(int i=1;i<=N;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n&&f[j]<=i;j++)//默认f[]已经升序排列
            vis[sg[i-f[j]]]=1;
        for(int j=0;j<=N;j++)
            if(vis[j]==0){sg[i]=j;break;}
    }
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n&&n)
    {
        for(int i=1;i<=n;i++)
            cin>>f[i];
        sort(f+1,f+n+1);//一定要保证f[]升序
        get_sg();
        cin>>m;
        while(m--)
        {
            cin>>k;
            sum=0;
            for(int i=1;i<=k;i++)
            {
                cin>>x;
                sum=sum^sg[x];
            }
            if(sum==0)printf("L");
            else printf("W");
        }
        printf("\n");
    }
    return 0;
}

hdu 3980 Paint Chain

题意:n元环,每次取m个连续的石子,最后取不了的判负。
n元环可以经过去一次之后变成n-m元链,而链可以用Nim和来计算sg值。
可以这样理解: 对于n-m元链,每次选择一个位置取m个石子,从而把剩余部分分成了两堆石子(石子数可以为0),将这两堆石子的sg值异或,即为取m个石子之前的sg值。
不过需要注意的一点是取了m个之后变成n-m元链,要转换先后手。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
bool vis[N];
int t,n,m,sg[N];
void get_sg()//n>m时,打表sg函数
{
    memset(sg,0,sizeof(sg));
    for(int i=1;i<=n-m;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=0;i-m-j>=0;j++)
            vis[sg[j]^sg[i-m-j]]=1;//左段长j,右段长i-m-j,总共长i-m
        for(int j=0;j<=n-m;j++)
            if(vis[j]==0){sg[i]=j;break;}
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    for(int cas=1;cas<=t;cas++)
    {
        cin>>n>>m;
        printf("Case #%d: ",cas);
        if(n==m)printf("aekdycoin\n");//先手胜
        else if(n<m)printf("abcdxyzk\n");//后手胜
        else//n>m时,打表sg函数
        {
            get_sg();
            if(sg[n-m])printf("abcdxyzk\n");//后手胜(转换先后手)
            else printf("aekdycoin\n");//先手胜
        }
    }
    return 0;
}

hdu 5795 A Simple Nim

输入的s[i]最大为1e9,sg数组开不了这么大,所以要打表sg函数找规律。

打表代码:

#include <bits/stdc++.h>
using namespace std;
int sg[110];
bool vis[110];
void get_sg()
{
    memset(sg,0,sizeof(sg));
    for(int i=1;i<=100;i++)
    {
        memset(vis,0,sizeof(vis));
        for(int j=0;j<i;j++)//若选择取石子,后继节点的sg值为sg[0]~sg[i-1]
            vis[sg[j]]=1;
        for(int j=1;j<i;j++)//若选择把石子分成三堆,第一堆个数j,第二堆个数k,后继节点的sg值为sg[j]^sg[k]^sg[i-k-j]
            for(int k=1;k<i&&i-k-j>=1;k++)//注意是i-k-j>=1,不是>=0!
                vis[sg[j]^sg[k]^sg[i-k-j]]=1;
        for(int j=0;j<=100;j++)
            if(vis[j]==0){sg[i]=j;break;}
    }
}
int main()
{
    get_sg();
    for(int i=0;i<=100;i++)
        printf("%d %d\n",i,sg[i]);
    return 0;
}

在这里插入图片描述
AC代码:

#include <bits/stdc++.h>
using namespace std;
int t,n,x,sum;
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n;sum=0;
        for(int i=1;i<=n;i++)
        {
            cin>>x;
            if(x%8==0)x--;
            else if(x%8==7)x++;//写else if,不要写if!
            sum^=x;
        }
        if(sum)printf("First player wins.\n");
        else printf("Second player wins.\n");
    }
    return 0;
}

hdu 2873 Bomb Game

二维sg函数打表。

题意:给定n*m的棋盘,棋盘中有炸弹,每进行一次操作炸弹炸一次,炸一次生成两个炸弹,分别位于左方和上方(左或上是边界则不生成),炸完之后原炸弹消失,两人轮流操作,最后不能引爆的输。

思路:

一维的情况,等价于多堆取石子的游戏,sg值即石子数,本题中也就是到1,1的距离。

二维时,引爆每个炸弹后会产生两个新的炸弹,而这个炸弹的sg即可看做新产生的两个炸弹的sg的异或(即"NIM和"),这样只要修改一下一维求sg的函数,变可以构造出二维的sg函数表,对应有炸弹的位置的sg值异或起来就可以判定胜负。

#include <bits/stdc++.h>
using namespace std;
char a[60][60];
bool vis[1010];//vis开大一点
int n,m,sum,sg[60][60];
int get_sg(int x,int y)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<x;i++)
        for(int j=1;j<y;j++)
        vis[sg[x][j]^sg[i][y]]=1;
    for(int i=0;;i++)
        if(!vis[i])return i;
}
int main()
{
    ios::sync_with_stdio(false);
    for(int i=1;i<=50;i++)
        for(int j=1;j<=50;j++)
        {
            if(i==1)sg[i][j]=j-1;
            else if(j==1)sg[i][j]=i-1;
            else sg[i][j]=get_sg(i,j);//打表
        }
    /*for(int i=1;i<=50;i++)
        for(int j=1;j<=50;j++)
        j==50?printf("%3d\n",sg[i][j]):printf("%3d ",sg[i][j]);*/
    while(cin>>n>>m&&(n||m))
    {
        sum=0;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(a[i][j]=='#')sum^=sg[i][j];
            }
        if(sum)printf("John\n");
        else printf("Jack\n");
    }
    return 0;
}