开头先不套模板我直接说点实际感受这个系列写到第五套模拟题后台私信一直在问华为OD机试到底刷什么、怎么刷才有效。我自己备考时最大的教训就是——刷题网站的“通过就好”和机试的“一次提交定生死”完全是两种体验。第五套我特意挑了四道风格差异明显的题涉及文件处理与排序去重、关键路径、优先队列搜索、二分答案。这四类考点在近年的真题里出现频率非常高而且每道题都能延伸出一串变种。另外现在的机考系统已经升级成双机位C卷模式很多人对这个新规则还没完全适应我先把这些场外因素说清楚再进入题目本身。1. 机试开考前必须搞清楚的三个客观因素1.1 新系统双机位C卷到底变了什么华为OD机试从早年的单机位、单摄像头到现在的“新系统 双机位 C卷”实际变化是很大的。很多人把注意力全放在算法题上却忽略了环境规则结果上了考场才发现自己连提交方式都搞错了。双机位意味着你需要一台正面摄像头设备通常是电脑自带摄像头和一台侧后方机位手机或另一台设备侧后方机位要能拍到你的双手、屏幕和桌面。这个要求会直接影响做题习惯——你不可能像平时在自己电脑上那样随意切换IDE和浏览器查资料切屏次数过多会被系统记录甚至直接判定违规。C卷是目前主流的试卷代号题目风格和以往的A卷、B卷相比更偏向工程场景描述本质考点没有跳出算法范围但题干会更长概念包装更多。所以备考时不能只看纯数据结构裸题要适应“把实际问题抽象成算法模型”的阅读方式。这也是我在这个系列里故意把每道题都包装成系统日志、任务调度、购物组合、货物分堆等场景的原因。1.2 ACM模式为什么说输入输出决定你能不能过机试一律采用ACM模式也就是你需要自己从标准输入读数据自己把结果打印到标准输出。这和LeetCode那种已经帮你封装好函数签名、只管填函数体的模式完全不同。我见过太多平时刷LeetCode很顺的人到了机试却因为读入卡壳甚至不会处理“第一行是测试数据组数”这种最基础的情况。ACM模式下有两个高频坑。第一个是多组测试数据有些题目会一口气给多组输入你需要循环处理到EOF有些题目只给一组数据但很多人习惯性写while判断结果死循环或输出多余内容。第二个是字符串解析日志、命令这类输入经常包含空格直接用split()会拆错字段必须限制拆分次数。这些细节不会写进算法考核点但比算法更容易让你丢分。1.3 阅卷系统只认三件事机试的在线评测系统判定结果时只关心三件事输出是否正确、是否在时间限制内、是否在内存限制内。输出正确是最严格的。多一个空格、少一个换行、最后多输出一个空行都算错误。所以每道题写完代码后一定要复制题目给的样例本地跑通再提交。时间限制一般在1到2秒内存限制通常在256MB或512MB。Python在这种环境下有一定劣势但差距并不大关键是不能写出指数级复杂度的暴力算法。内存方面最常见的翻车点是递归深度过大或数组开得太大比如有些题把数组开到10^7级别在Python里直接Memory Error。2. 第一道模拟题磁盘日志合并中的排序与去重陷阱2.1 题目描述与样例先上题。题目背景是分布式系统每个节点产生一个日志文件文件名格式为node_i.logi从1到N。每条日志记录的格式是“时间戳 日志级别 消息内容”时间戳是10位整数日志级别是INFO、WARNING、ERROR三者之一消息内容中可能包含空格。现在需要把N个节点的日志文件合并成一个按时间戳升序排列的文件并且对时间戳相同的记录做去重只保留消息内容最长的一条如果消息内容长度也相同则保留日志级别更严重的一条ERROR WARNING INFO。样例输入2 node_1.log node_2.lognode_1.log内容1699999990 INFO 开始加载配置 1699999995 ERROR 数据库连接失败 1699999995 INFO 重试连接node_2.log内容1699999992 WARNING 响应时间超过阈值 1699999995 ERROR 数据库连接失败期望输出1699999990 INFO 开始加载配置 1699999992 WARNING 响应时间超过阈值 1699999995 ERROR 数据库连接失败2.2 审题时最容易钻进的两个死胡同第一个死胡同文件名顺序到底按什么读。题目只说输入是“接下来N行每行一个文件名”并没有保证文件名有序。我见过有人默认node_1.log、node_2.log是有序给出的直接按读入顺序拼接结果输出顺序错乱。你要做的只是把每个文件都读完记录全部汇总到一起统一排序文件名的顺序对最终结果没有影响。第二个死胡同去重规则的处理时机。有人会把所有记录读进来后先用set对时间戳去重再排序。但“保留消息最长”这个条件要求你必须在去重时刻把所有同时间戳记录放到一起比较而不是随手丢进set。最稳妥的做法是先统一排序然后用双指针或分组遍历处理同一时间戳。2.3 排序配合哈希去重的具体实现我用Python实现核心逻辑分三步。第一步逐个文件读取每一行用partition或split的maxsplit参数拆成三个部分。第二步把记录存储为元组包含时间戳、日志级别权重、消息内容、原始日志级别字符串。第三步排序后分组去重。import sys def read_records(filename): records [] with open(filename, r, encodingutf-8) as f: for line in f: line line.strip() if not line: continue ts, level, msg line.split( , 2) records.append((int(ts), level, msg)) return records def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) files data[1:1 n] level_weight {INFO: 0, WARNING: 1, ERROR: 2} all_records [] for fname in files: for ts, level, msg in read_records(fname): all_records.append((ts, level_weight[level], len(msg), msg, level)) all_records.sort(keylambda x: (x[0], -x[2], -x[1])) merged [] i 0 while i len(all_records): ts all_records[i][0] best all_records[i] while i len(all_records) and all_records[i][0] ts: if all_records[i][2] best[2] or (all_records[i][2] best[2] and all_records[i][1] best[1]): best all_records[i] i 1 merged.append(f{best[0]} {best[4]} {best[3]}) sys.stdout.write(\n.join(merged)) if __name__ __main__: main()排序key我用的是时间戳升序、消息长度降序、级别权重降序。这样排序完成后同一个时间戳的第一个元素就是该组最优记录直接取第一个即可。这种写法的好处是代码简洁不用在循环里反复比较。2.4 为什么不建议用set暴力去重再排序先说结论不是不行而是容易出错。如果你先把所有记录装进set再自定义比较器排序会遇到两个问题。第一tuple的比较是逐字段进行的如果你想只按时间戳去重必须额外构造一个不包含消息内容的中间结构否则set会认为“1699999995 ERROR 数据库连接失败”和“1699999995 INFO 重试连接”是两个不同元素。第二set本身不保证顺序你仍然要在之后排序而排序时又得把去重逻辑重新写一遍等于做重复功。直接排序再分组本质上是“排序去重”的标准套路时间复杂度是O(M log M)M是总记录数在10^5级别完全够用。如果总记录量再上一个数量级就需要考虑多路归并的外部排序思路但机试一般不会把数据量出到需要你手写外部排序的程度。2.5 这题的扩展价值这道题其实是字符串处理 排序 自定义比较器的综合题在OD机试中属于中低难度但扩展性很强。把“日志级别”换成“优先级队列里的任务权重”把“消息长度”换成“任务耗时”就是一道任务调度题。把“文件”换成“网络节点上报数据”就是一道数据聚合题。刷题不能只求AC要能从一道题里总结出一个排序场景的通用处理模板。我后面几道题也都是这个思路。3. 第二道模拟题依赖任务的最短完成时间本质是找关键路径3.1 题目描述与样例这道题的背景是系统发布前的任务编排。有n个待执行任务编号1到n第i个任务耗时time[i]分钟。任务之间存在依赖关系若任务a依赖任务b则b必须在a开始前完成。系统支持无限多个并行执行单元因此只要某个任务的所有前置依赖已完成它就可以立即开始。求所有任务全部完成的最少时间。输入格式第一行两个整数n, m 第二行n个整数表示每个任务的耗时 接下来m行每行两个整数a b表示任务a依赖任务b样例输入6 6 3 2 1 4 5 2 1 2 1 3 4 3 5 4 6 5 6 2样例输出143.2 从“最少时间”到“最长路径”的转化很多人看到“最少完成时间”第一反应是贪心每次挑耗时最短的先执行。但题目给出了“无限并行”这个关键条件此时所有依赖链上的任务没办法提前总完成时间只取决于最长的依赖链。这就是项目管理里的关键路径法。关键路径的直觉可以这样理解你有一串串联的步骤比如先泡茶(2分钟)再煮面(5分钟)这两步必须按顺序合计7分钟另一条链是热牛奶(3分钟)没有前置依赖可以同时做。那总耗时就是7分钟而不是10分钟因为热牛奶在泡茶煮面的过程中就完成了。无限并行场景下所有没有依赖关系的任务都同时开工瓶颈永远是那条最长路径。3.3 拓扑排序加动态规划的完整推导这题的标准解法是拓扑排序配合动态规划转移。定义dp[i]表示任务i最早能完成的时间。初始时入度为0的任务没有前置依赖的dp值就是自己的耗时。对于一条边u到v表示v依赖u那么u完成后v才能开始所以v的最早完成时间至少是dp[u] time[v]。因为是“至少”所以要做max操作。from collections import deque import sys def main(): data sys.stdin.read().strip().split() if not data: return idx 0 n int(data[idx]); idx 1 m int(data[idx]); idx 1 time_cost [0] [int(data[idx i]) for i in range(n)] idx n indeg [0] * (n 1) graph [[] for _ in range(n 1)] for _ in range(m): a int(data[idx]); b int(data[idx 1]); idx 2 graph[b].append(a) indeg[a] 1 dp [0] * (n 1) q deque() for i in range(1, n 1): if indeg[i] 0: dp[i] time_cost[i] q.append(i) processed 0 ans 0 while q: u q.popleft() processed 1 ans max(ans, dp[u]) for v in graph[u]: dp[v] max(dp[v], dp[u] time_cost[v]) indeg[v] - 1 if indeg[v] 0: q.append(v) if processed ! n: print(存在环) else: print(ans) if __name__ __main__: main()这里有几个容易错的地方。第一建图方向输入是“a依赖b”也就是b是a的前置要建立边b到a。如果方向搞反入度统计就全乱了。第二dp[v]的初始化不要把dp[v]初始化为time_cost[v]因为v可能依赖多个前驱只有当所有前驱都处理完最后一次更新才是正确值。当然由于拓扑排序的性质入度减到0时所有前驱都已经更新过dp[v]了所以也可以在入队列时赋初值但我在循环外统一初始化为0更稳妥。第三答案不是dp某个固定节点而是所有节点dp的最大值因为最后完成的任务可能是任意一个没有后继的节点。3.4 为什么这道题容易超时大部分超时不是算法时间复杂度的问题而是建图和入度更新时用了O(n^2)的操作。例如有人用邻接矩阵存图m达到10^5时矩阵大小就爆了也有人每次找一个入度为0的点都全数组扫描复杂度变成O(n^2)。正确做法是及时用队列维护入度为0的节点每个节点只入队一次每条边只在拓扑排序中访问一次整体复杂度O(n m)。4. 第三道模拟题第K小组合优先队列如何控制爆炸式搜索4.1 题目描述与样例这道题我设计成购物组合。有n种商品第i种商品价格为price[i]。任意选择若干种商品组成一个购物组合每种商品最多选一件空组合不计入。组合总价为选中商品价格之和。把所有可能的组合按总价从小到大排序输出第K个组合的总价。输入格式第一行两个整数n, K 第二行n个整数price约束1 ≤ n ≤ 10^51 ≤ K ≤ 10^5。样例输入3 5 1 2 100样例输出101解释所有组合总价排序为1, 2, 3, 100, 101, 102, 103第5个是101。4.2 暴力枚举为什么一定会挂最直接的做法是枚举所有2^n个子集计算总和后排第K个。n到20左右还能勉强跑n到10^5的时候2^n是个天文数字内存和时间都会爆炸。所以我们必须利用“K只有10^5”这个约束只生成前K个最小的组合不生成全集。4.3 优先队列加状态扩展的经典套路这里的关键是设计一个状态扩展方式确保每次从优先队列中弹出的都是当前最小的组合并且每个组合只被生成一次。先对价格升序排序。定义状态为(sum, i)表示一个组合其中组合的总价为sum并且这个组合中下标最大的那个元素是price[i]。初始状态是(price[0], 0)也就是只包含最小元素的那个组合。每次从堆中弹出当前最小状态时如果这是第K次弹出就得到答案。否则生成两个后继状态当前组合加入下一个元素price[i1]新状态为(sum price[i1], i1)。当前组合把最大元素price[i]替换成下一个元素price[i1]新状态为(sum - price[i] price[i1], i1)。这个生成规则为什么成立因为它把所有组合按照“最大元素下标”分类。以price[i1]作为最大下标的组合要么是“某个以price[i]为最大下标的组合加上price[i1]”要么是“某个以price[i]为最大下标的组合去掉price[i]再加上price[i1]”。这样一来组合集合被切分成两个互不重叠的部分不会漏也不会重。import heapq import sys def main(): data sys.stdin.read().strip().split() if not data: return n int(data[0]) k int(data[1]) prices list(map(int, data[2:2 n])) prices.sort() heap [(prices[0], 0)] seen set() seen.add((prices[0], 0)) cnt 0 while heap: s, i heapq.heappop(heap) cnt 1 if cnt k: print(s) return if i 1 n: nxt1 (s prices[i 1], i 1) if nxt1 not in seen: seen.add(nxt1) heapq.heappush(heap, nxt1) nxt2 (s - prices[i] prices[i 1], i 1) if nxt2 not in seen: seen.add(nxt2) heapq.heappush(heap, nxt2) if __name__ __main__: main()我用一个set记录已经生成过的状态防止同一状态从不同路径被重复推入堆中。这个去重必须做否则可能出现重复弹出和死循环。4.4 去重细节与重复元素问题如果price数组中有重复元素比如[1, 1, 5]那么不同组合可能得到相同总价但它们是不同组合按题意都要计数。上面的生成方法对重复值仍然有效因为它按下标区分组合只要下标不同就视为不同组合。但如果题目问的是“第K小总价且重复总价只算一次”就需要额外用set对总价去重直到去重后数量达到K。还有一点要强调优先队列中每个状态扩展成两个后继最多扩展2K个状态复杂度是O(K log K)完全能跑过。相比之下折半搜索虽然也是常见思路但需要2^(n/2)级别的枚举只适用于n较小的情况。面对10^5的n堆扩展法才是正解。5. 套路的力量二分答案解决“最大值最小化”问题5.1 从一道货物分堆题看高频考点有一批货物依次排列在传送带上第i件货物重量为w[i]。需要按照原有顺序把这批货物分成不超过m组每组是连续的一段。每组货物重量之和形成“日运输量”。希望在运输时限内完成所以要让所有组中日运输量的最大值尽可能小。求这个最小的最大日运输量。样例输入5 3 7 2 5 10 8样例输出14我选这道题是因为“最大值最小化”在华为机试中出现的频率实在太高了。它表面是一道模拟运输场景的应用题本质上是判定一个阈值是否可行而判定过程只需要一次线性扫描。5.2 二分答案的可行性判定函数这题的核心是理解“可行性关于阈值单调变化”如果阈值X可行那么任何比X大的阈值都可行如果X不可行任何比X小的阈值都不可行。单调性是二分的前提。判定函数可以这样写从第一件货物开始累加如果累加和超过X就从当前货物开始新开一组组数加一。扫描完所有货物后如果所需组数不超过m说明X可行。def can_split(weights, m, limit): cnt 1 cur 0 for w in weights: if cur w limit: cnt 1 cur w if cnt m: return False else: cur w return True5.3 下界与上界为什么是这两个值二分下界是max(weights)因为任何一组至少包含一件货物所以单组和不可能小于最大单件重量。二分上界是sum(weights)因为把所有货物放在一组时最大日运输量就是总重量。如果下界设成0虽然二分仍然能收敛但会多做很多次无意义的判定。上界如果设得过大比如10^18虽然不影响结果但可能让二分次数增加。整数二分的写法有一个经典模板left, right max(weights), sum(weights) while left right: mid (left right) // 2 if can_split(weights, m, mid): right mid else: left mid 1 print(left)注意边界处理当判定可行时把右边界收缩到mid因为mid本身可能是答案当判定不可行时左边界收缩到mid 1因为mid一定不是答案。这个写法避免了死循环。5.4 这类题在机试中的变种“最大值最小化”和“最小值最大化”是一对孪生兄弟。把“分成不超过m组使最大和最小”改成“分成恰好m组使最小和最大”判定函数就从“每段和不超过X”变成“每段和至少X”其他逻辑完全一致。还有一类是“在数组中切分使最大值最小并输出切分方案”需要在二分之后再做一次从后往前的贪心还原分组。遇到这类题先识别出单调性再套二分框架比现场想贪心策略要稳得多。6. 提交前必须自查的三个隐藏炸弹6.1 数组越界与Runtime Error机试最常见的Runtime Error原因是数组越界。尤其是动态规划类题目下标从0开始还是从1开始特别容易搞混。我自己的习惯是只要题目涉及编号1到n就把数组开成n 1下标1到n存放真实数据下标0留空。这样虽然浪费一点点空间但能避免很多边界错误。另外在使用优先队列状态扩展时要特别检查i 1 n这个边界条件不然最后一轮扩展直接越界。6.2 大数溢出如果题目中数值范围很大Python自然不用担心溢出但C和Java选手要格外小心。比如求组合总价、任务总耗时时多个10^9级别的数相加可能超过int范围必须用long long或long。我建议做题前先看一眼数据范围凡是涉及求和、乘积的直接无脑用64位整数类型。6.3 输入输出性能陷阱Python的input()在数据量大的时候会拖慢程序。机试中如果出现10^5行级别的输入建议用sys.stdin.read()一次性读入再用split()解析速度会快很多。输出同理如果你在循环里逐行print会频繁调用IO建议用列表收集结果最后用sys.stdout.write(\n.join(lines))一次性输出。还有一个很多人不知道的问题如果print后面带flushTrue会大幅拖慢IO虽然机试一般不需要flush但最好也别用。这三点看起来不起眼但我在模拟测试中见过太多因为RE、TLE而失分的案例。算法思路写对了却挂在工程细节上真的非常可惜。这套模拟题做到这里我最想强调的还是那个观点刷题的价值不在题量而在能不能把一道题的解题思路抽象成可复用的套路。日志合并练的是排序去重任务调度练的是拓扑排序与关键路径第K小组合练的是优先队列状态扩展货物分堆练的是二分答案加贪心验证。把这四套东西吃透下一次遇到任何包装花哨的真题你都能一眼看穿它的内核。如果你自己把这些代码全部手写一遍再对照题解收获会比看十篇文章都大。咱们下一套模拟题见。