博弈（2019.3.9训练）【更新完成】

本次训练共6题，本文附AC代码和题目链接。

A题 hdu 1846 Brave Game

巴什博弈，模板题。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n%(m+1)==0)printf("second\n");
        else printf("first\n");
    }
    return 0;
}

B题 hdu 1847 Good Luck in CET-4 Everybody!

这题找规律，先打表前14个很容易就能找出规律。
前14个打表依次为：(P表示先手必败，即Cici赢；N表示先手必胜，即Kiki赢)

AC代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        if(n<=2)printf("Kiki\n");
        else
        {
            if(n%3==0)printf("Cici\n");
            else printf("Kiki\n");
        }
    }
    return 0;
}

C题 nefu 768 取石子游戏(二)

尼姆博弈，模板题。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,x,ans;
    while(cin>>m)
    {
        ans=0;
        while(m--)
        {cin>>x;ans=ans^x;}
        if(ans==0)printf("Lose\n");//所有石子异或为0，先手必输
        else printf("Win\n");
    }
    return 0;
}

D题 hdu 1527 取石子游戏

威佐夫博弈，模板题。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,w;
    ios::sync_with_stdio(false);
    while(cin>>x>>y)
    {
        w=(int)((sqrt(5.0)+1.0)/2.0*fabs(y-x));
        if(w==(min(x,y)))printf("0\n");
        else printf("1\n");
    }
    return 0;
}

E题 nefu 1322 捡火柴棍

尼姆博弈，先处理一下数据，把二维数组a的每行分成两个火柴堆，依次异或每个火柴堆，最后判断是否为0即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i,j,t,ans,tmp1,tmp2,a[101][101];
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        ans=0;
        for(i=1;i<=n;i++)
        {
            tmp1=tmp2=0;
            for(j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(j<=m/2)tmp1=tmp1+a[i][j];
                else tmp2=tmp2+a[i][j];
            }
            ans=ans^tmp1^tmp2;
        }
        if(ans==0)printf("Bob\n");
        else printf("Alice\n");
    }
    return 0;
}

F题 hdu 2509 Be the Winner

反尼姆博弈，模板题。
尼姆博弈是最先取光石子的人赢，而反尼姆博弈是最先取光石子的人输。
先把所有石子异或，设为ans，反尼姆博弈中先手必胜有两种可能：
①ans!=0且存在a[i]>1 ②ans=0且任意a[i]=1(因为每个石子堆只有一个石子且可以证明石子堆个数必为偶数，所以显然总是后手最先取光石子，也就是后手必败，先手必胜)

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int i,n,ans,flag,a[101];
    while(cin>>n)
    {
        ans=flag=0;
        for(i=1;i<=n;i++)
        {
            cin>>a[i];ans=ans^a[i];
            if(a[i]>1)flag=1;
        }
        if(ans==0&&flag==0||ans!=0&&flag==1)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

基础博弈论其他练习题：https://blog.csdn.net/ljw_study_in_CSDN/article/details/88356973