1、巴什博弈
题目一：
Problem Description
1、 本游戏是一个二人游戏;
2、 有一堆石子一共有n个；
3、 两人轮流进行;
4、 每走一步可以取走1…m个石子；
5、 最先取光石子的一方为胜；
如果游戏的双方使用的都是最优策略，请输出哪个人能赢。
Input
输入数据首先包含一个正整数C(C<=100)，表示有C组测试数据。
每组测试数据占一行，包含两个整数n和m（1<=n,m<=1000），n和m
的含义见题目描述。
Output
如果先走的人能赢，请输出“first”，否则请输出“second”，
每个实例的输出占一行。
Sample Input
2
23 2
4 3
Sample Output
first
second
解题思路：
一次可以去走1,2,3…m个石子，容易得出该问题的PN图， 1,2,3...m
为必胜状态，m+1为必败状态，其余类推即可。所以只要n%(m+1) == 0
则先手必输反之先手必胜。
#include <iostream>
using namespace std;
int main() {
int n, a, b;
cin >> n;
while(n--) {
cin >> a >> b;
if(a%(b+1) == 0)
cout << "second\n";
else
cout << "first\n";
}
return 0;
}
题目二：
Problem Description
大学英语四级考试就要来临了，你是不是在紧张的复习？也许紧张
得连短学期的ACM都没工夫练习了，反正我知道的Kiki和Cici都是
如此。当然，作为在考场浸润了十几载的当代大学生，Kiki和Cici
更懂得考前的放松，所谓“张弛有道”就是这个意思。这不，Kiki
和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”？“双扣”？“红五”？还是“斗地主”？
当然都不是！那多俗啊~
作为计算机学院的学生，Kiki和Cici打牌的时候可没忘记专业，她
们打牌的规则是这样的：
1、 总共n张牌;
2、 双方轮流抓牌；
3、 每人每次抓牌的个数只能是2的幂次（即：1，2，4，8，16…）
4、 抓完牌，胜负结果也出来了：最后抓完牌的人为胜者；
假设Kiki和Cici都是足够聪明（其实不用假设，哪有不聪明的学生），
并且每次都是Kiki先抓牌，请问谁能赢呢？
Input
输入数据包含多个测试用例，每个测试用例占一行，包含一个整数n
（1<=n<=1000）。
Output
如果Kiki能赢的话，请输出“Kiki”，否则请输出“Cici”，每个实
例的输出占一行。
Sample Input
1
3
Sample Output
Kiki
Cici
解题思路：
题目中文，题意不解释。同样画出PN图，如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
N NPN N PNN P N N P N N P N
上图很容易画出，因为剩余1或2张牌时，后者可以一次取光获胜，当剩
余3张牌时，因为后者只能取1张或者2张，所以后者必败，一次类推就
可以得出上图的PN图。跟据PN图可以很容易的得出当牌的张数为3的倍
数时先手必败，反之先手必胜。
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int n;
while(cin >> n && n != EOF) {
if(n%3==0)
cout << "Cici\n";
else
cout << "Kiki\n";
}
return 0;
}题目三：
Problem Description
任何一个大学生对菲波那契数列(Fibonacci numbers)应该都不会
陌生，它是这样定义的：
F(1)=1;
F(2)=2;
F(n)=F(n-1)+F(n-2)(n>=3);
所以，1,2,3,5,8,13……就是菲波那契数列。
在HDOJ上有不少相关的题目，比如1005 Fibonacci again就是曾
经的浙江省赛题。
今天，又一个关于Fibonacci的题目出现了，它是一个小游戏，定
义如下：
1、 这是一个二人游戏;
2、 一共有3堆石子，数量分别是m, n, p个；
3、 两人轮流走;
4、 每走一步可以选择任意一堆石子，然后取走f个；
5、 f只能是菲波那契数列中的元素（即每次只能取1，2，3，5，
8…等数量）；
6、 最先取光所有石子的人为胜者；
假设双方都使用最优策略，请判断先手的人会赢还是后手的人会赢。
Input
输入数据包含多个测试用例，每个测试用例占一行，包含3个整数m,
n,p（1<=m,n,p<=1000）。
m=n=p=0则表示输入结束。
Output
如果先手的人能赢，请输出“Fibo”，否则请输出“Nacci”，每个
实例的输出占一行。
Sample Input
1 1 1
1 4 1
0 0 0
Sample Output
Fibo
Nacci
解题思路：
取石子问题，一共有3堆石子，每次只能取斐波那契数个石子，先取完
石子者胜利，问先手胜还是后手胜
可选步数为一系列不连续的数，用GetSG(计算) 最终结果是所有SG值
异或的结果。
#include <iostream>
#include <cstring>
using namespace std;
#define N 1005
int f[N];
int sg[N];
void fun() {
int i;
f[0]=1;
f[1]=1;
f[2]=2;
for(i=3;;i++) {
f[i] = f[i-1]+f[i-2];
if(f[i] > 1000)
break;
}
}
int dfs(int v) {
int i;
if(sg[v] != -1)
return sg[v];
bool visit[N] = {0};
for(i = 1; i < 16; i++) {
if(v >= f[i]) {
int temp = dfs(v-f[i]);
visit[temp] = 1;
}
}
for(i = 0; visit[i];i++);
return sg[v] = i;
}
int main() {
fun();
int m, n, p;
while(cin >> m >> n >> p && m+n+p != 0) {
memset(sg, -1, sizeof(sg));
int ans;
ans = dfs(m)^dfs(n)^dfs(p);
if(ans) cout << "Fibo\n";
else cout << "Nacci\n";
}
return 0;
}
#include<stdio.h>
#include<string.h>
#define N 1001
//f[]：可以取走的石子个数
//sg[]:0~n的SG函数值
//hash[]:mex{}
int f[N],sg[N],hash[N];
void getSG(int n)
{
int i,j;
memset(sg,0,sizeof(sg));
for(i=1;i<=n;i++)
{
memset(hash,0,sizeof(hash));
for(j=1;f[j]<=i;j++)
hash[sg[i-f[j]]]=1;
for(j=0;j<=n;j++) //求mes{}中未出现的最小的非负整数
{
if(hash[j]==0)
{
sg[i]=j;
break;
}
}
}
}
int main()
{
int i,m,n,p;
f[0]=f[1]=1;
for(i=2;i<=16;i++)
f[i]=f[i-1]+f[i-2];
getSG(1000);
while(scanf("%d%d%d",&m,&n,&p)!=EOF)
{
if(m==0&&n==0&&p==0)
break;
if((sg[m]^sg[n]^sg[p])==0)
printf("Nacci\n");
else
printf("Fibo\n");
}
return 0;
} 二、Nim博弈
Problem Description
大学时光是浪漫的，女生是浪漫的，圣诞更是浪漫的，但是Rabbit和Grass
这两个大学女生在今年的圣诞节却表现得一点都不浪漫：不去逛商场，不去
逛公园，不去和AC男约会，两个人竟然猫在寝食下棋……
说是下棋，其实只是一个简单的小游戏而已，游戏的规则是这样的：
1、 棋盘包含1*n个方格，方格从左到右分别编号为0，1，2，…，n-1；
2、 m个棋子放在棋盘的方格上，方格可以为空，也可以放多于一个的棋子；
3、 双方轮流走棋；
4、 每一步可以选择任意一个棋子向左移动到任意的位置（可以多个棋子位
于同一个方格），当然，任何棋子不能超出棋盘边界；
5、 如果所有的棋子都位于最左边（即编号为0的位置），则游戏结束，并
且规定最后走棋的一方为胜者。
对于本题，你不需要考虑n的大小（我们可以假设在初始状态，棋子总是位于
棋盘的适当位置）。下面的示意图即为一个1*15的棋盘，共有6个棋子，其中，
编号8的位置有两个棋子。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
| | | | | | | | |** | | | | | | |
大家知道，虽然偶尔不够浪漫，但是Rabbit和Grass都是冰雪聪明的女生，如
果每次都是Rabbit先走棋，请输出最后的结果。
Input
输入数据包含多组测试用例，每个测试用例占二行，首先一行包含一个整数m
（0<=m<=1000），表示本测试用例的棋子数目，紧跟着的一行包含m个整数Ki
(i=1…m; 0<=Ki<=1000)，分别表示m个棋子初始的位置，m=0则结束输入。
Output
如果Rabbit能赢的话，请输出“Rabbit Win!”，否则请输出“Grass Win!”，
每个实例的输出占一行。
Sample Input
2
3 5
3
3 5 6
0
Sample Output
Rabbit Win!
Grass Win!
解题思路：
裸的NIM博弈，直接异或即可。
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
int n, p;
while(cin >> n && n != EOF) {
if(n == 0) break;
int ans=0;
for(int i = 0; i < n; i++) {
cin >> p;
ans ^= p;
}
if(ans == 0) cout << "Grass Win!\n";
else cout << "Rabbit Win!\n";
}
return 0;
}
/*hdu1850
*简单NIM博弈，如果异或不为0，找出异或可以使其成为0的值
*if(num[j]>(ans^num[j]))这是关键。
*/
#include <iostream>
using namespace std;
int num[105];
int main() {
int t;
while(cin >> t && t) {
int ans = 0;
for(int i = 0; i < t; i++) {
cin >> num[i];
ans ^= num[i];
}
int cnt = 0;
for(int j = 0; j < t; j++) {
if(num[j] > (ans^num[j])) {
cnt++;
}
}
cout << cnt << endl;
}
return 0;
}
/*hdu1851j简单NIM博弈*/
#include <iostream>
using namespace std;
int main() {
int t, n, m, l;
cin >> t;
while(t--) {
cin >> n;
int ans = 0;
while(n--) {
cin >> m >> l;
ans ^= (m%(l+1));
}
if(ans == 0) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
/*hdu1907 NIM博弈
*全是1的时候，特判，数1的个数，奇数输，偶数赢了。
*/
#include?<iostream>
using namespace std;
int main() {
int t, num;
cin >> t;
while(t--) {
int ans = 0, flag = 0;
int p[50];
cin >> num;
for(int i = 0; i < num; i++) {
cin >> p[i];
if(p[i] != 1) flag=1;
ans ^= p[i];
}
if(flag) {
if(ans == 0) cout << "Brother\n";
else cout << "John\n";
}
else {
if(num%2 != 0) cout << "Brother\n";
else cout << "John\n";
}
}
return 0;
}
/* hdu2147
* 判断P和N的状态，画出图标即可。利用SG函数的基本性质。
* P后面的都是N，N后面的一定存在一个P状态。
* 观察图表规律知道，n和m都是奇数时候，必败。
*/
#include <iostream>
using namespace std;
int main() {
int n, m;
while(cin >> n >> m != EOF) {
if(n == 0 && m == 0) break;
if(n&1 && m&1) cout << "What a pity!\n";
else cout << "Wonderful!\n";
}
return 0;
}
/* hdu2149 简单的巴什博弈。
*/
#include <iostream>
using namespace std;
int main() {
int m, n;
while(cin >> m >> n != EOF) {
if(m%(n+1) == 0) {
cout << "none\n";
continue;
}
else if(n > m) {
for(int i = m; i < n; i++)
cout << i << ' ';
cout << endl;
}
else cout << m%(n+1) << endl;//这里是开始的时候，如果先出m%(n+1)个，那么剩下的就是必败态了。
}
return 0;
}