写在开头2018年的牛客一模编程题现在翻出来看依然很有嚼头。那会儿牛客的模考系统还不像现在这么完善题目的风格也更“直给”——不绕弯子不玩花活就是老老实实考基本功字符串处理、动态规划、边界条件、数学递推。但也正因为如此那套题特别适合用来练笔试的基本盘。最近有人问起刷题路线我翻出当年的答题记录和赛后复盘笔记挑了几道有代表性的题目重新做了一遍顺便把思路和踩过的坑整理出来。这篇文章不是官方题解是我自己作为一个普通参赛者的解题复盘题目描述按记忆做了归纳简化核心考点和思路是完整的希望能给正在准备机试和校招笔试的朋友一点参考。1. 2018年牛客一模到底在考什么四个隐藏的考察维度很多人做模考卷只关心“这道题怎么解”但复盘的价值在于看懂“这套题为什么这样出”。2018年一模A卷的题目覆盖范围其实不广没有偏题怪题但每一道题背后都藏着一个笔试中最常被扣分的点。第一类考察是输入输出处理。听着简单实际翻车率极高。牛客的判题系统和力扣不一样不给你封装好的函数所有数据都要自己从标准输入读、自己解析、自己格式化输出。当年一模第一题就是典型的“字符串排序”组合数据不是规规矩矩一行一个而是混着逗号、空格和换行。很多人在本地IDE里跑得好好的一提交就是0分问题几乎都出在没处理干净换行符、没考虑空输入、或者输出格式多了个空格。第二类是状态转移的建模能力。动态规划题从来不是考你背模板而是考你能不能从题目描述里抽象出状态、找到转移方程。我记得卷子里有一道“股票买卖含冷冻期”的变体题和经典的股票问题不一样的是它额外限制了“卖出后第二天不能买入”。这一个小小的改动就让很多只会套模板的同学直接懵了——因为他们习惯的dp[i]表示“第i天结束后的最大利润”根本没法表达“冷冻期”这个约束。这类题拼的不是代码量是建模的细致程度。第三类是边界条件的敏感性。笔试里最容易丢分的不是算法不会而是“就差一点点”。数组越界、指针空引用、循环变量差一、整数溢出这些错误在本地小数据测试时根本看不出来一旦数据规模上来就原形毕露。模考卷子里的模拟题和双指针题简直就是为这个考察维度量身定做的。第四类是数学推导和找规律的能力。有些题看起来像是搜索题或者模拟题但数据范围一上来暴力解法直接超时。这时候需要你冷静下来从数学角度找递推关系或者公式。2018年一模里有一道环形涂色计数题就是这个套路。后面我会专门讲它。所以这篇文章的复盘主线我就按照这四个维度来拆。每一类我都挑一道当年错得最多或者最有代表性的题目完整还原思路推导、代码实现和踩坑过程。2. 字符串处理与栈括号匹配升级版真正的高手都在处理细节2.1 题面还原不仅匹配还要计算最大嵌套深度先看卷子里的第一道经典题。它的题面大致是这样给定一个只包含(、)、[、]、{、}六种字符的字符串长度不超过100000。判断括号序列是否合法如果合法输出最大嵌套深度如果不合法输出-1。很多人看到这题就笑了——括号匹配栈嘛大一课程设计都写过。但事实上这题的通过率并不高。为什么因为大部分人只答对了“是否合法”却在“最大嵌套深度”上栽了跟头。最大嵌套深度的定义是什么就是匹配过程中栈深度的最大值。比如({})这个序列处理(时栈深1处理{时栈深2处理}时栈深回到1处理)时栈深回到0所以最大深度是2。这个定义本身不难但问题在于很多人用“左括号计数”来代替“栈深度”一遇到右括号就减一导致在非法序列上算出错误的最大深度。2.2 正确解法边匹配边记录深度正确的做法依然是用栈但在入栈和出栈的过程中同步维护一个当前深度计数器每入栈一个左括号就加1每匹配一个右括号就减1全局最大值在每次入栈后更新。def max_depth(s: str) - int: stack [] depth 0 max_depth 0 pair {): (, ]: [, }: {} left set(([{) for ch in s: if ch in left: stack.append(ch) depth 1 max_depth max(max_depth, depth) else: if not stack or stack[-1] ! pair[ch]: return -1 stack.pop() depth - 1 return max_depth if not stack else -1这段代码的核心逻辑其实只有12行但背后有一个容易忽略的细节右括号匹配时弹出的左括号必须和当前右括号的配对类型一致。很多人写这道题时只用一个计数器遇到左括号加一遇到右括号减一最后检查计数器是否为0——这种做法在只有一种括号的题目里没问题但一旦括号种类变成三种计数器就没法判断([)]这种交叉非法的情况了。2.3 我当年踩过的两个坑栈残留和空字符串第一个坑是字符串匹配完之后没有检查栈是否为空。((()))这种完全匹配的没问题但((())这种左括号多出来的情况如果你只凭“中途没有匹配失败”就判定合法就会漏掉这种非法输入。我当年就是在这个用例上挂的因为本地测试用的都是合法序列压根没想到多左括号的情况。第二个坑是空字符串。理论上空字符串是合法的括号序列最大嵌套深度为0。但有些同学在判断条件里写成了if not s: return -1直接判非法。严格来说判题系统的测试用例里大概率有空串这个细节值得留意。这类字符串栈的题目在校招笔试里出现频率极高而且近年来的趋势是和表达式求值、HTML标签解析、JSON格式校验等场景结合。但不管外层包装怎么变核心永远是用栈保存需要“回溯匹配”的上下文用额外的计数器维护当前嵌套状态。把这一道题吃透等于把一整类题都吃透了。3. 动态规划题不是背模板而是找到状态转移的起点3.1 题面还原带冷冻期的股票买卖一模卷子里最有区分度的一道题是一道动态规划。题面原型是股票买卖但加了一个约束给定一个数组 pricesprices[i] 表示第 i 天的股票价格。你最多只能持有一股股票可以在任意一天买入在任意一天卖出但卖出后的第二天不能买入冷冻期1天。求能获得的最大利润。经典股票题大家都熟dp[i] max(dp[i-1], prices[i] - min_price)一次遍历搞定。但加了冷冻期之后这个简单公式直接失效。因为你第i天卖出的操作会影响第i1天的买入状态之间出现了“跨天依赖”。3.2 状态机建模三个状态比两个状态更清晰处理这种约束我的经验是别急着写转移方程先画状态机。不画图光在脑子里想很容易乱。这道题里每天结束后我们只关心三种状态状态A当天结束后不持有股票且不处于冷冻期也就是说今天是“空仓且可以买入”的状态。状态B当天结束后不持有股票但处于冷冻期即今天刚卖出。状态C当天结束后持有股票。为什么要把“不持有股票”拆成A和B两个状态因为冷冻期限制了下一步的买入动作如果笼统地用一个“不持有”状态表示转移时没法区分“能买”和“不能买”。这就是状态设计的关键。有了这三个状态转移方程就水到渠成了dpA[i] max(dpA[i-1], dpB[i-1])。今天结束后能买入说明今天没卖出也没买入那么昨天要么状态A要么状态B。dpB[i] dpC[i-1] prices[i]。今天卖出了股票卖出后进入冷冻期所以昨天一定持有股票状态C加上今天的卖出收益。dpC[i] max(dpC[i-1], dpA[i-1] - prices[i])。今天继续持有要么是昨天就持有状态C要么是今天从可买入状态状态A买入。初始化第一天dpA[0] 0没买dpB[0] 0不可能卖出初始为0但实际意义不大dpC[0] -prices[0]买入股票收益为负。最终答案是max(dpA[n-1], dpB[n-1])因为最后一天没必要持有股票。def max_profit_with_cooldown(prices): n len(prices) if n 2: return 0 dpA [0] * n # 空仓且可买入 dpB [0] * n # 空仓且冷冻期 dpC [0] * n # 持仓 dpA[0] 0 dpB[0] 0 dpC[0] -prices[0] for i in range(1, n): dpA[i] max(dpA[i-1], dpB[i-1]) dpB[i] dpC[i-1] prices[i] dpC[i] max(dpC[i-1], dpA[i-1] - prices[i]) return max(dpA[n-1], dpB[n-1])这段代码可以继续做空间优化用三个变量滚动更新把空间复杂度从O(n)降到O(1)。笔试里一般不会因为空间复杂度砍你的分但写出来也能体现基本功。优化后的代码如下def max_profit_with_cooldown_optimized(prices): n len(prices) if n 2: return 0 a, b, c 0, 0, -prices[0] for i in range(1, n): new_a max(a, b) new_b c prices[i] new_c max(c, a - prices[i]) a, b, c new_a, new_b, new_c return max(a, b)3.3 从这道题延伸出去的通用方法论这道题给我的启发比题本身大。很多人学动态规划喜欢背模板见到“股票买卖”就套“持有/不持有”两状态见到“背包”就套“选/不选”两状态。但笔试题目稍微加一点约束模板就失效了。我的建议是遇到约束条件先问自己三个问题题目里的“限制”会影响决策的哪些方面冷冻期影响的是买入动作所以买入和卖出必须用不同状态区分。有哪些信息是决策时必须知道的卖出后第二天不能买意味着“前一天是否卖过”这个信息必须被状态记录下来。所有可能的状态组合是否覆盖了全部情况不漏不重转移方程才完整。这三个问题问完状态设计基本就出来了。动态规划的核心不是代码是状态定义和转移逻辑。代码实现只是最后一步反而最不重要。4. 双指针与模拟题边界条件才是真正的得分分水岭4.1 题面还原有序数组原地去重并返回新长度2018年一模里还有一道看起来特别“人畜无害”的题给定一个已排序的数组 nums请在原地删除重复出现的元素使每个元素只出现一次并返回删除后数组的新长度。不要使用额外的数组空间必须原地修改输入数组空间复杂度要求O(1)。双指针慢指针指向“下一个不重复元素应该存放的位置”快指针遍历全数组。当快指针指向的元素和慢指针指向的元素不同就把它复制到慢指针的下一个位置。标准答案也就十几行def remove_duplicates(nums): if not nums: return 0 i 0 # 慢指针指向最后一个不重复元素 for j in range(1, len(nums)): if nums[j] ! nums[i]: i 1 nums[i] nums[j] return i 14.2 为什么这么简单的题通过率反而低这道题的正确率低得很离谱。我复盘了一下当年的排名数据发现很多人的代码思路完全正确但得分就是不全。问题出在哪里几乎全出在“返回值”和“原地修改”的配合上。牛客的判题逻辑是它会读取你返回的新长度 m然后检查 nums 数组的前 m 个元素是否满足“不重复且有序”的条件。如果你的代码返回了长度但没有实际修改数组或者修改后前 m 个元素里还有重复——那就会判错。我当年犯过的错误是用了一个count变量记录不重复元素个数但忘记了把不重复的元素往前搬。最后返回的长度是对的数组还是原样直接0分。这属于典型的“思路对了一半落地全错”。4.3 极端用例和进阶思考这道题还有几个边界情况值得注意空数组返回0且不能越界访问 nums[0]。数组只有一个元素直接返回1不需要进入循环。全部元素都相同循环走完i 始终为0返回1数组不变正确。全部元素都不同每个元素都会被搬到对应位置i 最终指向最后一个索引返回 len(nums)正确。学有余力的同学可以再想想一个进阶版本如果每个元素可以保留两个副本比如[1,1,1,2,2,3]变成[1,1,2,2,3]这个双指针还怎么写其实只改一个判断条件把nums[j] ! nums[i]改成nums[j] ! nums[i-1]因为最多保留两个副本的话当前位置元素只需要和前两个位置比较即可。改动极小但对“双指针维护区间”的理解就更深一层。模拟题和双指针题考察的不是算法天赋而是代码的严谨性。边界条件、返回值约定、数组是否真正被修改这些都是笔试判题的关键。写代码的时候多问自己一句“如果数据是空的怎么办”“如果数据全一样怎么办”往往就能避开很多坑。5. 数学递推与计数打表找规律是笔试里的合法战术5.1 题面还原环形涂色问题A卷压轴的是一道看起来像搜索、实际上是数学的题一个圆环被分成 n 等份n 3用 m 种颜色m 2给每一份涂色要求相邻两份颜色不同。问有多少种不同的涂色方案。结果可能很大对 1000000007 取模。n 的范围有多大我记得数据范围写的是 n 10^9。看到这个范围就知道暴力搜索或者状态压缩DP根本没戏——O(n) 都过不去必须推导公式或者找到矩阵快速幂的递推。5.2 从画图开始找到递推关系我第一次做这道题时第一反应是排列组合。但想了半天也不知道怎么直接用组合数表示因为圆环的首尾相连让“相邻”关系形成了一个环而不是一条线。画几个小 n 的情况找规律。n3 时第一块有 m 种选法第二块有 m-1 种第三块需要同时和第一块、第二块不同所以是 m-2 种。总数就是 m * (m-1) * (m-2)。n4 时就开始烧脑了。直接枚举太痛苦换个建模方式把第一个位置固定为颜色1因为圆环旋转对称固定第一块可以减少一种变量然后考虑剩下 n-1 块的涂色方案要求最后一块和第一块颜色不同。设 f[n] 表示长度为 n 的圆环首尾相邻的涂色方案数。考虑第一块颜色固定后第二块可以选 m-1 种第三块开始每一块都只要求和前一块不同所以是 m-1 种选择。如果按“线性链”来算从第2块到第n块一共 n-1 块每块都是 m-1 种选法但这样算到最后可能出现第n块和第一块颜色相同的情况。怎么办呢分两类讨论第n块和第一块颜色相同或者第n块和第一块颜色不同。如果第n块和第一块颜色相同那么第n-1块必须和第n块不同即和第一块不同。这种情况下前n-1块其实构成了一个长度为n-1的合法圆环涂色方案数是 f[n-1]。但这里注意我们讨论的前提是“第n块和第一块相同”而圆环涂色方案数 f[n-1] 里包含了各种情况需要细化。这个过程推到后面会绕晕。我后来用了更经典的递推公式设 a[n] 表示 n 等份圆环的涂色方案数。考虑第一块涂色有 m 种选择接下来每一块都和前一块不同同时最后一块还不能和第一块相同。定义 f[n] 为“从第二块开始线性涂色每一块和前一块不同”的方案数再减去最后一块和第一块相同的非法情况。最后一块和第一块相同的情况其实等价于把第一块和最后一块“合并”变成一个长度为 n-1 的圆环涂色方案数是 a[n-1]。于是得到关键递推a[n] m * (m-1)^(n-1) - a[n-1]这个递推的直观理解是总方案数按线性方式各块只和前一块不同减去最后一块和第一块冲突的方案数。而冲突的方案数和“把最后一块合并进第一块后形成的小一号圆环”正好一一对应。边界条件a[2] m * (m-1)两块相邻需要不同颜色。验证一下n3 时a[3] m * (m-1)^2 - a[2] m(m-1)^2 - m(m-1) m(m-1)(m-2)。和前面枚举的结果一致公式是对的。5.3 数据范围摆在那里快速幂和递推优化有了递推公式还不够。n 最大到 10^9O(n) 递推依然会超时。观察递推式a[n] m * (m-1)^(n-1) - a[n-1]这是一个一阶非齐次递推。好在这个递推可以展开成通项公式。手动推一下或者直接采用“递推 快速幂”的思路如果只求单个 a[n]可以解通项如果需要多次查询可以用矩阵快速幂。更直接的方法是拆开递推。设 x m-1则a[n] m * x^(n-1) - a[n-1]展开一层a[n] m * x^(n-1) - [m * x^(n-2) - a[n-2]] m * x^(n-1) - m * x^(n-2) a[n-2]继续展开交替出现加减号。最终通项公式是a[n] (x-1) * x^(n-1) (x-1) * (-1)^n把 x m-1 代回去a[n] (m-2) * (m-1)^(n-1) (m-2) * (-1)^n等等这个通项公式看起来有点奇怪我重新推导一遍确保没错。设 x m-1d m-2 x-1。递推式 a[n] m * x^(n-1) - a[n-1]且 a[2] m * x。假设通项是 a[n] A * x^(n-1) B * (-1)^n。代入递推式验证A * x^(n-1) B * (-1)^n m * x^(n-1) - [A * x^(n-2) B * (-1)^(n-1)]右边 m * x^(n-1) - A * x^(n-2) - B * (-1)^(n-1)因为 (-1)^n -(-1)^(n-1)所以左边 A * x^(n-1) - B * (-1)^(n-1)对比左右两边 x^(n-1) 的系数A m - A/x即 A(1 1/x) mA m * x / (x1)。但 x1 m所以 A x。咦A m*x/m x。对比 (-1)^(n-1) 的系数-B -B这个恒等式没有给出B的值。说明只有 x^(n-1) 项系数不够需要再用边界条件确定B。用 a[2] m * x x * (x1)代入通项x * x^(1) B * 1 x^2 B x(x1) x^2 x所以 B x m-1。于是通项公式为a[n] (m-1) * (m-1)^(n-1) (m-1) * (-1)^n (m-1) * [(m-1)^(n-1) (-1)^n]等等这个结果和前面写的 (m-2) 不一样需要用 n3 验证一下。m3n3 时a[3] 2 * [2^2 (-1)^3] 2 * (4 - 1) 6。但按枚举第一块有3种第二块2种第三块1种必须同时和前两块不同前两块颜色不同所以第三块只能选第三种色总数为 3*2*16。验证正确。用另一组数据m4n3a[3] 4*3*2 24。套公式3 * [3^2 (-1)^3] 3 * (9-1) 24。正确。这个通项公式很好用因为只需要计算一次快速幂时间复杂度 O(log n)。对大质数取模使用费马小定理或者直接用 Python 的 pow(x, n, mod) 就行。MOD 1000000007 def count_ways(n, m): if n 1: return m if n 2: return m * (m - 1) % MOD x m - 1 # 通项公式a[n] x * [x^(n-1) (-1)^n] term pow(x, n - 1, MOD) if n % 2 0: term (term 1) % MOD else: term (term - 1) % MOD return x % MOD * term % MOD注意 m 的范围如果很大要先把 m 和 x 取模再参与计算。另外 n1 时圆环退化成“一块”公式不适用要单独处理。5.4 这类题的经验实在推不出来了打表找规律通项公式的推导过程看起来很顺利但说实话比赛现场能直接想到通项的人并不多。我当年其实也没推出来用的方法是“暴力打表找规律”。先把 n3,4,5,6 的答案用暴力枚举算出来m 固定为一个小数比如 4然后观察数列60, 252, 1020, 4092... 这是什么可以发现每一项差不多是前一天的四倍。更精确地a[4] 4^4 - 4 252a[5] 4^5 4 1020a[6] 4^6 - 4 4092。于是猜测通项是a[n] (m-1)^n (m-1) * (-1)^n的类似形式。有了猜测再回带验证会快很多。打表找规律不是投机取巧它对数学类题目是合法的战术。它帮你建立对数据的直觉然后再用这种直觉反推公式。笔试不是数学竞赛只要你能在时限内解出正确答案任何手段都值得用。6. 从一模看校招笔试做题顺序、取舍和自测方法题目拆解完了再说点实践层面的东西。2018年一模A卷一共大概五六道编程题考试时间两个小时。我的经验是绝对不要按照题目顺序从头做到尾。先把所有题都快速扫一遍从易到难排序。怎么判断难易看数据范围。数据范围越小通常解法越简单n 10^9 的基本是数学题或者O(log n)算法n 1000 的可以考虑 O(n^2) 的DPn 10^5 的大概率是O(n log n)或O(n)的解法。这个判断几乎百试百灵。先做简单题有两个好处一是稳定心态确保基础分拿到手二是为难题留出足够的思考时间。我见过太多人死磕第一道难题结果后面三道简单题都没时间写最后惨败。笔试不是竞赛目标是“拿分最大化”不是“证明我能做难题”。做题过程中的自测也很重要。很多人写完代码本地跑一遍示例输入通过就交了。但示例输入往往是最普通的用例覆盖不到边界情况。我的习惯是每道题都自己构造三组测试用例一组是空输入或最小输入一组是最大数据范围一组是极端重复或极端乱序的情况。把这三个用例跑通了再提交基本不会有太大的意外。模考还有一个容易被忽略的价值它是标准输入输出的训练场。平时在力扣上刷题函数签名和返回值都给你定好了你根本不用管“怎么读进去”“怎么输出”。但真实笔试不是这样。我见过身边不少人算法能力很强但第一次统考连input().split()和sys.stdin.readline().strip().split()的区别都没搞明白第一题就浪费了二十分钟。这类基本功必须靠模考来练。7. 从一模到实战刷题路线上的三个具体建议最后聊点更长远的。一模结束之后大家最关心的往往是“接下来怎么刷题”。根据当年的复盘我给出三条具体的建议思路。第一条建立错题笔记但不要只记题目和解法。错题笔记的重点是记录“为什么错”。是因为边界条件没考虑到是因为状态定义不清是因为对数据范围不敏感还是因为某个API不熟悉把原因分类统计你会发现自己的短板高度集中。比如我当年统计下来80%的扣分都集中在“边界条件”和“输入输出格式”上——这是很典型的半路出家选手的问题。知道了短板才有针对性地练。第二条同一类题集中攻克而不是按难度梯度刷。很多人喜欢按题号顺序刷题一天刷几道简单题感觉很有成就感但遇到中等题还是不会。我的建议是按“题型”刷连续一周只做字符串栈的题从简单到中等再做困难做到闭着眼都能写出匹配逻辑为止。然后换下一类双指针、滑动窗口、动态规划、图论搜索……每一种题型集中训练两周左右效果比漫无目的地刷三个月好得多。第三条定期参加模拟考试严格计时。刷题和考试是两种完全不同的能力。刷题时你可以慢慢想做不出来就翻题解但考试要求你在有限时间内独立完成还要保证正确率。这个能力必须靠模考来培养。哪怕每周只参加一次模考坚持两个月你的时间分配、心态管理、代码调试速度都会有质的提升。我从2018年一模里拿到的最大收获其实不是某道题的解法而是一个清晰的认知笔试考的从来不是“你会不会某个算法”而是“你在有限时间内能不能稳定地拿到所有该拿的分”。这两个目标之间的距离就是通过一次次模考、复盘、针对性训练来缩短的。希望这篇复盘对你也有参考价值。