觅规律博弈小记（更新）

找规律博弈小记（更新）

最近在HDOJ上水博弈的题目，在这里记录一些小规律。

！！1）http://acm.hdu.edu.cn/showproblem.php?pid=2897

题意：一堆n个石子，每次最多取q个，最少取p个，切最后不少于p个时必须一次性取完。谁后取完者输。

PS：那么就是谁先取到剩p个时候就赢了，少于p个的话一定输，因为必须取完，

如果谁当前遇到0个，赢，大于p小于p+q个是赢，因为先手总是可以想办法给后手留下p个，让他不得不拿。

推理发现n个和n-（p+q）输赢一样，所以首先可对n%=（p+q）。

代码：

#include <cstdio>
int main()
{
    int n,p,q;
    while(~scanf("%d%d%d",&n,&p,&q))
    {
        if(p>q)
            std::swap(p,q);
        n%=(p+q);
        if(n<=p&&n!=0)
            printf("LOST\n");
        else
            printf("WIN\n");
    }
    return 0;
}

！！2）http://acm.hdu.edu.cn/showproblem.php?pid=2516

题意：n个石子，每次都必须取最少一个，第一次可以取任意多个，以后取不能超过上次的2倍，谁先取完者胜、

推理发现其正好符合斐波那契数列，为斐波那契数时后手赢，其他先手赢。

还要注意其范围为2^31次方，可用map容器解决。

#include<stdio.h>
#include <map>
using namespace std;
map<int,int> v;
void isit()
{
    v[2]=1,v[3]=1;
    int a=2,b=3;
    while(b<2147483648)
    {
        int c=a+b;
        v[c]=1;
        a=b;
        b=c;
    }
}
int main()
{
    int n;
    isit();
    while(~scanf("%d",&n)&&n)
    {
        if(v[n])
            printf("Second win\n");
        else
            printf("First win\n");
    }
    return 0;
}

！！3）http://acm.hdu.edu.cn/showproblem.php?pid=2147

题意：给定一个m*n的矩阵，放一个石子在右上角，每次可以向下，向左，或者下左（对角）移动，谁先移动到右下角胜。

假如m和n有一个偶数，那么先手总能够维持这个偶数直到赢，否则他会输。

#include<stdio.h>

int main()
{
    int n,m;
    while(~scanf("%d %d",&n,&m))
    {
        if(n==0||m==0)
            break;
        if(n%2==1&&m%2==1)
            printf("What a pity!\n");
        else
            printf("Wonderful!\n");
    }
}

！！4）http://acm.hdu.edu.cn/showproblem.php?pid=3951 （奇偶性博弈）

题意：n个硬币放成一圈，每次最多取连续k个，不能不取。最后取完者胜、

分析：n个硬币，不论n是奇数偶数，后手总能够在第一轮把它变成对称两部分的状态，对称状态下后手肯定赢。

那么先手能赢只能是k>=n或者每次只能取一个且n是奇数。

#include <cstdio>
int main()
{
    int T;
    scanf("%d",&T);
    for(int cas=1;cas<=T;cas++)
    {
        int m,n;
        scanf("%d%d",&m,&n);
        printf("Case %d: ",cas);
        if(n>=m || n==1&&m%2==1)
            printf("first\n");
        else
            printf("second\n");
    }
}

觅规律博弈小记（更新）

相关推荐