学步园

转自：http://hi.baidu.com/huicpc0207/item/f11a06f36ecfe91484d278fd  http://blog.csdn.net/cxb569262726/article/details/7841521
题意：两人取一堆n个石子 先手不能全部取完 之后每人取的个数不能超过另一个人上轮取的数*K，给n，K判断先手必胜并求第一步最小取的数。

博弈题

这题的思考过程非常有意义。

当k=1的时候 可知必败局面都是2^i  将n分解成二进制，然后先手取掉最后一个1.然后对方必然无法去掉更高的1，而对方取完我方至少还能拿掉最后一个1 导致对方永远取不完。

当k=2的时候，必败局面都是斐波那契数列。利用“先手去掉最后一个1，则后手必不能去掉更高阶的1导致取不完”的思想，斐波那契数列有一个非常好的性质就是：任意一个整数可以写成斐波那契数列中的不相邻的项的和，于是将n写成这种形式，先取走最后一个1，对方能取的数是这个数*2，小于高2位的1，所以取不完。

当K的时候， 想办法构造数列，将n写成数列中一些项的和，使得这些被取到的项的相邻两个倍数差距>k 那么每次去掉最后一个1 还是符合上面的条件。设这个数列已经被构造了i 项，第 i 项为a[ i ]，前 i 项可以完美对1..b[ i ] 编码使得每个编码的任意两项倍数>K 那么有

a[ i+1 ] = b[ i ] + 1;这是显然的 因为b[ i ] + 1没法构造出来，只能新建一项表示

然后计算b[ i+1] 既然要使用 a[ i+1 ] 那么下一项最多只能是某个 a[ t ] 使得 a[ t ] * K < a[ i+1 ] 于是

b[ i +1] = b[ t ] + a[ i+1 ]

然后判断n是否在这个数列里面

如果在，那么先手必败。否则不停的减掉数列a中的项构造出n的分解，最后一位就是了。

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int maxn = 750000;
int lose[maxn],maxok[maxn];
int m,n;

void solve()
{
    scanf("%d %d",&n,&m);
    if(n <= m + 1)
    {
        puts("lose");
        return;
    }
    int i = 0,j = 0;
    lose[i] = maxok[i] = 0;
    while(lose[i] < n)
    {
        i++;
        lose[i] = maxok[i-1] + 1;
        while(lose[j+1] * m < lose[i])
        {
            j++;
        }
        if(lose[j] * m < lose[i])
        {
            maxok[i] = lose[i] + maxok[j];
        }
        else maxok[i] = lose[i];
    }
    if(lose[i] == n) puts("lose");
    else
    {
        int ans;
        while(n)
        {
            i--;
            if(n >= lose[i])
            {
                ans = lose[i];
                n -= lose[i];
            }
        }
        printf("%d\n",ans);
    }
    return;
}

int main()
{
    int cas;
    scanf("%d",&cas);
    for(int i=1;i<=cas;i++)
    {
        printf("Case %d: ",i);
        solve();
    }
    return 0;
}