Poj-3922 A simple stone game（k倍动态减法）

墨蓝 2023-10-11 09:37 21阅读 0赞

题意：

游戏是这样的:两个玩家以一堆n个石头开始游戏。他们轮流从石堆里取石头，每次至少取一块。先走的人第一步最多可以拿n-1块石头。从那时起，一个玩家最多可以拿k倍于他的对手上次拿的石头。例如，如果一个玩家轮流拿m块石头，那么另一个玩家下一次最多可以拿k×m块石头。谁拿了最后一块石头，谁就赢了这场比赛。

题解：

原文：[k倍动态减法][k]

斐波那契博弈是本题当k==2的一种特殊情况：

当k==1的时候：

当n=2^i (i^2 把i和2按位异或) 的多少次方的时候，那么这就是一个必败态，因为此时k==1，那么你把它化为二进制，这个时候拿掉二进制的最后一个1，那么对方必然不能拿走倒数第二位的1，因为他不能拿的比你多。你只要按照这个策略对方一直都不可能拿完。所以你就会赢。

而当分解的二进制中只有一个1时，因为第一次先手不能全部取完，所以后手一定有办法取到最后一个1，所以必败！  
          举个例子，当 n = 6 = （110）时:  
                 第一轮：先手第一次取最右边的1，即2个，此时还剩4（100）个，后手能取1或2个；  
                 第二轮：假如上轮后手取的两个，先手再取两个直接赢了  
                               假如后手取了一个，那么还剩三个，自己只能去1个，以后也只能取一个，所以必胜！

当 k = 2 时，赤裸裸的Fibonacci博弈了，具体这儿不多说，自己再上述博客已写的很明白了。其实n经拆解后也可以表示成二进制的形式，用 k = 1时的方法来理解，比如 n = 11 = 7 + 3 + 1，可表示成 10101；

当 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=数列中的数，则必败，否则必胜；必胜时还要求输出第一步取法，其实就是分解的数列中最小的一个

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<iostream>
     4 #include<algorithm>
     5 using namespace std;
     6 const int maxn=20000005;
     7 int a[maxn],b[maxn];
     8 int main()
     9 {
    10     int t,k,n,p=0;
    11     scanf("%d",&t);
    12     while(t--)
    13     {
    14         scanf("%d%d",&n,&k);
    15         a[0]=b[0]=1;
    16         int i=0,j=0;
    17         while(n>a[i])
    18         {
    19             i++;
    20             a[i]=b[i-1]+1;
    21             while(a[j+1]*k<a[i])
    22                 j++;
    23             if(k*a[j]<a[i])
    24                 b[i]=b[j]+a[i];
    25             else b[i]=a[i];
    26         }
    27         if(n==a[i])
    28             printf("Case %d: lose\n",++p);
    29         else
    30         {
    31             int ans=0;
    32             while(n)
    33             {
    34                 if(n>=a[i])
    35                 {
    36                     n-=a[i];
    37                     ans=a[i];
    38                 }
    39                 i--;
    40             }
    41             printf("Case %d: %d\n",++p,ans);
    42         }
    43     }
    44     return 0;
    45 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11369584.html

[k]: https://blog.csdn.net/tbl_123/article/details/24884861?utm_source=tuicool&utm_medium=referral
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif