企业官网建设流程全解析

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 = 1，t = 9，直线距离是 8，但在环上从 1 减 2 次也能到 9。如果不理解环的规则，你会在最优解里漏掉很多方案。

从 1 到 9 为什么减 2 次可以？因为 1 减一次变 0，0 再减一次变 9。这是题目里“0 减 1 变成 9”的循环规定。所以 sub =(1 - 9 + 10) % 10= 2。同样，从 9 到 1，add =(1 - 9 + 10) % 10= 2，这里不是加两次，而是 9 加一次变 0，0 加一次变 1。

2.2 每个目标数字的可行性判断

对于目标 t，只要满足add <= a或者sub <= b，就说明当前这一位能变成 t。

这里要注意，不是要求两个条件同时满足。因为变成同一个目标数字，我只需要选加或选减其中一种方式完成即可。比如 d = 5，t = 9，add = 4，sub = 6。如果 a = 4，b = 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 = 5，t = 9，add = 4，sub = 6，a = 4，b = 2 这种输入直接被误判为不可行。因为 4 <= 4 成立但 6 <= 2 不成立，整个条件失败，导致本可以变成 9 的一位被我放弃了。

还有一种更隐蔽的误判：不能把add和sub同时扣掉。比如 d = 5，t = 9，add = 4，sub = 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 = 9，t = 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 = 5，a、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 = 3，t = 8，add = 5，sub = 5，没什么影响。但 d = 1，t = 9，add = 8，sub = 2，如果 a = 8，b = 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

最高位 1，t = 9 需要加 8 或减 2，a = 1，b = 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。十位 2，t = 9 加 7 或减 3，b = 1 不够。t = 8 加 6 减 4，不够。…… t = 1 需要减 1，b = 1 可行，所以十位变 1。个位 3，剩余 a = 0，b = 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

第一位 1，a = 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 短了整整一半。希望你也能体会到这种“化简”的乐趣。