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

相关文章

来自专栏张善友的专栏

Using sqlite with .NET

The other day I found that there is a .NET wrapper for sqlite. sqlite is a very ...

2278
来自专栏码匠的流水账

聊聊spring cloud的AbstractLoadBalancingClient

本文主要研究一下spring cloud的AbstractLoadBalancingClient

832
来自专栏互联网开发者交流社区

WinForm之窗体应用程序

1853
来自专栏谈补锅

记录C#常用的代码片段

using Newtonsoft.Json; using Newtonsoft.Json.Linq;

922
来自专栏成长道路

JDBC动态SQL语句连接orcale数据库的工具类

import java.sql.Connection; import java.sql.DriverManager; import java.sql.P...

2470
来自专栏跟着阿笨一起玩NET

GB2312转换成UTF-8与utf_8转换成GB2312

1831
来自专栏闻道于事

商城项目整理(三)JDBC增删改查

商品表的增加,修改,删除,订单表的增加,确认,用户表的查看,日志表的增加,查看 商品表建表语句: 1 create table TEST.GOODS_TABL...

5445
来自专栏菩提树下的杨过

MSDN官方的ASP.Net异步页面的经典示例代码

示例1.演示异步获取一个网址的内容,处理后显示在OutPut这一Label上 using System; using System.Web; using S...

1985
来自专栏DT乱“码”

简单的考勤系统

连接数据库类 package com.lianrui.it; import java.sql.Connection; import java.sql.Driv...

3469
来自专栏c#开发者

C# : row-clickable GridView and get and set gridview rows using JavaScript

Complete C# code: ---------------- using System; using System.ComponentModel; ...

2996

扫码关注云+社区