巴什博弈(Bash Game)

简述

只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个,最后取光者胜

分析

我们称先进行游戏的人为先手,后进行游戏的人为后手

1. 如果n = m + 1,由于一个人最少取1个,最多取m个,所以先手无论拿走多少个,后手都能一次拿走剩余物品,后手胜

2. 如果n = (m + 1)* r + s,(r为自然数,s ≤ m),先手取胜的方式为:先手第一次拿走s个物品,如果后手拿走k(k ≤ m)个,那么先手在拿走m + 1 – k个,即这一轮两人拿走的数和为m + 1,并且由于第一次先手拿走了s个,所以剩下(m + 1) * (r - 1)个,以后一直保持这样的取法,无论后手拿走多少个,先手拿走的数量与后手的和总是凑成(m + 1)。那么我们得到如下结论:n % (m + 1)等于0时后手必胜,否则先手必胜

#include <iostream>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m)
        if(n%(m+1) == 0)
            cout<<"后手必胜"<<endl;
        else
            cout<<"先手必胜"<<endl;
    return 0;
}

变形

如果我们规定,最后取光者输,那么又如何考虑呢?

反过来想,如果先手拿走了n - 1个,那最后就剩下一个给后手了,后手就输了(因为这一个必拿,拿了他就是最后一个取光的人,他就输了),那么这个问题就转换为,有一堆n – 1个物品,最后取光者胜不就行了么,当然,操作方式和基础巴什博弈一样,永远跟对方凑(m + 1)。结论:(n - 1) % (m + 1)等于0时,后手胜,反之先手胜

例题

    1.HDU1846 Brave Game

思路:这题就是套个巴什博弈模板

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

    2.HDU4764 Stone

思路:这题就是刚才说的巴什博弈的变形,利用结论就行了

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

    3. HDU2147 kiki's game

思路画出PN图,观察规律发现,若矩阵的行列n、m同时为奇数的时候,先手必输,反之必赢,关于PN图画法思路,这里有一篇很好的文章

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    while(cin>>n>>m;)
    {
        if(n == 0 && m == 0)
            return 0;
        if(n % 2 == 1 && m % 2 == 1)
            printf("What a pity!\n");
        else
            printf("Wonderful!\n");
    }
    return 0;
}

参考文章:https://hrbust-acm-team.gitbooks.io/acm-book/content/game_theory/ba_shi_bo_yi.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器人网

工业机器人的三头六臂(常用运动学构形)

一、常用运动学构形 1、笛卡尔操作臂 优点:很容易通过计算机控制实现,容易达到高精度。 缺点:妨碍工作, 且占地面积大, 运动速度低, 密封性不好。 ①焊接、...

3297
来自专栏AI科技大本营的专栏

上海大学建了一个“突发事件语料库”,包括地震、恐怖袭击等5大类

本体最初是一个哲学上的概念,十多年前被引入计算机领域中作为知识表示的方法并被广泛使用。本体对于探索人的认知原理、发展自然语言理解技术和人机交互技术有重要意义。

1432
来自专栏小小挖掘机

COR“竞争市场条件下航班计划策略研究”论文解析

本文是针对发表在《Computers & Operations Research(计算与运筹)》上的一篇论文 “Airline flight schedule ...

3435
来自专栏量子位

AI何时能懂环境会沟通?别急,这个“你说我画”小游戏开了个好头 | 论文

安妮 夏乙 编译整理 量子位 出品 | 公众号 QbitAI 晚上9点,一下午开了3个会的你终于回到家,换了衣服瘫倒在沙发里。放空了三分钟之后,你缓过神来,喊了...

3125
来自专栏量子位

《黑镜》黑科技成真 | 解码脑电信号,AI重构脑中的画面

原作 TIM COLLINS Root 编译自 Dailymail 量子位 出品 | 公众号 QbitAI 上周五,一贯借黑科技刻画人性阴暗面的英剧《黑镜》刚出...

3239
来自专栏量子位

打游戏时领悟了“向死而生”,这个AI算法真的不虚强化学习

问耕 发自 凹非寺 量子位 出品 | 公众号 QbitAI ? 来自德国弗莱堡大学的研究团队,最近有了一个好玩的发现。 AI又在打游戏时掌握了新技能。 “向死而...

4167
来自专栏量子位

Facebook发布对话研究框架ParlAI,包含20多种常用数据集

李林 编译整理 量子位 出品 | 公众号 QbitAI ? 昨天,Facebook发布了开源的对话研究软件框架ParlAI。 GitHub地址:facebook...

2674
来自专栏QQ大数据团队的专栏

聚类算法如何应用在营收业务中——个性化催费的尝试

932
来自专栏人工智能头条

上海大学建了一个“突发事件语料库”,包括地震、恐怖袭击等5大类

1442
来自专栏VRPinea

与家人一起互动,Holoplayer One带来家庭级裸眼全息体验

2884

扫码关注云+社区