题解：AT_kupc2016_i 一坨日文看不懂思密达

2huk · 2024-11-22 15:35:08 · 题解

upd on 26/7/15：修改代码错误，修改表述。感谢 xingchen666（link）。

把 Eli 先生及其分身称为“机器人”，Eli- gen 称为等级为 gen 的机器人。

考虑只有一次询问怎么做。

考虑 DP。设 f(i, j) 表示若最开始有一个等级为 i 的机器人，在 j 秒内最多能发多少张纸巾。转移有：

表示接下来这个机器人是否复制至少一个。当然后者能转移的前提是 j \ge ic。答案为 f(1,n)。

不难发现一个机器人最终的等级不会很大。升到某个级别的所花时间是一个等差数列，也就是说它的等级最大 \sqrt n。所以第一维是 \mathcal O(\sqrt n) 的。所以一次询问的复杂度是 \mathcal O(n \sqrt n)。

但是 f 的值会很大（所以题目要求取模），这个 \max 不好做。写高精度复杂度肯定不对。因此考虑挖掘一些性质，避开这个比较，直接转移。

注意到，让等级为 i 的机器人再复制一个后，答案至少为 2(j-ci)，即这两个不会再复制，而是一直发纸巾到结束。

那么如果 2(j-ci) \ge j，即复制一个一定不劣于不复制，那么一定选择复制。换言之 f(i,j) 会从 f(i,j-ci)+f(i+1,j-ci) 转移过来。

否则如果 j > 2(j-ci)，是否不复制一定最优呢？

是的。因为这等价于 j < 2ci，其意义是剩下的 j 时间内无法复制 \ge 2 个机器人，也就是最多复制 1 个。而复制 1 个不优，所以就不复制了。换言之 f(i,j) 会从 f(i,j-ci)+f(i+1,j-ci) 转移过来。

这样就解决了一次询问。

考虑多次询问。

注意到最终能直接或间接转移到 f(i,j) 的所有状态 f(i',j') 一定满足 j \equiv j' \pmod c。这里有点类似完全背包。

所以重新令 f'(i,j)=f(i,jc)。不难发现：

考虑答案。首先有 f'(1,\lfloor n/c \rfloor) \times c。乘 c 的原因是第二种转移时状态值不对。表示前 \lfloor n/c \rfloor c 的时间的贡献。

然后考虑最后 n \bmod c 的时间。显然在这点时间里没有机器人能来的及再复制。因此我们记录 g(i,j) 表示考虑一个等级为 i 的机器人在 j 个时间内纸巾数量最多的情况下，最多复制几个机器人（包括自己）。

所以答案为 f'(1,\lfloor n/c \rfloor) \times c + g(1,\lfloor n/c \rfloor) \times (n \bmod c)。

转移范围的话，第一维从 500 \to 1，第二维从 0 \to 10^5 即可。注意要滚动数组。

:::success[Code]

提交记录

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, P = 1e9 + 7;

int q, n, c;
int f[2][N], g[2][N];

signed main() {
    for (int i = 498; i; -- i ) {
        memset(f[i & 1], 0, sizeof f[i & 1]);
        memset(g[i & 1], 0, sizeof g[i & 1]);
        for (int j = 0; j < N; ++ j ) {
            if (j >= i * 2) {
                f[i & 1][j] = (f[i + 1 & 1][j - i] + f[i & 1][j - i]) % P;
                g[i & 1][j] = (g[i + 1 & 1][j - i] + g[i & 1][j - i]) % P;
            } else {
                f[i & 1][j] = j;
                g[i & 1][j] = 1;
            }
        }
    }

    cin >> q;
    while (q -- ) {
        cin >> n >> c;
        cout << (1ll * f[1][n / c] * c + 1ll * g[1][n / c] * (n % c)) % P << '\n';
    }

    return 0;
}