MENU

巴什博弈(Bash Game)

April 15, 2018 • Read: 88 • 算法

简述

只有一堆 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 时,后手胜,反之先手胜

题目链接: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;
}

题目链接: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;
}

题目链接:HDU2147 kiki's game

题解

思路画出 PN 图,观察规律发现,若矩阵的行列 n、m同时为奇数的时候,先手必输,反之必赢

代码

#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;
}
Archives Tip
QR Code for this page
Tipping QR Code