首页 > ACM题库 > HDU-杭电 > HDU 1729 Stone Game-博弈论-[解题报告] C++
2013
12-21

HDU 1729 Stone Game-博弈论-[解题报告] C++

Stone Game

问题描述 :

This game is a two-player game and is played as follows:

1. There are n boxes; each box has its size. The box can hold up to s stones if the size is s.
2. At the beginning of the game, there are some stones in these boxes.
3. The players take turns choosing a box and put a number of stones into the box. The number mustn’t be great than the square of the number of stones before the player adds the stones. For example, the player can add 1 to 9 stones if there are 3 stones in the box. Of course, the total number of stones mustn’t be great than the size of the box.
4.Who can’t add stones any more will loss the game.

Give an Initial state of the game. You are supposed to find whether the first player will win the game if both of the players make the best strategy.

输入:

The input file contains several test cases.
Each test case begins with an integer N, 0 < N ≤ 50, the number of the boxes.
In the next N line there are two integer si, ci (0 ≤ ci ≤ si ≤ 1,000,000) on each line, as the size of the box is si and there are ci stones in the box.
N = 0 indicates the end of input and should not be processed.

输出:

For each test case, output the number of the case on the first line, then output “Yes” (without quotes) on the next line if the first player can win the game, otherwise output “No”.

样例输入:

3
2 0
3 3
6 2
2
6 3
6 3
0

样例输出:

Case 1:
Yes
Case 2:
No

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

HDU 1729

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

给出一些盒子,盒子有容量限制,有初始容量,每次给某一个盒子中添加石头。

添加的数量必须小于等于盒子中已有数量的平方。

感觉上有一点像 巴什博弈,当然肯定比那个复杂

对于上限为S,当前容量如果为C,如果C+C*C<S&&(C+1)+(C+1)*(C+1)>=S,那么对于(S,C)显然是一个必败态

因为你不管一次取多少,不可能直接获胜,而对方都能直接获胜。

那么就继续递归求C状态。

如果最大的必败T>当前的C,那么就求出C后继中最小,也就是S-C

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10005
#define LL long long
#define inf 1<<29
#define eps 1e-7
using namespace std;
int get_sg(int s,int c){
	int q=sqrt((double)s);
	while(q+q*q>=s)
		q--;
	if(c>q) return s-c;
	else return get_sg(q,c);
}
int main(){
	int n,cas=0;
	while(scanf("%d",&n)!=EOF&&n){
		int s,c;
		printf("Case %d:\n",++cas);
		int ans=0;
		while(n--){
			scanf("%d%d",&s,&c);
			ans^=get_sg(s,c);
		}
		if(ans)
			puts("Yes");
		else
			puts("No");
	}
	return 0;
}



解题报告转自:http://blog.csdn.net/acm_cxlove/article/details/7838563


  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环