ZOJ 3452 Doraemon's Stone Game（博弈）

ZOJ的博弈题目，主角是哆啦A梦和多啦美，下面简称为A和B

游戏背景是两个人相互取石子，石子有黑白两种颜色，每个人只能去对应颜色的石子。谁不能操作就算输。

游戏规则

1 A只能拿白色的石头，也就是w的石头，B只能拿黑色的石头，也就是b的石头。

2每个人每次只能拿走一块石头

3 每堆石头块最多有两块石头，玩家有两种取石头的方式，可以从石头块的上面拿，也可以从石头快的下面拿。如果从下面拿，那么这一堆石头块就会消失，此时最底下上面那块石头会消失。这是关键。

题目的输入数据：首先输入石头块的种类N，简单排列一下知道有 b, w wb,bw,aa,bb这六种。

字符串从左到右代表石头块从上到下的顺序。

接下来N行，每一行一个字符串和数字，代表石头块的种类和数量。

最后问你A先手和后手的胜负情况。

首先分析下情况：在给定的情况下，每个人可以操作的步数（或者说回合数）基本可以确定。

那么谁的可操作数大，那么谁就可以在对方用尽操作步数以后获胜。

那么最后问题就简化为，说的可操作步数多，谁赢。这一点比较容易想到。

解题关键是上面说的关键部分，当拿走最底下一块以后这堆石头会消失，那么对方就会少一种可以操作的方式。

这样每次可操作步数，会受到对方选择而改变。

但这也是解题的思路。

当对方拿走wb这堆石头，我就少了一个w可以拿，那我的可以操作的步数就少了，这样的情况对我不利。那么轮到我操作的时候，我就拿bw的石堆。这样对方可以操作的步数也少了。这样情况就趋于平衡。

最后场面只会有两种情况，纯色的黑白石堆和多的wb石堆或者bw石堆。

这时候，情况就大大简化，统计下双方可以操作的步数就可以知道谁赢。

假设最后只有wb有X堆，我先手的情况下可以操作（X+1）/2次，后手的情况下可以操作X/2次；

假设最后只有bw有Y堆，我先手的情况下可以操作（Y+1）/2次，后手的情况下可以操作Y/2次。

到这里，代码就比较容易写了。混合的情况如上面所说的，纯色的情况下，一个石头算一次操作步数。

其他人的博客我也看过，ans1和ans2的处理是把多种情况混合在一起，这样难得理解点。

我尽量把代码写的通俗易懂，更容易理解。

#include<iostream>
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
long long bb,ww,wb,bw;
char s[10];
int n;
void fprint(long long x,long long y)//先手的情况
{
	if(x>y)
		printf("win ");
	else
		printf("lose ");
}
void sprint(long long x,long long y)//后手的情况
{
	if(x>=y)
		printf("win\n");
	else
		printf("lose\n");
}
int main()
{
	int i,j,len;
	long long ans1,ans2,a;
	while(scanf("%d",&n)!=EOF)
	{
		bb=ww=wb=bw=0;//统计数据清零
		for(i=1;i<=n;i++)
		{
			scanf("%s %lld",&s,&a);//输入
			len=strlen(s);
			if(len==1)//统计单个石头的情况
			{
				if(s[0]=='b')
					bb+=a;
				else
					ww+=a;
			}
			else//统计两个石头的情况
			{
				if(s[0]=='b'&&s[1]=='b')
					bb+=2*a;
				else if(s[0]=='w'&&s[1]=='w')//纯色石子统计
					ww+=2*a;
				else if(s[0]=='b'&&s[1]=='w')
					bw+=a;
				else if(s[0]=='w'&&s[1]=='b')//混合石子统计
					wb+=a;
			}
		}
		if(bw==wb)//计算最后是哪一种混合石堆剩下
			bw=wb=0;
		else if(bw>wb)
			bw-=wb, wb=0;
		else
			wb-=bw, bw=0;

		if(bb==ww)//只用算多出的部分，可以缩减一下数据范围
			bb=ww=0;
		else if(bb>ww)
			bb-=ww, ww=0;
		else
			ww-=bb, bb=0;

		if(bw==wb)
		{
			fprint(ww,bb);
			sprint(ww,bb);
		}
		else if(bw>wb)//ans1值没有改变，可以省略一个，这样写容易看
		{//wb=0
			ans1=ww+bw;//bw这种石堆都可以拿
			ans2=bb+bw/2;//后手只能拿一半
			fprint(ans1,ans2);//输出先手的情况

			ans1=ww+bw;//我后手
			ans2=bb+(bw+1)/2;//对于别人来说是先手
			sprint(ans1,ans2);//输出后手的情况
		}
		else//ans2值没有改变，可以省略一个，这样写容易看
		{//bw=0
			ans1=ww+(wb+1)/2;//理由同上
			ans2=bb+wb;
			fprint(ans1,ans2);

			ans1=ww+wb/2;
			ans2=bb+wb;
			sprint(ans1,ans2);
		}
	}
	return 0;
}