学步园

poj:点击打开链接

题目意思是，一堆石子，两人轮流取，每次最少取一个，最多取前面一次对手取的石子的k倍。给出石子数和k，求先手的输赢状态，如果赢，输出第一步走法。

具体请看大神写的---->点击打开链接

貌似还是没有理解透彻，还是要多琢磨琢磨………

#include <stdio.h>

int a[1000000], b[1000000];

int main (void)
{
	int t, c = 0;
	scanf("%d", &t);
	while(t --)
	{
		c ++;
		int n, k;
		scanf("%d %d", &n, &k);
		a[0] = b[0] = 1;
		int i = 0; 
		int j = 0;
		//将n分解 
		while(n > a[i])
		{
			a[++i] = b[i - 1] + 1;
			while(a[j + 1] * k < a[i])
				j++;
			if(a[j] * k < a[i])
				b[i] = b[j] + a[i];
			else	
				b[i] = a[i];
		}
		
		int ans;
		printf("Case %d: ", c);
		
		if(n == a[i])//如果相等，那么必输 
			printf("lose\n");
		else//否则输出能分解成的最小的数作为第一步 
		{
			while(n)
			{
				if(n >= a[i])
				{
					n -= a[i];
					ans = a[i];
				}
				i --;
			}
			printf("%d\n", ans);
		}		
		
	}
	return 0;
} 

zoj3599:点击打开链接

题目意思是先手先从N个石子中选出n个作为起始的石子数，然后按照跟上一题一样的规则游戏，问想要先手赢，n有多少种不同的取值。

这题与上一题的过程大体一样，只是最后输出不一样。

看过大神写的东西以后，知道a数组存的是必败的状态，所以比N小的除了a数组中的数字其余都可以取，那么问题就简单了。

还要注意数组a，b要用long long 

#include <stdio.h>
#include <iostream>
using namespace std;

long long a[3000000], b[3000000];

int main (void)
{
	int t;
	scanf("%d", &t);
	while(t --)
	{
		int m;
		long long n;
		scanf("%d %lld", &m, &n);
		a[0] = b[0] = 1;
		int i = 0, j = 0; 
		while(n > a[i])
		{
			i ++;
			a[i] = b[i - 1] + 1;
			while(a[j + 1] * m < a[i])
				j++;
			if(a[j] * m < a[i])
				b[i] = b[j] + a[i];
			else
				b[i] = a[i];
		}
		long long ans;
		if(n == a[i])
			ans = (long long)n - i - 1;//因为n不能取N所以要减1 
		else
			ans = (long long)n - i;//i是a的下标，也正好是比N小的不能取的数的个数 
		printf("%lld\n", ans);
	}
	return 0;
}