巴什博弈（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;
}