P7790

yyandy · 2022-11-13 15:11:29 · 题解

关于题目的吐槽

感觉这道题没什么思维含量，但是却处处是细节，处处恶心人。
被某搬题人放在模拟赛里了，赛时根本不想动这道题。
感觉首先是一大堆数据范围，什么 K,M,T,Q 一大堆的，非常容易弄混。
当年的线上赛上没人通过这题大概也是因为这个原因。

题解

题意已经非常简洁了（虽然还是很吓人），这里就不再简化了。
首先仔细读一遍题，大概观察一下，就只有两种操作。
操作一是将一个数变为严格小于它的因数，操作二是在特殊点上原地不动。

不妨先考虑简单的情况，T=0，也就是没有特殊点。
考虑到进行操作一最少将原数除以 2。
所以操作一的次数肯定是不超过 O(\log w) 的。（其中 w 是值域，下同）
于是我们就可以预处理出 F_{i,j} 表示通过 j 步将 i 变为 1 的最小花费。
这个比较容易计算，每次枚举倍数转移即可。
时间复杂度 O(w\log w\log n)。
不理解的可以看一下这一部分代码。

for(int i=1;i<=N;++i){
    int Mlen=Maxlen[i];
    for(int j=(i<<1),c=2;j<=N;j+=i,++c){
        Maxlen[j]=max(Maxlen[j],Mlen+1);
        for(int k=0;k<=Mlen;++k)
            getmin(F[j][k+1],F[i][k]+d[c]);
    }
}

对于每一个 L_i，答案就是 F_{A/B,L_i}。

解决了这一个简单版本，思考 T > 0 时怎么解决。
对于 L_i 比较小的时候可以简单处理掉，只需要考虑 L_i 较大的时候。