题解(多种方案)
2026-09-06 18:36:32
发布于:湖南
方法 1:因为牛奶的总量是不变的,所以可以用,中的牛奶量做状态,初始状态是,每次只能有6种选择,倒,倒,倒,倒,c倒,倒。用一个数组判重,记录中所有可能值(表示中可能出现),如果当前状态是,那么,最后输出中所有的就可以了。 用也行,也就是说三维的也行。
方法 2 这个题目也可以递归…不过我不知道临界点是多少,就乱试了,结果用能过…不过我不知道为什么要等于14,没证明过当等于14时能包括大多数的过程… (假如用BFS。只有在扩充的状态没有出现过的情况下,才把它加入队列,这样可以保证不重不漏)
方法3 人脑解法 这题简直是赤裸裸的奥数啊,直接手动算出所有的解再让计算机输出了就行了!估计只用0微秒 由于题目不对称(要为),导致了源代码的丑陋。分小于和大于等于两种情况,每种情况各有两种不同的方法,不断用灌,或者反之,如果灌完了就用充满继续,如果充不满就说明做完了,如果灌满了还有就把被灌的倒回,然后继续灌。最多做20次循环,因为 最后输出很简单,先遍历数组到,之后再输出()就行(永远是一个解)
方法4 使用枚举的方法,按照顺序寻找每一个牛奶非空的桶,假设我们找到了, 则接下来只能是从或或则什么都不做这三种情况;使用递归来完成。 我们需要一个数组来储存遍历过的三个桶中牛奶的状态, 当 当前状态已经在之前出现过,就退出。同样也是使用一个数组来储存中可能的牛奶量。.这样或许更容易理解。
方法5 使用二进制保存状态,因为都在之间,所以可以分别用8位表示他们的容量
int a = (status&0xFF0000)>>16;
int b = (status&0x00FF00)>>8;
int c = (status&0x0000FF);
然后分别对六种情况进行, 用一个数组保存已经判断过的状态。
方法6 将从到带入一个函数(定义:桶为,桶空),的功能是bfs遍历到状态为,判断能否遍历到或者此时的状态是否为0;这样做效率貌似是很低的,不过可以加一个数组,设定为全局变量,在遍历时遇到的状态就记录,另外在将带入前判断是否记录过,这样一来效率大大提高了。
上代码
(减少代码复制,创造美好ACGO)
#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;
}
这里空空如也





有帮助,赞一个