usaco-3.1.6 邮票

GitHub跳转原题关系图返回列表

把“某邮资能否贴出”换成“最少需要几张”，用一个大整数的第 v 位表示邮资 v 可达；每轮对所有面值做左移按位或，重复至多 K 次后数连续 1 前缀。

OJ: roj

题目 ID: 2045

难度:普及+/提高-

标签:动态规划背包完全背包位运算python

创建: 2026-10-01 04:54

更新: 2026-10-07 13:50

前置题目
leetcodecn perfect-squares完全平方数A 教的 min 型完全背包 dp[i]=min(dp[i-j*j]+1) 正是 B 正解「第一步：把问题换成最少张数」后照搬的转移 f(v)=1+min f(v-s)，只把物品从平方数换成邮票面值；B 的主要难度来自第一位表示可达性的位并行实现与 K·max A 上界，故属模板级复用。luogu B3611【模板】传递闭包B 的第三步把邮资可达性编码成整数位集，用 `reachable << s` 表示集合整体加 s、按位或表示求并，直接沿用 A 教的「可达集合编码成整数位集并用大整数 OR 合并」这一步，只是把 Warshall 的行并入换成按面值平移的 K 轮集合迭代，并额外叠加最少张数建模与上界 K·maxA。luogu P2347[NOIP 1996 提高组] 砝码称重B 的正解直接复用 A 教的「可达性编码成位集合 + 左移或转移」这一状态设计与关键实现，只在外面叠加 K 轮分层、K*maxA 上界与连续可达前缀计数。

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结

形式化题目

给定邮票面值集合 AA 与张数上限 KK。一个邮资 v⩾1v \geqslant 1 可贴出，当且仅当存在 x1,x2,…,xm∈Ax_1, x_2, \dots, x_m \in A（可重复选取，m⩽Km \leqslant K）使

x1+x2+⋯+xm=v. x_1 + x_2 + \cdots + x_m = v .

求最大的 MM，使 1,2,…,M1, 2, \dots, M 全部可贴出；若 11 就贴不出，则 M=0M = 0。

规模上 K⩽200K \leqslant 200、面值种数 N=∣A∣⩽50N = |A| \leqslant 50、面值 ⩽10000\leqslant 10000， 所以答案最大约 2×1062 \times 10^6；这些数字决定了下面每条复杂度是否可行。

正解

思路

先看最直白的做法。 维护一个集合 RR，表示"当前能贴出的邮资"。一张都没贴时 R={0}R = \{0\}；每多贴一张面值 ss 的邮票，就把 RR 里每个数都加上 ss：

R←R∪⋃s∈A{x+s:x∈R}, R \leftarrow R \cup \bigcup_{s \in A} \{x + s : x \in R\},

重复 KK 次后，从 11 开始数 RR 的连续前缀。这个做法是对的，但每轮都要重建一遍整个集合。

瓶颈在哪。 两个地方都浪费：

  1. 整个"张数"维度是多余的。 我们要回答的只有"存在某个 m⩽Km \leqslant K 能凑出 vv"， 而这等价于"凑出 vv 最少需要几张 ⩽K\leqslant K"。既然只关心最少张数， 就没有必要把 0,1,…,K0, 1, \dots, K 每一层都算一遍。
  2. 集合的元素级操作太慢。 用 Python 的 set 或数组存 RR，每个元素都要单独循环， 最坏是 K⋅N⋅K⋅max⁡A=2×1010K \cdot N \cdot K \cdot \max A = 2 \times 10^{10} 次操作。

第一步：把问题换成"最少张数"。 记 f(v)f(v) 为凑出 vv 所需的最少邮票张数，则

v 可贴出  ⟺  f(v)⩽K, v \text{ 可贴出} \iff f(v) \leqslant K,

答案是 min⁡{v⩾1:f(v)>K}−1\min\{v \geqslant 1 : f(v) > K\} - 1。ff 的转移是

f(0)=0,f(v)=1+min⁡s∈A, s⩽vf(v−s). f(0) = 0, \qquad f(v) = 1 + \min_{s \in A,\ s \leqslant v} f(v - s).

这正是"重量为面值、每种邮票可以反复取、求恰好装满时的最少件数"的完全背包： 外层把 vv 从小到大扫一遍，内层枚举 NN 个面值，复杂度和标准完全背包同阶。

第二步：容量上界取 K⋅max⁡AK \cdot \max A。 设 S=max⁡AS = \max A。

  • KS+1KS + 1 一定不可贴出：凑出它至少要 K+1K + 1 张邮票（每张面值不超过 SS）。
  • 答案 M⩽KSM \leqslant KS：1,2,…,M1, 2, \dots, M 全部可贴出，而任何可贴出的邮资不超过 KSKS， 所以 MM 也在 KSKS 以内。也就是只需在 [0,KS][0, KS] 上记录可达性， "从 1 往后第一个不可达位置"必定在 KS+1KS + 1 或更早出现。

