首页 > ACM题库 > HDU-杭电 > hdu 2177 取(2堆)石子游戏-分治-[解题报告]C++
2013
12-30

hdu 2177 取(2堆)石子游戏-分治-[解题报告]C++

取(2堆)石子游戏

问题描述 :

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

输入:

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

输出:

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

样例输入:

1 2 
5 8
4 7
2 2
0 0

样例输出:

0
1
4 7
3 5
0
1
0 0
1 2

转载请注明出处,谢谢 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;
}

解题转自:http://blog.csdn.net/acm_cxlove/article/details/7836150


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1