HDU 1846 Brave Game 博弈

题目地址: http://acm.hdu.edu.cn/showproblem.php?pid=1846


首先来玩个游戏,引用杭电课件上的:

(1) 玩家:2人;
(2) 道具:23张扑克牌;
(3) 规则:
游戏双方轮流取牌;
每人每次仅限于取1张、2张或3张牌;
扑克牌取光,则游戏结束;
最后取牌的一方为胜者。

      想一下。。

      首先申明一点,博弈的讨论是在大家都玩的最好的情况下讨论的。(如果2个玩家智商有差别,那就没法讨论了~~~~开个玩笑哈。)

      介绍概念:P点 即必败点,某玩家位于此点,只要对方无失误,则必败;

                        N点 即必胜点,某玩家位于此点,只要自己无失误,则必胜。

定理:

     一、 所有终结点都是必败点P(上游戏中,轮到谁拿牌,还剩0张牌的时候,此人就输了,因为无牌可取);

    二、所有一步能走到必败点P的就是N点;

    三、通过一步操作只能到N点的就是P点;

    自己画下图看看。

    x :0  1  2  3  4  5  6  7  8  9  10。。。

pos:P   N N  N  P N  N  N  P N   N 。。。

    所以若玩家甲位于N点。只要每次把P点让给对方,则甲必胜;

   反之,若玩家甲位于P点,他每次只能走到N点,而只要乙每次把P点让给甲,甲必败;

所以当n%(m+1)==0那么处于p点,必败,否则赢



代码如下:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;

/*
freopen("input.txt",  "r", stdin);
freopen("output.txt", "w", stdout);
*/

int main()
{
    int n,m,t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        if(n>m&&n%(m+1)==0)
            printf("second\n");
        else
            printf("first\n");
    }
    return 0;
}


原文地址:https://www.cnblogs.com/xinyuyuanm/p/3019548.html