usaco-4.1.1 麦香牛块

题目描述

给定 $N$ （ $1 \le N \le 10$ ）种包装盒，第 $i$ 种可装 $b_i$ （ $1 \le b_i \le 256$ ）块麦香牛块，每种数量无限。求顾客不能买到的最大块数；若所有正整数都能买到，输出 $0$ 。

思路

先求所有盒容量的最大公约数 $g$ ，若 $g > 1$ 则非 $g$ 倍数的块永远买不到且无最大值，输出 $0$ 。若 $g = 1$ ，由 Frobenius 数论结论可知最大凑不出的数严格小于 $256^2 = 65536$ ，因此在 $[0, 65536]$ 上做一遍完全背包可达性筛，取最大的不可达数即可。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37#!/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 05:50
# update_at: 2026-10-01 05:50

import sys
from functools import reduce
from math import gcd

# 不可表示数的上界：互质的 a,b 最大凑不出的数是 ab-1，盒容量 ≤ 256，故 256*256 内必出答案
LIMIT = 256 * 256


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    boxes = [next(data) for _ in range(n)]

    # 所有盒容量的公约数 g>1 时，买到的块数永远是 g 的倍数，其余需求无限多且都没有最大者
    if reduce(gcd, boxes) != 1:
        print(0)
        return

    # 可达性筛：s 块能凑出 ⇔ 存在盒子 b，使 s-b 块能凑出（0 块是唯一初始事实）
    reachable = bytearray(LIMIT + 1)
    reachable[0] = 1
    for s in range(1, LIMIT + 1):
        reachable[s] = any(b <= s and reachable[s - b] for b in boxes)

    # 找不到不可表示的数说明范围内全能凑出，输出 0
    print(max((s for s in range(1, LIMIT + 1) if not reachable[s]), default=0))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
 * 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 10:36
 * update_at: 2026-10-06 10:36
 */

#include <iostream>
using namespace std;

typedef long long ll;

const int LIMIT = 256 * 256; // 盒容量 ≤256，互质时最大凑不出的数 < 256*256

int n;
int b[15];        // 盒容量
bool reach[LIMIT + 1]; // reach[s] 表示 s 块能否凑出

ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> b[i];

    // 所有盒容量的最大公约数 g > 1 时，非 g 倍数的块数永远买不到且无最大值
    ll g = b[1];
    for (int i = 2; i <= n; ++i) g = gcd(g, b[i]);
    if (g != 1) {
        cout << 0 << "\n";
        return 0;
    }

    // 完全背包可达性筛：s 能凑出 ⇔ 存在盒子 b，使 s-b 能凑出
    reach[0] = true;
    for (int s = 1; s <= LIMIT; ++s) {
        bool ok = false;
        for (int i = 1; i <= n; ++i) {
            if (b[i] <= s && reach[s - b[i]]) {
                ok = true;
                break;
            }
        }
        reach[s] = ok;
    }

    int ans = 0;
    for (int s = 1; s <= LIMIT; ++s)
        if (!reach[s]) ans = s; // 取最大不可达数

    cout << ans << "\n";
    return 0;
}

usaco-4.1.1 麦香牛块

目录

题目描述

思路

参考代码