自动搬运

查看原文

来自洛谷，原作者为

	Tjaweiof 资瓷互关 | 需要壶关请私信 | 蓝名不要再找我互关了 | ENTP-A

搬运于2025-08-24 22:44:49，当前版本为作者最后更新于2024-10-19 13:42:21，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P9038 题解

题目传送门

容易发现一次操作之后必然有一个瓶子是满的或是空的，于是我们记 $s=a+b+c$，即橙汁的总量。假设满（空）的瓶子是第一个，则另外两个瓶子的橙汁的总量必为 $s$ 或 $s-a$，故不同的状态数不超过 $\max(A,B,C)$，直接记忆化搜索即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in", "r", stdin);freopen(x".out", "w", stdout);
int A, B, C, a, b, c;
bool vis[100001][3][2];
int ans[100001];
struct Tjaweiof{
	int x, m;
	bool p;
	int t;
};
queue <Tjaweiof> q;
void pu(int a, int b, int c, int t){
	if (a + b <= A){
		q.push({c, 1, 0, t});
	}
	if (a + b >= A){
		q.push({a + b - A, 0, 1, t});
	}
	if (b + c <= B){
		q.push({a, 2, 0, t});
	}
	if (b + c >= B){
		q.push({b + c - B, 1, 1, t});
	}
	if (c + a <= C){
		q.push({b, 0, 0, t});
	}
	if (c + a >= C){
		q.push({c + a - C, 2, 1, t});
	}
	if (a + c <= A){
		q.push({a + c, 2, 0, t});
	}
	if (a + c >= A){
		q.push({b, 0, 1, t});
	}
	if (b + a <= B){
		q.push({b + a, 0, 0, t});
	}
	if (b + a >= B){
		q.push({c, 1, 1, t});
	}
	if (c + b <= C){
		q.push({c + b, 1, 0, t});
	}
	if (c + b >= C){
		q.push({a, 2, 1, t});
	}
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> A >> B >> C >> a >> b >> c;
	memset(ans, -1, sizeof ans);
	ans[a] = 0;
	ans[b] = 0;
	ans[c] = 0;
	pu(a, b, c, 1);
	while (!q.empty()){
		auto u = q.front();
		q.pop();
		if (vis[u.x][u.m][u.p]){
			continue;
		}
		vis[u.x][u.m][u.p] = true;
		int na, nb, nc;
		if (!u.m){
			na = A * u.p;
			nb = u.x;
			nc = a + b + c - na - nb;
		} else if (u.m == 1){
			nb = B * u.p;
			nc = u.x;
			na = a + b + c - nb - nc;
		} else if (u.m == 2){
			nc = C * u.p;
			na = u.x;
			nb = a + b + c - nc - na;
		}
		if (ans[na] == -1){
			ans[na] = u.t;
		}
		if (ans[nb] == -1){
			ans[nb] = u.t;
		}
		if (ans[nc] == -1){
			ans[nc] = u.t;
		}
		pu(na, nb, nc, u.t + 1);
	}
	for (int i = 0; i <= C; i++){
		cout << ans[i] << " ";
	}
	return 0;
}