元旦后那场模拟机试我卡在t49题上整整四十分钟最后用暴力枚举勉强过了两个小数据测试点。后来把t49到t55这批题按算法类型重刷了一遍才发现它们的出题顺序是有规律可循的——区间查询、单调栈、快速幂、拓扑排序、动态规划、质数优化、双指针、综合模拟几乎覆盖了机试里能考到的基础算法全集。这篇不是单纯讲某一道题的题解而是把t49-t55当作一个完整的训练切片来处理每道题对应什么知识点、为什么考它、考场上该怎么快速识别题型、代码骨架怎么写、哪些边界最容易翻车。无论你是正在准备华为OD机试还是平时刷题总是“背了模板不会用”这套拆解思路都能直接拿过去用。花了一周时间把这批题啃完后我最大的感受是机试拉开差距的往往不是“难题会不会”而是“中等题能不能又快又稳地拿下”。所以下面我会把每道题的核心解法、原理、易错点全部铺开讲最后再聊聊从“刷过一遍”到“稳定拿分”的工程化训练方法。1. 先把t49-t55这批题的目标能力摸清1.1 这条题链隐藏的考察逻辑接触这批题的初期我习惯性地一道一道单独看结果复盘时发现它们并不是孤立的知识点而是一条能力链题号核心考点常考变形t49前缀和 / 差分数组静态区间求和、矩阵二维前缀和t50单调栈下一个更大元素、柱状图最大矩形t51快速幂大数幂取模、矩阵快速幂t52拓扑排序依赖关系、判环、任务调度t53质数判断与筛法单点判断、区间筛、质因数分解t54双指针 / 滑动窗口最长无重复子串、最小覆盖子串t55综合模拟状态机、规则模拟、时间序列看起来是七个独立模板实际上是在训练同一种能力面对一个陌生问题时能不能在最短时间内把它映射到已知的算法模型上。t49到t51是“模板直接套用”t52到t54开始要求“模板做局部改造”t55则干脆不给明确算法提示需要你自己从题目描述里拆出状态和规则。这就是机试最常见的难度递进方式。我在复盘时把每条题的错误原因记在文档里发现一个高频共性不是不会算法而是没看出来“这题能用这个算法”。所以从t49开始我就强迫自己先读题三分钟不做任何代码只回答三个问题数据规模是多少操作类型是查询还是修改有没有明显的“依赖”“前后关系”“单调性”线索1.2 拿到机试题先做的三分钟决策很多同学一上来就敲代码这是机试的大忌。尤其像t49-t55这种题量大的批次平均下来每道题留给你的时间并不多如果读题判断错了方向后面调试会非常痛苦。我的固定流程是第一分钟扫数据范围第二分钟圈出关键词第三分钟确定算法方向。数据范围直接决定复杂度底线。比如看到n 10^5基本就宣告O(n^2)的写法很难通过这时前缀和、双指针、单调栈这些O(n)方案就该立刻浮出来看到n 20才需要考虑状态压缩或暴力DFS。t49那道题我之所以卡那么久就是因为第一遍用暴力前缀循环做区间求和没注意到查询次数是10^5级别后来改成前缀和数组查询从O(n)变成O(1)整个问题迎刃而解。关键词也是线索。题目里出现“连续子数组”“不重复”“覆盖”这类字眼大概率是滑动窗口出现“依赖”“课程先后”“编译顺序”基本是拓扑排序出现“区间内多次求和”“子矩阵求和”前缀和没跑。这套映射关系不是背出来的是刷题刷出来的手感。但如果你还没建立这种手感可以从t49-t55这批题开始刻意训练每做一道题先别看题解用自己的话写出“为什么这题对应这种算法”写不出来再查效果比盲目刷十道强得多。2. t49到t51三个高频模板的直接套用与变形2.1 t49区间求和前缀和数组的“空间换时间”t49这类题通常长这样给你一个长度为n的整数数组然后来m次查询每次问你区间[L, R]的和是多少。裸做法是每次遍历区间累加单次查询O(n)m次就是O(n*m)一旦n和m都到10^5基本就超时了。前缀和的核心思想是把“多次重复计算的区间和”提前算好。定义一个数组pre[i]表示原数组前i个元素的和注意这里我习惯让下标从1开始避免处理pre[-1]的边界那么区间[L, R]的和就是pre[R] - pre[L-1]一次减法搞定。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long pre(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; } while (m--) { int l, r; cin l r; cout pre[r] - pre[l - 1] \n; } return 0; }这段代码有几个细节值得说。第一pre数组用long long因为n和元素值都可能很大区间和可能超过int范围第二下标从1开始是刻意为之这样L-1最小是0pre[0]正好是0完全不用特判第三ios::sync_with_stdio(false)和cin.tie(nullptr)这两行建议直接写进你的机试模板后面讲输入输出时会细说。如果题目从“区间求和”升级成“区间内每个值都加一个常数然后问单点值”那就是差分数组的主场。差分数组和前缀和互为逆运算构造diff[i] a[i] - a[i-1]区间[L, R]加c时只要改diff[L] c和diff[R1] - c最后求一遍前缀和就能还原数组。这个思路在t49的变形题里出现过建议一起练掉。2.2 t50单调栈用栈维护“下一个更大元素”t50这类题的经典描述是给你一个数组让你求每个元素右边第一个比它大的元素下标。暴力解法是双重循环O(n^2)。单调栈的做法很巧妙维护一个栈栈内元素的下标对应的数组值保持单调递增从栈底到栈顶。每次遍历到一个新元素a[i]只要栈不空且a[栈顶] a[i]就说明a[i]是栈顶元素右边第一个更大的元素这时把栈顶弹出、更新答案然后继续比较新栈顶。最后把当前下标压入栈。vectorint nextGreater(vectorint a) { int n a.size(); vectorint ans(n, -1); stackint st; for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) { ans[st.top()] i; st.pop(); } st.push(i); } return ans; }单调栈最难理解的地方在于为什么弹出的元素以后不会再用到道理很简单因为当前元素a[i]比它更大而且位置更靠右所以以后任何查询“右边第一个更大元素”都不可能再落到那个被弹出的旧元素上。这个“及时淘汰无用候选”的思路和滑动窗口里淘汰队尾较小值是同一个哲学。做题时容易踩的坑有这几个。一是比较符号用错还是取决于题目是求“严格大于”还是“大于等于”——我见过不少同学因为少写一个等号在隐藏用例上翻车。二是栈里存下标而不是存值因为答案要求返回下标存下标才能同时拿到值和位置。三是很多变形题需要你走两遍数组比如环形数组或者在下标差值上做文章但核心骨架完全一样。如果是“柱状图最大矩形”那种题单调栈的用法稍有调整弹栈时不是记录“谁比我大”而是以弹出元素为高用当前下标和栈顶下标的差作为宽计算面积。推荐把这类题和t50放在同一天刷对比两者的区别体会单调栈的“结算时机”。2.3 t51快速幂别让循环把时间烧光t51这类题描述通常很短求a的b次方模p的结果其中b可以大到10^18。如果你直接写for (int i 0; i b; i)哪怕编译器再优化也是O(b)面对10^18直接爆炸。快速幂的原理是把指数按二进制拆开比如a^1313的二进制是1101等于a^8 * a^4 * a^1。我们只需要循环b的二进制位数约60次每次把a自乘一次变成a^2, a^4, a^8...遇到二进制位为1就乘进答案。long long qpow(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) { res res * a % mod; } a a * a % mod; b 1; } return res; }这里有个容易被忽视的细节res的初始值是1 % mod而不是直接写1。因为当模数等于1时任何结果都应该是0而1 % 1 0恰好正确如果直接初始化为1而不取模边界用例直接就错了。类似的坑我在别的题里踩过多次现在凡是“结果可能要取模”的函数初始值一律先对mod取模。另外a a * a % mod这行乘法运算可能超过int范围所以a和res都要用long long。这一批题里t51常和组合数、矩阵快速幂联动但在机试场景中先把基础快速幂模板记扎实比什么都强。建议把上面这段代码默写三遍目标是20秒内无脑打出来。3. t52到t55从模板到综合题差距在“拆题”能力3.1 t52拓扑排序把“谁先谁后”画成一张图拓扑排序是处理依赖关系的标准工具。它的经典场景是有若干任务某些任务必须在另一些任务之前完成问能否找到一种合法顺序。算法本身不复杂用入度表配合队列BFS就能搞定vectorint topo(int n, vectorvectorint g, vectorint indeg) { queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } vectorint order; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { if (--indeg[v] 0) { q.push(v); } } } if (order.size() ! n) { // 图中存在环不存在合法拓扑序 return {}; } return order; }这个模板看起来简单真正容易出错的地方在建模阶段。比如题目说“A依赖B”到底是B - A还是A - B方向反了整道题就崩了。我的经验是在建图前先明确两句话——“谁先完成才能开始谁”然后画箭头从先指向后再写一行注释贴在代码旁边防止写一半忘记方向。另一个高频考点是“是否能完成全部课程”本质上就是判环。你不需要真的把拓扑序列存下来只要统计出队节点个数如果个数小于n就说明有环。判环这件事用DFS也能做但BFS写法更不容易栈溢出而且天然给出了字典序最小的拓扑序变形空间只要把普通队列换成优先队列。我在刷t52时还总结过一个规律凡是题目里出现“依赖”“先后”“编译顺序”“课程表”这些词的想都不用想先把邻接表和入度数组建起来。真正麻烦的是那些披着其他外衣的隐藏拓扑题比如“文件夹的删除顺序”“包管理器的安装顺序”识别它们需要你已经把这个模板内化成一种思维习惯。3.2 t53判断质数优化根号法、6k±1、埃氏筛“判断质数”本身不难基础写法是遍历2到sqrt(n)。但机试里它经常以“批量判断1到n所有质数”或“判断m个大数”的形式出现这时候逐个数用根号法就会非常慢。先说单个数判断的优化版本。一个经典技巧是除了2和3以外所有质数都可以写成6k±1的形式。原因是任何整数模6的余数只能为0、1、2、3、4、5其中0、2、3、4对应的数都能被2或3整除不可能是质数只剩下1和5两类。所以循环步长可以直接取6每次只检查i和i2两个候选。bool isPrime(long long x) { if (x 2) return false; if (x 2 || x 3) return true; if (x % 2 0 || x % 3 0) return false; for (long long i 5; i * i x; i 6) { if (x % i 0 || x % (i 2) 0) { return false; } } return true; }注意这里i * i可能溢出所以i要用long long或者写成i x / i。如果是批量筛1到n的所有质数埃氏筛是性价比最高的选择开一个bool数组从2开始每遇到一个质数就把它的所有倍数标记成合数。时间复杂度是O(n log log n)对n等于10^7以内的范围完全够用。vectorbool sieve(int n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; 1LL * i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } return isPrime; }埃氏筛里有个小优化从i * i开始标记而不是从2*i开始因为小于i*i的合数已经被更小的质因子筛过了。这个细节能省不少时间建议写进自己的模板注释里。3.3 t54双指针字符串滑动窗口的“右扩左缩”t54最典型的考法是“求最长无重复字符子串”。暴力做法是枚举所有子串然后检查有无重复O(n^2)。滑动窗口可以做到O(n)右指针不断向右扩展把新字符加入窗口一旦发现窗口内有重复字符就移动左指针缩小窗口直到重复消除。int lengthOfLongestSubstring(string s) { int n s.size(); int l 0, ans 0; unordered_mapchar, int cnt; for (int r 0; r n; r) { cnt[s[r]]; while (cnt[s[r]] 1) { --cnt[s[l]]; l; } ans max(ans, r - l 1); } return ans; }核心就在while循环里窗口右端每加入一个字符就检查这个字符是否出现过如果出现过就把左端往右收直到该字符计数降为1。因为窗口收缩时每个字符最多被移除一次整个过程的均摊复杂度是O(n)。每次写这类题我都会提醒自己右指针驱动扩展左指针负责消除不合法状态答案在窗口合法的那一刻更新。不少变形题最小覆盖子串、字符串的排列都是在这个框架上加一个“目标字符种类计数器”理解了“右扩左缩”的本质后遇到新题就不会慌。t54的另一个坑是ans初始化成0还是1取决于题目是否保证字符串非空建议读题时确认好测试边界用例时重点对待。3.4 t55综合模拟先把状态机画清楚再动笔t55这类题一般不考复杂算法而是考耐心和细节。常见的形式有模拟一台自动售货机、模拟棋子的行走轨迹、模拟LRU缓存、模拟文本编辑器操作。题目描述往往很长逻辑分支多很容易写着写着把自己绕进去。我处理t55的心得是先不写代码用纸笔画状态机。每个输入事件会引起哪些状态变化用箭头标出来哪些事件是互斥的哪些可以叠加。把enum定义好用有名字的状态常量代替魔法数字比如用enum State { WAIT, SELECT, PAY, OUT }。这样写出来的分支判断清晰得多调试时cout也容易定位。模拟题的另一个关键是“读题别跳字”尤其是对于“如果同时满足A和B优先执行C”这类优先级规则一定要原文照抄到代码注释里。我t55第一次提交时漏掉了一个“当某事件发生时先取消原先的延迟任务再执行新任务”的隐藏条件导致一半用例不过。这种题没有技巧就是细。如果时间紧张t55采用“先暴力后优化”的策略也没问题先按题面描述逐句翻译成最直白的代码跑通样例后再考虑用哈希表或栈加速。机试判分的规则是部分用例按点给分一个能跑小数据的暴力解法远好于一个写完就崩的“最优解”。4. 机试中的输入输出细节与边界条件比算法更致命4.1 读入方式别让cin/cout成为性能瓶颈很多同学在本地用cin、cout跑小数据没感觉一上机试大数据量就发现超时。最常见的原因就是没关流同步。默认情况下cin会和scanf的缓冲区同步这带来巨大的性能开销。只要在代码开头加上两行ios::sync_with_stdio(false); cin.tie(nullptr);cin/cout的读写速度就能拉到和scanf/printf接近的水平。这两行相当于主题模板的一部分我平时刷题时直接默认带上不需要犹豫。另外使用\n而不是endl因为endl会强制刷新缓冲区高频率输出时也是一个隐藏的耗时点。如果题目输入格式复杂比如混合字符和数字、不定行数用getline结合stringstream来拆分会更稳。我处理多维数组、坐标对这类输入时习惯先用cin读数量再用getline读一整行然后用istringstream逐字段处理能避免很多因换行符残留导致的错位问题。4.2 溢出、取模和负数三个永远查一遍的坑C里最容易翻车的不是算法而是数据范围。我给自己定了个规矩只要题目里出现“求和”“乘积”“次数”一律用long long如果涉及大量乘法取模乘法运算前先把两个数都取模防止一次乘法就溢出。取模还有个隐藏细节C的负数取模结果是负数例如-3 % 5等于-3而数学上我们通常希望它落在[0, mod)区间。如果题目需要非负余数记得统一处理auto mod [](long long x, long long p) { return (x % p p) % p; };竞赛里很多答案要求对10^97取模本质上是在防溢出、方便哈希化并不是出题人闲着无聊。理解这一点后你就不会在“为什么要取模”上浪费情绪直接当作必须遵守的规则即可。4.3 边界用例自查清单提交前花两分钟我吃过太多“样例通过但提交0分”的亏所以现在每道题写完后都会按下面这张清单自测一遍检查项典型边界为什么重要最小规模n0、n1、空字符串数组访问越不越界、循环执不执行全相同所有元素都相等单调栈、滑动窗口的等号逻辑正确吗单调序列完全升序、完全降序栈/队列的结算时机是否覆盖两端极值数据INT_MAX、LONG_LONG_MAX加法/乘法会不会溢出重复字符/数字aaaa、[1,1,1,1]去重和计数逻辑是否正常结果等于0或1的情况空区间、单次操作初始值是否设置正确这个表不用背关键是形成“写完就扫一眼边界”的习惯。很多看起来很难的题目之所以拿不满分差的不是算法而是一个long long或一个等号。5. 从“刷过一遍”到“稳定拿分”的工程化训练方法5.1 建立自己的模板库而不是依赖脑内记忆把t49-t55刷完后你应该把每类题的最小可运行模板整理成单独的文件放在本地一个template/目录里。我的模板库包含十几个文件每个文件顶部注释写明“适用场景、复杂度、易错点”这样机试前半小时快速过一遍比临时翻题解有效得多。以调用模板的心态写机试题会显著降低不确定性。比如看到区间求和就立刻想到前缀和模板看到依赖关系就立刻想到拓扑排序模板省去大量思考“怎么写框架”的精力把脑力留给真正的难点。STL选型也值得形成固定习惯可变长数组用vector而不是裸数组需要快速查找用unordered_map需要保持有序且频繁插入删除用set需要单调性结构时可以考虑priority_queue。每种容器背熟三件事头文件、常用操作、时间开销就够了。机试里80%的场景轮不到你手写平衡树。5.2 考场上时间分配与“保底策略”机试的时间分配直接决定你能不能把会做的题都转化成分数。我的策略是先把所有题目花10分钟通读一遍按“容易-中等-难”分档做的时候先做最容易的快速拿分建立信心再做中等题最后攻难题。切忌死磕一道题超过30分钟很多时候卡住是因为思路错了换个题回来再看反而能发现问题。“暴力保底”也是个成熟策略。比如t55综合模拟题如果最优解法一时想不出来先写一个只过小数据的暴力版本把能拿的分数先攥到手里。机试按用例给分10个测试点拿7个也比“追求完美解法最后0个用例通过”强得多。5.3 考前的最后一道工序编译与自检交卷前这几分钟价值很高我通常按固定顺序做最后一轮自检先确认没有使用尚未定义的变量或函数再确认数组下标没有写成i n导致越界然后看输出格式空格和换行是否和题目要求完全一致最后确认所有cout都带上了\n而不是endl。编译参数上我习惯在本地开-Wall -Wextra把大部分未使用变量、类型溢出警告提前揪出来。虽然机试环境未必允许你改编译器参数但本地开警告养成的“零警告强迫症”会让你在考场上少犯很多低级错误。最后分享一个我坚持了很久的习惯每道题AC之后不管对错都要写一句“这道题让我新学到的点”回填到题号旁边。t49到t55这七道题我写下的收获各不相同比如t49让我记住“区间和必须用long long”t50让我明白“弹出即结算”t53让我学会“6k±1优化”。这些零碎的笔记才是下一次考试前真正能救命的东西。刷题当然要看量但更关键的是把每一道的教训真正留在自己手里而不是让它们随着交卷烟消云散。
华为OD机试t49-t55题组：七种算法模板的实战拆解
元旦后那场模拟机试我卡在t49题上整整四十分钟最后用暴力枚举勉强过了两个小数据测试点。后来把t49到t55这批题按算法类型重刷了一遍才发现它们的出题顺序是有规律可循的——区间查询、单调栈、快速幂、拓扑排序、动态规划、质数优化、双指针、综合模拟几乎覆盖了机试里能考到的基础算法全集。这篇不是单纯讲某一道题的题解而是把t49-t55当作一个完整的训练切片来处理每道题对应什么知识点、为什么考它、考场上该怎么快速识别题型、代码骨架怎么写、哪些边界最容易翻车。无论你是正在准备华为OD机试还是平时刷题总是“背了模板不会用”这套拆解思路都能直接拿过去用。花了一周时间把这批题啃完后我最大的感受是机试拉开差距的往往不是“难题会不会”而是“中等题能不能又快又稳地拿下”。所以下面我会把每道题的核心解法、原理、易错点全部铺开讲最后再聊聊从“刷过一遍”到“稳定拿分”的工程化训练方法。1. 先把t49-t55这批题的目标能力摸清1.1 这条题链隐藏的考察逻辑接触这批题的初期我习惯性地一道一道单独看结果复盘时发现它们并不是孤立的知识点而是一条能力链题号核心考点常考变形t49前缀和 / 差分数组静态区间求和、矩阵二维前缀和t50单调栈下一个更大元素、柱状图最大矩形t51快速幂大数幂取模、矩阵快速幂t52拓扑排序依赖关系、判环、任务调度t53质数判断与筛法单点判断、区间筛、质因数分解t54双指针 / 滑动窗口最长无重复子串、最小覆盖子串t55综合模拟状态机、规则模拟、时间序列看起来是七个独立模板实际上是在训练同一种能力面对一个陌生问题时能不能在最短时间内把它映射到已知的算法模型上。t49到t51是“模板直接套用”t52到t54开始要求“模板做局部改造”t55则干脆不给明确算法提示需要你自己从题目描述里拆出状态和规则。这就是机试最常见的难度递进方式。我在复盘时把每条题的错误原因记在文档里发现一个高频共性不是不会算法而是没看出来“这题能用这个算法”。所以从t49开始我就强迫自己先读题三分钟不做任何代码只回答三个问题数据规模是多少操作类型是查询还是修改有没有明显的“依赖”“前后关系”“单调性”线索1.2 拿到机试题先做的三分钟决策很多同学一上来就敲代码这是机试的大忌。尤其像t49-t55这种题量大的批次平均下来每道题留给你的时间并不多如果读题判断错了方向后面调试会非常痛苦。我的固定流程是第一分钟扫数据范围第二分钟圈出关键词第三分钟确定算法方向。数据范围直接决定复杂度底线。比如看到n 10^5基本就宣告O(n^2)的写法很难通过这时前缀和、双指针、单调栈这些O(n)方案就该立刻浮出来看到n 20才需要考虑状态压缩或暴力DFS。t49那道题我之所以卡那么久就是因为第一遍用暴力前缀循环做区间求和没注意到查询次数是10^5级别后来改成前缀和数组查询从O(n)变成O(1)整个问题迎刃而解。关键词也是线索。题目里出现“连续子数组”“不重复”“覆盖”这类字眼大概率是滑动窗口出现“依赖”“课程先后”“编译顺序”基本是拓扑排序出现“区间内多次求和”“子矩阵求和”前缀和没跑。这套映射关系不是背出来的是刷题刷出来的手感。但如果你还没建立这种手感可以从t49-t55这批题开始刻意训练每做一道题先别看题解用自己的话写出“为什么这题对应这种算法”写不出来再查效果比盲目刷十道强得多。2. t49到t51三个高频模板的直接套用与变形2.1 t49区间求和前缀和数组的“空间换时间”t49这类题通常长这样给你一个长度为n的整数数组然后来m次查询每次问你区间[L, R]的和是多少。裸做法是每次遍历区间累加单次查询O(n)m次就是O(n*m)一旦n和m都到10^5基本就超时了。前缀和的核心思想是把“多次重复计算的区间和”提前算好。定义一个数组pre[i]表示原数组前i个元素的和注意这里我习惯让下标从1开始避免处理pre[-1]的边界那么区间[L, R]的和就是pre[R] - pre[L-1]一次减法搞定。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorlong long pre(n 1, 0); for (int i 1; i n; i) { long long x; cin x; pre[i] pre[i - 1] x; } while (m--) { int l, r; cin l r; cout pre[r] - pre[l - 1] \n; } return 0; }这段代码有几个细节值得说。第一pre数组用long long因为n和元素值都可能很大区间和可能超过int范围第二下标从1开始是刻意为之这样L-1最小是0pre[0]正好是0完全不用特判第三ios::sync_with_stdio(false)和cin.tie(nullptr)这两行建议直接写进你的机试模板后面讲输入输出时会细说。如果题目从“区间求和”升级成“区间内每个值都加一个常数然后问单点值”那就是差分数组的主场。差分数组和前缀和互为逆运算构造diff[i] a[i] - a[i-1]区间[L, R]加c时只要改diff[L] c和diff[R1] - c最后求一遍前缀和就能还原数组。这个思路在t49的变形题里出现过建议一起练掉。2.2 t50单调栈用栈维护“下一个更大元素”t50这类题的经典描述是给你一个数组让你求每个元素右边第一个比它大的元素下标。暴力解法是双重循环O(n^2)。单调栈的做法很巧妙维护一个栈栈内元素的下标对应的数组值保持单调递增从栈底到栈顶。每次遍历到一个新元素a[i]只要栈不空且a[栈顶] a[i]就说明a[i]是栈顶元素右边第一个更大的元素这时把栈顶弹出、更新答案然后继续比较新栈顶。最后把当前下标压入栈。vectorint nextGreater(vectorint a) { int n a.size(); vectorint ans(n, -1); stackint st; for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) { ans[st.top()] i; st.pop(); } st.push(i); } return ans; }单调栈最难理解的地方在于为什么弹出的元素以后不会再用到道理很简单因为当前元素a[i]比它更大而且位置更靠右所以以后任何查询“右边第一个更大元素”都不可能再落到那个被弹出的旧元素上。这个“及时淘汰无用候选”的思路和滑动窗口里淘汰队尾较小值是同一个哲学。做题时容易踩的坑有这几个。一是比较符号用错还是取决于题目是求“严格大于”还是“大于等于”——我见过不少同学因为少写一个等号在隐藏用例上翻车。二是栈里存下标而不是存值因为答案要求返回下标存下标才能同时拿到值和位置。三是很多变形题需要你走两遍数组比如环形数组或者在下标差值上做文章但核心骨架完全一样。如果是“柱状图最大矩形”那种题单调栈的用法稍有调整弹栈时不是记录“谁比我大”而是以弹出元素为高用当前下标和栈顶下标的差作为宽计算面积。推荐把这类题和t50放在同一天刷对比两者的区别体会单调栈的“结算时机”。2.3 t51快速幂别让循环把时间烧光t51这类题描述通常很短求a的b次方模p的结果其中b可以大到10^18。如果你直接写for (int i 0; i b; i)哪怕编译器再优化也是O(b)面对10^18直接爆炸。快速幂的原理是把指数按二进制拆开比如a^1313的二进制是1101等于a^8 * a^4 * a^1。我们只需要循环b的二进制位数约60次每次把a自乘一次变成a^2, a^4, a^8...遇到二进制位为1就乘进答案。long long qpow(long long a, long long b, long long mod) { long long res 1 % mod; while (b) { if (b 1) { res res * a % mod; } a a * a % mod; b 1; } return res; }这里有个容易被忽视的细节res的初始值是1 % mod而不是直接写1。因为当模数等于1时任何结果都应该是0而1 % 1 0恰好正确如果直接初始化为1而不取模边界用例直接就错了。类似的坑我在别的题里踩过多次现在凡是“结果可能要取模”的函数初始值一律先对mod取模。另外a a * a % mod这行乘法运算可能超过int范围所以a和res都要用long long。这一批题里t51常和组合数、矩阵快速幂联动但在机试场景中先把基础快速幂模板记扎实比什么都强。建议把上面这段代码默写三遍目标是20秒内无脑打出来。3. t52到t55从模板到综合题差距在“拆题”能力3.1 t52拓扑排序把“谁先谁后”画成一张图拓扑排序是处理依赖关系的标准工具。它的经典场景是有若干任务某些任务必须在另一些任务之前完成问能否找到一种合法顺序。算法本身不复杂用入度表配合队列BFS就能搞定vectorint topo(int n, vectorvectorint g, vectorint indeg) { queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } vectorint order; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : g[u]) { if (--indeg[v] 0) { q.push(v); } } } if (order.size() ! n) { // 图中存在环不存在合法拓扑序 return {}; } return order; }这个模板看起来简单真正容易出错的地方在建模阶段。比如题目说“A依赖B”到底是B - A还是A - B方向反了整道题就崩了。我的经验是在建图前先明确两句话——“谁先完成才能开始谁”然后画箭头从先指向后再写一行注释贴在代码旁边防止写一半忘记方向。另一个高频考点是“是否能完成全部课程”本质上就是判环。你不需要真的把拓扑序列存下来只要统计出队节点个数如果个数小于n就说明有环。判环这件事用DFS也能做但BFS写法更不容易栈溢出而且天然给出了字典序最小的拓扑序变形空间只要把普通队列换成优先队列。我在刷t52时还总结过一个规律凡是题目里出现“依赖”“先后”“编译顺序”“课程表”这些词的想都不用想先把邻接表和入度数组建起来。真正麻烦的是那些披着其他外衣的隐藏拓扑题比如“文件夹的删除顺序”“包管理器的安装顺序”识别它们需要你已经把这个模板内化成一种思维习惯。3.2 t53判断质数优化根号法、6k±1、埃氏筛“判断质数”本身不难基础写法是遍历2到sqrt(n)。但机试里它经常以“批量判断1到n所有质数”或“判断m个大数”的形式出现这时候逐个数用根号法就会非常慢。先说单个数判断的优化版本。一个经典技巧是除了2和3以外所有质数都可以写成6k±1的形式。原因是任何整数模6的余数只能为0、1、2、3、4、5其中0、2、3、4对应的数都能被2或3整除不可能是质数只剩下1和5两类。所以循环步长可以直接取6每次只检查i和i2两个候选。bool isPrime(long long x) { if (x 2) return false; if (x 2 || x 3) return true; if (x % 2 0 || x % 3 0) return false; for (long long i 5; i * i x; i 6) { if (x % i 0 || x % (i 2) 0) { return false; } } return true; }注意这里i * i可能溢出所以i要用long long或者写成i x / i。如果是批量筛1到n的所有质数埃氏筛是性价比最高的选择开一个bool数组从2开始每遇到一个质数就把它的所有倍数标记成合数。时间复杂度是O(n log log n)对n等于10^7以内的范围完全够用。vectorbool sieve(int n) { vectorbool isPrime(n 1, true); isPrime[0] isPrime[1] false; for (int i 2; 1LL * i * i n; i) { if (isPrime[i]) { for (int j i * i; j n; j i) { isPrime[j] false; } } } return isPrime; }埃氏筛里有个小优化从i * i开始标记而不是从2*i开始因为小于i*i的合数已经被更小的质因子筛过了。这个细节能省不少时间建议写进自己的模板注释里。3.3 t54双指针字符串滑动窗口的“右扩左缩”t54最典型的考法是“求最长无重复字符子串”。暴力做法是枚举所有子串然后检查有无重复O(n^2)。滑动窗口可以做到O(n)右指针不断向右扩展把新字符加入窗口一旦发现窗口内有重复字符就移动左指针缩小窗口直到重复消除。int lengthOfLongestSubstring(string s) { int n s.size(); int l 0, ans 0; unordered_mapchar, int cnt; for (int r 0; r n; r) { cnt[s[r]]; while (cnt[s[r]] 1) { --cnt[s[l]]; l; } ans max(ans, r - l 1); } return ans; }核心就在while循环里窗口右端每加入一个字符就检查这个字符是否出现过如果出现过就把左端往右收直到该字符计数降为1。因为窗口收缩时每个字符最多被移除一次整个过程的均摊复杂度是O(n)。每次写这类题我都会提醒自己右指针驱动扩展左指针负责消除不合法状态答案在窗口合法的那一刻更新。不少变形题最小覆盖子串、字符串的排列都是在这个框架上加一个“目标字符种类计数器”理解了“右扩左缩”的本质后遇到新题就不会慌。t54的另一个坑是ans初始化成0还是1取决于题目是否保证字符串非空建议读题时确认好测试边界用例时重点对待。3.4 t55综合模拟先把状态机画清楚再动笔t55这类题一般不考复杂算法而是考耐心和细节。常见的形式有模拟一台自动售货机、模拟棋子的行走轨迹、模拟LRU缓存、模拟文本编辑器操作。题目描述往往很长逻辑分支多很容易写着写着把自己绕进去。我处理t55的心得是先不写代码用纸笔画状态机。每个输入事件会引起哪些状态变化用箭头标出来哪些事件是互斥的哪些可以叠加。把enum定义好用有名字的状态常量代替魔法数字比如用enum State { WAIT, SELECT, PAY, OUT }。这样写出来的分支判断清晰得多调试时cout也容易定位。模拟题的另一个关键是“读题别跳字”尤其是对于“如果同时满足A和B优先执行C”这类优先级规则一定要原文照抄到代码注释里。我t55第一次提交时漏掉了一个“当某事件发生时先取消原先的延迟任务再执行新任务”的隐藏条件导致一半用例不过。这种题没有技巧就是细。如果时间紧张t55采用“先暴力后优化”的策略也没问题先按题面描述逐句翻译成最直白的代码跑通样例后再考虑用哈希表或栈加速。机试判分的规则是部分用例按点给分一个能跑小数据的暴力解法远好于一个写完就崩的“最优解”。4. 机试中的输入输出细节与边界条件比算法更致命4.1 读入方式别让cin/cout成为性能瓶颈很多同学在本地用cin、cout跑小数据没感觉一上机试大数据量就发现超时。最常见的原因就是没关流同步。默认情况下cin会和scanf的缓冲区同步这带来巨大的性能开销。只要在代码开头加上两行ios::sync_with_stdio(false); cin.tie(nullptr);cin/cout的读写速度就能拉到和scanf/printf接近的水平。这两行相当于主题模板的一部分我平时刷题时直接默认带上不需要犹豫。另外使用\n而不是endl因为endl会强制刷新缓冲区高频率输出时也是一个隐藏的耗时点。如果题目输入格式复杂比如混合字符和数字、不定行数用getline结合stringstream来拆分会更稳。我处理多维数组、坐标对这类输入时习惯先用cin读数量再用getline读一整行然后用istringstream逐字段处理能避免很多因换行符残留导致的错位问题。4.2 溢出、取模和负数三个永远查一遍的坑C里最容易翻车的不是算法而是数据范围。我给自己定了个规矩只要题目里出现“求和”“乘积”“次数”一律用long long如果涉及大量乘法取模乘法运算前先把两个数都取模防止一次乘法就溢出。取模还有个隐藏细节C的负数取模结果是负数例如-3 % 5等于-3而数学上我们通常希望它落在[0, mod)区间。如果题目需要非负余数记得统一处理auto mod [](long long x, long long p) { return (x % p p) % p; };竞赛里很多答案要求对10^97取模本质上是在防溢出、方便哈希化并不是出题人闲着无聊。理解这一点后你就不会在“为什么要取模”上浪费情绪直接当作必须遵守的规则即可。4.3 边界用例自查清单提交前花两分钟我吃过太多“样例通过但提交0分”的亏所以现在每道题写完后都会按下面这张清单自测一遍检查项典型边界为什么重要最小规模n0、n1、空字符串数组访问越不越界、循环执不执行全相同所有元素都相等单调栈、滑动窗口的等号逻辑正确吗单调序列完全升序、完全降序栈/队列的结算时机是否覆盖两端极值数据INT_MAX、LONG_LONG_MAX加法/乘法会不会溢出重复字符/数字aaaa、[1,1,1,1]去重和计数逻辑是否正常结果等于0或1的情况空区间、单次操作初始值是否设置正确这个表不用背关键是形成“写完就扫一眼边界”的习惯。很多看起来很难的题目之所以拿不满分差的不是算法而是一个long long或一个等号。5. 从“刷过一遍”到“稳定拿分”的工程化训练方法5.1 建立自己的模板库而不是依赖脑内记忆把t49-t55刷完后你应该把每类题的最小可运行模板整理成单独的文件放在本地一个template/目录里。我的模板库包含十几个文件每个文件顶部注释写明“适用场景、复杂度、易错点”这样机试前半小时快速过一遍比临时翻题解有效得多。以调用模板的心态写机试题会显著降低不确定性。比如看到区间求和就立刻想到前缀和模板看到依赖关系就立刻想到拓扑排序模板省去大量思考“怎么写框架”的精力把脑力留给真正的难点。STL选型也值得形成固定习惯可变长数组用vector而不是裸数组需要快速查找用unordered_map需要保持有序且频繁插入删除用set需要单调性结构时可以考虑priority_queue。每种容器背熟三件事头文件、常用操作、时间开销就够了。机试里80%的场景轮不到你手写平衡树。5.2 考场上时间分配与“保底策略”机试的时间分配直接决定你能不能把会做的题都转化成分数。我的策略是先把所有题目花10分钟通读一遍按“容易-中等-难”分档做的时候先做最容易的快速拿分建立信心再做中等题最后攻难题。切忌死磕一道题超过30分钟很多时候卡住是因为思路错了换个题回来再看反而能发现问题。“暴力保底”也是个成熟策略。比如t55综合模拟题如果最优解法一时想不出来先写一个只过小数据的暴力版本把能拿的分数先攥到手里。机试按用例给分10个测试点拿7个也比“追求完美解法最后0个用例通过”强得多。5.3 考前的最后一道工序编译与自检交卷前这几分钟价值很高我通常按固定顺序做最后一轮自检先确认没有使用尚未定义的变量或函数再确认数组下标没有写成i n导致越界然后看输出格式空格和换行是否和题目要求完全一致最后确认所有cout都带上了\n而不是endl。编译参数上我习惯在本地开-Wall -Wextra把大部分未使用变量、类型溢出警告提前揪出来。虽然机试环境未必允许你改编译器参数但本地开警告养成的“零警告强迫症”会让你在考场上少犯很多低级错误。最后分享一个我坚持了很久的习惯每道题AC之后不管对错都要写一句“这道题让我新学到的点”回填到题号旁边。t49到t55这七道题我写下的收获各不相同比如t49让我记住“区间和必须用long long”t50让我明白“弹出即结算”t53让我学会“6k±1优化”。这些零碎的笔记才是下一次考试前真正能救命的东西。刷题当然要看量但更关键的是把每一道的教训真正留在自己手里而不是让它们随着交卷烟消云散。