hdu 2486/2580 / poj 3922 A simple stone game 博弈论

思路：

这就是K倍动态减法游戏，可以参考曹钦翔从“k倍动态减法游戏”出发探究一类组合游戏问题的论文。

首先k=1的时候，必败态是2^i,因为我们把数二进制分解后，拿掉最后一个1，那么会导致对方永远也取不完，我们可以拿到最后一个1.

k=2的时候，必败态是斐波那契数列，因为任何一个整数n都可以写成两项斐波那契数的和，所以我们拿掉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 ] = b[ t ] + a[ i+1 ]

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

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

代码如下：

 #include<cstdio>

 int a[],b[];

 int main()

 {

     int i,j,t,n,k,c=,ans;

     scanf("%d",&t);

     while(t--){

         scanf("%d%d",&n,&k);

         i=j=;

         a[]=b[]=;

         while(a[i]<n){

             i++;

             a[i]=b[i-]+;

             while(a[j+]*k<a[i]) j++;

             if(a[j]*k<a[i]) b[i]=b[j]+a[i];

             else b[i]=a[i];

         }

         printf("Case %d: ",++c);

         if(a[i]==n) puts("lose");

         else{

             while(n){

                 if(n>=a[i]){

                     n-=a[i];

                     ans=a[i];

                 }

                 i--;

             }

             printf("%d\n",ans);

         }

     }

     return ;

 }

巴特西

hdu 2486/2580 / poj 3922 A simple stone game 博弈论

最新文章

热门文章