巴什博弈（Bash Game）

简述

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

题解

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

1. 如果$n = m + 1$，由于一个人最少取$1$个，最多取$m$个，所以先手无论拿走多少个，后手都能一次拿走剩余物品，后手胜
2. 如果$n = （m + 1）\times r + s$，($r$为自然数，$s\leq m$)，先手取胜的方式为：先手第一次拿走$s$个物品，如果后手拿走$k(k \leq m)$个，那么先手在拿走$m + 1 – k$个，即这一轮两人拿走的数和为$m + 1$，并且由于第一次先手拿走了$s$个，所以剩下$(m + 1) \times (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;
}