HDU 2177 取(2堆)石子游戏 Wythoff Game+输出方案

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

HDU 2177 取(2堆)石子游戏 Wythoff Game+输出方案

http://acm.hdu.edu.cn/showproblem.php?pid=2177

由于要输出方案，便 得复杂了。数据不是很大，首先打表，所有whthoff 的奇异局势。

然后直接判断是否为必胜局面。、

如果必胜，首先判断能否直接同时相减得到。这里不需要遍历或者二分查找。由于两者同时减去一个数，他们的差不变，而且ak=k*(sqrt(5)+1),bk=ak+k;

则可以通过二者的差直接定位，然后判断。

对于另外一种情况，其中一个减去某个数，得到奇异局势，则是分情况二分查找。

注意一些细节

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<map>
#define LL long long
#define N 1000000
#define inf 1<<20
using namespace std;
int a[500000],b[500000],cnt;
void Search1(int n,int m){
	int low=0,high=cnt,mid;
	while(low<=high){
		mid=(high+low)>>1;
		if(n==a[mid]){
			if(m>b[mid])
	    		printf("%d %d\n",a[mid],b[mid]);
			return;
		}
		if(a[mid]<n)
			low=mid+1;
		else
			high=mid-1;
	}
}
void Search2(int n,int m){
	int low=0,high=cnt,mid;
	while(low<=high){
		mid=(high+low)>>1;
		if(n==b[mid]){
			if(m>a[mid])
	    		printf("%d %d\n",a[mid],b[mid]);
			return;
		}
		if(b[mid]<n)
			low=mid+1;
		else
			high=mid-1;
	}
}
int main(){
	for(int i=0;i<500000;i++){
		a[i]=(int)(i*(sqrt(5.0)+1)/2);
		b[i]=a[i]+i;
		if(b[i]>=1000000){
			cnt=i;
			break;
		}
	}
	int n,m;
	while(scanf("%d%d",&n,&m)!=EOF&&n+m){
		if(n>m)
			swap(n,m);
		if(n==(int)((sqrt(5.0)+1)*(m-n)/2))
			printf("0\n");
		else{
			printf("1\n");
			if(m-n<cnt&&n-a[m-n]==m-b[m-n])
				printf("%d %d\n",a[m-n],b[m-n]);
			Search1(n,m);
			if(n!=m)
		    	Search1(m,n);
			Search2(n,m);
			if(n!=m)
		    	Search2(m,n);
		}
	}

	return 0;
}