[数据结构与算法]三种博弈模板

威佐夫博弈：

原理：https://blog.csdn.net/qq_41311604/article/details/79980882

有两堆石子，数量任意，可以不同。游戏开始由两个人轮流取石子。游戏规定，每次有两种不同的取法，一是可以在任意的一堆中取走任意多的石子；二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目，如果轮到你先取，假设双方都采取最好的策略，问最后你是胜者还是败者。

Input

输入包含若干行，表示若干种石子的初始情况，其中每一行包含两个非负整数a和b，表示两堆石子的数目，a和b都不大于1,000,000,000。

Output

输出对应也有若干行，每行包含一个数字1或0，如果最后你是胜者，则为1，反之，则为0。

Sample Input

2 1
8 4
4 7

Sample Output

0
1
0

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		if(n>m)swap(n,m);
		int k=((m-n)*((sqrt(5.0)+1)/2)); 
		if(n==k)puts("0");
		else puts("1");
	}
	return 0;
}

巴什博弈

虽然不想，但是现实总归是现实，Lele始终没有逃过退学的命运，因为他没有拿到奖学金。现在等待他的，就是像FarmJohn一样的农田生涯。

要种田得有田才行，Lele听说街上正在举行一场别开生面的拍卖会，拍卖的物品正好就是一块20亩的田地。于是，Lele带上他的全部积蓄，冲往拍卖会。

后来发现，整个拍卖会只有Lele和他的死对头Yueyue。

通过打听，Lele知道这场拍卖的规则是这样的：刚开始底价为0，两个人轮流开始加价，不过每次加价的幅度要在1～N之间，当价格大于或等于田地的成本价 M 时，主办方就把这块田地卖给这次叫价的人。

Lele和Yueyue虽然考试不行，但是对拍卖却十分精通，而且他们两个人都十分想得到这块田地。所以他们每次都是选对自己最有利的方式进行加价。

由于Lele字典序比Yueyue靠前，所以每次都是由Lele先开始加价，请问，第一次加价的时候，
Lele要出多少才能保证自己买得到这块地呢？

Input

本题目包含多组测试，请处理到文件结束(EOF)。每组测试占一行。
每组测试包含两个整数M和N(含义见题目描述，0<N，M<1100)

Output

对于每组数据，在一行里按递增的顺序输出Lele第一次可以加的价。两个数据之间用空格隔开。
如果Lele在第一次无论如何出价都无法买到这块土地，就输出"none"。

Sample Input

4 2
3 2
3 5

Sample Output

1
none
3 4 5

题解：题意可看成，有M块石子，两人轮流拿，谁先拿完谁赢，每次所拿石子大于0小于等于N。

当N>=M是，先加价者必胜

?当N<M时，如果m%(n+1)==0则先手必败（即设先手第一回拿x个（1<=x<=n），后手总会拿n+1-x个,最后轮到先手时还剩下m=n+1，则先手必输），即无论轮到谁开始拿时，遇到m%(n+1)==0必输。

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
	int n,m;
	while(cin>>m>>n)
	{
		if(n>=m)
		{
			while(m<n)
			{
				printf("%d ",m);
				m++;
			}
			printf("%d\n",m);
		} 
		else
		{
			if(m%(n+1)==0)puts("none");
			else 
			{
				int t=m%(n+1);	 
				printf("%d\n",t);
			}
		}
	}
	return 0;
}

Nim博弈：
原理：https://blog.csdn.net/u013514928/article/details/69055286

通常的Nim游戏定义：有若干堆石子，每堆石子的数量都是有限的，合法的移动是“选择一堆石子并拿走若干颗（不能不拿）”，如果轮到某个人时所有的石子堆都已经被拿空了，则判负（因为他此刻没有任何合法的移动）。”

m堆石子,两人轮流取.只能在1堆中取.取完者胜.先取者负输出No.先取者胜输出Yes,然后输出怎样取子.例如5堆 5,7,8,9,10先取者胜,先取者第1次取时可以从有8个的那一堆取走7个剩下1个,也可以从有9个的中那一堆取走9个剩下0个,也可以从有10个的中那一堆取走7个剩下3个.

Input

输入有多组.每组第1行是m,m<=200000. 后面m个非零正整数.m=0退出.

Output

先取者负输出No.先取者胜输出Yes,然后输出先取者第1次取子的所有方法.如果从有a个石子的堆中取若干个后剩下b个后会胜就输出a b.参看Sample Output.

Sample Input

2
45 45
3
3 6 9
5
5 7 8 9 10
0

Sample Output

No
Yes
9 5
Yes
8 1
9 0
10 3

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e6+6;
int a[N];
int main()
{
	int i,j,k;
	int n,m,x,y;
	while(~scanf("%d",&n)&&n)
	{
		scanf("%d",&a[0]);
		m=a[0];
		for(i=1;i<n;i++)
			scanf("%d",&a[i]),m=m^a[i];
		if(m==0)puts("No");
		else
		{
			puts("Yes");
			for(i=0;i<n;i++)
			{
				k=m^a[i];	
				if(k<a[i])
					printf("%d %d\n",a[i],k);
			}
		}
	}
	return 0;
}

一年在外 父母时刻牵挂
春节回家 你能做几天好孩子吗
寒假里尝试做做下面的事情吧

陪妈妈逛一次菜场
悄悄给爸爸买个小礼物
主动地 强烈地 要求洗一次碗
某一天早起 给爸妈用心地做回早餐

如果愿意 你还可以和爸妈说
咱们玩个小游戏吧 ACM课上学的呢～

下面是一个二人小游戏：桌子上有M堆扑克牌；每堆牌的数量分别为Ni(i=1…M)；两人轮流进行；每走一步可以任意选择一堆并取走其中的任意张牌；桌子上的扑克全部取光，则游戏结束；最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负，我只想问大家：
――“先手的人如果想赢，第一步有几种选择呢？”

Input

输入数据包含多个测试用例，每个测试用例占2行，首先一行包含一个整数M(1<M<=100)，表示扑克牌的堆数，紧接着一行包含M个整数Ni(1<=Ni<=1000000，i=1…M)，分别表示M堆扑克的数量。M为0则表示输入数据的结束。

Output

如果先手的人能赢，请输出他第一步可行的方案数，否则请输出0，每个实例的输出占一行。

Sample Input

3
5 7 9
0

Sample Output

1

#include<cstdio>
#include<iostream>
using namespace std;
const int N=1e6+6;
int a[N];
int main()
{
	int i,j,k;
	int n,m,x,y;
	while(~scanf("%d",&n)&&n)
	{
		scanf("%d",&a[0]);
		m=a[0];
		for(i=1; i<n; i++)
			scanf("%d",&a[i]),m=m^a[i];
		int s=0;
		for(i=0; i<n; i++)
		{
			k=m^a[i];
			if(k<a[i])
				s++;
		}
		printf("%d\n",s);
	}
	return 0;
}