第六篇了。按惯例我还是围绕几个有关联的知识点挑六道左右有代表性的题目做精析不追求刷题数量而是把每道题的思考路径、代码模板和踩坑记录都留下来。这期选了模幂、构造、背包、贪心、剪枝、堆维护六个方向其中背包部分从0-1背包一路拆到多维背包、分组背包和退背包算是整篇里分量最重的一块。之所以这么排是因为最近在打比赛和复盘时明显感觉到单纯会写模板远远不够得知道每个经典模型在什么场景下变形、什么时候能优化、什么时候该果断放弃DP换思路。这六道题正好把我这几个月的薄弱环节都戳了一遍整理出来给同样在修炼算法路上的朋友做个参照。1. 选题思路与整体规划1.1 为什么是这六个知识点先说选题逻辑。模幂和构造题是很多人的老大难它们不像动态规划那样有固定的状态定义套路更多是靠数感、手算经验和对数学性质的敏感度。背包系列则是面试和算法竞赛里出现频率极高的模型从最基础的0-1背包到分组背包、退背包一脉相承非常适合一次性吃透。贪心、剪枝、堆维护这三个点表面上分散实际上在实战里往往互相纠缠贪心需要证明证明不出来就可能要退回去用搜索搜索跑不动就需要剪枝而反悔贪心和动态最值类问题又离不开堆的维护。这样一排六个知识点形成了一条自然的修炼路径先打数学基础再啃背包主干最后用剪枝和堆来应对复杂搜索与贪心场景。1.2 六道题的考点分布先把这期的题单拉出来后面每一章都会有一道完整的精析。题型核心考点难度适合谁练模幂快速幂二进制拆分、取模细节、逆元场景入门刚学数论的人构造奇偶排布、反推验证、边界处理中等遇构造题就慌的人0-1背包滚动数组、逆序枚举、状态初始化入门动态规划新手多维背包多成本维度扩展、复杂度预估中等会基础背包想进阶的人分组背包至多/恰好/至少选一个三种模型中高想彻底搞懂背包变体的人反悔贪心优先队列维护反悔点、推公式证明中高凭感觉写贪心总被卡的人搜索剪枝可行性剪枝、最优性剪枝、顺序优化中高做搜索题容易TLE的人堆维护优先队列、延迟删除、自定义堆中等想系统梳理堆用法的人这里说一句题外话看到后台有人搜“哪个版本的植物大战僵尸背包有铁桶和时空碎片”我只能说背包模型确实已经深入人心到游戏玩家都来凑热闹了但算法里的背包可比游戏背包严肃多了下面正经开整。2. 模幂与构造数学题的两种“不讲道理”2.1 快速幂模板二进制拆分和取模的三个坑第一道是经典的模幂题输入三个整数 a、b、m求 a^b mod m其中 b 可能达到 10^18 级别。直接把幂pow出来显然不现实正确做法是用快速幂核心思想是把指数按二进制拆开比如 b13 时二进制是 1101那么 a^13 a^(841) a^8 * a^4 * a^1。代码写出来很简洁long long mod_pow(long long a, long long b, long long m) { long long res 1 % m; a % m; while (b 0) { if (b 1) res res * a % m; a a * a % m; b 1; } return res; }这段代码的细节坑不少。第一res必须初始化为1 % m因为当 m1 时任何数对1取模都是0直接初始化为1会得到错误结果。第二a在进入循环前要先取模否则 a 很大时第一步乘法就可能溢出在 C 里 long long 也扛不住 a*a 这种操作一定要养成先取模再乘的习惯。第三如果题目给的底数或指数是负数要提前处理成同余意义下的正数一般是(a % m m) % m。很多朋友学快速幂时只把它当模板背忽略了它真正应用最广的地方其实是配合费马小定理求模逆元当 m 是质数且 a 与 m 互质时a 的逆元就是 a^(m-2) mod m。还有组合数取模、矩阵快速幂、哈希滚动计算这些都是快速幂的一线应用场景。建议把这一个模板吃透后面在数论题里会非常赚。2.2 构造题先手算小数据再上墙验证第二道是构造题给定正整数 n要求构造一个 1 到 n 的排列使得任意两个相邻位置的数字差的绝对值都落在 [2, n-1] 区间内n 大于等于 3。如果不存在就输出无解。这种题第一次见很容易懵因为排列的约束听起来很宽松但要保证差值的上下界限同时满足乱排很容易踩线。我当时是先在草稿纸上手算了 n3、n4、n5 的情况发现一个规律把奇数全部放在前面再把偶数全部放在后面比如 n6 时排列是 1 3 5 2 4 6 或者反过来 2 4 6 1 3 5。奇数之间相邻差值固定为2偶数之间相邻差值也是2都满足下限。关键的跨界处最后一个奇数和第一个偶数之间的差值不会小于2也不会超过 n-1因为奇数集合和偶数集合天然错开。这样就构造出来了。这个题的经验是构造题不要一开始就想严格证明先拿小数据试出模式再用数学语言去验证边界是否成立。很多构造题的解法本质就是“把集合按奇偶、按模数、按大小分段然后把段之间的边界处理好”。如果验证之后发现边界恰好差1那就是坑比如某些题要求差值严格大于1那奇偶分段的跨界就差在最小差为1的情况上需要微调配列顺序。这里的教训是写完构造结果后一定在程序里加一个循环检查答案是否真的满足条件尤其是 n 很小的边界值。我见过太多构造题思路对了但边界写挂的例子加个自检函数能省下大把调试卷的时间。3. 背包四连从0-1背包到多维背包、分组背包、退背包3.1 动态规划法求解0-1背包为什么一维数组必须倒序第三题是最经典的0-1背包n 个物品每个物品重量 w[i]、价值 v[i]背包容量 V问能带走的最大总价值。状态定义不废话dp[i][j] 表示前 i 个物品在容量 j 下能获得的最大价值转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])二维写法很好理解但很多新手在把它压缩成一维滚动数组时会犯方向性错误。一维写法是for (int i 0; i n; i) { for (int j V; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } }关键点就是内层循环必须从 V 往 w[i] 方向倒着枚举。为什么因为正序枚举时dp[j-w[i]] 可能已经在当前物品 i 的循环中被更新过这样会出现同一个物品被选两次的情况0-1背包就悄悄变成了完全背包。倒序枚举可以保证 dp[j-w[i]] 还是上一轮 i-1 的状态也就是没有选过当前物品的状态。举一个具体例子假设有一个物品重量2、价值9V4。正序更新时j2 得到 dp[2]9继续 j4 时 dp[4] 会取 dp[2]918相当于这个物品被装了两份显然是错的。倒序更新时j4 用的是 dp[2] 在更新前的值也就是0所以 dp[4] 最多是 dp[2] 的旧值加9正确得到9。这个例子我每次讲背包都会画一遍理解了它滚动数组就再也不会写反。3.2 多维背包限制条件不止一个时状态维度直接加第四题是0-1背包的升级版物品每种有两个成本维度比如重量限制和件数限制同时存在背包最多能装 V 容积同时最多装 K 件每件物品有体积 v[i]、数量成本1和价值 w[i]求最大价值。这就是典型的多维背包模型状态直接加一维// dp[j][k] 表示容积为j、件数为k时的最大价值 for (int i 0; i n; i) { for (int j V; j v[i]; j--) { for (int k K; k 1; k--) { dp[j][k] max(dp[j][k], dp[j - v[i]][k - 1] w[i]); } } }多维背包的本质是状态扩展但代价是复杂度成倍增长。这里我特别想说一下复杂度预估的习惯假设 n1000, V5000, K500三维循环是 10005000500直接 25 亿次基本必超时。所以遇到多维背包先看数据范围如果状态数在千万级以内可以考虑过亿就要寻找别的优化比如把循环顺序调优、使用位移优化、或者换成分组背包的思路。这题还让我养成了一个好习惯凡是状态维度超过二维的动态规划先把复杂度算清楚再动手写别浪费大把时间在一个注定超时的方案上。3.3 分组背包至多选一个、恰好选一个、至少选一个第五题是分组背包的变体。先讲最常见的分组背包若干组物品每组里最多只能选一个物品求最大价值。标准写法是组外层循环、容量中层循环、组内物品内层循环且容量倒序。但变形题就麻烦多了。先说“每组恰好选一个”的模型。处理方法是在初始化时把 dp 数组全部设为负无穷dp[0] 设为0这样只有那些每一组都有合法选择的状态才能被转移到最后。负无穷的作用是挡住那些跳过了某一组的状态这个初始化细节很多人会忽略结果答案变成“每组最多选一个”。再说“每组至少选一个”的模型这个更隐蔽也是热词里专门被点名的。它和“至多选一个”最大的区别是一组里可以选多个物品但至少得有1个。直接套用组内0-1背包的滚动顺序会出大问题因为如果组内物品都可以选多个就必须区分“这个组还没选过东西”和“这个组已经选了至少一个东西”两种状态。我的处理方式是引入一个临时数组 g表示当前组至少选了1个物品时的最优值初始化全部为负无穷。对组内每个物品分别尝试从上一组的 dp 状态转移进来以及从当前组已经选过物品的 g 状态继续叠加vectorint ndp(V 1, -INF); for (auto [w, v] : group) { for (int j V; j w; j--) { ndp[j] max(ndp[j], dp[j - w] v); // 本组第一个从上一组转移 } for (int j V; j w; j--) { ndp[j] max(ndp[j], ndp[j - w] v); // 本组已选过继续叠加 } } dp ndp;第一个循环保证物品可以作为本组的第一个物品被选中第二个循环保证本组已经选了物品之后还能继续叠加其他物品同时容量倒序保证同一物品不会被重复选。这个代码理解起来比普通分组背包要难一个维度但实际遇到“分组且至少选一个”的题带上这个模板直接套会顺利很多。3.4 退背包正向推完之后如何撤销一个物品第六题我挑了“退背包”这个偏门但非常实用的模型。题目描述大概是有 n 个物品每个物品重量 w[i]现在要把每个物品分别删除问删除该物品后凑出容量 C 的方案数分别是多少。如果每次删一个物品就重新跑一遍背包复杂度是 O(nVn)大概率超时退背包可以把这个过程优化到 O(nV)。退背包的思路很直接先用标准0-1背包算出所有物品都可用时的方案数 dp其中 dp[x] 表示凑出重量 x 的方案数。然后从 dp 里把第 i 个物品的影响减掉。0-1背包加入一个物品时是倒序遍历for (int j V; j w[i]; j--) { dp[j] dp[j - w[i]]; }那么撤销它对应的操作就是正序遍历并减去for (int j w[i]; j V; j) { dp[j] - dp[j - w[i]]; }为什么是正序因为加入时倒序保证了不会重复参考新状态撤销时正序则恰好把之前加入时扩散出去的影响一条条收回。很多朋友第一次写退背包会顺手写成倒序结果发现撤销后 dp 数组越减越乱。记住一个规律加入是倒序删除是正序这两个方向正好相反。退背包最常见的应用是计数类问题而不是最大价值类问题。因为 dp 状态存的是方案数线性运算天然支持“撤销”而 max 操作的语义是“被覆盖”无法简单撤销。我之前见过有人试图用退背包处理最大价值DP折腾半天发现根本撤销不掉后来才明白退背包只适合加法、乘法这类可逆运算。还有一个低配版的退背包思路记录每个状态被哪些物品更新过查询时避开但空间开销太大除非数据量极小否则不推荐。4. 反悔贪心用堆维护撤销操作贪心也能有后悔药4.1 一个典型的反悔贪心场景第七题虽然编号排到后面但它是我想重点讲的一道题有 n 个任务每个任务有一个截止时间 t 和利润 p同一时刻只能做一个任务求能获得的最大总利润。直观贪心是先按截止时间从小到大排序然后依次处理但走到后面会发现某任务虽然截止时间靠后利润却很高它有可能比前面一个低利润任务更值得做。这时前面那个任务已经被选中了怎么办答案是反悔把低利润任务踢出去换高利润任务进来。换成代码实现就是配合一个小顶堆维护当前被选中的任务利润集合。每遇到一个任务先假设要选它然后检查当前已选任务数量是否超过了它的截止时间。如果超过了说明排不下就把堆里利润最小的任务弹出去。弹出堆顶的那一步就是典型的反悔操作sort(tasks, tasks n, [](auto a, auto b) { return a.t b.t; }); priority_queueint, vectorint, greaterint pq; long long sum 0; for (auto task : tasks) { pq.push(task.p); sum task.p; if ((int)pq.size() task.t) { sum - pq.top(); // 反悔扔掉利润最小的那个任务 pq.pop(); } }这段代码写完之后整个问题的正确性有很清晰的逻辑链在任意时刻堆里的任务集合都是“截止时间在 t 以内的所有任务里能够按期完成且利润最大的一个子集”。用反证法可以证明每加入一个任务时把最小利润踢掉不会破坏最优性。这个题的思考过程比代码本身更重要它让我彻底理解了贪心的边界贪心不是瞎猜而是需要找“局部最优决策是否会影响全局最优”的证据。如果找不出来就要考虑用反悔机制来弥补。4.2 为什么贪心需要“证明”而不是“感觉”学贪心算法最容易踩的坑就是凭借“感觉上没问题”就写代码结果WA到怀疑人生。比如前面这道任务调度题如果一开始拍脑袋按利润从大到小贪心再安排到可用的截止时间里也能做但要额外维护时间槽。用堆维护反悔点的做法看起来“绕弯”实际上它保证了每一步的集合都是当前时刻下的最优集合不用回头反复调整。我还想分享一个辨别真假贪心的技巧先问自己如果当前选了 A之后来了一个 B能不能在只撤销局部决策的情况下得到最优解如果答案是“能”那说明这个贪心大概率可以配合反悔机制写成堆维护如果答案是“不能”那基本就是DP题或者需要额外的搜索。这种思路让我少走了很多弯路也正好衔接上后面要讲的堆维护。5. 剪枝的艺术让搜索树小一半5.1 搜索题里三类最常用的剪枝第八题是经典的木棒拼接问题给出一堆短木棒的长度要把它们拼成若干根长度相同的长木棒求长木棒的最小可能长度。直接深搜枚举所有组合n 稍大一点就指数爆炸不剪枝根本过不了。搜索题里的剪枝大致分三类可行性剪枝、最优性剪枝、对称性剪枝。可行性剪枝是在搜索过程中判断当前状态是否还有机会达到目标不行就立刻返回。木棒拼接里最常见的可行性剪枝是当前拼接长度加上下一根木棒的长度已经超过目标长度就跳过这根木棒。最优性剪枝是在枚举答案时只在可能成为最优解的范围里搜索。这题里目标长度必须能够整除所有木棒总长度而且至少不小于最长木棒长度就能极大压缩枚举范围。对称性剪枝专门处理重复状态比如两根长度相同的木棒如果某根作为当前段的第一个失败另一根相同长度的也必定失败可以直接跳过。5.2 剪枝顺序对运行时间的影响这里分享一个非常实在的经验剪枝不是写不写的问题而是顺序和覆盖面的问题。我一开始只加了可行性剪枝跑的仍然很慢后来加了“相同长度木棒跳过”的对称性剪枝时间立刻降了一截。真正关键的是“第一个失败了直接返回”这个剪枝if (nowLen 0 || nowLen stick[i] target) return false;这个剪枝的逻辑是如果当前段的长度为0也就是正在拼接一段新的长木棒此时尝试了某根木棒作为第一根却失败那么这段一定拼不出来因为第一根木棒换哪根都一样会失败没必要继续试其他等长的木棒。同理如果当前段刚好凑满 target 却继续后续失败也说明前面部分的组合不可行。我为了写这题前前后后跑了三版代码从超时到0.8秒再到0.04秒运行时间的变化让我真正体会到剪枝的威力。5.3 搜索剪枝和决策树的剪枝其实是同一回事多说一句有人问搜索题和机器学习里的“决策树的剪枝”有什么关系。从思想上看它们本质都是通过提前删除不会产生更优解的子树来减少计算量。决策树的预剪枝和后剪枝对应到搜索题里预剪枝就是“枚举答案之前先预处理排序、设计枚举顺序”后剪枝就是“递归过程中发现状态非法或不可能超过当前最优解时立刻返回”。神经网络里的非结构化剪枝是对单个权重做取舍搜索题的剪枝也经常细到针对某个具体分支、某个等值元素做判断粒度可以非常细。理解了这种跨领域的类比剪枝的思路就不再是死记硬背而是变成一种通用的优化直觉。6. 堆维护的进阶用法不只是优先队列6.1 堆的三个高频使用场景第九题没有单独开题而是把前面反悔贪心用的堆单独拎出来系统讲一遍。堆在算法题里的作用主要集中在三个场景动态最值、多路归并、TopK问题。动态最值最常见的就是 Dijkstra 堆优化每次拿出当前距离最小的节点多路归并典型是合并 k 个有序链表每次从 k 个链表的头节点中选最小的TopK问题则是用一个大小为 k 的小顶堆维护前 k 大的元素。掌握这三种场景堆维护的代码基本就能应付大多数要求。6.2 自定义比较器与多维堆使用 C 的 priority_queue 时自定义比较器是一个非常容易写错但必须掌握的语法。默认的 priority_queue 是大顶堆如果想构造小顶堆可以传 greaterpriority_queueint, vectorint, greaterint pq;如果堆里存的是结构体或者 pair想按某个维度排序就需要自定义比较器。比如按截止时间排序的任务结构体或者按 pair 的第一个字段取最小的堆auto cmp [](const pairint, int a, const pairint, int b) { return a.first b.first; }; priority_queuepairint, int, vectorpairint, int, decltype(cmp) pq(cmp);这个语法里真正的比较函数是“当返回值是 true 时a 排在 b 后面”所以想得到小顶堆效果要返回 a.first b.first。每次写自定义堆我都会默念一遍greater 是小的优先lambda 里返回大于号。别看这里只有一个符号的区别写反了很容易造成逻辑错误。6.3 延迟删除堆里有过期元素怎么办堆的一个弱点是它只允许快速访问堆顶无法快速删除任意中间元素。滑动窗口最大值这类场景里窗口右移后堆顶左边的元素可能已经不在窗口内了这时不能直接把它删除。解决办法是“延迟删除”先不管它只有在它成为堆顶时才检查是否过期如果过期就弹出直到堆顶是合法元素为止。给个模板priority_queuepairint, int pq; // first是值second是下标 for (int i 0; i n; i) { pq.push({nums[i], i}); while (pq.top().second i - k) pq.pop(); if (i k - 1) ans.push_back(pq.top().first); }这个写法的核心是“取堆顶前先清理过期元素”配合一个 while 循环保证每次看到的堆顶都是当前窗口里的最大值。延迟删除在某些需要自定义修改堆内值的算法里也很有用比如 Dijkstra 堆优化中某个节点的距离被更新后旧节点还留在堆里但我们可以不删它只判断取出的节点距离是否已经不对了。这套思想掌握了堆维护就不再是背模板而是一种可以灵活处理动态数据的思路。7. 六题复盘与常见错误速查7.1 各题带来的认知升级这六道题精析下来收获最大的是明白了“模板”和“模型”的区别。模板是固定的代码比如快速幂的四行循环、0-1背包的倒序双层循环模型则是这些代码背后的适用条件。会背模板只能解决原题理解模型才能应对变化。分组背包“至少选一个”和普通分组背包的时间复杂度差不多但状态定义和转移来源完全不同如果不能区分“从上一组转移”和“从当前组继续选”这两种路径写出来肯定是错的。7.2 六题中值得记住的易错点下面这个表是我专门给自己列的错误速查现在也分享出来题目类型常见错误正确做法快速幂res 没取模、a 进制后未先取模res 1 % m循环前先 a % m构造题写完不检查边界加自检函数特判 n 最小的情况0-1背包内层循环正序导致物品重复选容量倒序枚举多维背包忽略复杂度爆炸先算状态数再决定是否使用分组背包至少选一个直接用普通分组背包滚动顺序引入 ndp 区分组内是否已选退背包删除顺序写成倒序加入倒序删除正序反悔贪心贪心后不维护反悔点用小顶堆踢出最小利润搜索剪枝只加可行性剪枝不管对称性相同长度跳过配第一根失败返回堆延迟删除堆顶过期元素未清理取堆顶前 while 清理过期元素7.3 后续修炼计划与一个小建议这次刷完之后我给自己定了一个新的计划每天至少一题旧题重做而不是只顾着开新题。重做旧题时不要按记忆里的答案写而是重新推导一遍重点看能不能在第一次写的时候就避开上次的坑。这样坚持下来模板的熟练度和模型判断的准确度都会有明显提升。最后分享一个小技巧刷题时准备一个“错误清单”文件把每次WA的根因和对应修正写下来。这个文件比收藏一堆题解有用得多因为题解是别人的思考错误清单才是你自己的修炼记录。如果这期内容对你有些帮助也建议你从今天开始给自己的每一道错题写三句话错在哪、为什么错、下次怎么避免。这个习惯坚持下去比多刷一百道新题都值。