一、巴什博奕(Bash Game)

这显然是一个很经典的问题：

1.问题描述

问题描述：有一堆石头甲同学先取，乙同学后取，每次可以拿1~m个石头，拿到最后一个石头的同学获胜，甲乙都是很聪明的同学。
分析：

当n≤m时，甲同学一次取完，甲同学获胜。
当n≥m+1时，不管第一次甲同学取多少，乙同学可取的数量都是小于m的，乙同学一次取完，乙获胜。
当乙同学第二次取不完时，即n≥2m+1时，如果n%(m+1)==0，因为甲乙都很聪明，我们先假设甲同学拿了k个，则聪明的乙同学一定会拿m+1-k个，这样，剩下的石头个数一定是m+1的整数倍，那么，到最后一次，还是剩下m+1个，甲同学先拿，不管他多少个，都是乙获胜(参考第一种情况)；
当n%(m+1) != 0时，n不是m+1的整数倍。假设n%(m+1)==s，那么聪明的甲同学第一次一定会拿s个，这样，问题就转变成第三种情况了，不过此时“攻守异形”了，甲同学获胜。
2.模板示例

二、P/N分析的动态规划解析

1.问题描述与定义

我们把刚才的问题换一下。假设甲乙俩同学拿石头的数量不是连续的，而是只能在数组{a1,a2,a3….}里面选。
我们定义P-position为前一个同学的必胜位置(即在这一步先手已经走了)，简称为P，
N-position为后一个同学的必胜位置(下一步轮到后手走)，简称为N
我们再假设数组为{1,4},即甲同学和乙同学每次要么拿1个石头，要么拿4个石头

2.dp打表

问题的dp状态表是这样的：

x表示石头的数量，pos表示此时的位置，位于P位置则是后手必胜，N位置则是先手必胜
这里必须再解释一遍，位置p表示位于此位置的前一个玩家必胜，N表示当前位于此位置的玩家必胜，假设先手位于P位置，则是后手必胜；先手位于N位置则是先手必胜。
计算：
当x=0时，即没有石头时，先手玩家没有石头可拿，先手输了，则是先手的前一个赢了，即后手赢了，所以位置为P。
x=1时，先手可以一次拿完，先手获胜 pos=N.
x = 2时，先手只能拿一个，剩下一个给后手拿，后手获胜pos=P.
x=3时，先手拿一个，后手拿一个，先手再拿一个，先手获胜 pos=N.。
x = 4时，先手一次拿完，先手获胜 pos=N.
x=5时，假设先手一次拿4个，退回到x-4=1的情况，后手胜pos=P；假设先手一次拿1个，退回到x-1=4的情况，此时的后手相当于第一种情况的”先手”，后手获胜pos=P.
x=8时，退回到x=7时，后手位于P（p表示前一个玩家必胜，即先手必胜）；但退回到x=4，后手位于N（p表示当前玩家必胜，即后手必胜），在两种情况矛盾的情况下，聪明的先手肯定选择拿1个，即第一种情况，先手必胜pos=N.
以此类推我们可以得到状态转移方程：
dp[i - a1] == dp[i - a2] ==dp[i - a3]….时dp[i] = dp[i-a1];
else dp[i] = !dp[i - 1]
结合dp边界 i < a1 时，dp[i] = P; 可以很方便的写出代码。

3.模板示例

三、实际应用

由于杭电oj好像打不开了，题目直接手写把。

1.解题步骤

p/n分析的题一般是先打表，用dp的方法打表会非常简单。
然后找规律解题
注意：尽管我们打表时使用dp,但在操作时,尤其是在二维p/n分析中不会使用，因为代码太长，容易出错。
况且，这类题目都是很有规律的题，用表找规律，只要一些简单的代码即可解题

2.hdu 1846 Brave Game

十年前读大学的时候，中国每年都要从国外引进一些电影大片，其中有一部电影就叫《勇敢者的游戏》（英文名称：Zathura），一直到现在，我依然对于电影中的部分电脑特技印象深刻。今天，大家选择上机考试，就是一种勇敢（brave）的选择；这个短学期，我们讲的是博弈（game）专题；所以，大家现在玩的也是“勇敢者的游戏”，这也是我命名这个题目的原因。当然，除了“勇敢”，我还希望看到“诚信”，无论考试成绩如何，希望看到的都是一个真实的结果，我也相信大家一定能做到的~

各位勇敢者要玩的第一个游戏是什么呢？很简单，它是这样定义的： 1、本游戏是一个二人游戏; 2、有一堆石子一共有n个； 3、两人轮流进行; 4、每走一步可以取走1…m个石子； 5、最先取光石子的一方为胜；

如果游戏的双方使用的都是最优策略，请输出哪个人能赢。

INPUT

输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m的含义见题目描述。

Output

如果先走的人能赢，请输出“first”，否则请输出“second”，每个实例的输出占一行。

过关代码；

#include<iostream>
using namespace std;
int main()
{
    int n,m;   
    cin >> n >> m;
    if (n % (m + 1) == 0) cout << "second" << endl;
    else cout << "first" << endl;
    return 0;
}

3.hdu 2147 kiki’s game

Problem Description Recently kiki has nothing to do. While she is bored, an idea appears in his mind, she just playes the checkerboard game.The size of the chesserboard is n*m.First of all, a coin is placed in the top right corner(1,m). Each time one people can move the coin into the left, the underneath or the left-underneath blank space.The person who can’t make a move will lose the game. kiki plays it with ZZ.The game always starts with kiki. If both play perfectly, who will win the game?

INPUT

Input contains multiple test cases. Each line contains two integer n, m (0 < n,m<=2000). The input is terminated when n=0 and m=0.

Output

If kiki wins the game printf “Wonderful!”, else “What a pity!”.

Sample Input

5 3
5 4
6 6
0 0

Sample Output

What a pity!
Wonderful!
Wonderful!

思路分析
先结合示例画出pn图（P先手必败，N先手必胜）
m == 1的情况

	1	2	3	4
1	N	N	N	N

m == 2 的情况

	1	2	3	4	5	6
1	P	N	P	N	P	N
2	N	N	N	N	N	N

n== m ==6的情况

	1	2	3	4	5	6
1	p	N	P	N	P	N
2	N	N	N	N	N	N
3	P	N	P	N	P	N
4	N	N	N	N	N	N
5	P	N	P	N	P	N
6	N	N	N	N	N	N

当n,m全为奇数是先手必败

#include <iostream>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<int, int> pir;
int main()
{
    int n, m;
    while (~scanf("%d%d",&n,&m))
    {
        if (n %2 != 0 && m % 2 != 0)
            puts("What a pity!");
        else
            puts("Wonderful!");
    }
    return 0;
}

3.codeforce 1695 B Circle Game

题目链接 https://codeforces.com/contest/1695/problem/B
这是一个经典的变种：尼姆游戏

c 刷题分享

巴什博奕与P/N分析的动态规划解析