大四那年我基本把牛客当刷题主场每周都会蹲一场模考。2023年的牛客一模算法笔试我是在截止日期前最后一天晚上做的做完之后盯着成绩单看了很久不是因为分数多高而是那套卷子把我复习里的几个盲区一次性全暴露了。这里说的牛客模考是牛客网定期组织的在线算法笔试模拟赛题目风格和难度对标互联网大厂的技术岗笔试题环境也尽量还原真实笔试限时、ACM模式下自己处理输入输出、不能跳题回头改。对于想冲春招秋招的同学来说它本质上是一次低成本体检能让你在真正投简历之前知道自己处在什么水平。这篇复盘我按“试卷结构、高频考点、时间分配、失分排查、考后复习”五块来讲重点会把我在考场上卡壳的KMP、Dijkstra、快速幂全部拆开重讲一遍。不管你是刚开始刷题还是已经刷了三百道这篇都值得对着题目过一遍。1. 2023牛客一模的整体情况与试卷定位1.1 一场模考到底在模拟什么牛客的算法模考形式上走的是“限时 ACM模式 实时判题”的路线。我说的ACM模式是指题目不会像力扣那样把函数签名和参数都准备好而是给你一段标准输入你自己负责读写。很多第一次参加牛客模考的人会直接懵在这里明明思路对了但代码卡在解析输入上白白浪费二十分钟。这里要提醒刚接触牛客笔试的同学不要把“力扣核心代码模式”的习惯直接带进模考。你需要熟悉 raw_input、input().split()、while True try/except 这一整套输入处理逻辑尤其是多组测试用例的情况。你可以先找一套往年的模考题练手专门练习IO处理不然正式笔试第一题就会消耗你大量时间。那场一模的做题体验是比较典型的四道算法题难度从简单到偏难递增总时长90分钟。第一题是签到性质基本就是考基础语法和简单模拟第二题开始上数据结构的常规操作第三题是中等偏上的经典算法变体第四题则是扛区分度的题目能AC的人不会太多。我当时的策略是前两题尽量满分第三题拿部分分第四题看情况。1.2 试卷结构算法题之外还有哪些内容很多人以为牛客模考全是算法题其实并不完全如此。以2023一模为例前面有一部分是计算机基础知识的客观题包括操作系统、计算机网络、数据库、C/Java语言基础等。这部分虽然不涉及写代码但占比不小而且往往被刷题党忽略。常识层面网络层协议、TCP三次握手、进程与线程区别、数据库索引失效场景这些几乎每次都会出现。技术岗笔试的客观题并不是靠刷算法题能覆盖的你需要额外过一遍408核心知识点。建议在刷算法的同时每周抽两个晚上系统看基础题否则成绩单上算法分再高总分也可能被客观题拉下来。客观题之后才是算法编程题。从我的经验看编程题的分值权重明显更高但客观题和编程题是同一份成绩单任何一块放松都会影响最终排名。尤其是大厂筛简历时笔试排名会直接决定你是否进入面试环节。1.3 我为什么建议应届生认真对待模考模拟考最大的价值不是排名而是让你提前踩坑。我在那次一模里就踩了三个典型的坑第一第三题KMP变体我写了暴力匹配时间复杂度直接爆炸第二Dijkstra堆优化版本没有用visited数组剪枝导致重复松弛在极端数据下超时第三快速幂取模时没注意中间结果溢出用例直接错了一半。这些坑平时刷题时很少遇到因为力扣的测试用例通常不会故意卡边界。可真实笔试的用例设计者就是来“找茬”的数据范围会拉满边界条件会刁钻。模考就是在正式翻车之前先给你一次低成本翻车的机会考完再总结远比等到正式笔试才发现问题要好得多。2. 考场上的高频算法考点复盘2.1 字符串与KMPnext数组必须能手推一模第三题考了一道字符串匹配变体给定文本串和一个模式串要求统计模式串在文本串中出现的次数允许重叠。看到“允许重叠”四个字我就意识到暴力匹配会出问题。文本串长度10^5模式串长度10^4O(n*m)的暴力做法在最后一组用例上必定超时必须上KMP。先说最简单的暴力为什么不行从文本串每个位置开始尝试匹配模式串最坏情况下每比较一个字符都要回溯到开头整体复杂度O(n*m)。而KMP的核心思想是匹配失败时不让文本串指针回退只让模式串指针通过next数组跳到合适的位置这样整体复杂度降到O(nm)。next数组的定义很关键我当场用的版本是next[i]表示前i个字符组成的子串中最长相等真前后缀的长度。模式串 p abacaba 的 next 数组手推过程如下next[0] -1作为哨兵表示没有可跳转的位置next[1] 0前1个字符是a真前后缀为空长度为0next[2] 0前2个字符是ab前缀a不等于后缀b长度为0next[3] 1前3个字符是aba前缀a等于后缀a长度为1next[4] 0前4个字符是abac最长相等前后缀为0next[5] 1前5个字符是abaca前缀a等于后缀a长度1next[6] 2前6个字符是abacab前缀ab等于后缀ab长度2next[7] 3前7个字符是abacaba前缀aba等于后缀aba长度3所以 next 数组是 [-1, 0, 0, 1, 0, 1, 2, 3]。这个数组的含义是当匹配到模式串第i个字符失败时j跳转到next[i]继续匹配。比如模式串匹配到第7个字符下标6失败j直接跳到3因为前3个字符aba已经和当前文本串的后缀匹配了。考场上我曾经以为理解了KMP原理就可以放心直到那次把next数组死记硬背搞混。从这次之后我学乖了每次笔试前把 next 数组手推口诀过一遍“j从0开始i从1开始相等则next[i1]j1然后i、j都前进不相等则j回到next[j]”。不要只在脑子里想一定要在草稿纸上演算至少两个模式串否则考场上很容易手滑。KMP的代码实现也要注意一个细节统计允许重叠的出现次数时匹配成功后 j 不是重置为0而是回退到 next[j]这样下一轮可以从已经匹配的前缀继续不会漏掉重叠部分。如果这里写错样例能过但大数据量下计数就会偏少。2.2 图论最短路Dijkstra堆优化是保底技能一模第二题就是最短路问题给了一个带权无向图节点数和边数都在10^5级别求从起点到每个节点的最短距离。看到数据范围我第一反应就是Dijkstra堆优化裸的O(V^2)版本在这种数据量下面一定超时。Dijkstra的核心思路是贪心维护一个集合S表示已经确定最短路的节点每次从集合外选一个距离起点最近的点加入S然后用这个点去松弛它邻接的节点。朴素实现里找最近点需要扫描全部节点复杂度O(V^2)在稠密图上还能接受但V到10^5就完全不行。堆优化版本用优先队列维护候选节点。每次弹出一个距离最小的节点如果这个节点已经被处理过就跳过否则用它对邻接边做松弛新距离更小的节点再次入队。复杂度降为O((VE)logV)可以稳稳跑过10^5的数据量。这里有个容易踩的坑优先队列默认是大顶堆而Dijkstra需要每次取最小距离所以必须传入 greaterpairint,int 改成小顶堆。C写法是 priority_queuepairint,int, vectorpairint,int, greaterpairint,int。如果你用JavaPriorityQueue默认就是小顶堆直接new就行。语言习惯不同笔试前最好把常用模板都准备好别到了考场现查API。还有一个性能细节出队时判断 if (d ! dist[u]) continue 比另开一个visited数组更简洁。它的原理是如果一个节点的距离已经在入队后被更新过那么老的记录就会和当前dist[u]不一致直接跳过即可。这个写法既省内存又省时间我到现在还在用。2.3 贪心排序区间类题目几乎是必考模考第一题其实是一道披着模拟外衣的贪心题。题目给了一组会议的开始时间和结束时间问最多能参加多少场要求会议时间不能重叠。这是非常经典的“最多不重叠区间数”问题。这类题的贪心策略是按结束时间从小到大排序然后依次选择只要当前区间的开始时间晚于或等于上一个选中区间的结束时间就选它。为什么按结束时间排序而不是按开始时间原因很直观结束越早后面留下的空闲时间越长能容纳更多区间如果按开始时间排可能选了一个开始早但结束很晚的区间把后面所有区间都堵死了。类似变体还有“合并区间”和“最少箭矢引爆气球”。合并区间是按开始时间排序然后依次合并重叠部分引爆气球虽然描述不同本质也是射箭点覆盖所有区间的最少数量。这三个题型底层逻辑一样建议放到一起练一次吃透。我见过很多人在贪心题上翻车不是不会写而是没证明贪心策略的正确性就急着写代码结果样例过了隐藏用例挂了。笔试题量有限最好在动笔前花30秒想一个反例如果按当前策略选能不能构造出一个更优的解想不出反例基本就是对的。2.4 数学与数论快速幂与模运算一模的最后一题里有一个子问题需要计算 a^b mod m其中a和b的上限都是10^18这时候C的pow函数完全不能用必须上快速幂。快速幂的思想是把指数b拆成二进制利用幂运算的结合律减少乘法次数。举个例子计算 3^1313的二进制是1101也就是 3^13 3^8 * 3^4 * 3^1。从最低位开始扫描b的二进制位如果当前位是1就乘上当前的底数幂次底数每移动一位就自乘一次。这样只需要O(log b)次乘法。代码框架大致是long long pow_mod(long long a, long long b, long long mod) { long long res 1; a % mod; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }这段代码里最容易出问题的是中间乘积溢出。res * a 和 a * a 都可能在取模之前超过long long的范围。如果mod本身接近10^18这两个乘法会溢出结果就错了。遇到这种情况可以用“快速乘”代替普通乘法也就是把乘法也按二进制的思路拆开边加边取模。在笔试中如果数据范围给到10^18这个细节往往是区分AC和WA的关键。还有一个小技巧当模数是质数时可以用费马小定理先化简指数比如要求 a^(b mod (m-1)) mod m。虽然不是每道题都需要但能让你多一个化简思路。2.5 堆与TopK大数据场景的基础题模考里没有单独考TopK但我在热词整理时发现“堆排序算法”多次出现所以特别想提一句堆排序和TopK是面试笔试里出镜率非常高的基础题。尤其是“从10万个数字中找出最大的K个”用大小为K的小顶堆一遍扫描就能解决。具体做法是先拿前K个数建一个大小为K的小顶堆堆顶是堆中最小的元素。然后遍历剩下的数字只要比堆顶大就弹出堆顶、插入当前数字堆会自动调整。遍历结束后堆中剩下的K个元素就是整个数组中最大的K个。整趟下来复杂度是O(n log K)当K远小于n时非常高效。考场上如果遇到需要自己手写堆的题目要注意堆的下沉和上浮操作。我习惯把堆写成数组下标从1开始这样父子节点的关系就是 i/2 和 2i、2i1。如果你用Java的PriorityQueue注意它默认是小顶堆找最大的K个正好合适C则要自己传greater类型。2.6 二分图匹配与HK算法进阶考点怎么准备热词列表里有“二分图 hk算法”这说明近期不少大厂笔试开始往图论进阶方向出题。匈牙利算法是解决二分图最大匹配的经典算法复杂度O(VE)当节点数较大时容易超时。HK算法Hopcroft-Karp通过每次找多条不相交增广路来加速复杂度降到O(E sqrt(V))适合处理大规模二分图。我在2023一模里没遇到HK但之前在某家暑期实习笔试里遇到过“最小点覆盖”的变体本质就是要求最大匹配。如果你时间充裕建议把匈牙利算法和HK都写一遍模板如果比较赶先掌握匈牙利算法它代码短、适合保底绝大多数笔试都够用。判断一道题是不是二分图匹配有几个常见信号任务是给左侧对象分配右侧对象每个分配有互斥条件求最多能分配多少个或者反过来求最少需要移除多少条边让图变成完美匹配。这类题目描述通常很绕但识别出“二分图”三个字后直接套模板就是送分。3. 笔试过程中的时间分配与做题策略3.1 拿到卷子先做“三分钟热身”我的建议是不管考试时间多紧前3分钟不要急着写代码。先把四道题全部读一遍标记每道题的数据范围和大概考点。这样做有三个好处一是心理上有底知道前面有简单题垫着二是大脑会在后台自动想难题的思路等你做完简单题回头时思路往往会自己冒出来三是避免在最后才发现第四题其实不难但已经没有时间了。读题时要特别注意数据范围。看到n10^5基本就能排除O(n^2)的解法看到需要取模十有八九是快速幂或组合数学看到字符串匹配就要考虑KMP或哈希。数据范围就是题目的“提示”很多人忽略它结果用错误复杂度的算法硬扛。3.2 70分钟的主干时间怎么切如果总时长是90分钟我大概的切法是前20分钟解决签到题和简单模拟30到45分钟集中放大题留出15分钟检查边界情况。模板题比如Dijkstra、快速幂应该做到5到10分钟敲完因为思路是现成的敲代码只是手速问题。最怕遇到的情况是第二道题卡了40分钟。我的止损原则是一道题如果30分钟还没有任何AC进展立刻进入“部分分模式”。ACM模式下即使拿不到满分通过部分用例也能得分。先把暴力解法写上保证拿一部分然后继续下一题。这比死磕一道题导致后面全空要划算得多。记得一模那天我第三题KMP想了很久最后果断写了一个哈希匹配来保底虽然不能覆盖所有数据但至少拿到了30%的分。不要觉得写暴力丢人笔试的本质是得分不是道德表演。3.3 代码模板与本地调试的手感问题牛客的在线判题系统支持无模板编程但强烈建议你提前准备好自己的“代码骨架”。我每次笔试前会花10分钟默写一遍这些模板快读输入、并查集、Dijkstra堆优化、KMP匹配、快速幂、二分查找、二叉树的遍历。不是为了考场上照抄而是为了唤醒手感。平时写算法题时我建议直接用牛客的在线编辑器模拟真实考试环境。我见过不少同学在IDE上写得好好的一到网站自带的代码框就各种不适应自动提示没了、缩进靠手动、调试输出要自己加。这些都是可以通过多次模考来适应的。真正进考场后我习惯先把每个题的输入输出框架写出来跑一次样例确保解析正确再往中间填充算法逻辑。这样可以避免出现“算法对了但输入解析错了”的低级失误因为这种失误在ACM模式下太常见了。4. 失分点排查与常见坑位4.1 常见失分点速查表我把那次一模和后续几次模考踩过的典型问题整理成了一个速查表每次考试前扫一眼很有用失分场景具体原因解决方式KMP匹配漏计数匹配成功后j重置为0没跳过重叠部分匹配成功后执行j next[j]Dijkstra超时没做堆优化或没有跳过过期堆节点用优先队列 dist判断快速幂WA中间乘法溢出结果被截断判断数据范围必要时用快速乘二分死循环mid取值向下取整时更新边界不对记住 l mid 1、r mid 的匹配关系输入解析失败循环读取多组数据时没有退出条件while try/except或读到EOF数组下标越界忽略模式串长度为1的边界写代码前单独跑长度为1的测试这张表里的问题本质都是“平时练习没覆盖到边界情况”。笔试的测试数据不会像力扣那样温柔经常会把空数组、单元素数组、全相同字符这些情况混在里面。建议每次提交前先脑补几个极端输入跑一遍代码。4.2 边界条件与输入输出的细节ACM模式下输入输出是很多人翻车的第一现场。牛客的输入不一定是一次性给完的有些题是多行输入有些是“读一个处理一个”还有些说是多组测试数据却没有明确组数。我吃过最大的亏是“多组数据读取”。刚接触牛客笔试时我习惯性只读一组数据就退出循环结果样例能过提交后却只通过很少的用例。后来养成了“先读后判”的习惯先用 sys.stdin 尝试读取一行如果读到内容就继续处理读不到就结束。C就用 while (cin n) 这种写法天然支持多组输入。输出格式也要注意有时要求输出空格分隔有时要求换行分隔还有的题目要求末尾不能有多余空格。尽量把输出逻辑独立封装成一个函数这样统一处理比较稳妥。4.3 “看起来会做但一直超时”的三种原因超时是笔试里最可惜的失分方式明明是正解却因为常数太大或写法不够干净而被卡掉。我总结出三种最常见的超时原因。第一种是数据结构选型错误。比如有序集合操作明明可以用TreeSet红黑树实现O(log n)的前驱后继查找结果自己写了个链表遍历复杂度直接变成O(n)。处理元素动态插入并频繁查询排名的题目平衡树或跳跃表几乎是唯一解。第二种是重复计算。比如在循环里反复调用substring截取字符串导致每次都复制一遍底层数组整体复杂度被抬高一个量级。遇到这种场景优先考虑用下标范围代替截取。第三种是算法思想正确但实现细节拉垮。比如Dijkstra忘了把边存成邻接表用邻接矩阵存10^5个节点光是初始化就够超时了。笔试前先把每个常用数据结构的空间复杂度算清楚能避免很多这类问题。5. 模考之后的复盘方法论5.1 成绩不是重点错题才是资产模考结束后我第一件事不是看排名而是把四道题全部重写一遍哪怕已经AC的题也重新看一次有没有更优解。因为模考的判题数据是固定的AC不代表你的解法就是最优的可能只是数据没卡你。重新用更优解法写一遍比刷十道新题更有价值。复盘时我习惯做三件事一是记录每道题的考点和错误原因用一句话概括比如“边界判断漏了n1”二是把当天没写出来的题标记为“二刷题”一周后再做一次三是总结这一轮的薄弱模块比如字符串处理薄弱下一周优先刷KMP和AC自动机相关题目。错题本不用做得很精美只要你自己能看懂就行。我用的是一个Markdown文件按考点分类记录考前花半小时翻一遍效果比临时抱佛脚好得多。5.2 简历方向算法粒子群、PID、卡尔曼滤波什么时候需要学热词列表里出现了“粒子群算法原理”“PID算法”“卡尔曼滤波算法”这类内容这里我想多说一句。它们和牛客模考里的算法题不是同一类东西前者更多出现在特定领域的笔试或面试项目深挖中。粒子群算法属于优化算法常用于求解连续或离散的优化问题在运筹、控制、图像分割等领域有应用。嵌入式或自动驾驶岗位的笔试有可能让你解释PID或卡尔曼滤波的原理但通常不会让你手写完整实现更多是问参数含义、适用场景。比如PID的三个参数Kp、Ki、Kd分别影响响应的快速性、稳态误差和超调但实际调试时往往还要考虑积分饱和、微分噪声放大等问题。如果你投的岗位明确写了“自动驾驶”“机器人”“智能控制”这些关键词建议额外看一点信号处理和优化算法的基础刷题之外增加这部分知识储备。但如果投的是通用后端或客户端岗位这些内容的优先级可以往后放重心还是LeetCode和牛客真题上的算法。5.3 模考频率与长期刷题节奏我建议备战国考笔试的同学每两周至少参加一次牛客模考。模考本身不是目的它更像是定时校准自己的“考试状态”。长期只刷题不模考容易陷入“天天刷题但一上考场就紧张”的状态。模考能训练你的时间感知和抗压能力这两点平常自己刷题很难练到。日常刷题节奏上我比较推荐“模块化”方式一周主攻一个专题比如这周图论下周字符串再下周动态规划。专题刷题比随机刷题更容易形成体系也能让你快速发现自己真正薄弱的地方。配合每两周一次的模考基本可以保持一个良好的备考状态。我个人体会最深的一点是模考成绩单上的数字往往比你想象中更能反映真实水平。因为它是限时、陌生环境、完整流程下的表现而不是你在自己舒服的IDE里慢慢调试出来的结果。2023牛客一模之后我把每次模考都当正式考试来对待到了真正笔试时心态和手感都好了很多。如果你也想检验自己的算法笔试水平找个晚上完整抽出90分钟认真做一套牛客模考然后像我一样把每道题都复盘一遍。这个过程可能有点难受但值得。
