P8801 这道题我是真的一句话都忘不掉。名字叫“最大数字”背景是蓝桥杯 2022 年国赛 B 组难度标的是“普及”。但你别看它定位不高这道题在考场上能卡住一批练过不少动态规划题的人。原因很简单题面太短了短到容易让人想歪操作太“绕”了绕到很多选手一上来就往广搜、状态压缩里钻结果越写越复杂。我这篇就围绕它完整的思考链展开从题目建模、贪心选择、代码实现到为什么标签挂在“动态规划”上但正解其实是更简单的思路再到考场上的调试技巧和常见翻车点。不管你是准备蓝桥杯还是在刷 OJ 上的搜索、贪心、DP 题这篇都值得看完再动手敲一遍。1. 题目到底在说什么1.1 两种操作的本质题面给出了一个正整数你可以对它执行两类操作操作 1选择一位数字让它加 1。如果这位原来是 9加 1 之后变成 0。操作 2选择一位数字让它减 1。如果这位原来是 0减 1 之后变成 9。两类操作都有次数上限。比如操作 1 最多执行 a 次操作 2 最多执行 b 次。最终要求通过若干次操作能得到的最大的整数是多少。这里最关键的一点是每一位的变化是独立的。你在第 k 位做操作不会影响其它位的数字。而且因为“9 再加变成 0”“0 再减变成 9”所以每一位都相当于在一个长度为 10 的环上移动。这个环的特性让这道题从“普通加加减减”变成了“模 10 循环移动”。很多选手刚开始会把每一位单独拎出来做 BFS比如用状态记录这一位现在是多少还有多少剩余操作次数然后暴力搜。对于一位来说这是可行的但把多位放在一起状态空间立刻爆炸。我自己第一次做的时候也差点走进这个坑。1.2 为什么高位能决定一切题目要的是“最大整数”不是“最大各位数字之和”也不是“最优操作次数最少”。这个目标决定了我们必须优先照顾高位。举个非常直观的例子如果最高位能从 1 变成 2即使后面所有位都被迫变成 0这个数也从 1999 变成了 2000。2000 一定大于 1999。换句话说最高位每增加 1哪怕只增加 1它带来的收益也大于它右边所有位同时从 0 变成 9 的总收益。这个性质在十进制里是天然的第 i 位增加 1数值增量是固定权重它后面的所有位从全 0 变成全 9总增量也追不上它的一位权重。正是这一点为后面整套贪心策略提供了理论依据。2. 从建模到贪心核心思路拆解2.1 每一位变成一个目标数字的代价先把问题抽象成对于当前某一位原来的数字是 d我想让它变成 t。那么我至少需要消耗多少操作次数因为是在环上走从 d 到 t 有两种纯走法只做操作 1加法需要(t - d 10) % 10次。只做操作 2减法需要(d - t 10) % 10次。用公式写出来就是add (t - d 10) % 10 sub (d - t 10) % 10这里有个容易算错的地方不要直接用abs(t - d)。比如 d 1t 9直线距离是 8但在环上从 1 减 2 次也能到 9。如果不理解环的规则你会在最优解里漏掉很多方案。从 1 到 9 为什么减 2 次可以因为 1 减一次变 00 再减一次变 9。这是题目里“0 减 1 变成 9”的循环规定。所以 sub (1 - 9 10) % 10 2。同样从 9 到 1add (1 - 9 10) % 10 2这里不是加两次而是 9 加一次变 00 加一次变 1。2.2 每个目标数字的可行性判断对于目标 t只要满足add a或者sub b就说明当前这一位能变成 t。这里要注意不是要求两个条件同时满足。因为变成同一个目标数字我只需要选加或选减其中一种方式完成即可。比如 d 5t 9add 4sub 6。如果 a 4b 2那add a成立于是这一位可以变成 9代价是消耗 4 次操作 1操作 2 完全不用动。如果两种方式都可行那就选消耗更小的那个省下的次数留给后面的位。这个选择在绝大多数情况下是安全的因为后面的位权重更低所以当前位能变到多大优先级永远排在剩余次数分配之前。2.3 为什么逐位贪心是对的很多人看到这类题会怀疑当前位选了一个很大的数字代价是不是可能太大了导致后面某一位从 1 变成 9 的机会没了反而整体变小这个怀疑很合理但在十进制逐位比较下不成立。关键在于位的权重。假设当前处理的是第 i 位它的权重是 10 的某次幂。当前位增加 1带来的数值增量是 10 的这次幂。而第 i 位之后的所有位即使每一位都从 0 变成 9总增量最大也只是10^i - 1依然小于 10 的一次幂增量。所以在当前位还能继续增大的时候把所有能用上的资源优先砸在当前位永远是全局最优的。用大白话说百位从 1 变 2比十位和个位从 00 变 99 还值钱。因此处理完最高位之后再去处理次高位每一层选择当前可达最大值就是一个严格的贪心过程而不是碰巧过得去的“启发式”。3. 具体实现步骤与代码3.1 数据预处理读入一个数字 n把它当成字符串处理是最方便的。原因有两个可以从左到右逐位访问天然符合“从高位到低位”的处理顺序。最后的结果也是字符串直接修改对应字符即可不用做复杂的整数拼接。操作次数 a 和 b 用long long因为题面里它们可以给到很大的值。别用int参与运算时一旦接近上限很容易出错。然后进入主循环从字符串的最左边开始逐位尝试把这一位变成 9不行就变成 8再不行就变成 7一直到 0。如果当前位保持原样那就不消耗任何次数。3.2 核心逻辑枚举目标数字对于每一位数字 d我按 t 从 9 到 0 的顺序枚举目标值。为什么从 9 开始因为要的是最大数字能取 9 绝不取 8。for (int t 9; t 0; --t) { int add (t - d 10) % 10; int sub (d - t 10) % 10; if (add a || sub b) { if (add sub) { a - add; } else { b - sub; } ch 0 t; break; } }这段代码里有个不易察觉的细节当 add 和 sub 都小于等于剩余次数时我选择消耗更小的那一种。如果 add sub就消耗 a否则消耗 b。当 add 和 sub 相等时我选择消耗 a也就是操作 1。这个选择对结果影响极小但如果要问哪种更好我倾向于优先保留 b因为后续如果想从较大的数字绕回较小的目标减法方案会更常用不过这属于体感层面的经验不是数学上的绝对最优。3.3 完整可运行代码下面是一份可以直接提交的 C 版本。注释写在关键位置方便你对照思路看。#include bits/stdc.h using namespace std; int main() { string s; long long a, b; cin s a b; for (char ch : s) { int d ch - 0; // 从 9 到 0 枚举当前位越大越好 for (int t 9; t 0; --t) { int add (t - d 10) % 10; // 纯加法需要的操作 1 次数 int sub (d - t 10) % 10; // 纯减法需要的操作 2 次数 // 两种方式有一种可行即可 if (add a || sub b) { // 选择消耗更小的方案尽量给后面的位留资源 if (add sub) { a - add; } else { b - sub; } ch 0 t; break; } } } cout s \n; return 0; }整体复杂度是 O(位数 × 10)常数级跑得飞快。有一个细节我在第一次写的时候忽略了判断里用的是||不是。当时我脑子一热写成add a sub b结果像 d 5t 9add 4sub 6a 4b 2 这种输入直接被误判为不可行。因为 4 4 成立但 6 2 不成立整个条件失败导致本可以变成 9 的一位被我放弃了。还有一种更隐蔽的误判不能把add和sub同时扣掉。比如 d 5t 9add 4sub 6如果add a成立我就只扣 add不能因为 6 也小于 b就把两个都扣一遍。同一目标只选一条路径不然白白浪费资源。4. 为什么标签写着“动态规划”4.1 官方标签与参赛直觉如果你打开某评测系统看这道题会看到它的算法标签是“动态规划”。这给很多准备蓝桥杯的同学一个误导以为必须写出状态转移方程才能过。但实际上这道题完全可以用贪心解决。那为什么还挂 DP我从出题和教学两个角度理解从出题角度这道题确实可以用记忆化搜索来做状态是“当前处理到第几位、剩余多少次操作 1、剩余多少次操作 2”。递归枚举每一位变成什么数字取最大值。这种思路本质是动态规划因为每一位的选择会影响后面的最优值整体上具备重叠子问题。从教学角度出题人希望选手理解当每一步决策都会消耗共享资源时可以用搜索或 DP 系统性枚举所有可能性而不是只靠灵光一现。所以标签标 DP 并不算错只是它不是唯一解也不是最优解。4.2 用 DFS/DP 思路怎么写如果按动态规划或深搜的思路可以定义一个递归函数dfs(pos, a, b)表示当前处理到从高位开始的第 pos 位剩余操作 1 次数 a、操作 2 次数 b能得到的最大后缀值。每次进入一位枚举目标数字 t 从 9 到 0只要 add 或 sub 可行就递归到下一位。搜完整条字符串后把结果拼起来。这种做法的正确性显然因为它在全空间搜索。问题是状态太多了如果 a 和 b 都很大状态根本没法记忆化递归深度超过 10 层之后分支数也非常可观。所以在正式比赛里暴力 DFS 只能拿部分分除非你用很强的剪枝把所有明显劣化的分支砍掉。而贪心方案只需要证明一次“高位优先”的性质然后一行循环就能扫完。两相对比你就会明白为什么比赛里遇到这种题先想清楚数学性质比急着套模板更重要。4.3 什么情况下 DP 真的必要如果题目改一改操作变成“必须从最高位开始对连续若干位同时操作”或者“每位操作次数不能共享而是分开限制”那贪心就不一定成立需要 DP 或其它算法出场。比如改成这样每次操作必须选择一个前缀把前缀所有位都加一。这种情况下某一位的变化会影响右边所有位高位决策就不再独立问题复杂度直接上升。这时候“优先照顾高位”的朴素想法就不够用了因为高位动一下低位也会被拉着动。所以说P8801 能贪心依赖的是“位与位独立”这个关键条件。题目里的操作是针对“某一位”的而不是“某一段”这个字眼才是整道题的题眼。5. 常见翻车点与调试实录5.1 忘记处理循环边界我见过很多人在 d 9t 0 的时候算 add会用t - d得到 -9然后直接取绝对值 9看起来好像没错。但实际上加法从 9 到 0 只需要 1 次不是 9 次。这就是没有用取模公式导致的错误。正确写法永远是int add (t - d 10) % 10; int sub (d - t 10) % 10;加一个 10 再取模是处理环上差值的标准姿势。这一步写错了后面全错而且样例小的时候还不一定能测出来。5.2 枚举顺序写反如果 for 循环从 0 枚举到 9那每次都会先尝试把当前位变成最小的数字最后结果会小得离谱。比如 d 5a、b 很大你从 t 0 开始试第一位就变成 0整个数的位权直接崩了。所以必须从 9 倒着枚举遇到第一个可行的 t 立刻 break。这个顺序是“最大数字”题目的生命线。5.3 操作次数扣错看下面这段“错误示范”if (add a) { a - add; } else if (sub b) { b - sub; }这个逻辑表面没问题实际有问题。当add a和sub b同时成立时它强制选择 add即使 add 比 sub 大很多。比如 d 3t 8add 5sub 5没什么影响。但 d 1t 9add 8sub 2如果 a 8b 2这个写法会消耗 8 次操作 1而不是更优的 2 次操作 2。虽然当前位都变成 9但对于后续位来说剩余资源少了一大截结果可能差很多。正确做法是if (add sub) { a - add; } else { b - sub; }也就是两个都判断然后挑消耗小的扣。5.4 数据范围要用 long long这种题输入里的 a、b 上限经常给到 10^9 级别。如果你用int减法稍微一多就溢出。尤其我在调试时喜欢用随机大数测边界用int会直接出现负数剩余次数然后误判所有位都不可变得到原数字输出结果看起来“好像也对”实际上完全错误。建议做题时养成习惯只要涉及操作次数可能超过 10^5 的题目直接开long long省心。5.5 几个值得手测的边界数据我自己在写题解的时候会拿这组数据测代码输入 123 1 1最高位 1t 9 需要加 8 或减 2a 1b 1都不行。t 8 需要加 7 或减 3不行。t 7 需要加 6 或减 4不行。t 6 加 5 减 5不行。t 5 加 4 减 6不行。t 4 加 3 减 7不行。t 3 加 2 减 8不行。t 2 加 1可行消耗 a所以第一位变 2。十位 2t 9 加 7 或减 3b 1 不够。t 8 加 6 减 4不够。…… t 1 需要减 1b 1 可行所以十位变 1。个位 3剩余 a 0b 0只能保持 3。最终得到 213。很多同学会算成 223这是因为他们让十位保持 2个位减 1 变成 2得到 222不对b 只有一次。如果十位不变个位减 1结果 122等等个位 3 变成 2结果是 122。如果十位减 1个位不变结果 213。213 122所以贪心是合理的。再测一组输入 999 0 0没有操作次数所有位都保持原样输出 999。再测输入 9 100 0只有一位操作 1 次数 100把它加到 9 需要 0 次直接保持 9。再测循环输入 10 1 0第一位 1a 1加一次变 2。第二位 0没有次数保持 0。答案是 20。如果把操作 1 用在第二位第一位还是 1第二位变 1答案是 11。20 大于 11验证了高位优先。这些手测数据看起来简单但能帮你快速定位是不是枚举顺序、取模公式或者资源扣除逻辑出了问题。6. 延展一类“逐位决策 资源分配”的通用套路6.1 从这道题抽象出的方法论P8801 表面上是字符串处理和模拟本质上是一类“逐位决策共享资源”的问题。这类问题的通用解法有四步第一步判断每一位之间是否独立。如果操作只影响单独一位那就可以逐位处理如果操作会联动其它位就必须换思路。第二步确定位权关系。十进制里高位的权重大于低位所有位之和这是所有贪心成立的基础。不要小看这一步很多题目表面上是求最大数实际上隐藏了这个性质。第三步设计“变成某个目标”的代价模型。就像这道题里用 add 和 sub 表示两种操作的消耗如果你的目标数字是任意值就需要枚举所有可能目标用代价判断可行性。第四步按位决策时如果当前位有多种达到同一目标的方式选择消耗资源更少的那一种如果多种方式消耗相同看剩余资源的分布情况优先保留后续更需要的资源。这个方法不止能解“最大数字”很多字符串构造题、进制题、数字重构题都可以套。6.2 类似的变种题目如果把这道题稍微改一下问你“最小的数字”那策略就从从 9 到 0 枚举变成从 0 到 9 枚举其它框架不变。如果再改一下操作 1 和操作 2 不再共享全局次数而是每一对相邻位之间共享一组独立次数那问题就变成一个多阶段资源分配模型需要用 DP 去做。因为某一位选什么目标不仅影响自己的剩余资源还影响右边可用的资源池位之间的决策不再是完全独立的。如果改成“每次选择一段连续区间把区间内所有数字加一”那高位优先贪心直接失效。因为动高位会牵动低位低位的收益会反过来影响高位决策这类题通常要配线段树或差分数组再结合贪心或二分难度会明显上一个台阶。我建议刷完 P8801 之后自己试着改这三个方向每种改法都动手写一遍。你会发现一道普及题目能延伸出的思维模型比单纯背十个模板有用得多。7. 写在最后的实操心得这道题我自己在训练时踩过不少坑最深刻的一条是遇到“数字操作类”题目先不要急着写 BFS 或记忆化搜索。花两分钟把操作规则“翻译”成数学表达式比如把加一减一理解成环上移动把目标数字变成代价公式往往一眼就能看到贪心结构。还有一条测试时不只要测样例一定要测“当前位能变 9但代价很大”和“当前位不能变 9只能小幅度提升”这两种场景。很多选手死在自以为正确的贪心上就是因为只测了愉快的样例没测资源紧张的情况。最后给你一个小技巧输出结果时直接修改字符串。不要在循环里频繁拼接字符串或转成整数那样既容易越界又影响效率。直接ch 0 t干净利落。这道题我在复现时全代码不到 30 行核心循环不超过 10 行比一开始写的 BFS 短了整整一半。希望你也能体会到这种“化简”的乐趣。