HDU_2580 A simple stone game

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

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

以下摘自[ lccycc][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;
     }

[lccycc]: http://hi.baidu.com/lccycc_acm/item/a6f0dd0ec5c44a39f3eafcd3http://