【 HDU 2177 】取(2堆)石子游戏 （威佐夫博弈）

BUPT2017 wintertraining(15) #5C hdu2177

题意

两个人轮流取石子，可以取一堆的任意非负整数个或两堆取相同个，先取完的输。 给定若干组数据：a,b表示两堆的石子数量，求先手输还是赢，赢还要求第一步之后的两堆石子数，如果有取相同的方案，先输出。

题解

威佐夫博弈问题。 必输的状态（奇异局势）：（0，0），（1，2），（3，5），..（a_k,a_k+k）其中a_k是前面未出现过的最小的正整数。 有一些性质：每个正整数在必输状态中出现且仅出现一次。 于是可以计算并存储下必输状态(X,Y)，x[k]为第k个必输状态的较小的数，y[i]为必输状态中是较小的数i 对应的较大的数，z[i]为必输状态中较大的数i 对应的较小的数。 先手输的情况就是一开始就是必输态，也就是k=b-a，x[k]==a。 先手赢的情况，是将局面变成必输态: 取走两个相同的数后，差k不变，若a>x[k]，则可变成(x[k]，y[x[k]])。 只取第一堆： 若b在它所在的必输态中是较大的数（z[b]!=0），且a>z[b]，则可变成（z[b],b）。 只取第二堆：

1. 第二堆仍更大：若a在必输态中是较小的数(y[a]!=0)，且b>y[a]，则可变成（a,y[a]）。
2. 第二堆更小了：若a在必输态中是较大的数，因为b>a>z[a]，可以变成（z[a],a）。

这题数据比较水，错误的代码也ac了。按我现在的思路我也不敢说一定是正确的代码。 另外也可以用公式直接求出奇异局势： a_k = [k\cdot (1+√5)/2],b_k= a_k + k

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define N 1000005
using namespace std;
int a,b,vis[N<<1],x[N],y[N],z[N<<1],k;
int main() {
	for(int i=1;i<N;i++)
		if(!vis[i]){
			x[++k]=i;y[i]=i+k;z[i+k]=i;
			vis[i]=vis[y[i]]=1;
		}
	while(scanf("%d%d",&a,&b),a||b){
		if(x[b-a]==a)
			puts("0");
		else{
			puts("1");
			if(a>x[b-a]) printf("%d %d\n",x[b-a],y[x[b-a]]);
			if(z[b]&&a>z[b]) printf("%d %d\n",z[b],b);
			if(y[a]&&b>y[a]) printf("%d %d\n",a,y[a]);
			if(z[a])printf("%d %d\n",z[a],a);
		}
	}
	return 0;
}