题意回顾

有三个瓶子，容积分别为 $A, B, C$，初始橙汁量为 $a, b, c$。
允许的操作：在两个瓶子间倒橙汁，只能倒空一个瓶子或倒满一个瓶子。
对于每个 $k = 0, 1, \dots, C$，求让某个瓶子恰好有 $k$ 升橙汁的最少操作次数。

数据范围：$1 \le A \le B \le C \le 10^5$。

---

关键观察

1. 状态表示

系统的状态可以用三元组 $(x, y, z)$ 表示，其中：

• $x$ = 第一个瓶子的橙汁量，$0 \le x \le A$
• $y$ = 第二个瓶子的橙汁量，$0 \le y \le B$
• $z$ = 第三个瓶子的橙汁量，$0 \le z \le C$
• 且 $x + y + z = a + b + c$（总量守恒）

2. 操作类型

从状态 $(x, y, z)$ 可以进行的操作：

• 从 $i$ 瓶倒向 $j$ 瓶：
  • 倒空 $i$：$x' = 0$, $y' = y + x$（如果 $i=1,j=2$）
  • 倒满 $j$：$y' = B$, $x' = x - (B - y)$（如果 $i=1,j=2$）
  • 实际倒的量是 $\min(x, \text{剩余容量})$，其中剩余容量 = $容量 - 当前量$

3. 问题转化

我们需要找到从初始状态 $(a, b, c)$ 出发，到达任意状态 $(x, y, z)$ 的最少步数，其中 $x = k$ 或 $y = k$ 或 $z = k$。

---

算法设计

BFS 搜索

由于状态空间有限，可以用 BFS 遍历所有可达状态。

状态数分析

• $x$ 有 $A+1$ 种可能
• $y$ 有 $B+1$ 种可能
• $z$ 由 $x+y+z = \text{常数}$ 确定
• 总状态数 $\le (A+1)(B+1) \le (10^5+1)^2 \approx 10^{10}$？太大！

需要优化状态表示。

---

状态优化

注意到 $z = \text{总容量} - x - y$，所以状态可由 $(x, y)$ 唯一确定。
状态数 = $(A+1) \times (B+1) \le 10^{10}$，仍然太大。

但实际可达状态远少于理论值，因为 $x+y \le a+b+c \le A+B+C \le 3\times 10^5$。
我们可以用哈希表或二维数组记录访问状态。

---

BFS 实现

数据结构

• 使用 dist[x][y] 记录到达状态 $(x, y)$ 的最少步数
• 初始化为 $-1$（未访问）
• 队列存储 $(x, y)$ 状态

转移过程

对于当前状态 $(x, y)$，$z = \text{total} - x - y$，尝试所有 6 种倒法：

1. 1→2: 倒量 = $\min(x, B-y)$，新状态 $(x-\text{amount}, y+\text{amount})$
2. 1→3: 倒量 = $\min(x, C-z)$，新状态 $(x-\text{amount}, y)$
3. 2→1: 倒量 = $\min(y, A-x)$，新状态 $(x+\text{amount}, y-\text{amount})$
4. 2→3: 倒量 = $\min(y, C-z)$，新状态 $(x, y-\text{amount})$
5. 3→1: 倒量 = $\min(z, A-x)$，新状态 $(x+\text{amount}, y)$
6. 3→2: 倒量 = $\min(z, B-y)$，新状态 $(x, y+\text{amount})$

答案记录

对于每个访问的状态 $(x, y, z)$，更新：

• $ans[x] = \min(ans[x], dist)$
• $ans[y] = \min(ans[y], dist)$
• $ans[z] = \min(ans[z], dist)$

---

算法步骤

1. 初始化 $ans$ 数组为 $-1$
2. 初始化 $dist$ 数组为 $-1$
3. $dist[a][b] = 0$，将 $(a, b)$ 加入队列
4. BFS：
   • 弹出队首 $(x, y)$，计算 $z$
   • 更新 $ans[x], ans[y], ans[z]$
   • 枚举 6 种倒法，生成新状态
   • 如果新状态未访问，更新距离并入队
5. 输出 $ans[0], ans[1], \dots, ans[C]$

---

复杂度分析

• 状态数：最多 $(A+1)(B+1)$，但实际远少于 $O(\text{总容量}^2)$
• 每个状态 6 个转移
• 使用哈希表：$O(\text{状态数} \times 6)$
• 可处理 $C \le 10^5$

---

样例验证

输入：$A=2, B=7, C=9$，初始 $(1,3,6)$

BFS 过程：

• 初始状态 $(1,3)$，步数 0，更新 $ans[1]=0, ans[3]=0, ans[6]=0$
• 1→2: $(0,4)$，步数 1，更新 $ans[0]=1, ans[4]=1$
• 1→3: $(0,3)$，步数 1，更新 $ans[0]=1$（已更优）
• 2→1: $(2,2)$，步数 1，更新 $ans[2]=1$
• 2→3: $(1,0)$，步数 1，更新 $ans[0]=1$
• 3→1: $(2,3)$，步数 1，更新 $ans[2]=1$
• 3→2: $(1,7)$，步数 1，更新 $ans[7]=1$
• 继续 BFS 找到更多状态...

最终得到输出：1 0 1 0 1 1 0 1 2 1

---

总结

本题的核心解法是状态空间 BFS：

1. 用 $(x, y)$ 表示状态，$z$ 由总量确定
2. BFS 遍历所有可达状态
3. 记录每个 $k$ 值的最少步数
4. 输出 $0$ 到 $C$ 的答案

通过 BFS 可以找到所有可达状态的最短路径，解决这个倒水问题。