巴什博弈(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 条评论
登录 后参与评论

相关文章

来自专栏CDA数据分析师

读累了看视频 :YouTube上最火的10个大数据视频

翻译 | 伯乐在线 - 柒柒 原文来自Eileen McNulty 无论你对大数据一无所知,还是想要拓展机器学习方面的知识;无论你有三小时,还是三分钟;无论你...

2317
来自专栏大数据

解析大数据基准测试—TPC-H or TPC-DS?

随着开源Hapdoop、Map/Reduce、Spark、HDFS、HBASE等技术的商用化,大数据管理技术得到了突飞猛进的发展。一般来说,大数据具有3V特性,...

2798
来自专栏PPV课数据科学社区

还在迷茫?点进来马上get→从零开始学数据分析最佳路线!

? 俗话说读万卷书,行万里路.不如阅人无数,阅人无数不如名师指路.可见一个好的导师是多么的重要,选择正确的路线,就能避免走许多弯路, 让自己站在巨人的肩膀上去...

2686
来自专栏大数据

大数据基本概念及技术

关注我的人都成为了月薪5w以上的技术大牛 ? 大数据是当前很热的一个词。这几年来,云计算、继而大数据,成了整个社会的热点,不管什么,都要带上“大数据”三个字才显...

2425
来自专栏华章科技

一篇文章解决你所有关于数据分析的问题!

比如说在生产线上,在生产的数据库里面,各种各样的数据,可能是银行的业务数据,也可能是电信运营商在交换机里面采集下来的数据等等,然后这些生产的数据通过ETL,是英...

932
来自专栏Crossin的编程教室

一行代码扫出“敬业福”

好吧,我承认有那么一点标题党。不过说起标题党这事儿,咱先来看看支付BAO,最近几天搞得全国人民都不安心工作的“集五福”: ? 好(shua)好(hou)的“集五...

3508
来自专栏CDA数据分析师

【资源】想进行数据科学项目却没有数据集?25个数据集网站汇总

原作者 Kunal Jain 编译  Mika 本文为 CDA 数据分析师原创作品,转载需授权 前言 如果用一个句子总结学习数据科学的本质,那就是: 学习数据科...

3118
来自专栏数据科学与人工智能

【数据科学】数据科学,你不可不读的十三本书!

大数据已经成为这个时代的标志,如何理解和运用大数据,也是我们这个时代的重中之重。今天,小编从“实战”和“拓展”两个方向,为各位推荐几本书,希望能够有助于你在大数...

2228
来自专栏数据科学与人工智能

【数据挖掘】模型、工具、统计、挖掘与展现

1. 数据分析多层模型介绍 这个金字塔图像是数据分析的多层模型,从下往上一共有六层: ? 底下第一层称为Data Sources 元数据层。 比如说在生产线上,...

2306
来自专栏悦思悦读

大数据基本概念浅析及技术简介

大数据是当前很热的一个词。这几年来,云计算、继而大数据,成了整个社会的热点,不管什么,都要带上“大数据”三个字才显得时髦。大数据究竟是什么东西?有哪些相关技术?...

3417

扫码关注云+社区