简单博弈10道

hdu1846巴什博弈，n%(m+1)==0先手必败。

#include <iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

using namespace std;

int main()

{

    int n,a,b;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d",&a,&b);

        if(a%(b+1)==0)

        printf("second\n");

        else printf("first\n");

    }

    return 0;

}

hdu1847

只要留下两类都是2的指数幂，就是必输状态，然后找规律，发现这两类的和为3的倍数。即有下面的结论。

#include <iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int main()

{

   int n;

   while(scanf("%d",&n)!=EOF)

   {

       if(n%3==0)

       printf("Cici\n");

       else printf("Kiki\n");

   }

    return 0;

}

hdu1848

#include <iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define N 1005

int f[N];

int sg[N];

void fun()

{

    int i;

    f[0]=1;

    f[1]=1;

    f[2]=2;

    for(i=3;;i++)

    {

    f[i]=f[i-1]+f[i-2];

    if(f[i]>1000)

    break;

    }

}

int dfs(int v)

{

    int i;

    if(sg[v]!=-1)

    return sg[v];

    bool visit[N]={0};

    for(i=1;i<16;i++)

    {

       if(v>=f[i])

       {

           int temp=dfs(v-f[i]);

           visit[temp]=1;

       }

    }

    for(i=0;visit[i];i++);

    return sg[v]=i;

}

int main()

{

    fun();

    int m,n,p;

    while(scanf("%d%d%d",&m,&n,&p),m||n||p)

    {

        memset(sg,-1,sizeof(sg));

        int ans;

        ans=dfs(m)^dfs(n)^dfs(p);

        if(ans)

        printf("Fibo\n");

        else printf("Nacci\n");

    }

    return 0;

}

hdu1849

裸的NIM博弈，直接异或即可。

#include <iostream>

#include<cstdio>

using namespace std;

int main()

{

    int n,p;

    while(scanf("%d",&n)!=EOF)

    {

        if(n==0)break;

        int ans=0;

        for(int i=0;i<n;i++)

        {

            scanf("%d",&p);

            ans^=p;

        }

        if(ans==0)

        printf("Grass Win!\n");

        else printf("Rabbit Win!\n");

    }

    return 0;

}

hdu1850

简单NIM博弈，如果异或不为0，找出异或可以使其成为0的值， if(num[j]>(ans^num[j]))这是关键。

#include <iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int num[105];

int main()

{

    int t;

    while(scanf("%d",&t)&&t)

    {

        int ans=0;

        for(int i=0;i<t;i++)

        {

            scanf("%d",&num[i]);

            ans^=num[i];

        }

        int cnt=0;

        for(int j=0;j<t;j++)

        {

            if(num[j]>(ans^num[j]))

            {

            cnt++;

            }

        }

        printf("%d\n",cnt);

    }

    return 0;

}

hdu1851j简单NIM博弈

#include <iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

using namespace std;

int main()

{

    int t,n,m,l;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        int ans=0;

        while(n--)

        {

            scanf("%d%d",&m,&l);

            ans^=(m%(l+1));

        }

        if(ans==0)

        printf("Yes\n");

        else printf("No\n");

    }

    return 0;

}

hdu1907 NIM博弈，全是1的时候，特判，数1的个数，奇数输，偶数赢了。

#include <iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<cstdlib>

using namespace std;

int main()

{

    int t,num;

    scanf("%d",&t);

    while(t--)

    {

        int ans=0,flag=0;

        int p[50];

        scanf("%d",&num);

        for(int i=0; i<num; i++)

        {

            scanf("%d",&p[i]);

            if(p[i]!=1)

                flag=1;

            ans^=p[i];

        }

        if(flag)

        {

            if(ans==0)

                printf("Brother\n");

            else printf("John\n");

        }else

        {

            if(num%2!=0)

                printf("Brother\n");

            else printf("John\n");

        }

    }

    return 0;

}

hdu2147

判断P和N的状态，画出图标即可。利用SG函数的基本性质。P后面的都是N，N后面的一定存在一个P状态。

观察图表规律知道，n和m都是奇数时候，必败。

#include <iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstring>

using namespace std;

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        if(n==0&&m==0)break;

        if(n&1&&m&1)

        printf("What a pity!\n");

        else printf("Wonderful!\n");

    }

    return 0;

}

hdu2148

简单的巴什博弈。

#include <iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

using namespace std;

int main()

{

    int m,n;

    while(scanf("%d%d",&m,&n)!=EOF)

    {

        if(m%(n+1)==0)

        {

        printf("none\n");

        continue;

        }

        else if(n>m)

        {

            for(int i=m;i<n;i++)

            printf("%d ",i);

            printf("%d\n",n);

        }

        else printf("%d\n",m%(n+1));//这里是开始的时候，如果先出m%(n+1)个，那么剩下的就是必败态了。

    }

    return 0;

}

hdu2149 简单的巴什博弈，同上题类似。

#include <iostream>

#include<cstdio>

using namespace std;

int main()

{

    int t,n,m;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        if(m>n)

        printf("Grass\n");

        else if(n%(m+1)==0)

        {

            printf("Rabbit\n");

        }

        else printf("Grass\n");

    }

    return 0;

}