首页 > ACM题库 > HDU-杭电 > hdu 2580 a simple stone game-动态规划-[解题报告]C++
2014
02-10

hdu 2580 a simple stone game-动态规划-[解题报告]C++

a simple stone game

问题描述 :

After he has learned how to play Nim game,Mike begins to try another stone game which seems much easier.

The game goes like this:Two players start the game with a pile of n stones.They take stones from the pile in turn and every time they take at least one stone.The one who goes first can take at most n-1 stones for his first move .from then on a player can take at most k times as many stones as his opponent has taken last time.For example,if one player take m stones in his turn,then the other player can taken at most k * m stones next time.The player who takes the last stone wins the game.suppose that those two players always take the best moves and never make mistakes,your job is to find out who will definitely win the game.

输入:

The first line contains a integer t,indicating that there are t test cases following. (t<=20).Each test is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

输出:

The first line contains a integer t,indicating that there are t test cases following. (t<=20).Each test is a line consisting of two integer n and k.(2<=n<=10^8,1<=k<=10^5).

样例输入:

6 
16 1
11 1
32 2
34 2
19 3
100000000 100000

样例输出:

Case 1: lose
Case 2: 1
Case 3: 3
Case 4:lose
Case 5: 4
Case 6: 912

Hint
Hint
When k=1,the first player will definitely lose if the initial amount of stones is in the set {2,4,8,16,32,….}. Let’s call this kind of set “first-player-lose set” (必败点集合) When k=2,the first-player-lose set is {2,3,5,8,13,21,34,57…},which happens to be the Fibonacci sequence starting from 2.

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<set>
#include<vector>
#define MAXN 15
#define INF 1000
using namespace std;
int no[2000000],maxok[2000000];//no储存的是lose的数。  maxok【i】存的是在i之前能组成的最大的数; 
int main()
{
	int i,j,n,m,k,t,c,ca=0;
	for(scanf("%d",&t);t--;)
	{
		ca++;
		scanf("%d%d",&n,&k);
		if(n<=k+1)//n<=k+1时一定是输; 
		{
			printf("Case %d: lose\n",ca);
			continue;
		}
		int x=0,y=0;
		no[0]=maxok[0]=1;
		while(no[x]<n)
		{
			x++;
			no[x]=maxok[x-1]+1;//在x之前,最大的能符合的数是maxok【x-1】、加1后就不符合。 
			while(no[y+1]*k<no[x])//找小于no[x]的最大数:例子k=3时有15得到4 
				y++;
			if(no[y]*k<no[x])//前面得到的数可能不符合条件 
				maxok[x]=no[x]+maxok[y];//如果符合直接得no[x]+maxok[y];例子中推得15+maxok[3] 
			else
				maxok[x]=no[x];//否则能组成最大的数为本身。 
		}
		if(no[x]==n)//刚好组成n  说明这个数属于no数组。即不能由符合条件的数组成,lose! 
		{
			printf("Case %d: lose\n",ca);
			continue;
		}
		int ans;
		while(n)
		{
			if(n>=no[x])//不断的减去最大的数,剩下的最小的数就是了。 
			{
				ans=no[x];
				n-=no[x];
			}
			x--;
		}
		printf("Case %d: %d\n",ca,ans);
	} 
	return 0;
}
/*
k=3时:
  no={1,2,3,4,6,8,11,15,21,29
maxok=1,2,3,5,7,10,14,20
*/

解题转自:http://blog.csdn.net/cxb569262726/article/details/7841521


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n

  2. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