由于被老师要求讲题，这里塞一个用DeepSeek编写的题解。

直接复制AC代码的万劫不复。

倒牛奶题解

问题描述

昊昊有三个容量分别为x、y、z升的桶。一开始，x桶和y桶是空的，z桶装满了牛奶。他会将一个桶中的牛奶倒入另一个桶，直到被灌桶装满或原桶空了。每次倒牛奶都是完全的，没有浪费。我们需要找出当x桶为空时，z桶中剩余牛奶量的所有可能值。

输入格式

单独的一行包括三个整数x，y，z（1 ≤ x, y, z ≤ 20）

输出格式

只有一行，升序地列出当x桶是空的时候，z桶牛奶所剩量的所有可能性。

本人考试时提交的代码分析

#include<bits/stdc++.h>
using namespace std;
int x,y,z,pc[21][21][21];
bool a[21];
void dfs(int dx,int dy,int dz){
    if(pc[dx][dy][dz]){
        return;
    }
    pc[dx][dy][dz]=1;
    if(dx==0&&!a[dz]){
        a[dz]=1;
    }
    if(!(dx==x&&dy==y)){
        if(dy!=0){
            if(dx+dy>x){
                dfs(x,dy-(x-dx),dz);
            }
            else{
                dfs(dx+dy,0,dz);
            }
        }
        if(dx!=0){
            if(dy+dx>y){
                dfs(dx-(y-dy),y,dz);
            }
            else{
                dfs(0,dy+dx,dz);
            }
        }
    }
    if(!(dx==x&&dz==z)){
        if(dz!=0){
            if(dx+dz>x){
                dfs(x,dy,dz-(x-dx));
            }
            else{
                dfs(dx+dz,dy,0);
            }
        }
        if(dx!=0){
            if(dz+dx>z){
                dfs(dx-(z-dz),dy,z);
            }
            else{
                dfs(0,dy,dz+dx);
            }
        }
    }
    if(!(dy==y&&dz==z)){
        if(dy!=0){
            if(dz+dy>z){
                dfs(dx,dy-(z-dz),z);
            }
            else{
                dfs(dx,0,dz+dy);
            }
        }
        if(dz!=0){
            if(dy+dz>y){
                dfs(dx,y,dz-(y-dy));
            }
            else{
                dfs(dx,dy+dz,0);
            }
        }
    }
}
int main(){
    cin>>x>>y>>z;
    dfs(0,0,z);
    for(int i=1;i<=20;i++){
        if(a[i]){
            cout<<i<<' ';
        }
    }
    return 0;
}

喜提70分。

问题分析：

1. 代码冗长复杂：状态转移的条件判断过多，容易出错
2. 可能遗漏状态：某些转移条件限制过严，可能导致部分状态未被访问
3. 输出范围错误：从1开始输出，但z桶剩余量可能为0
4. 状态标记数组命名不清晰：pc数组命名不够直观

满分AC代码

#include<bits/stdc++.h>
using namespace std;
int x,y,z;
bool v[21][21][21];
bool a[21];
void dfs(int dx,int dy,int dz){
    if(v[dx][dy][dz]){
        return;
    }
    v[dx][dy][dz]=1;
    if(dx==0){
        a[dz]=1;
    }
    if(dx>0&&dy<y){
        int t=min(dx,y-dy);
        dfs(dx-t,dy+t,dz);
    }
    if(dx>0&&dz<z){
        int t=min(dx,z-dz);
        dfs(dx-t,dy,dz+t);
    }
    if(dy>0&&dx<x){
        int t=min(dy,x-dx);
        dfs(dx+t,dy-t,dz);
    }
    if(dy>0&&dz<z){
        int t=min(dy,z-dz);
        dfs(dx,dy-t,dz+t);
    }
    if(dz>0&&dx<x){
        int t=min(dz,x-dx);
        dfs(dx+t,dy,dz-t);
    }
    if(dz>0&&dy<y){
        int t=min(dz,y-dy);
        dfs(dx,dy+t,dz-t);
    }
}
int main(){
    cin>>x>>y>>z;
    memset(v,0,sizeof(v));
    memset(a,0,sizeof(a));
    dfs(0,0,z);
    for(int i=0;i<=20;i++){
        if(a[i]){
            cout<<i<<' ';
        }
    }
    return 0;
}

来之不易的100分。

算法思路详解

核心思想：深度优先搜索（DFS）

我们使用DFS遍历所有可能的状态，状态用三元组(dx, dy, dz)表示，分别代表三个桶中当前的牛奶量。

状态空间

• 每个桶的容量最大为20，因此状态总数为21×21×21=9261
• 使用三维布尔数组v记录已访问状态，避免重复搜索

算法步骤

1. 初始化：从状态(0, 0, z)开始，即x桶和y桶为空，z桶满

2. 标记状态：每次进入新状态，先标记为已访问

3. 记录答案：如果当前x桶为空（dx=0），记录此时z桶的牛奶量

4. 状态转移：尝试所有可能的倒牛奶操作（共6种）：

   • 从x倒向y
   • 从x倒向z
   • 从y倒向x
   • 从y倒向z
   • 从z倒向x
   • 从z倒向y

   每次倒牛奶的量是min(原桶牛奶量, 目标桶剩余容量)

5. 递归搜索：对每个合法转移进行DFS

6. 输出结果：升序输出所有记录的z桶牛奶量

时间复杂度分析

• 每个状态最多访问一次
• 每个状态最多产生6个子状态
• 总时间复杂度约为O(6×9261) ≈ O(55566)，完全在1秒时限内

正确性证明

1. 完备性：算法枚举了所有可能的状态转移，不会遗漏任何可能状态
2. 无重复：通过标记数组避免重复搜索
3. 终止性：状态数有限，且每次转移后至少有一个桶的牛奶量发生变化，不会无限循环

到此结。

幽默总结

这道题就像是一场牛奶的"三国演义"：x桶、y桶和z桶这三个"国家"互相"征战"（倒牛奶），我们作为"史官"需要记录下每一次x桶"亡国"（为空）时，z桶的"国库剩余"（牛奶量）。通过DFS这位"时光法师"，我们遍历了所有可能的"历史走向"，最终得到了z桶的所有可能结局。

记住倒牛奶的规矩：要么倒到对方桶满，要么倒到自己桶空，就像分享奶茶时，要么朋友杯子满了，要么你的杯子空了，但绝不能浪费一滴！