巴什博弈（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时，后手胜，反之先手胜
例题
思路：这题就是套个巴什博弈模板
#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;
}思路：这题就是刚才说的巴什博弈的变形，利用结论就行了
#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;
}思路画出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