找规律博弈小记（更新）

古城微笑少年丶 2022-08-26 00:53 191阅读 0赞

最近在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");
        }
    }

！！5）http://acm.hdu.edu.cn/showproblem.php?pid=3389 （阶梯博弈）

题意：给出n个盒子，编号1--n，在满足b>a && (a+b)%2==1 && (a+b)%3==0 && b不为空，的情况下从b中取出任意多个石子放入a总，不能操作者输，求先手输赢

分析：首先，要满足（a+b）%3==0 ,既为3的倍数，又（a+b）%2==1，既为奇数，所以（a+b）为 3 ， 6 ， 9， 15 ， 21...依次+6，发现周期为6

在一个周期 0 - - 6中

只有（1,2）（3 ，6 ）（4,5）满足条件，那么就可以从 2 6 5中取出其中石子，变为nim游戏。所以只要求 I%6 == 0 || 1 || 5，的值异或就行

#include <cstdio>
    int main()
    {
        int T,n,cas=1;
        scanf("%d",&T);
        for(int cas=1;cas<=T;cas++)
        {
            scanf("%d",&n);
            int ans=0,x;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&x);
                if(i%6==2 || i%6==0 || i%6==5)
                    ans^=x;
            }
            printf("Case %d: ",cas);
            printf(ans==0?"Bob\n":"Alice\n");
        }
        return 0;
    }

！！6）http://acm.hdu.edu.cn/showproblem.php?pid=1517

题意：给出p=1，博弈双方每次可以乘以2--9之间的数，谁先达到或超过 n 为胜者，求先手胜败。

分析：首先1 --- 9 区间先手胜。

10 --- 18 区间，先手输，先手不论乘以几，后手总可以乘以一个数超过。假设乘最小的2，后手乘以 9 ，变为18 超过 。

19 ---- 162 区间，先手胜，先手可以在第一次选择性乘以一个数让对手乘以最大的 9 达不到，然后在下一轮轻松达到赢。比如161，首先先手乘以9，后手发现乘以

最大的 9 也才 81 ，那么他会乘以最小的 2 ，后手乘以 9 ，结果162，超出161.赢！

162 ----324区间，先手输 ,假如163，先手发现乘以最大的 9 的话局面也不能再第二轮由自己控制，那么他乘以2，相当于163 / 2 = 82，在区间 19 --- 162中，可得后

手必赢，如果他乘以 9 的话，163 / 9 = 18余1，相当于19，那么也是输。

继续向下推理发现每次交替乘以 2 或 9 ，那么程序就很简单了。

#include <cstdio>
    int main()
    {
        __int64 n;
        while(~scanf("%I64d",&n))
        {
            int k=0;
            for(int i=9;i<n;){
                i*=k%2?9:2;
                k++;
            }
            printf(k%2==1?"Ollie wins.\n":"Stan wins.\n");
        }
        return 0;
    }

!!7) http://www.bnuoj.com/bnuoj/problem\_show.php?pid=4353

描述：给出一个m\*n的矩阵，每次可以选择一个点，把其右上角的格子全部删去，谁删掉了最坐下角的格子的话为输，求先手输赢。

分析：首先看 1 \* n 的格子，出了 1 \* 1 的其他的都先手赢，因为先手可以一次取完只给队友留校左下一个。

2 \* n 的格子，先手赢。看 2 \* 2 的，先手必定先取右上一个，那么剩下的后手不能一次取完，后手取完先手取剩下的给后手留给左下的。

2 \* 3 的先手赢，前面知 2 \* 2 的先手赢，那么谁能取到面对 2 \* 2 的则必胜，先手必先取最左上一个，那么不论后手怎么取都输。

2 \* n 的，都是先手赢，总可以推到前面的，而前面无论哪个都是先手赢。所以。。

3 \* n 的，先手赢，首先先手一定不能一次变成 2 \* n 的，因为后手面对2 \* n 的则先手必输，那么先手可以取到 2 \* n 多一个。那么他必胜。

推理发现除了 1 \* 1 的所有情况都是先手必胜。

#include <cstdio>
    int main()
    {
        int n,m,T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&n,&m);
            if(n==1 && m==1)
                printf("Alice\n");
            else
                printf("Bob\n");
        }
        return 0;
    }