自动搬运

查看原文

来自洛谷，原作者为

	远航之曲 **

搬运于2025-08-24 21:22:30，当前版本为作者最后更新于2016-05-12 09:05:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

发现没有c++的题解，果断来一发。

想出了好几种解法，我就一点一点地写吧。

方法 1:DFS 因为牛奶的总量是不变的，所以可以用a,b中的牛奶量做状态，初始状态是(0,0)，每次只能有6种选择，a倒b，a倒c，b倒a，b倒c，c倒a，c倒b。用一个数组vis[i][j]判重，s[i]记录c中所有可能值（s[i]=true表示c中可能出现i），如果当前状态是(0,x)，那么s[mc -x]=true，最后输出s中所有true的就可以了。 用vis[i][j][k]也行，也就是说三维的也行。

方法 2 这个题目也可以递归…不过我不知道临界点是多少,就乱试了,结果用i=14能过…不过我不知道为什么i要等于14,没证明过当i等于14时能包括大多数的过程… (假如用BFS。只有在扩充的状态没有出现过的情况下，才把它加入队列，这样可以保证不重不漏）

方法3 人脑解法 这题简直是赤裸裸的奥数啊，直接手动算出所有的解再让计算机输出了就行了！估计只用0微秒 由于题目不对称（a要为0），导致了源代码的丑陋。分a小于b和a大于等于b两种情况，每种情况各有两种不同的方法，不断用b灌a，或者反之，如果灌完了就用c充满继续，如果充不满就说明做完了，如果灌满了还有就把被灌的倒回c，然后继续灌。最多做20次循环，因为c<=20 最后输出很简单，先遍历数组到c-1，之后再输出（c）就行（c永远是一个解）

方法4 使用枚举的方法，按照顺序A，B，C寻找每一个牛奶非空的桶，假设我们找到了B， 则接下来只能是从B-》A或B-》C或则什么都不做这三种情况；使用递归来完成。 我们需要一个数组state[500][3]来储存遍历过的三个桶中牛奶的状态， 当 当前状态已经在之前出现过，就退出。同样也是使用一个数组bool leave_c[]来储存C中可能的牛奶量。.这样或许更容易理解。

方法5 使用二进制保存状态，因为A,B,C都在1-20之间，所以可以分别用8位表示他们的容量

int a = (status&0xFF0000)>>16;

int b = (status&0x00FF00)>>8;

int c = (status&0x0000FF);

然后分别对a->b, a->c, b->c, b->a, c->a, c->b六种情况进行DFS， 用一个数组保存已经判断过的状态。

方法6 思维模式还是BFS， 把每种状态压成了一个点，如果能从状态k1转换到k2，[k1,k2]:=true; 即相当于连一条有向边。 然后不断更新，直到不能产生新的状态，最后扫描一次A桶为0的状态的点是否能到达即可。

方法7 模拟n次

设一个标记用的数组 f[0..20,0..20,0..20]记录f[a,b,c]的情况是否出现过...

6种倒法用递归循环一下..边界出口就是当前a，b，c内的牛奶量曾出现过

也就是 f[a,b,c]=true 时。。。程序巨短》。时间和其他差不多。。性价比 较高

方法8 将i从0到c带入一个bool函数f（i定义：c桶为i，a桶空），f的功能是bfs遍历到状态为（x,x,i）,判断能否遍历到或者此时的状态a是否为0；这样做效率貌似是很低的，不过可以加一个数组p[]，设定为全局变量，在遍历时遇到（0,x,i）的状态就记录，另外在将i带入f前判断p[i]是否记录过，这样一来效率大大提高了。

上代码

（减少代码复制，创造美好洛谷）

#include <cstdio>
#include <cstring>
#include <algorithm>
const int MAX = 22;
bool milk[MAX] = {0};
bool vis[MAX][MAX][MAX] = {0};
static int bkt[3];
void dfs(int a[]) {
    if (vis[a[0]][a[1]][a[2]]) return;
    vis[a[0]][a[1]][a[2]] = true;
    if (a[0] == 0) milk[a[2]] = true;
    //six ways to check, from bkt i to bkt j
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            if (j == i) continue;
            if (a[j] < bkt[j] && a[i] > 0) {
                int rec = std::min(bkt[j] - a[j], a[i]);
                int b[3];
                memcpy(b, a, sizeof(int)*3);
                b[i] -= rec, b[j] += rec;
                dfs(b);
            }
        }
    }
int main() {
    //freopen("milk3.in", "r", stdin);
    //freopen("milk3.out", "w", stdout);
    int &A = bkt[0], &B = bkt[1], &C = bkt[2];
    scanf(" %d %d %d", &A, &B, &C);
    int a[3] = {0,0,C};
    dfs(a);
    for (int i = 0; i < C; ++i) {
        if (milk[i]) printf("%d ", i);
    }
    printf("%d\n", C);
    return 0;
}