【题目标题】小码君喝牛奶 【算法分析】 因为牛奶的总量是不变的，所以可以用 a,ba,ba,b 中的牛奶量做状态，初始状态是(0,0)(0,0)(0,0) ，每次只能有6种选择，aaa倒bbb，aaa倒ccc，bbb倒aaa，bbb倒ccc，ccc倒aaa，ccc倒bbb。用一个数组vis[i][j]vis[i][j]vis[i][j]判重，res[i]res[i]res[i]记录ccc中所有可能值（s[i]=trues[i]=trues[i]=true表示ccc 中可能出现iii ，如果当前状态是(0,x)(0,x)(0,x)，那么res[tot−x]=trueres[tot -x]=trueres[tot−x]=true，最后输出sss中所有truetruetrue的z就可以了。 用vis[i][j][k]vis[i][j][k]vis[i][j][k]也行，也就是说三维的也行。 【参考代码】 【时间复杂度】 O(abc)O(abc)O(abc) 【预期得分】 100pts

#include<bits/stdc++.h> using namespace std; bool a[30][30],b[30]; int n,m,k; void dfs(int x,int y,int z){ if(a[x][y]) return; if(!x) b[z] = 1; a[x][y] = 1; int t = min(z,n-x); if(z)dfs(x+t,y,z-t); t = min(z,m-y); if(z)dfs(x,y+t,z-t); t = min(x,m-y); if(x)dfs(x-t,y+t,z); t = min(x,k-z); if(x)dfs(x-t,y,z+t); t = min(n-x,y); if(y)dfs(x+t,y-t,z); t = min(k-z,y); if(y)dfs(x,y-t,z+t); } int main(){ cin >> n >> m >> k; dfs(0,0,k); for(int i=0;i<=k;i++) if(b[i]) cout << i << " "; }

*这篇题解借鉴了AC君的题解思路,但是部分内容会讲得较为详细,如果只是思路不清楚,可以直接看AC君的题解 一.思路与难点 题目 : (因为题目本身没有特别繁琐,就直接把重点了解一下就好) 有三个容量分别为a,b,c的桶. 最开始, a,b桶为空, c桶装满牛奶. 本篇文章中会将容量为a,b,c的桶分别命名为a,b,c. 小码君会把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶为空. 当然每一次灌注都是完全的。由于节约，牛奶不会有丢失. 想求在a桶为空时,c桶的所有可能性(升序) 先说难点: 1.如何模拟倒牛奶的过程? 2.如何确保倒牛奶的过程中没有重复过程? 3.如何正确的存储所有符合要求的答案? 难点的相应思路: 1.如何模拟倒牛奶的过程? 在DFS的函数中设置三个参数x,y,z(或者a1,b1,c1也可以) 来对应a,b,c三个桶的牛奶量 如果想要倒牛奶,一共有六种可能: (a,b) (a,c) (b,a) (b,c) (c,a) (c,b) *(a,b)代表将a桶中的牛奶倒入b桶中 前提:a桶中有牛奶且b桶还能倒牛奶 然后要决定倒入牛奶的量 注意前文题目: 小码君会把牛奶从一个桶倒到另一个桶中,直到被灌桶装满或原桶为空 还是以(a,b)为例 设b桶能倒入的牛奶量为: b-y (y是b桶中,牛奶的数量) 设a桶能倒入b桶的牛奶量为: x (x是a桶中牛奶的量) 那么,最终能从a桶倒入b桶中的牛奶量为: 因为要保证最终倒入b桶的牛奶量小于等于b-y(不然会浪费,溢出) 2.如何确保倒牛奶的过程中没有重复过程? 可以用二维/三位数组,(bool/int都可以),比如: 每当进行了一次倒牛奶操作: 可以只用二维数组的原因是牛奶的总量是不变的,而且只有三个桶. 所以当a,b桶中的牛奶数量确定,c桶中的牛奶数量其实也是确定的. 3.如何正确的存储所有符合要求的答案? 这里考虑到如果直接用数组存然后排序的话,可能就会有重复的现象,所以可以用一个bool或者int数组来当桶 如果有符合条件的答案就记录 最后输出时,直接判断ans[i]是否为1即可,如果为1,输出i 二.题解 *因为前面已经把大量重要代码放出,这里就不放挖空题解了 *此代码并不是格式上,时间上,空间上的最优代码;但是比较容易理解;后期可能会放优化代码. 完