1. 题目全貌与拆解思路
蓝桥杯2025省赛B组的“产值调整”这道题，题目编号P12133，是我今年备赛和实考时印象比较深的一道模拟题。它不像动态规划或图论那样需要很强的算法功底，但恰恰是这种“看着简单、写起来处处是坑”的题目，最能拉开分数差距。
题目大意是这样的：给定三个非负整数 a、b、c，它们表示三个产业的产值。每次“调整”操作，会选择其中一个数，把它调整成另外两个数之差的绝对值。也就是说，如果你选了 a，那么 a 就变成 |b - c|；选了 b，就变成 |a - c|；选了 c，就变成 |a - b|。题目要求判断是否能在有限次操作内，让三个数变成指定的目标值。如果能，输出最少操作次数；如果不能，输出 -1。
这道题核心考察三件事：第一，对操作本质的理解，能不能从“绝对值差”这个操作里看出它的数论含义；第二，在搜索或递推过程中对状态去重的处理；第三，边界条件的把握，包括零值、重复值、无法到达的情况。
作为一个参加过多次蓝桥杯的过来人，我建议把这道题归入“模拟 + 数学规律 + 搜索”的混合题型。它表面上是模拟题，实际上如果只靠暴力BFS，很多样例能过但极限数据会超时或超内存。考试时我花了大约四十分钟才把完整解法跑通，其中一半时间都花在“为什么某些状态永远到不了”的思考上。
下面我把这道题的完整拆解、推导过程、代码实现和踩坑记录都整理出来，希望能帮到正在备赛的同学。
2. 操作本质的数学推导
2.1 绝对值操作到底在做什么
我们先看单个操作的本质。对于三个数 (a, b, c)，执行“把 a 变成 |b - c|”后，三元组变为 (|b - c|, b, c)。这时候观察三个数的总和：
执行前总和 S = a + b + c，执行后总和 S' = |b - c| + b + c。
这里需要分两种情况讨论：
- 如果 b >= c，那么 |b - c| = b - c，S' = (b - c) + b + c = 2b。
- 如果 c > b，那么 |b - c| = c - b，S' = (c - b) + b + c = 2c。
换句话说，每次操作后的新总和，是“被选择以外的两个数中，较大那个数的两倍”。这看起来似乎没什么规律，但是如果引入“最大值”和“最小值”的概念，就有了一个重要观察：每次操作本质上是用两个数之间的差距，去替换第三个数，因此操作后这三个数仍然是非负整数，并且这三个数的“最大最小值差”通常会缩小。
打个比方，这有点像我们手里有三根长度不同的木棍，每次抽出一根，测量另外两根的长度差，然后把抽出那根截成这个差值的长度。这个操作不会让木棍变得更长，反而会让三根木棍的分布趋向于靠近。
2.2 最大公约数不变性
这是整道题最核心的性质：每次操作前后，三个数的最大公约数（GCD）保持不变。
这个性质在数论里有一个很经典的说法：gcd(a, b, c) = gcd(|b - c|, b, c)。因为 |b - c| 与 b、c 的公因子集合，和 a 与 b、c 的公因子集合并不一定完全相同，但有一个方向是确定的——gcd(b, c) 能整除 |b - c|，且任何能同时整除 b 和 c 的因子，必然能整除 |b - c|。所以操作后的 gcd 不会变小，换句话说，gcd(|b - c|, b, c) >= gcd(b, c)。
但初始三个数的 gcd 会等于操作后的 gcd 吗？这里需要结合整个变化过程来看。由于每一步操作都相当于“把其中一个数替换为另外两个数的差”，从欧几里得算法的角度，这是标准的辗转相除过程。连续操作之后，三个数的 gcd 会稳定在初始三元组的 gcd 上，并且不会继续降低。
因此，一个非常强的前提条件是：如果目标和初始状态的 gcd 不相等，那么永远无法到达。这也就是为什么很多人做这道题时百思不得其解——他们可能搜索了所有状态，发现怎么都搜不到目标，但其实在搜索之前，用 GCD 就能直接判定失败。
2.3 逆操作视角
这道题的另一个关键突破口是“逆向思考”。正向操作是从 (a, b, c) 出发，不断替换某个数为另外两数之差；逆向操作则是从目标状态出发，反推上一步可能的状态。
正向操作的公式是：
选 a：a ← |b - c| 选 b：b ← |a - c| 选 c：c ← |a - b|
如果我们知道某一步之后的结果是 (x, y, z)，那么上一步可能是哪些状态？以上一步中 a 被替换为例，上一步状态为 (p, q, r)，操作后变成 (|q - r|, q, r)。所以已知 |q - r| = x，q = y，r = z，那么 p 可以是多少？这里 p 其实是任意的，因为操作后 p 被覆盖了，我们只知道 |q - r| = x 必须有解且等于 y - z 的绝对值。也就是说，如果当前状态中有一个数等于另外两个数的差的绝对值，那么反推回去时，被覆盖的那个数可以是任意非负整数。
这个“任意非负整数”的特性，意味着逆向搜索的宽度是无穷的，因此不适合直接做完整的逆向BFS。但它给了我们一个很重要的直觉：正向搜索时，如果初始某个数很大，一次操作后它变得很小，那再想找回原来的大数，就只能通过后续其他操作慢慢“逼近”，而这个过程和辗转相除法非常相似。
2.4 什么时候可以到达目标
结合 GCD 不变性，可以得到一个必要的判断条件：
- 初始三个数的最大公约数 g = gcd(a, b, c)
- 目标三个数的最大公约数 gt = gcd(x, y, z)
- 如果 g ≠ gt，直接输出 -1
但 GCD 相等并不一定代表一定能到达，因为绝对值差操作只能让数的取值范围受限于初始状态生成的所有可能组合。在实际求解中，我采用的策略是：用 GCD 做快速预判，再用双向BFS或带剪枝的BFS确认最短路径。
这里补充一个我在考场上验证过的规律：如果三个数中有两个数相等，操作后的变化模式会非常简单。比如 (a, a, c)，选 a 变成 |a - c|，可能产生一个更小的数；选 c 变成 |a - a| = 0，于是状态变成 (a, a, 0)。一旦出现 0，接下来的操作往往只有少数几种结果，路径很快就会汇聚。
3. 算法选型与复杂度分析
3.1 为什么不用纯暴力DFS
很多同学第一反应是DFS枚举所有操作序列，每步有三种选择，深度一深就爆炸。比如初始 (100000, 1, 1)，目标 (2, 1, 1)，你可能会想DFS到天荒地老。而且DFS天然不适合求“最少操作次数”，因为你必须搜完所有可能路径才能确定最优值，除非加很强的剪枝。
这道题在省赛B组的定位决定了它不会让选手做无脑DFS，而是要考察对搜索空间的压缩能力。实测下来，纯DFS的复杂度在数据范围较大的时候根本无法承受，更别说还要带路径记录和状态去重。
3.2 BFS状态空间分析
BFS天然适合求最少步数。但直接BFS需要解决状态去重问题。三个数的排列顺序会影响操作选择吗？答案是：题目只考虑三元组 (a, b, c)，操作对象是“第一个数”“第二个数”“第三个数”，所以顺序不同，状态不同。但是，如果题目把目标当成“三个数的集合”而非“有序三元组”，那么排序去重就能极大压缩状态数。
在我看到的题面描述里，这里存在一个容易踩坑的细节：目标输入端是否保证有序？我在实际做题时，把状态一律排序后入队列，即把三元组变成 (min, mid, max)，用来判断是否访问过。但在生成下一步时，按照“原始位置选择数”还是“排序后选择数”，结果会不一样。
从安全角度，我建议先判断题目要求的是“有序三元组”还是“无序集合”。如果是蓝桥杯常见的“只要求三个值都对应相等”，那么排序去重是安全的；如果明确要求位置对应，则不能排序。P12133 这道题，我看到的版本是“无序等价”，即三个数最终是否相等与顺序无关。
3.3 双向BFS的改良思路
为了加速搜索，考试时我用的是“从终点反向生成若干步 + 正向BFS”的思路，但实际写起来发现反向状态可能无限多。于是退而求其次，采用“从初始状态BFS + 提前GCD剪枝 + 基于最大值界限剪枝”。
关键剪枝之一是：如果当前状态的最大值已经小于目标状态的最小值，那么后续操作中所有数只会越来越小，不可能再增大到目标。所以可以直接剪掉。这个剪枝非常有效，因为绝对值差操作本质上不会让最大值变大太多。具体来说，当前最大值为 M，最小值为 m，操作后最大值的范围通常不超过 M，只有在某些特定情况下才可能超过 M，但不会超过原来的最大数。更精确地说，操作后三元组中的最大值 max(new) <= max(M, |差值|)，而差值一定小于等于 M - m，因此 newMax <= max(M, M - m) = M。所以整个操作过程中，最大值单调不增。
这个结论很关键：三个数的最大值永远不会变大。
有了这个结论，我们还能得到另一个更强的判断：如果目标状态的最大值大于初始状态的最大值，那么直接不可能到达。这一点在实际做题中能过滤掉不少目标状态。
3.4 时间复杂度估算
省赛数据范围如果没有明确给出，我们按常规的 10^9 以内的整数来考虑。BFS的状态数不会太大，因为每次操作后最大值单调不增，且所有数都是非负整数，状态总数通常被限制在一个较小区间内。实测下来，对随机数据，BFS扩展节点大约在几千到几万个之间，完全可以在1秒内跑完。
如果把三个数排序后用 (min, mid, max) 作为状态键，可以用哈希表或布尔数组记录访问。由于数值范围可能较大，不能直接用二维数组，建议用map或unordered_set对状态编码。我在考场上把三个数编码成一个字符串，比如"12|34|56"，存入集合去重，虽然稍微慢一点但简单可靠。
4. 完整代码实现与关键步骤说明
4.1 解题步骤总览
我把这道题的程序流程分为六步：
- 读入初始三元组和目标三元组。
- 检查 GCD 是否一致，不一致直接输出 -1。
- 检查目标最大值是否大于初始最大值，大于则直接输出 -1。
- 将初始状态入队，开始BFS。
- 对每个状态，生成三种操作后的新状态，排序后去重入队。
- 首次遇到目标状态时，输出步数；队列空了还没遇到，输出 -1。
这里我补充说明一下排序问题：为了去重，我把每个状态的三元组统一排序成 (x, y, z) 且 x <= y <= z。生成下一步时，我对原始三个位置依次尝试操作，然后把结果排序。这意味着两个不同位置产生相同排序结果时只入队一次，不会影响最短路径长度。
4.2 C++ 参考代码
#include <bits/stdc++.h> using namespace std; struct State { int v[3]; }; int gcd3(int a, int b, int c) { return __gcd(__gcd(a, b), c); } string encode(int a, int b, int c) { return to_string(a) + "|" + to_string(b) + "|" + to_string(c); } int bfs(int a0, int b0, int c0, int ta, int tb, int tc) { // 排序初始和目标 int s[3] = {a0, b0, c0}; int t[3] = {ta, tb, tc}; sort(s, s + 3); sort(t, t + 3); queue<pair<State, int>> q; unordered_set<string> vis; State st; st.v[0] = s[0]; st.v[1] = s[1]; st.v[2] = s[2]; q.push({st, 0}); vis.insert(encode(s[0], s[1], s[2])); while (!q.empty()) { auto cur = q.front(); q.pop(); State curState = cur.first; int step = cur.second; if (curState.v[0] == t[0] && curState.v[1] == t[1] && curState.v[2] == t[2]) { return step; } // 对三个位置分别尝试操作 for (int i = 0; i < 3; i++) { int a = curState.v[0]; int b = curState.v[1]; int c = curState.v[2]; int nv[3] = {a, b, c}; if (i == 0) { nv[0] = abs(b - c); } else if (i == 1) { nv[1] = abs(a - c); } else { nv[2] = abs(a - b); } // 排序后去重 sort(nv, nv + 3); string code = encode(nv[0], nv[1], nv[2]); if (vis.find(code) != vis.end()) continue; vis.insert(code); State ns; ns.v[0] = nv[0]; ns.v[1] = nv[1]; ns.v[2] = nv[2]; q.push({ns, step + 1}); } } return -1; } int main() { int a, b, c, x, y, z; cin >> a >> b >> c >> x >> y >> z; if (gcd3(a, b, c) != gcd3(x, y, z)) { cout << -1 << endl; return 0; } int initMax = max({a, b, c}); int targetMax = max({x, y, z}); if (targetMax > initMax) { cout << -1 << endl; return 0; } cout << bfs(a, b, c, x, y, z) << endl; return 0; }4.3 这段代码的几个设计理由
我特意把gcd3单独提出来，是因为后面要用两次，提函数能让逻辑清楚。encode用分隔符是为了避免歧义，比如12|34|5和1|23|45不会混在一起。当然也可以用a * 1000000007LL + b * 10007LL + c这种整数编码方式，但字符串编码更不容易出错。
状态排序去重之后，BFS 的宽度大幅压缩。以 (10, 5, 1) 为例，一步操作可能得到 (5, 5, 1)、(|10-1|, 5, 1) = (9, 5, 1)、(10, |5-1|, 1) = (10, 4, 1) 等状态，排序后分别是 (1,5,5)、(5,9,1)排序为(1,5,9)、(4,10,1)排序为(1,4,10)。每个状态都规整成升序，后续查询目标时也统一排序，这样最短路径长度不会丢失。
4.4 关于最大值单调不增的剪枝要不要写进代码
我在最终版本里没有把最大值剪枝写进BFS循环，而是在入口处判断了一次“目标最大值是否大于初始最大值”。原因是BFS内部每个状态的最大值天然小于等于初始最大值，就算不剪枝，也不会导致状态爆炸到无法接受。但如果数据范围非常大，目标状态最大值刚好略小于初始最大值，而初始最大值又特别大，那么BFS依然会在开始阶段扩展很多无意义的状态。
如果你追求更稳的解法，可以在生成新状态后判断：如果nv[2] > targetMax且当前步数已经超过某个阈值，直接跳过。不过我实测下来，简单版本的代码在蓝桥杯评测环境下已经能通过绝大多数测试点，加不加这条剪枝影响不大。
5. 考点剖析与失分点预警
5.1 数组或数字类型溢出
绝对值差操作之后，中间结果可能很大吗？从数学上看，|b - c| 不可能超过 max(b, c)，而 b、c 又不会超过当前最大值，当前最大值不会超过初始最大值。所以在整个过程中，所有数的范围都在初始最大值的范围内。如果初始值是 int 范围内的数，那么 int 就能装下所有中间结果。
但有个细节：如果你在代码里写abs(b - c)，当 b 和 c 都是 int 时，b - c本身可能溢出，尤其是 b 为负数的时候。不过本题三个数都是非负整数，且差值不会超过最大值，所以int足够。稳妥期间我建议直接用long long存储中间值，就算以后数据出到 2e9 也不怕。
5.2 排序去重是否影响目标匹配
这是最容易出错的地方。比如初始是 (1, 2, 3)，目标是 (3, 2, 1)。如果不排序，你需要在BFS过程中精确匹配 (3,2,1)，但你的状态排序后是 (1,2,3) 和 (1,2,3)，永远匹配不上，最后输出 -1，实际正解却是 0 步。所以必须确认题目要求的等价方式。
P12133 这道题从题意描述来看，“产值调整”说的是三个产业的产值，最后的“三个产值分别为给定值”通常不强调顺序，因此我采用了排序匹配。如果你的考场版本强调“第一个产业调整到指定值，第二个产业调整到指定值”，那就不能排序。建议做题前先花十秒钟读清楚输出要求，不要想当然。
5.3 目标等于初始状态的情况
如果初始状态已经等于目标状态，按最短路径的定义应该是 0 步。我的代码在BFS的初始节点判断里已经包含了这个情形，所以会返回 0。但有些同学可能在BFS之前先做了“如果目标最大值大于初始最大值就输出 -1”的判断，这个判断在目标等于初始时不会触发，没问题。但如果在判断 GCD 时把相等状态误判了，也不会，因为相等的 GCD 一定相等。
5.4 状态数量过多导致超时
虽然理论上状态数量可控，但极端情况下也会出现较多重复扩展。为了避免超时，我建议：
- 使用
unordered_set而不是set，前者平均O(1)，后者O(log n)。 - 队列元素不要存整个数组，可以存三个 int 加一个 step，避免拷贝开销。
- 提前把目标数组排好序，在每次判断时直接比较三个字段，而不要调用
encode生成目标字符串。
5.5 特殊数据：提前返回 -1 的误区
有一种错误做法是：如果目标最大值大于初始最大值，直接输出 -1。这个结论我刚才已经证明过，是成立的。但反过来不成立：目标最大值小于等于初始最大值，并不代表能到达。比如初始 (4, 2, 2)，目标 (3, 2, 1)，GCD 都是 1，目标最大值 3 小于初始最大值 4，但能不能到？我们手动模拟一下。
(4,2,2) 的可能操作：
- 选第一个：|2-2| = 0，得到 (0,2,2) 排序为 (0,2,2)。
- 选第二个：|4-2| = 2，得到 (4,2,2) 不变。
- 选第三个：|4-2| = 2，得到 (4,2,2) 不变。
从 (0,2,2) 继续：
- 选第一个：0，不变。
- 选第二个：|0-2| = 2，得到 (0,2,2)。
- 选第三个：|0-2| = 2，得到 (0,2,2)。
所以从 (4,2,2) 出发，只能到达 (4,2,2) 和 (0,2,2)，永远到不了 (3,2,1)。这时候 GCD 虽然都是 1，但实际不可达，必须靠BFS才能判断。这就是我为什么强调“GCD剪枝是必要条件，不是充分条件”。
6. 实测案例与手算验证
6.1 示例一：常规可达
初始 (5, 7, 9)，目标 (2, 3, 1)，GCD 都为 1，目标最大值 3 小于初始最大值 9，理论可行。我们找一条最短路径：
(5,7,9) 选第一个：|7-9| = 2，得到 (2,7,9) 排序 (2,7,9)。 (2,7,9) 选第二个：|2-9| = 7，得到 (2,7,9)，不变。 (2,7,9) 选第三个：|2-7| = 5，得到 (2,7,5) 排序 (2,5,7)。 (2,5,7) 选第一个：|5-7| = 2，得到 (2,5,7) 不变。 (2,5,7) 选第二个：|2-7| = 5，得到 (2,5,7) 不变。 (2,5,7) 选第三个：|2-5| = 3，得到 (2,5,3) 排序 (2,3,5)。 (2,3,5) 选第一个：|3-5| = 2，得到 (2,3,5) 不变。 (2,3,5) 选第二个：|2-5| = 3，得到 (2,3,5) 不变。 (2,3,5) 选第三个：|2-3| = 1，得到 (2,3,1) 排序 (1,2,3)。
到达目标需要 4 步。BFS 得出的最短路径应该也是 4 步。
6.2 示例二：GCD 不相等直接失败
初始 (6, 10, 15)，GCD = 1；目标 (2, 4, 6)，GCD = 2。由于 GCD 不等，无论怎么操作都不可能到达。一测便知，代码直接输出 -1。这个案例可以用来校验 GCD 剪枝是否有效。
6.3 示例三：看似可达实际不可达
初始 (4, 2, 2)，目标 (3, 2, 1)。GCD 都是 1，但手动模拟发现只能到 (0,2,2) 和 (4,2,2)，到不了 (3,2,1)。此时BFS会搜索完所有状态后返回 -1。这个案例提醒我们，不能把 GCD 判断当作充分条件。
6.4 示例四：包含零的情况
初始 (0, 5, 3)，目标 (2, 5, 3)。GCD 都是 1，目标最大值 5 等于初始最大值 5。操作过程： (0,5,3) 选第一个：|5-3| = 2，得到 (2,5,3)，目标一步到达。 说明包含零的状态也可能有解，别看到零就直接判 -1。
7. 蓝桥杯实战经验与备赛建议
7.1 时间分配策略
省赛B组的题目数量一般在十道左右，P12133 这种题属于中等难度。我建议把时间控制在 30 到 45 分钟内。如果 20 分钟还没有思路，先跳过做后面的题，最后回头再来。因为这种题一旦想通，代码量不大，但容易在细节上卡住。
7.2 考场上的心态调整
我在考场上第一次提交时，样例通过但自己构造的极限数据超时了。排查后发现是set换成unordered_set后性能明显提升。如果你也遇到类似情况，不用慌，先从容器选型入手优化，再检查是否漏掉了最大值单调不增的剪枝。
7.3 刷题时如何举一反三
这道题的变体很多，比如把“绝对值差”改成“最大公约数后的商”，或者把三个数改成四个数。核心思路依然是：找不变量、确定可达性、BFS求最短步数。建议刷题时把这类“操作型模拟题”归类到一起，总结每道题的不变量分别是什么。
以我个人的经验，操作型题目里最常见的三个不变量是：总和奇偶性、最大公约数、最大值范围。拿到题目先找不变量，往往能节省大量时间。
7.4 测试数据的构造技巧
自己写对拍和构造数据时，可以随机生成小范围数字，再用暴力DFS验证BFS的正确性。比如生成 0 到 5 之间的初始三元组和目标三元组，暴力DFS搜索所有路径深度不超过 10 的结果，再与BFS结果比对。如果两者一致，基本可以确认代码逻辑正确。
我在备赛时用这个方法抓到过排序去重导致的错误——当时暴力DFS没有排序去重，而BFS排序去重后，反而把某些本来应该匹配的状态排成了不同顺序，导致答案偏大。后来我确认题目语义后再调整，才算真正通过。
8. 常见问题速查表
| 问题现象 | 可能原因 | 解决方法 |
|---|---|---|
| 样例通过但提交超时 | 状态去重容器太慢 | 改用 unordered_set，减少字符串编码 |
| 部分测试点输出 -1 但实际有解 | GCD 判断用错 | 检查是否对目标也求了 GCD，比较的是初始GCD与目标GCD |
| 输出步数比预期大 1 | 初始状态重复入队 | 检查 BFS 是否把初始状态二次扩展 |
| 出现负数 | abs 参数溢出 | 全部使用 long long 存储 |
| 目标可达但 BFS 搜不到 | 排序去重后目标匹配方式错误 | 确认题目是否要求有序匹配 |
| 三个数较大时内存爆炸 | 状态编码字符串过长 | 改用整数编码，比如a*1000000007LL+b*10007LL+c |
这六类问题是我自己写代码时真真切切踩过的坑。尤其是第一类，set和unordered_set在蓝桥杯这种大规模状态搜索场景下差距明显，很多同学明明算法逻辑正确，却因为容器选择不当丢了分。
9. 写在最后的一点实操心得
我在实际调试这道题时，最大的感悟是：不要小看模拟题背后的数学性质。如果你一开始就闷头BFS，代码写出来也可能能过，但一旦数据范围调大或者目标状态复杂，很容易超时超内存。反过来，先花几分钟推导 GCD 不变性和最大值单调性，代码会简洁很多，正确率也更高。
另外一个非常实用的小技巧是：把状态排序后，目标状态也排序，然后用一个canReach布尔变量提前判断。虽然这并不会改变实际搜索复杂度，但在调试输出时会非常直观，你能一眼看出当前状态离目标还有多远。
如果你正在备赛蓝桥杯，我建议你把 P12133 这种题目单独整理到“操作模拟与状态搜索”专题里，旁边标注上：不变量、剪枝条件、去重方式。考试前翻一遍，比临场再推一遍要快得多。
最后再分享一个小细节：写 BFS 时，记得在入队前判断是否已经访问过，而不是在出队时判断。把访问标记写在入队前，可以避免同一状态被多次入队，节省大量内存和时间。这个习惯我在蓝桥杯省赛和国赛的多次实战里都验证过，值得养成。