这一步很关键：上界由最大面值 SS 推得，等于 K⋅max⁡AK \cdot \max A； 换成最小面值就没有依据了。像 {1,3}\{1, 3\}、K=5K = 5 这种例子， K⋅min⁡A=5K \cdot \min A = 5 会把正确答案 1313 直接截掉。

第三步：用大整数承载整个集合。 把"可达"编码进一个整数的位：第 vv 位为 1 表示邮资 vv 可达。 那么"集合里每个数加 ss"就是 reachable << s，"求并"就是按位或。于是上面那个 KK 轮迭代变成

text
reachable = LAYER0                 # 第 0 层 = 1，只有邮资 0 可达
重复至多 K 次：
    nxt = reachable
    对每个面值 s：nxt |= (reachable << s) & mask
    reachable = nxt

一次移位或就覆盖整段 [0,KS][0, KS]，每轮只剩 NN 次整字运算，替掉了上面分层集合法里 那 N⋅KSN \cdot KS 次元素级操作（准确的复杂度对比见下文）。

三个实现细节必须注意：

  • 内层用的是 reachable 而不是 nxt。 一轮只加一张邮票，所有平移都以同一层为基准； 若写成 nxt << s，一轮里就会连续叠加多张，层数含义就错了。
  • & mask 不能省。 否则位宽每轮增长 SS，整数越来越长，移位越来越慢。
  • nxt == reachable 时提前停。 这说明再贴邮票也贴不出新邮资， 于是之后每一轮都等于当前层，继续迭代纯属浪费。

最后是取答案：reachable 里第 vv 位为 1 表示 vv 可达，把它右移一位， 第 ii 位就表示邮资 i+1i + 1；取反后最低的那个 1 位就是第一个不可达邮资， 它的下标即答案。

用样例走一遍。 K=5K = 5，A={1,3}A = \{1, 3\}，cap=5×3=15cap = 5 \times 3 = 15。位串从左到右对应邮资 0∼150 \sim 15：

text
t=0: 1000000000000000
t=1: 1101000000000000
t=2: 1111101000000000
t=3: 1111111101000000
t=4: 1111111111101000
t=5: 1111111111111101
     0123456789012345   <- 邮资

每一行恰好是"不超过 tt 张可达的邮资"，且逐行单调（新方案只能变多不能变少）。 t=5t = 5 这行从邮资 1 到 13 全是 1，邮资 14 是第一个 0，所以答案 M=13M = 13，与题面一致。

代码

Python 版：

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 04:56
# update_at: 2026-10-01 04:56

import sys

# 一个整数当成一个"位集合"：bit v 为 1 表示邮资 v 可达。
# 这就是第 0 层的值——一张邮票都没贴，只有邮资 0 可达。
LAYER0 = 1


def min_impossible(cap: int, values: list[int], limit: int) -> int:
    """返回从 1 开始不能连续贴出的最小邮资；cap 是答案的搜索上界。"""
    # 多贴一张邮票 = 再选一个面值：第 t 层就是第 t-1 层整体左移 s 位后按位或（每个面值 s）。
    # 层内只做常数次大整数运算，因此只保留一层整数，不需要 O(K) 层的数组。
    mask = (1 << (cap + 1)) - 1  # 只保留邮资 0..cap，位宽不随层数增长
    reachable = LAYER0
    for _ in range(limit):
        nxt = reachable
        for s in values:
            nxt |= (reachable << s) & mask
        if nxt == reachable:  # 再贴也贴不出新邮资，更多张数同样贴不出
            break
        reachable = nxt

    # 邮资 v（v >= 1）可达 <=> reachable 的第 v 位为 1，等价于第 v-1 位为 0 的 gaps 里那一位置 1。
    gaps = ~(reachable >> 1)
    lowest_gap = gaps & -gaps  # 最低的 1 位，就是第一个不可达邮资
    return lowest_gap.bit_length() - 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    stamps, kinds = next(data), next(data)  # 可用邮票张数上限 K，面值种数 N
    values = sorted({next(data) for _ in range(kinds)})  # 重复面值不影响可达性，先去重

    # 答案不会超过 K * 最大面值：K*max+1 至少要 K+1 张邮票，本来就不可能贴出；
    # 而一旦出现空隙，它必是最小的不可达值——比它大的邮资都能用减法回到它之前，
    # 所以更早处就已经断了。于是搜索上界取 K*max 即可。
    cap = stamps * values[-1]
    print(min_impossible(cap, values, stamps))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:41
 * update_at: 2026-10-06 09:41
 */

// 完全背包求"凑出每个邮资最少要几张邮票"，从 1 开始数连续可达的邮资个数。
#include <cstdio>

typedef long long ll;

