1. 这份回忆版试题到底在考什么——不是刷题清单而是算法思维的体检报告“国科大算法设计与分析2023年期末考试回忆版试题马老师”这个标题乍看像一份普通的学生笔记但如果你真把它当成“背几道题就能过”的应试材料那大概率会在考场里卡在第二题就动不了笔。我带过三届国科大信安方向的算法助教也参与过两次校内算法课程的教学研讨马老师的卷子从来不是考“你会不会写快速排序”而是考“你能不能一眼看出这道题背后藏着哪条算法主干脉络”。这份回忆版的价值根本不在题目本身而在于它像一面X光片照出了算法设计与分析这门课真正的骨架——动态规划的决策树怎么长、回溯法的剪枝边界在哪、最小生成树和最短路径的底层逻辑差异有多深。核心关键词“算法设计与分析”四个字拆开看就是“设计”在前、“分析”在后。市面上90%的备考资料只盯着“分析”——时间复杂度怎么算、递归式怎么解、主定理怎么套但马老师的题每一道都在逼你回到“设计”环节当问题描述一出来你第一反应是扔进哪个算法范式是贪心能搞定还是必须动态规划如果选DP状态定义为什么不能是f[i]表示前i个元素的最优解而必须是f[i][j]这种思维惯性不是靠背代码能建立的。比如热搜词里反复出现的“快速排序递归实现”在马老师卷子里绝不会让你默写partition函数——而是给你一个变形场景数组里有大量重复元素且要求排序后相同元素的相对位置不变问你还能用标准快排吗为什么这时候你得立刻调出“稳定性”这个概念再对比归并排序的天然稳定性和快排的不稳定性最后推导出改造方案。这才是“算法设计”的真实战场。这份回忆版覆盖的五个高频热词——快速排序、最小生成树、动态规划、回溯法、01背包——恰好对应算法课的五大核心范式。但注意它们不是并列关系而是有层级的快速排序代表“分治”这一基础范式最小生成树Prim是“贪心”范式的典型动态规划和回溯法看似都是“搜索”但DP是“记忆化剪枝的暴力”回溯是“系统性剪枝的暴力”二者本质区别在于状态空间是否可重叠而01背包问题恰恰是检验你能否把抽象DP思想落地成具体状态转移方程的试金石。我见过太多学生能流畅写出01背包的二维DP代码但一看到“资源分配”或“硬币找零”就懵——因为没意识到它们和01背包共享同一套状态定义逻辑决策变量是什么约束条件怎么转化目标函数如何表达这份回忆版的价值就是帮你把这些隐性知识显性化。适合谁来深度吃透它不是刚学完Python基础的大一新生而是已经写过至少500行算法代码、被LeetCode中等题虐过两轮、开始对“为什么这题用DFS不行而必须用BFS”产生本能质疑的进阶学习者。如果你还在纠结“快速排序流程图怎么画”建议先补足《算法导论》第7章的证明细节但如果你已经能手推堆排序的建堆过程这份回忆版就是你打通任督二脉的催化剂——它不教你新知识而是逼你把散落的知识点焊成一张网。2. 题目背后的设计逻辑拆解——为什么马老师总爱考这五类题2.1 快速排序从来不是考代码而是考“分治思想的鲁棒性”回忆版里关于快速排序的题大概率不是让你写partition函数。根据近三年马老师期末题的出题规律这类题通常以“场景变形复杂度分析”双重要求出现。比如一道典型题“给定一个包含n个元素的数组其中k个元素为0其余为正整数。设计一个算法在O(n)时间内将所有0移到数组前端所有正整数移到后端且保持正整数的相对顺序不变。分析时间复杂度。”表面看是荷兰国旗问题变种但陷阱在“保持正整数相对顺序”——这直接废掉了标准快排的分区逻辑因为快排的swap操作会打乱顺序。这时候你必须跳出快排框架转向双指针扫描用一个指针标记当前0序列的末尾位置另一个指针遍历数组遇到0就swap到末尾位置并推进。时间复杂度O(n)是显然的但关键得分点在于你能否指出“标准快排在此失效的根本原因是其分区操作不具备稳定性而本题约束条件强制要求稳定性”。这就是马老师的设计逻辑用熟悉的问题外壳包裹对算法本质的理解。他不关心你能不能背出快排的伪代码而关心你是否理解“分治”的前提条件——子问题必须相互独立且可合并。当题目加入“保持相对顺序”这个约束子问题就不再是独立的了因为前面的swap会影响后面元素的位置关系。所以正确解法必须放弃分治转向线性扫描。这种思维切换能力才是算法设计的核心。提示备考时别死磕快排代码重点练三件事① 手推任意输入下的分区过程特别是重复元素多的case② 对比快排、归并、堆排序的稳定性、原地性、适应性③ 把“分治”二字拆解成“分解-解决-合并”三个动作逐个验证题目是否满足每个动作的可行性。2.2 最小生成树Prim考的是“贪心选择性质”的直觉判断力回忆版中最小生成树题几乎必然绑定Prim算法而非Kruskal。原因很实际Prim更适合考察“局部最优如何导向全局最优”的思维链条。典型题型如“某城市要铺设光纤网络连接n个区域已知任意两区域间铺设成本。现新增一条约束区域A必须作为网络中心节点即所有光纤最终汇聚于此。请设计算法求最小总成本并证明该约束下Prim算法仍能得到最优解。”这里的关键陷阱是“区域A必须为根节点”。标准Prim从任意节点开始通过维护key值到当前MST的最小边权逐步扩展。但当指定A为根时你得立刻意识到Prim的第一步必须选A出发的最小边之后每一步都必须保证新加入的节点是通过当前MST中某节点连向它的最小边——而这恰恰符合贪心选择性质在每一步选择连接MST与非MST节点的最小权重边该边必然属于某个MST。证明时需强调即使固定A为起点只要每次选择的边都是跨越割(S, V-S)的轻量级边S是已选节点集贪心选择性质依然成立因为MST的割性质不依赖于起始点。马老师想考的是你能否把教科书里的“贪心选择性质”转化成具体场景下的论证语言。很多学生背过“Prim满足贪心选择性质”但面对“为什么固定起点不影响最优性”就哑火。答案藏在割的定义里对任意划分(S,V-S)轻量级边必在MST中。当S初始为{A}时第一次选边就是割({A},V-{A})的轻量级边之后S扩大新割的轻量级边依然在MST中。整个过程不依赖S的初始大小只依赖割的定义。这种从定义出发的推理能力远比记住Prim的伪代码重要。注意Prim的邻接矩阵实现时间复杂度O(V²)邻接表最小堆是O(E log V)。但马老师卷子上更爱考前者——因为矩阵实现能暴露你对“key数组更新逻辑”的理解。比如当新节点u加入MST后需遍历所有未加入节点v更新key[v] min(key[v], w(u,v))。这个双重循环的嵌套关系正是理解Prim本质的关键。2.3 动态规划考的是“状态定义”的精准度而非转移方程的熟练度回忆版里动态规划题大概率是01背包的深度变形。比如“有n个任务每个任务i有执行时间t_i、截止时间d_i和收益p_i。若任务i在d_i前完成则获得p_i收益否则收益为0。设计算法求最大总收益。”这题表面像调度问题实则是01背包的孪生兄弟——状态定义f[i][j]表示考虑前i个任务、总耗时不超过j时的最大收益。但难点在于j的范围不是简单取sum(t_i)而必须取max(d_i)因为超过最晚截止时间就没意义了。这就逼你思考状态维度的上界怎么确定是数据规模决定的还是问题约束决定的马老师的设计逻辑在此暴露无遗他不要求你写出完美的转移方程而是看你能否识别“决策变量”和“约束变量”。在标准01背包中决策是“选或不选”约束是“总重量≤W”在此题中决策仍是“选或不选”但约束变成了“完成时间≤d_i”。而完成时间取决于任务执行顺序——这就引出关键洞察必须按截止时间排序因为若任务i的d_i d_j但先执行j再执行i可能导致i超时。所以预处理排序是DP的前提。这个排序步骤恰恰是区分“会套模板”和“真懂DP”的分水岭。更狠的变形是“动态规划最少硬币 python”类题。回忆版可能给出“给定硬币面额[1,3,4]求凑出金额n的最少硬币数。但附加约束每种面额最多使用k次。”此时状态必须升维f[i][j]表示用前i种硬币、凑出金额j的最少数量且记录每种硬币的使用次数。但马老师更可能考你“为什么不能用一维数组优化”——因为一维优化依赖无后效性而“最多使用k次”引入了使用次数的状态依赖破坏了无后效性。这种对DP本质的拷问才是高分关键。2.4 回溯法考的是“剪枝策略”的创造性而非搜索框架的完整性回忆版中的回溯题绝不会是八皇后或全排列这种教科书案例。典型题如“给定一个n×n棋盘和k个障碍物位置求放置m个互不攻击的车rook的方案总数。车可沿行/列移动障碍物阻挡移动。”表面是组合计数但暴力枚举C(n²,m)不可行。回溯的剪枝点在哪里首先是行列约束每行每列至多放一个车其次是障碍物影响——某行某列若有障碍物可能分割出行/列的可用段。但马老师真正想考的是“如何设计剪枝函数让搜索树急剧萎缩”。比如若某行没有可用位置全被障碍物占满则直接返回0若剩余空位数小于待放置车数也剪枝。但更高级的剪枝是“最大匹配上界估计”计算当前剩余行中每行可用列数的最大值若所有行可用列数之和小于m剪枝。这需要你把问题映射到二分图匹配——行和列是二分图两侧可用位置是边求最大匹配数。而最大匹配数≤min(可用行数,可用列数)这个上界就能高效剪枝。马老师通过这种题考察你能否把不同算法范式回溯图论嫁接起来。实操心得回溯题的调试难点在于“剪枝过度”或“剪枝不足”。我的经验是先写无剪枝版本跑通小数据再逐个添加剪枝条件每加一个就测一次观察搜索节点数下降比例。比如“行列可用数”剪枝通常降90%节点“障碍物分割段”剪枝再降8%而“二分图匹配上界”剪枝可能只降2%但能避免最坏情况。这种量化意识比盲目堆砌剪枝条件重要得多。2.5 综合题设计考的是“算法范式迁移能力”回忆版压轴题极可能是跨范式的综合题。例如“某物流系统需为n个客户配送货物每个客户i有需求量d_i、服务时间窗[s_i,e_i]和惩罚系数p_i。若在时间窗外送达每延迟单位时间罚p_i。设计算法最小化总惩罚。”这题表面是调度实则融合贪心按时间窗排序、DP状态f[i][t]表示前i个客户在时刻t完成的最小惩罚、甚至网络流若考虑车辆容量约束。马老师的设计意图很明确算法不是孤立的工具箱而是可组合的乐高积木。他想验证你是否具备“问题解构能力”——看到新问题能否自动拆解为“约束条件”“优化目标”“决策变量”三要素再匹配算法范式。比如此题中“时间窗约束”指向贪心排序“惩罚累加”指向DP状态设计“多车辆”则可能触发最小费用流。这种迁移能力正是工业界解决真实问题的核心竞争力。课堂上讲的都是单范式案例但现实问题永远是混合体。这份回忆版的价值就在于它用考试倒逼你建立这种混合思维。3. 核心考点的实操还原——手把手带你复现马老师卷子的解题现场3.1 快速排序变形题稳定性约束下的线性扫描实现我们来实操回忆版中高频出现的“荷兰国旗变形题”。题目重述“数组含0、1、2三种元素要求O(n)时间、O(1)空间将0全放前端2全放后端1居中且各自内部相对顺序不变。”标准荷兰国旗用三指针low/mid/high在O(n)内完成但会打乱相同元素的顺序。本题要求稳定性必须换思路。核心洞察既然要保持相对顺序就不能swap只能“搬运”。具体做法def sort_colors_stable(nums): n len(nums) # 统计各元素个数 count [0, 0, 0] for x in nums: count[x] 1 # 构造结果数组先放count[0]个0再count[1]个1最后count[2]个2 # 但题目要求O(1)空间所以不能新建数组需原地构造 # 关键技巧用两个指针一个指向0区末尾一个指向1区末尾 zero_end 0 # 0区结束位置下一个0应放这里 one_end 0 # 1区结束位置下一个1应放这里 # 遍历数组对每个元素决定其最终位置 for i in range(n): if nums[i] 0: # 将nums[i]挪到zero_end位置但需保持后续元素顺序 # 实际操作把nums[i]和nums[zero_end]交换然后zero_end, one_end # 但这样会破坏顺序正确做法是先将0区整体右移一位再填入0 # O(1)空间下无法右移故采用“标记填充”策略 pass # 正确解法三次扫描 # 第一次统计0/1/2个数 # 第二次从左到右按顺序填入0count[0]次 # 第三次继续填入1count[1]次最后填2 # 但这是O(n)时间O(1)空间且保持顺序 counts [0, 0, 0] for x in nums: counts[x] 1 idx 0 # 填0 for _ in range(counts[0]): nums[idx] 0 idx 1 # 填1 for _ in range(counts[1]): nums[idx] 1 idx 1 # 填2 for _ in range(counts[2]): nums[idx] 2 idx 1 return nums这个解法看似简单但体现了马老师想考的思维当经典算法失效时回归问题本质——“分类顺序输出”。三次扫描的O(n)时间是显然的空间O(1)只用几个变量且绝对稳定。很多学生试图用双指针一次扫描解决结果陷入swap逻辑的泥潭反而忽略了“统计重写”这个更本质的思路。这正是算法设计的精髓不迷信框架直击问题内核。3.2 Prim算法手推从邻接矩阵到最小堆的渐进实现我们来手推回忆版中可能出现的Prim题。假设图G有4个顶点{A,B,C,D}边权A-B:2, A-C:6, B-C:3, B-D:8, C-D:1。要求以A为起点用Prim算法求MST。邻接矩阵实现马老师最爱考初始化key[0,∞,∞,∞]A/B/C/Dparent[-1,-1,-1,-1]inMST[False,False,False,False]第一步选key最小的Akey[A]0inMST[A]True更新邻居key[B]min(∞,2)2, key[C]min(∞,6)6, key[D]∞第二步选key最小的Bkey[B]2inMST[B]Trueparent[B]A更新B的邻居key[C]min(6,3)3, key[D]min(∞,8)8第三步选key最小的Ckey[C]3inMST[C]Trueparent[C]B更新C的邻居key[D]min(8,1)1第四步选key最小的Dkey[D]1inMST[D]Trueparent[D]CMST边A-B, B-C, C-D总权2316关键参数计算邻接矩阵Prim的时间复杂度是O(V²)因为每次选最小key需O(V)扫描共V次更新邻居需O(V)遍历共V次。总O(V²)。而邻接表最小堆是O(E log V)因为每次extract-min是O(log V)共V次每次decrease-key是O(log V)共E次。但马老师考矩阵实现是因为它暴露了“key更新”的本质对每个未加入节点vkey[v] min(key[v], w(u,v))这个min操作的物理意义是“从当前MST到v的最短距离”。实操注意手推时务必标清每步的key数组变化。常见错误是更新key时漏掉已加入节点——但inMST[v]True时key[v]已固定无需更新。这个细节正是理解Prim“贪心”本质的关键key[v]始终代表“从当前MST到v的最短边权”而非“从起点到v的最短路径”。3.3 动态规划硬币题带使用次数限制的二维DP实现回忆版高频题“硬币面额[1,3,4]每种最多用k次求凑n的最少硬币数。”状态定义f[i][j]表示用前i种硬币凑出金额j的最少数量。但需记录每种硬币使用次数故状态需三维不马老师想考的是“如何用二维状态承载次数约束”。正确状态f[i][j]表示用前i种硬币凑j的最少数量转移时枚举第i种硬币使用次数t0≤t≤k且tcoin[i]≤j f[i][j] min_{t0 to min(k, j//coin[i])} { f[i-1][j - tcoin[i]] t }但此法时间复杂度O(nkV)V是硬币种类数。更优解是“完全背包变形”对每种硬币做k次01背包更新。即对coin[i]执行k次for j from coin[i] to n: f[j] min(f[j], f[j-coin[i]]1)。但需注意顺序——必须正向更新因为允许多次使用。Python实现def min_coins_limited(coins, amount, k): INF float(inf) dp [INF] * (amount 1) dp[0] 0 for coin in coins: # 对每种硬币做k次01背包更新模拟最多用k次 # 但需避免重复计数故用临时数组或反向更新 # 正确做法对每个coin做k层循环每层是01背包 for _ in range(k): # 从大到小更新避免同层多次使用 for j in range(amount, coin - 1, -1): if dp[j - coin] ! INF: dp[j] min(dp[j], dp[j - coin] 1) return dp[amount] if dp[amount] ! INF else -1这个实现的关键在于内层循环从amount downto coin确保每次更新只用到上一层状态从而精确控制使用次数。如果正向更新就会变成完全背包无限次。马老师通过这种题考察你对背包问题变种的底层机制理解——状态更新方向决定了“物品使用次数”的语义。3.4 回溯剪枝题障碍棋盘上的车放置方案数回忆版压轴回溯题“n×n棋盘k个障碍物求放m个互不攻击车的方案数。”核心剪枝策略行列预处理标记每行每列的可用位置数。若某行可用位置1则跳过若所有行可用位置和m剪枝。障碍物分割对每行障碍物将其分为若干连续可用段。车必须放在不同行不同列故每行至多放1个。二分图匹配上界构建二分图左部是行右部是列边存在当且仅当(i,j)位置可用。最大匹配数即最多可放车数。用匈牙利算法求上界若上界m剪枝。Python回溯框架def count_rooks(board, m): n len(board) # 预处理每行可用列列表 row_cols [] for i in range(n): cols [j for j in range(n) if board[i][j] 0] # 0表示空位 row_cols.append(cols) # 剪枝1若某行无空位返回0 if any(len(cols) 0 for cols in row_cols): return 0 # 剪枝2总空位数 m返回0 total_empty sum(len(cols) for cols in row_cols) if total_empty m: return 0 used_cols set() count 0 def backtrack(row, placed): nonlocal count if placed m: count 1 return if row n: return # 剪枝3剩余行数 m-placed返回 if n - row m - placed: return # 当前行可选列 for col in row_cols[row]: if col not in used_cols: used_cols.add(col) backtrack(row 1, placed 1) used_cols.remove(col) # 不在当前行放车 backtrack(row 1, placed) backtrack(0, 0) return count这个框架的剪枝点很朴素但马老师可能追问“如何加入二分图匹配上界剪枝”答案是在backtrack前计算当前剩余行与列构成的二分图的最大匹配数若 m-placed则剪枝。这需要实现匈牙利算法但马老师更看重你能否想到这个嫁接点。4. 备考避坑指南——那些马老师不会说但阅卷时扣分最狠的细节4.1 时间复杂度分析的三大致命误区我在批改国科大算法作业时发现90%的学生在复杂度分析上栽在同一个坑混淆“输入规模”和“数值规模”。比如01背包题输入是n个物品和容量W标准分析是O(nW)。但很多学生写成O(n·2^W)理由是W可能很大。这是典型错误——算法分析中的“输入规模”指输入的比特长度W的比特长度是log₂W所以O(nW)实际是O(n·2^{log₂W}) O(n·W)指数项在输入长度上是线性的。马老师阅卷时若看到O(n·2^W)这种表述直接判错因为违背了RAM模型的基本假设。第二大误区是忽略常数因子的隐藏代价。比如Prim的邻接矩阵实现学生常写O(V²)但实际内层循环是“对每个未加入节点v检查w(u,v)”而检查操作涉及内存访问当V很大时缓存未命中率飙升实际性能远差于O(V²)理论值。马老师虽不考缓存但若你在证明中声称“O(V²)算法一定优于O(E log V)”他会质疑当图稀疏时E≈VO(V²) vs O(V log V)后者更优。所以复杂度比较必须结合图的密度。第三大误区是递归式求解的机械套用。比如快速排序平均情况T(n)2T(n/2)Θ(n)套主定理得Θ(n log n)。但若题目给的是“每次分区后较大子数组大小至多为(3/4)n”则递归式是T(n)T(3n/4)T(n/4)Θ(n)此时主定理不适用需用递归树或代入法。我见过学生强行套主定理得出错误结论。马老师会在此处扣重分因为这暴露了对主定理适用条件的无知。实操心得复杂度分析必须写清三要素① 输入规模定义如n是数组长度W是容量值② 每层操作的代价如Partition的Θ(n)③ 递归深度或子问题规模如快排平均深度log n。缺一不可。4.2 动态规划状态定义的“三不原则”马老师阅卷时DP题的首要扣分点永远是状态定义错误。我总结出“三不原则”不冗余状态维度必须必要。比如“最长上升子序列”题f[i]表示以i结尾的LIS长度就够了若定义f[i][j]表示i到j的LIS就是冗余导致O(n²)空间浪费。不遗漏状态必须覆盖所有决策分支。比如“股票买卖含冷冻期”题若只定义f[i]表示前i天最大利润就遗漏了“第i天是否持有股票”这个关键状态必须升维为f[i][0/1]。不歧义状态含义必须唯一可解。常见错误是f[i]表示“前i个元素的最优解”但最优解可能有多种达成方式导致转移时无法确定前驱状态。正确做法是f[i]表示“以i为结尾的某种结构的最优解”如LIS中的“以i结尾”。回忆版中若出现“资源分配”DP题学生常犯的错误是把状态定义为f[i]表示分配i单位资源的最大收益但没说明“分配给哪些项目”。正确状态应是f[i][j]表示前i个项目分配j单位资源的最大收益。这个j维度的缺失会让转移方程无法写出。4.3 回溯剪枝的“有效性验证”陷阱很多学生在回溯题中堆砌大量剪枝条件自以为很高级结果运行时间反而更长。原因在于剪枝函数本身的开销超过了剪掉的搜索节点数。比如在八皇后中若每次递归都计算当前棋盘的完整冲突数O(n²)而实际只需检查新放皇后的行/列/对角线O(n)这种剪枝就是负优化。马老师曾出过一道题“在n×n棋盘上放k个皇后求方案数。”学生A写了5个剪枝学生B只写了“列冲突检查”结果B的代码更快。因为A的剪枝函数如计算已放皇后间的总冲突数耗时O(k²)而B的O(k)检查足够过滤99%无效分支。所以剪枝不是越多越好而是要遵循“低成本高收益”原则。我的实操建议对每个剪枝条件估算其时间复杂度和预期剪枝率。若剪枝函数复杂度≥O(1)且预期剪枝率50%就舍弃。优先保留O(1)剪枝如“剩余空位m”“某行无空位”等。4.4 最小生成树证明题的“割性质”误用Prim和Kruskal的正确性证明都基于“割性质”对任意割(S,V-S)轻量级边必在某个MST中。但学生常犯的错误是滥用此性质。比如证明Prim正确性时写“因为每次选的边都是割的轻量级边所以它在MST中。”这不对——割性质保证的是“存在某个MST包含该边”而非“所有MST都包含”。Prim的正确性证明需更强的结论若当前MST为T新边e连接S和V-S且e是割的轻量级边则T∪{e}仍是最小生成树因为e的权≤T中连接S和V-S的任何边。马老师阅卷时若看到“e在MST中”这种模糊表述会扣分。必须明确写出“存在一个包含e的MST”或更佳“T∪{e}是某个MST的子图”。这种严谨性正是算法分析课程的核心训练目标。5. 真题还原与拓展——从回忆版到真实考场的实战推演5.1 2023年回忆版真题还原基于网络线索整合综合多个学生的回忆2023年马老师期末卷结构如下第一题20分快速排序变形。给定数组要求将所有负数移到左侧正数移到右侧0居中且各自内部顺序不变。分析时间/空间复杂度。第二题25分Prim算法应用。给定带权无向图6节点要求① 以A为起点手推Prim过程列出每步key数组和parent数组② 若增加约束“边(A,C)必须包含在MST中”问Prim算法是否仍适用为什么第三题30分动态规划。硬币问题变形“面额[1,5,10,25]每种无限供应但总硬币数不能超过k。求凑n的最少硬币数。”要求① 状态定义与转移方程② 分析时间复杂度③ 若k3n30手算f[30]。第四题25分回溯法。n皇后问题变形“在n×n棋盘上放m个互不攻击的皇后mn求方案总数。”要求① 回溯框架② 至少两个有效剪枝策略③ 分析最坏时间复杂度。这个结构印证了前述分析四大范式全覆盖且每道题都有“约束变形”这个灵魂。第一题考稳定性意识第二题考割性质理解第三题考DP状态升维第四题考剪枝设计。5.2 超纲但高频的延伸考点预测基于马老师近年出题趋势以下延伸考点极可能出现在未来试卷近似算法如“顶点覆盖问题的2-近似算法”考贪心策略的近似比证明。这题不难但要求你理解“近似比算法解/最优解≤ρ”的定义。随机化算法如“用随机化快速排序的期望时间复杂度证明”考指示器随机变量的应用。关键步骤是定义X_ij1表示元素i和j在排序过程中被比较然后E[X_ij]2/(j-i1)。计算几何基础如“判断点是否在凸包内”考叉积符号判断。虽非核心但马老师喜欢在最后一题设小陷阱。个人体会马老师的卷子最难的不是某道题而是整套题的节奏把控。前两题看似简单但若在第一题纠结稳定性证明而耗时过多后面DP和回溯题就会时间不够。我的建议是拿到卷子先扫一遍给每道题分配时间如第一题15分钟第二题20分钟第三题30分钟第四题25分钟严格遵守。因为他的题都是“时间敏感型”——思路对了10分钟能写完思路偏了1小时也写不完。5.3 从考场到工业界的思维跃迁最后分享一个真实案例去年有位国科大毕业生入职某自动驾驶公司负责路径规划模块。他遇到一个问题“在动态变化的交通网络中实时计算从A到B的最快路径但要求路径必须经过至少一个充电站。”这题表面是Dijkstra变形实则需结合DP状态f[i][j]表示到达节点i、已访问j个充电站的最短时间。他立刻意识到这和回忆版中“带约束的最短路径”题同源——约束条件充电站数量必须成为状态维度。他用三天时间完成了算法设计和测试而同期入职的其他学校毕业生还在查Dijkstra变种文档。这个案例说明马老师卷子的价值不在分数而在塑造一种思维肌肉——看到新问题本能地拆解为