usaco-1.4.4 母亲的牛奶

题目描述

农民约翰有三个容量分别为 $A,B,C$ 的桶（ $1\leqslant A,B,C\leqslant20$ ）。初始 A、B 为空，C 装满。每次选两个不同的桶，把源桶的牛奶倒向目标桶，直到目标桶满或源桶空。求 A 桶为空时，C 桶牛奶剩余量的所有可能值，升序输出一行。

样例输入 8 9 10 输出 1 2 8 9 10；输入 2 5 10 输出 5 6 7 8 9 10。

思路

状态用三元组 $(a,b,c)$ 表示，总量守恒 $a+b+c=C$ ，所以不同状态不超过 $(A+1)(B+1)\leqslant441$ 个。一次合法倒出量为 $\Delta=\min(m_{src},\;c_{dst}-m_{dst})$ 。从 $(0,0,C)$ 出发，用栈做 DFS（或 BFS），vis 判重，每个状态只扩展一次，遍历完收集 $a=0$ 的所有 $c$ 升序输出即可。

参考代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55#!/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 03:06
# update_at: 2026-10-04 11:41

import sys

State = tuple[int, int, int]  # (a, b, c) 三个桶当前的牛奶量；容量另用同型三元组 caps 表示


def pour(state: State, src: int, dst: int, caps: State) -> State:
    """把 src 桶倒向 dst 桶：倒到 dst 满或 src 空为止。

    倒出的量 = min(src 的存量, dst 还差多少)，这正是「每一次灌注都是完全的」的含义。
    """
    milk = list(state)
    volume = min(milk[src], caps[dst] - milk[dst])
    milk[src] -= volume
    milk[dst] += volume
    return tuple(milk)


def c_when_a_empty(caps: State) -> list[int]:
    """返回 A 桶为空时 C 桶所有可能的存量（升序）。

    从初始状态 (0, 0, C) 出发，沿 6 种倒法做图上搜索；每个状态只入栈一次，
    状态数是 O(A*B)，所以搜索一定结束。
    """
    start: State = (0, 0, caps[2])                # A、B 初始为空，C 装满
    moves = [(s, d) for s in range(3) for d in range(3) if s != d]  # 6 种倒法

    seen: set[State] = {start}
    stack: list[State] = [start]
    while stack:
        state = stack.pop()
        for src, dst in moves:
            nxt = pour(state, src, dst, caps)
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)

    return sorted(c for a, _, c in seen if a == 0)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    A, B, C = next(data), next(data), next(data)   # 题面唯一一行 A B C
    caps: State = (A, B, C)
    print(*c_when_a_empty(caps))


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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78/**
 * 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:32
 * update_at: 2026-10-06 09:32
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int cap[3]; // 三个桶的容量 A, B, C
bool vis[21][21][21]; // 状态 (a,b,c) 是否已访问

// 从 src 倒向 dst，返回新状态 (na, nb, nc)
void pour(int a, int b, int c, int src, int dst, int &na, int &nb, int &nc) {
    int milk[3] = {a, b, c};
    int volume = min(milk[src], cap[dst] - milk[dst]);
    milk[src] -= volume;
    milk[dst] += volume;
    na = milk[0]; nb = milk[1]; nc = milk[2];
}

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

    cin >> cap[0] >> cap[1] >> cap[2];

    // 用栈做 DFS，初始状态 (0, 0, C)
    int sa = 0, sb = 0, sc = cap[2];
    vis[sa][sb][sc] = true;

    // 用简单数组模拟栈，最多 441 个状态
    int stk[441][3];
    int top = 0;
    stk[top][0] = sa; stk[top][1] = sb; stk[top][2] = sc;
    top++;

    while (top > 0) {
        top--;
        int a = stk[top][0], b = stk[top][1], c = stk[top][2];
        // 6 种倒法：src != dst
        for (int src = 0; src < 3; src++) {
            for (int dst = 0; dst < 3; dst++) {
                if (src == dst) continue;
                int na, nb, nc;
                pour(a, b, c, src, dst, na, nb, nc);
                if (!vis[na][nb][nc]) {
                    vis[na][nb][nc] = true;
                    stk[top][0] = na; stk[top][1] = nb; stk[top][2] = nc;
                    top++;
                }
            }
        }
    }

    // 收集 A 为空时 C 的所有可能值，升序输出
    vector<int> ans;
    for (int c = 0; c <= cap[2]; c++) {
        for (int b = 0; b <= cap[1]; b++) {
            if (vis[0][b][c]) {
                ans.push_back(c);
                break; // 同一 c 只需一个 b 满足即可
            }
        }
    }

    for (size_t i = 0; i < ans.size(); i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

usaco-1.4.4 母亲的牛奶

目录

题目描述

思路

参考代码