P1215 母亲的牛奶 Mother’s Milk网页链接P1215 母亲的牛奶 Mother’s Milk题目描述农民约翰有三个容量分别是a , b , c a,b,ca,b,c升的桶。最初a , b a,ba,b桶都是空的而c cc桶是装满牛奶的。有时农民把牛奶从一个桶倒到另一个桶中直到被灌桶装满或原桶空了。当然每一次灌注都是完全的。由于节约牛奶不会有丢失。写一个程序去帮助农民找出当a aa桶是空的时候c cc桶中牛奶所剩量的所有可能性。输入格式单独的一行包括三个整数a , b , c a,b,ca,b,c。输出格式只有一行升序地列出当a aa桶是空的时候c cc桶牛奶所剩量的所有可能性。输入输出样例 #1输入 #18 9 10输出 #11 2 8 9 10输入输出样例 #2输入 #22 5 10输出 #25 6 7 8 9 10说明/提示【数据范围】对于100 % 100\%100%的数据1 ≤ a , b , c ≤ 20 1\le a,b,c \le 201≤a,b,c≤20。题目翻译来自NOCOW。USACO Training Section 1.4解题思路本题核心是深度优先搜索(DFS) 状态去重遍历所有合法的牛奶倾倒状态求解目标答案。三个桶的牛奶总量恒定为初始值C CC用三元组( a , b , c ) (a,b,c)(a,b,c)表示当前状态通过三维数组标记已访问状态避免重复搜索。枚举6种倾倒方式A→B、A→C、B→A、B→C、C→A、C→B每次倾倒遵循规则将牛奶倒至目标桶满或源桶空。搜索过程中若A AA桶为空则记录此时C CC桶的牛奶量。最后将所有合法结果升序输出。由于数据范围极小≤ 20 ≤20≤20DFS 暴力搜索简洁高效完全满足题目要求。总结核心逻辑通过DFS枚举所有牛奶倾倒的合法状态筛选出A桶为空时C桶的所有可能容量。关键操作三维状态标记去重、6种倾倒逻辑实现、结果收集与排序。效率保障极小的数据范围让暴力搜索成为最优解代码简洁且无超时风险。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll A,B,C;ll v[22][22][22];ll r[22];voiddfs(ll a,ll b,ll c){if(v[a][b][c]1)return;v[a][b][c]1;if(a0r[c]0)r[c]1;if(c(A-a))dfs(A,b,c-(A-a));elsedfs(ca,b,0);if(c(B-b))dfs(a,B,c-(B-b));elsedfs(a,cb,0);if(b(A-a))dfs(A,b-(A-a),c);elsedfs(ba,0,c);if(b(C-c))dfs(a,b-(C-c),C);elsedfs(a,0,bc);if(a(C-c))dfs(a-(C-c),b,C);elsedfs(0,b,ac);if(a(B-b))dfs(a-(B-b),B,c);elsedfs(0,ab,c);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinABC;dfs(0,0,C);for(ll i0;i21;i)if(r[i])couti ;cout\n;return0;}