首页 > 代码库 > Poj-3922 A simple stone game（博弈，k倍动态减法）
Poj-3922 A simple stone game（博弈，k倍动态减法）
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 310 | Accepted: 161 |
Description
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 take 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.
Input
Each test case is a line consisting of two integer n and k.(2<=n<=108,1<=k<=105).
Output
Sample Input
5 16 1 11 1 32 2 34 2 19 3
Sample Output
Case 1: lose Case 2: 1 Case 3: 3 Case 4: lose Case 5: 4
思路：
博弈论中的 K倍动态减法游戏，难度较大，参看了好多资料才懵懂！
此题可以看作 Fibonacci 博弈的扩展，建议没弄懂 Fibonacci博弈的先学那个，个人整理 http://blog.csdn.net/tbl_123/article/details/24033245 ；
而说扩展体现在数列不再是Fib数列，是根据 k 的值自行构造的，其它换汤不换药，具体构造方法如下：
这儿方便说明白，首先根据k的值分情况讨论：
1) 当 k = 1 时，必败态为 n = 2 ^ i, 因为我们把数按二进制分解后，拿掉二进制的最后一个1，那么对方必然不能拿走倒数第二位的1，因为他不能拿的比你多。你只要按照这个策略对方一直都不可能拿完。所以你就会赢。而当分解的二进制中只有一个1时，因为第一次先手不能全部取完，所以后手一定有办法取到最后一个1，所以必败！
举个例子，当 n = 6 = （110）时:
第一轮：先手第一次取最右边的1，即2个，此时还剩4（100）个，后手能取1或2个；
第二轮：假如上轮后手取的两个，先手再取两个直接赢了
假如后手取了一个，那么还剩三个，自己只能去1个，以后也只能取一个，所以必胜！
2) 当 k = 2 时，赤裸裸的Fibonacci博弈了，具体这儿不多说，自己再上述博客已写的很明白了。其实n经拆解后也可以表示成二进制的形式，用 k = 1时的方法来理解，比如 n = 11 = 7 + 3 + 1，可表示成 10101；
3) 当 k 取任意非零正值时，重点来了：
犹如Fibonacci博弈，我们首先要求一个数列，将n分解成数列中一些项的和，然后就可以按Fibonacci博弈的解决方法来完成，也可以按二进制的方法来理解，每次取掉最后一个1 还是符合上面的条件。
我们用a数组表示要被求的数列，b数组中的b[i]保存 a[0...i] 组合能够构造的最大数字。这儿有点难理解，所谓构造就是指n分解为Fib数相加的逆过程。举例说明，当k = 2 时，a[N]={1, 2, 3, 5, 8, 13, 21, 33....} （Fibonacci数组）；那么b[3] 即 1、2、 3 能够构造的最大数字，答案是4，有点匪夷所思？或许你会问为什么不是5、6或者其它的什么，其实是这样的 ，4 能分解成 1+3 是没有争议的，但5能分解成2+3吗? 不能，因为5本身也是Fibonacci数；6虽然能分解，但不是分解成1+2+3，而是分解成1+5。
经过上述，我们知道b[i] 是 a[0...i] 能够构造出的最大数字，那么a[i +1] = b[i]+1；因为a数组（Fib数组）所存的数字都是不可构造的（取到它本身就是必败态），显然a[0...i]构造的最大数字 + 1 即为下一个不可构造的数字了(a[i + 1])。
然后关于b[i]的计算，既然是a[0...i]构造最大数字，那么 a[i]是一定要选用的（这儿需要一定的推理，a[i]构造数字时，相邻的j个是不能同时用的，就像上述的2、3不能构造出5一样，推理请自己完成），那么要选用的下一项只能递减寻找，直到找到 a[t] 满足 a[t] * K < a[i] ，而b[t]就是a[0...t]所能构造的最大数字，再加上a[i], 即为a[0...i]能构造的最大数字，于是b[i] = b[t] + a[i]。
求的数列后，之后的工作就简单了，跟Fibonacci博弈一样一样的，如果n=数列中的数，则必败，否则必胜；必胜时还要求输出第一步取法，其实就是分解的数列中最小的一个，将见代码。
代码：
#include <stdio.h>
#define N 20000005
int a[N], b[N]; // a 为数列， b 保存 a[0...i] 能构造出的最大的数
int main()
{
int n, k;
int loop = 0, casei = 1;
scanf("%d",&loop);
while(loop --){
scanf("%d%d",&n,&k);
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] * k < a[i])
j ++;
if(k * a[j] < a[i])
b[i] = b[j] + a[i];
else
b[i] = a[i];
}
printf("Case %d: ", casei ++);
if(n == a[i])
printf("lose\n");
else{
int ans;
while(n){
if(n >= a[i]){ // 构成 n 的最小的数列中的数字，即为第一次要取的数字
n -= a[i];
ans = a[i];
}
i --;
}
printf("%d\n",ans);
}
}
return 0;
}