const ll MAXV = 200 * 10000 + 5; // 邮资上界 K * max(面值) + 余量，答案不会超过 K * 最大面值

int k;      // 最多能贴的邮票张数
int n;      // 邮票面值种数
int val[55]; // val[i] = 第 i 种邮票的面值
int f[MAXV]; // f[v] = 凑出邮资 v 所需的最少邮票张数，INF 表示暂时凑不出

const int INF = 0x3f3f3f3f;

int main() {
    scanf("%d %d", &k, &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &val[i]);

    int cap = k * 10000; // 每张邮票面值 <= 10000，超过 cap 的邮资一定贴不出，无需计算

    // 完全背包：v 从小到大扫（面值可重复选取），f[v] = 1 + min(f[v - s])
    f[0] = 0;
    for (int v = 1; v <= cap; ++v) {
        f[v] = INF;
        for (int i = 1; i <= n; ++i) {
            int s = val[i];
            if (s <= v && f[v - s] + 1 < f[v])
                f[v] = f[v - s] + 1;
        }
    }

    // 从 1 开始找第一个"最少张数 > k"的邮资，它前面连续可达的个数就是答案
    int ans = 0;
    while (ans + 1 <= cap && f[ans + 1] <= k)
        ++ans;

    printf("%d\n", ans);
    return 0;
}

复杂度

设 C=K⋅max⁡A⩽2×106C = K \cdot \max A \leqslant 2 \times 10^6，N=∣A∣N = |A|，ww 为机器字长。

  • 参考解法（完全背包）的时间：O(N⋅C)O(N \cdot C) 次元素级转移，也就是本题的标准做法。 C=2×106C = 2 \times 10^6 时是 10810^8 次转移，C++ 轻松通过； 在 Python 里逐元素循环实测要 6.1s。
  • 本文实现的时间：同一条转移方程，但用位并行执行——外层至多 KK 轮， 每轮对 NN 个面值各做一次 CC 位整数的移位与按位或，共 O(K⋅N)O(K \cdot N) 次大整数运算， 折算成字级操作是 O(K⋅N⋅C/w)O(K \cdot N \cdot C / w)。 这个字级工作量其实是参考解法的 K/w≈3K / w \approx 3 倍（K=200K = 200，w=64w = 64）： 位并行没有减少理论运算量，它换来的是每次操作由处理器整字完成。 在 Python 里这一换非常划算——同样的 stamps10.in 从 6.1s 降到 0.43s， 才留出了对 1000ms 限制的余量。
  • 空间：只保存 reachable、nxt、mask 三个大整数。C=2×106C = 2 \times 10^6 时 每个整数实测约 0.25MB，进程峰值内存 17.9MB。作为对照，参考解法那个长度为 C+1C+1 的 int 列表本身就要约 15MB 的指针数组，进程峰值 30.0MB——两者都能塞进 128MB， 但位集合的余量大得多。
  • 实测：13 组真实数据全部 PASS。最强数据 stamps10.in （K=200K = 200，N=50N = 50，面值最大 1000010000，答案 19960891996089）耗时 0.43s / 峰值 17.9MB， 对 1000ms / 128MB 分别有约 2.3 倍和 7 倍余量。

总结

  • “能不能"换成"最少要几个”。 题面问的是可达性，但按张数分层会白白重复 KK 遍； 一旦改问"凑出 vv 最少几张"，整个张数维度就消失了，一次背包扫完所有 vv。
  • 完全背包的扫描方向由"能不能重复取"决定。 这里的转移 f(v)=1+min⁡sf(v−s)f(v) = 1 + \min_s f(v-s) 只依赖同一层里更小的 vv，所以 vv 必须从小到大扫，读到的就是本轮已更新的值， 面值可以重复选取；若每种面值只能用一次，就必须倒序扫。
  • 上界要用 K⋅max⁡AK \cdot \max A。 它是由"每张邮票至多 max⁡A\max A"推出来的，与最小面值无关； 写成 K⋅min⁡AK \cdot \min A 会截断答案，样例 K=5K = 5、A={1,3}A = \{1, 3\} 就是反例（5<135 < 13）。
  • 面值只能去重，不能删除。 看似"被别的面值覆盖"的面值可能恰恰是答案的关键： A={1,3}A = \{1, 3\} 删掉任一个，答案就从 1313 掉到 55 或 00；A={1,10000}A = \{1, 10000\}、K=200K = 200 时 删掉 1000010000 会让答案从 20000002000000 变成 200200。代码只做去重。
  • 位运算是"集合平移 + 并"的天然载体。 把可达性编码成第 vv 位， 一次左移就是"全体加 ss"，一次按位或就是求并，KK 轮迭代成了 K⋅NK \cdot N 次大整数运算。 代价是要守住三条纪律：以本层为基准、及时截位、遇不动点即停。