1. 题目背景与需求解析倒水问题是蓝桥杯竞赛中的经典题型考察参赛者的算法设计能力和数学建模思维。这类题目通常描述为给定若干容量不同的容器通过一系列倒水操作最终得到特定容量的水。P12167作为2025年省赛题目延续了蓝桥杯一贯注重基础算法与实际问题结合的特点。从竞赛角度看这类题目主要测试以下几个核心能力状态空间建模能力如何表示水量变化搜索算法应用BFS/DFS的选择与优化数学思维最大公约数等数论知识的应用边界条件处理满杯、空杯等特殊状态2. 问题建模与算法选择2.1 状态表示方法最直接的建模方式是使用元组表示各容器中的当前水量。例如对于两个容器A和B状态可以表示为(A_water, B_water)。这种表示法的优势在于直观反映系统状态便于哈希存储和比较适合作为搜索算法的节点# Python示例状态类定义 class State: def __init__(self, a, b): self.a a self.b b def __hash__(self): return hash((self.a, self.b)) def __eq__(self, other): return self.a other.a and self.b other.b2.2 基本操作枚举在任何状态下通常有6种基本操作将A装满将B装满将A倒空将B倒空将A倒入B直到A空或B满将B倒入A直到B空或A满// C语言操作示例 typedef struct { int a; int b; } State; State fillA(State s, int capA) { return (State){capA, s.b}; }2.3 算法选择对比算法时间复杂度空间复杂度适用场景BFSO(b^d)O(b^d)最优解DFSO(b^m)O(b*m)内存有限数学方法O(1)O(1)特定条件提示蓝桥杯竞赛中BFS通常是更稳妥的选择因为它能保证找到最少操作步数的解3. BFS实现详解3.1 基础BFS框架广度优先搜索是解决此类问题的标准方法其核心是通过队列系统地探索所有可能状态from collections import deque def water_pouring(capA, capB, target): visited set() queue deque([(0, 0, [])]) # (a, b, path) while queue: a, b, path queue.popleft() if a target or b target: return path if (a, b) in visited: continue visited.add((a, b)) # 生成所有可能的下一个状态 next_states [ (capA, b, path [Fill A]), # 填满A (a, capB, path [Fill B]), # 填满B (0, b, path [Empty A]), # 倒空A (a, 0, path [Empty B]), # 倒空B # A倒入B (a - min(a, capB - b), b min(a, capB - b), path [A to B]), # B倒入A (a min(b, capA - a), b - min(b, capA - a), path [B to A]) ] for state in next_states: if state[:2] not in visited: queue.append(state) return None # 无解3.2 关键优化技巧路径压缩存储操作序列会消耗大量内存改为存储前驱状态双向BFS从初始状态和目标状态同时开始搜索数学剪枝利用数论知识提前判断是否有解// C语言优化示例使用位压缩存储状态 #define MAX_CAP 1000 typedef unsigned long long StateKey; StateKey make_key(int a, int b) { return ((StateKey)a 32) | b; } void unpack_key(StateKey key, int *a, int *b) { *a key 32; *b key 0xFFFFFFFF; }4. 数学方法解析4.1 贝祖定理应用倒水问题是否有解取决于目标容量是否能被容器容量的最大公约数整除。具体来说若有两个容器容量分别为A和B则可以得到的水量x必须满足x ≤ max(A, B)x必须是gcd(A, B)的倍数import math def has_solution(capA, capB, target): return (target max(capA, capB) and target % math.gcd(capA, capB) 0)4.2 数学解法步骤检查是否有解使用贝祖定理通过扩展欧几里得算法找到系数根据系数确定操作序列// C语言实现扩展欧几里得算法 int extended_gcd(int a, int b, int *x, int *y) { if (b 0) { *x 1; *y 0; return a; } int x1, y1; int gcd extended_gcd(b, a % b, x1, y1); *x y1; *y x1 - (a / b) * y1; return gcd; }5. 竞赛实战技巧5.1 常见错误与调试无限循环忘记记录已访问状态边界条件未处理满杯/空杯时的倒水操作性能问题使用字符串存储路径导致内存爆炸调试技巧在BFS循环中加入状态打印观察搜索过程# 调试打印示例 print(fCurrent: ({a}, {b}), Queue size: {len(queue)})5.2 蓝桥杯特有注意事项输入输出格式严格遵循题目要求的格式时间限制Python需注意优化C/C更占优势特殊测试用例容器容量相等目标量为0容器容量与目标量相等5.3 性能对比测试语言测试用例(3,5,4)测试用例(7,11,2)内存消耗Python0.12s0.35s15MBC0.003s0.008s2MB6. 扩展变种问题6.1 多容器问题当容器数量增加到3个或更多时状态表示需要扩展但基本方法不变# 三容器状态表示 class State3: def __init__(self, a, b, c): self.a a self.b b self.c c6.2 带成本的操作不同操作可能有不同成本如倒水耗时此时需要使用优先队列Dijkstra算法import heapq def dijkstra_water(capA, capB, target): heap [] heapq.heappush(heap, (0, 0, 0, [])) # (cost, a, b, path) # 其余部分类似BFS6.3 不可测量问题某些变种可能限制操作类型如只能填满或倒空这需要调整状态生成逻辑。7. 代码模板与资源7.1 Python完整模板from collections import deque import math def solve_water_pouring(capA, capB, target): def get_next(a, b): return [ (capA, b), # Fill A (a, capB), # Fill B (0, b), # Empty A (a, 0), # Empty B (a - min(a, capB - b), b min(a, capB - b)), # A to B (a min(b, capA - a), b - min(b, capA - a)) # B to A ] if not has_solution(capA, capB, target): return None visited set() queue deque([(0, 0, [])]) while queue: a, b, path queue.popleft() if a target or b target: return path if (a, b) in visited: continue visited.add((a, b)) for na, nb in get_next(a, b): if (na, nb) not in visited: # 需要根据具体操作更新路径 queue.append((na, nb, path [f({a},{b})-({na},{nb})])) return None7.2 C语言关键部分#include stdio.h #include stdlib.h #include string.h #define MAX_SIZE 1000 typedef struct { int a; int b; int steps; char path[1000]; } State; State queue[MAX_SIZE*MAX_SIZE]; int front 0, rear 0; void enqueue(State s) { queue[rear] s; } State dequeue() { return queue[front]; } int is_empty() { return front rear; } // 其余BFS实现类似Python版本8. 训练建议与学习路径基础训练实现标准两容器问题添加路径记录功能优化内存使用进阶训练实现三容器版本添加操作成本计算实现双向BFS竞赛准备收集历年蓝桥杯真题进行限时编程训练学习优秀解题报告对于Python选手建议重点掌握collections.deque的高效使用状态哈希技巧生成器表达式优化内存对于C/C选手应熟练掌握队列的手动实现位压缩存储技巧内存预分配策略