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<<20using 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;elsehigh=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;elsehigh=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;}