CF1989D Smithing Skill 题解

题意简述

有 $n$ 种武器和 $m$ 种材料。锻造第 $i$ 种武器消耗 $a_i$ 个同种材料，熔毁该武器返还 $b_i$ 个材料（$1 \le b_i < a_i \le 10^6$）。每次锻造得 $1$ 经验，每次熔毁也得 $1$ 经验。初始第 $j$ 种材料有 $c_j$ 个（$c_j \le 10^9$）。

你可以无限次锻造与熔毁，任意武器可用任意材料。求能获得的最大总经验值。

$1 \le n, m \le 10^6$。

---

转化为循环模型

将锻造+熔毁视为一个循环：消耗 $a_i$，返还 $b_i$，净消耗 $d_i = a_i - b_i$，获得 $2$ 经验。

锻造的门槛是当前材料数必须 $\ge a_i$。一次循环后材料数变为 $c - d_i$。

如果一直用同一种武器，从 $c$ 开始能完成的循环次数为：

$$\left\lfloor \frac{c - a_i}{d_i} \right\rfloor + 1 \quad (c \ge a_i) $$

等价于 $\left\lfloor \dfrac{c - b_i}{d_i} \right\rfloor$。

---

有效武器的筛选

对于同一个净消耗 $d$，门槛 $a$ 越小越好。令

$$s[d] = \min\{a_i \mid a_i - b_i = d\}$$

（若不存在则为 $+\infty$）。

若 $d_1 < d_2$ 且 $s[d_1] \le s[d_2]$，则武器 $2$ 被武器 $1$ 完全支配。去除被支配的选项后，剩下的武器满足：$d$ 递增时，$s[d]$ 递减。

构造两个数组：

• $q[k]$：第 $k$ 个有效武器的门槛 $a$（严格递减）；
• $p[k]$：第 $k$ 个有效武器的净消耗 $d$（严格递增）。

---

DP 计算 $f[i]$

设 $f[i]$ 表示手上有 $i$ 个同种材料时，能完成的最大循环次数。

对于给定的 $i$，在所有满足 $a \le i$ 的武器中应选哪个？材料多时用 $d$ 小的武器（循环次数 $\approx i/d$），材料少时只能用门槛低的武器（$d$ 大）。由于 "$d$ 越大 $a$ 越小"，满足 $a \le i$ 的武器恰好是序列的一段后缀。用指针 $now$ 找到后缀起点，然后转移：

c = i;
f[i] += (c - q[now]) / p[now];          // 整批循环
c = (c - q[now]) % p[now] + q[now];    // 剩余材料
while (c >= q[now]) c -= p[now], f[i]++; // 可能还有最后一次
f[i] += f[c];                           // 递归到更小的状态

大状态拆成整除部分 + 余数部分，余数递归到已算好的 $f$。

---

回答询问

对于每种初始材料 $c_j$：

• 若 $c_j < q[1]$（最优武器门槛都不够）：直接 $f[c_j]$；
• 否则，先用最优武器批量消耗到 $< q[1]$，再加 $f[\text{余数}]$。

if (c < q[1]) { ans += f[c]; continue; }
ans += (c - q[1]) / p[1];
c = (c - q[1]) % p[1] + q[1];
while (c >= q[1]) c -= p[1], ans++;
ans += f[c];

最终答案 = 总循环次数 $\times 2$。

---

复杂度

• 预处理 $s$：$O(n + \max a)$
• 构建 $q,p$：$O(\max a)$（$\max a \le 10^6$）
• DP $f$：$O(\max a)$
• 回答询问：$O(m)$

总复杂度 $O(n + m + \max a)$，足以通过。

---

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1500000;
int n, m;
ll a[N], b[N], s[N], q[N], p[N], f[N], cnt = 0, now = 0, ans = 0;

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); }
    return x * f;
}

int main() {
    for (int i = 0; i <= 1000000; i++) s[i] = 1e9;
    n = read(); m = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    for (int i = 1; i <= n; i++) b[i] = read();
    for (int i = 1; i <= n; i++) {
        ll d = a[i] - b[i];
        if (a[i] < s[d]) s[d] = a[i];
    }
    cnt = 0;
    q[0] = 1e9; p[0] = 0;
    for (int i = 1; i <= 1000000; i++) {
        if (s[i] < q[cnt]) {
            q[++cnt] = s[i];
            p[cnt] = i;
        }
    }
    now = cnt;
    for (int i = 1; i <= 1000000; i++) {
        while (q[now] <= i && now > 0) now--;
        if (now < cnt) now++;
        else continue;
        ll c = i;
        f[i] += (c - q[now]) / p[now];
        c = (c - q[now]) % p[now] + q[now];
        while (c >= q[now]) c -= p[now], f[i]++;
        f[i] += f[c];
    }
    for (int i = 1; i <= m; i++) {
        ll c = read();
        if (c < q[1]) {
            ans += f[c];
            continue;
        }
        ans += (c - q[1]) / p[1];
        c = (c - q[1]) % p[1] + q[1];
        while (c >= q[1]) c -= p[1], ans++;
        ans += f[c];
    }
    printf("%lld\n", ans * 2);
    return 0;
}