HDU_2580 A simple stone game-蒲公英云

HDU_2580 A simple stone game

蔚落 2022-08-12 14:59 125阅读 0赞

刚开始看这一题时，就知道这根本不是一道简单题（对当时没学K倍动态减法的我来说），因为前几天刚做完一道斐波那契额数列的博弈而且它仅仅是这道题k=2的一个特例而已-_-|||。

以下摘自 lccycc

刚开始考虑k=1的时,先手的必败态只有2^i(i=1,2,3…)这几种情况而已；

将n分解成二进制，然后先手取掉最后一个1，.然后对方必然无法去掉更高的1，也不可能取奇数个，而对方取完我方至少还能拿掉最后一个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的分解，最后一位就是了。

P.s：题目的思想用到了k倍动态减法，同学可自动搜索学习。反正我是要去学习了，自己的智商太有限了……

#include <cstdio>
#include <cstring>
#include <iostream>
#define N 2000000
using namespace std;
int no[N],maxok[N];
int solve(int n,int k){
     if(n<=k+1)return 0;
     int x=0,y=0;
     no[0]=maxok[0]=1;
     while(no[x]<n)
     {
         x++;
         no[x]=maxok[x-1]+1;
         while(no[y+1]*k<no[x])
             y++;
         if(no[y]*k<no[x])
             maxok[x]=no[x]+maxok[y];
         else
             maxok[x]=no[x];
     }
     if(no[x]==n) return 0;
     int ans;
     while(n)
     {
         if(n>=no[x])
         {
             ans=no[x];
             n-=no[x];
         }
         x--;
     }
     return ans;
}
int main(){
    int t,n,k,Case=0;
    scanf("%d",&t);
    while(++Case<=t){
        scanf("%d%d",&n,&k);
        printf("Case %d: ",Case);
        int tmp=solve(n,k);
        if(tmp)printf("%d\n",tmp);
           else printf("lose\n");
    }
 return 0;
 }