2020年牛客模考一模那套编程题我到现在还有印象。那是我第一次完整在OJ上按校招笔试流程走卡在输入输出上浪费了快二十分钟最后一道DP题只写了半截就去交了。后来复盘那套题发现出错点其实都很典型不是算法不会而是不知道牛客题该怎么读、怎么答。这篇帖子我就把当时踩过的坑和后来整理出的通用解法按题型拆开讲结合Python实现给准备走校招笔试的朋友做个参考。1. 牛客一模的实际情况考什么、怎么考1.1 ACM模式才是最大门槛很多第一次刷牛客的人都有同一个错觉觉得LeetCode刷得熟笔试就没问题。实际上牛客模考用的是ACM模式也就是你要自己处理输入输出函数入口要自己写。举个最简单的例子LeetCode上你只需要实现一个方法输入参数已经给你处理好了而牛客一模的题往往是给一段原始输入文本多组样例、以特定字符分隔你得自己从标准输入里读出来、解析出来再按指定格式打印结果。所以备考第一步不是背算法而是练熟那套输入输出模板。Python环境一般用sys.stdin.read()一次把整个数据流读进来再按行或按空格拆要么用input()配合while True循环读。我在一模前已经刷了不少题但第一次上牛客的OJ还是翻车原因是读入一行数据后没有转成int就往下算本地测试没报错提交后直接出Runtime Error。这类问题只有多练多踩才能记住光看解析没用。1.2 一模的难度分布与时间分配牛客模考是模拟真实互联网公司校招笔试的题目数量和难度都是按校招标准来的。以2020年一模为例整体题量在四到五道之间难度分为三档前一两道是模拟题和字符串处理属于送分题占总分百分之三十左右中间一道是排序、双指针、二分这类经典数据结构题属于拉分题最后一道往往是动态规划或贪心用来区分高分选手的。我当时犯的错误是前面小题做得太慢总觉得要一次写完美才提交结果最后一道题只剩十五分钟。正确策略应该是一开始先把所有题都扫一遍先做最有把握的哪怕前两道每题只拿了部分分也好过最后一道题完全空着。牛客判分是按通过用例数算的部分通过也有分所以优先抢分而不是追求全对。这套策略后来我一直用实测比闷头按顺序做多拿不少分。2. 高频题型一字符串与模拟题的通用解法2.1 这一类题具体能考什么一模前半段几乎必考字符串题。2020年那套题里就有密码强度检查、字符统计排序这类操作看似简单却很容易丢分。比如密码强度检查题目会规定密码长度下限、必须包含的字符类型种类让你输出强、中、弱等级。只要把条件一条条理清楚基本就是遍历字符加布尔标记的事没有算法难度但非常考验细心程度。字符串题还有一个常见变体是字符统计排序给一段只有小写字母的文本让你按出现次数从高到低输出次数相同的按字典序。这种题看似简单但在Python里需要注意sort的稳定性以及key函数的写法比如arr.sort(keylambda x: (-cnt[x], x))就同时实现了次数降序和字典序升序。很多人会忘记字典序这个次级条件直接按次数排完就交结果错掉好几个用例。2.2 模拟类题目的通式化写法模拟题的核心原则是先拆条件再写框架最后填细节。不要一上来就写几十行代码很容易漏条件。我习惯先把题目里所有判定规则用注释列出来再逐条翻译成代码。比如密码检查def check_pwd(pwd: str) - str: if len(pwd) 8: return weak has_lower any(c.islower() for c in pwd) has_upper any(c.isupper() for c in pwd) has_digit any(c.isdigit() for c in pwd) has_symbol any(not c.isalnum() for c in pwd) level sum([has_lower, has_upper, has_digit, has_symbol]) if level 3: return strong if level 2: return medium return weak这个写法有几个细节值得说。第一any和isalpha、isalnum、isdigit这些内置方法组合起来比手动遍历再写if判断要简洁得多也不容易写错。第二判断符号时用not c.isalnum()而不是c in !#$%^*...因为题目可能允许的符号范围不是固定的用取反逻辑最稳。第三返回值必须和题目指定的大小写完全一致牛客OJ对字符串比对是区分大小写的有个同学就是输出Strong没通过调了半天发现是多了一个大写。2.3 踩过的坑字符编码和多余空格字符串题里最容易忽略的是编码和格式问题。有一年牛客模考出现过输入一行带BOM头的文本Python直接input()读出来第一个字符是\ufeff导致字符统计结果整体错位。这种问题本地跑不出来只有提交后会报错。解决办法是读入后先做一次strip()如果有异常字符再用codecs处理。另外输出格式尽量用\n.join(results)拼接不要在循环里print一遍既慢又容易多出一个空行。一模的字符串题我吃过一次亏题目要求统计后输出每行一个字符我在最后一行后面也打了换行本地上看没问题但OJ的用例比对把多出的换行判定为答案错误。从那以后我养成了习惯循环里只往列表里存结果最后统一输出。3. 高频题型二数组、排序与双指针的实战招法3.1 双指针不是玄学是暴力法的优化版如果一模中间有一道数组题八成可以用排序或双指针解。这类题考察的核心是你能不能在O(n)或O(n log n)的时间复杂度内解决问题。比如最常见的合并区间题目给一堆[start, end]的区间要求把重叠部分合并。我第一次做这题时用的是两层循环暴力合并结果用例一多就超时。后来才意识到必须先排序再线性扫描。合并区间的标准写法很短def merge(intervals): intervals.sort(keylambda x: x[0]) res [] for start, end in intervals: if not res or start res[-1][1]: res.append([start, end]) else: res[-1][1] max(res[-1][1], end) return res逻辑不复杂按左端点排序后如果当前区间的起点比结果列表最后一个区间的终点大说明不重叠直接加入否则说明有交集合并时更新终点为两者较大值。关键就在这个max很多人写成res[-1][1] end遇到[1, 10]和[2, 3]这种用例就漏数据。牛客一模就有一道改动版合并区间题很多人挂在没取最大值上。3.2 排序和去重的小技巧数组题里还有一种考法是排序加去重或者按某种自定义规则排序。这类题真正考点是能不能熟练写出稳定的排序方式。Python的sort方法默认是稳定的这在某些场景下是优势比如按分数排序后保持原先后顺序。但如果你需要多关键字排序一定记得用tuple做key且注意正负号控制升降序。曾经有一道一模题要求按数字出现频率升序排列数组频率相同按数字大小降序排列。我当时的写法是arr.sort(keylambda x: (cnt[x], -x))一提交就通过了。这个写法的核心在于元组作为排序key时先比较第一个元素相同再比较第二个。如果想频率升序就原样写cnt[x]想要数字降序就写成-x。这个习惯值得养成比用cmp_to_key写自定义比较函数要方便得多。3.3 二分查找的边界是重灾区二分查找几乎是校招笔试必考一模也不例外。常见的题目包括在有序数组里找某个数、找插入位置、找左右边界。很多人背了模板但还是错原因是不理解mid和left、right的更新逻辑。记住一个口诀左闭右开区间用while left rightright midleft mid 1全闭区间用while left rightleft mid 1或right mid - 1。两者别混用。一模有一道题要求找第一个大于等于目标值的下标。我一开始写成了普通二分没有处理“找不到”的情况结果当目标值比数组中所有元素都大时返回了数组长度题目预期是返回-1直接WA。所以回答二分题时一定要在开写前想清楚两个问题目标值不存在时该返回什么区间定义到底是什么这两个问题想明白二分题就不会错。4. 高频题型三数学题与位运算的速解思路4.1 数学题的常见考法校招笔试很少考纯数学理论但很爱考欧几里得算法、质数判断、进制转换、大数取模这类组合题。2020牛客一模最后一道题之前有一道求最大公因数的小题直接递归两行代码就出来了def gcd(a, b): return a if b 0 else gcd(b, a % b)关键是这题的输入是字符串形式的大整数直接int()会报内存错误或者超时。Python的大整数在某些OJ环境里虽然能处理但长度达到上万位时转成整数再辗转相除会非常慢。正确做法是用辗转相除法配合字符串做模运算或者直接使用Python内置的math.gcd但前提是先把超大数字符串逐段处理。我那次模拟考就没考虑整数长度直接用int()读取结果一提交就报MemoryError。后来学乖了凡是看到“数字特别长”的题目先想有没有可能不需要把整个数字变成整数如果一定要取模就按位取模一次一位地累乘累加这样时间复杂度和内存占用都只和字符串长度相关可控得多。4.2 位运算的几个实用场景位运算在笔试里出现频率不高但一旦出现往往就是高分题。最常见的是统计二进制中1的个数、判断一个数是不是2的幂、找只出现一次的数字。这些题在Python里用bin(x).count(1)就能完成统计但更好的办法是用x (x - 1)循环清零最低位的1这样可以避免生成字符串性能更高。判断2的幂只需一行return n 0 and (n (n - 1)) 0。原理很简单如果n是2的幂那么它的二进制表示中只有一个1n - 1会把那个1变成0把后面的所有0变成1两者按位与结果必为0。这类位运算技巧背诵成本低收益高建议在考前集中刷一遍。一模还有一个找数组中唯一出现一次数字的题用异或最方便ans 0 for x in nums: ans ^ x因为相同的两个数异或会抵消成0任何数和0异或还是它本身最后剩下的就是答案。这个思路在现场比用字典统计快得多而且代码极短。我总结的经验是看到“数组中只有一个数出现奇数次其他都出现偶数次”这类描述第一时间就该想到异或而不是哈希表。5. 高频题型四动态规划与贪心的识别与突破5.1 怎么一眼判断这题该用动态规划一模压轴题大概率是动态规划或贪心。对普通选手来说最难的不是不会写状态转移方程而是不知道什么时候该往DP方向想。我的判断标准是三个关键词最值、方案数、可行性。题目出现“最大子段和”“最长上升子序列”“最少步数”“有多少种方式”这样的字眼基本就是动态规划。拿最长上升子序列举例这是一模常客。朴素做法是dp[i]表示以第i个数结尾的最长上升子序列长度转移时遍历前面所有j如果nums[j] nums[i]就用dp[j] 1更新。时间复杂度O(n^2)。如果数据范围是10的4次方以上这个写法会超时需要换成贪心加二分import bisect def length_of_lis(nums): tails [] for x in nums: i bisect.bisect_left(tails, x) if i len(tails): tails.append(x) else: tails[i] x return len(tails)这段代码里tails[i]表示长度为i 1的上升子序列的最小末尾元素。重点在于bisect_left和bisect_right的选择会直接影响是否允许相等元素参与序列。如果题目要求严格上升必须用bisect_left如果允许相等改成bisect_right。一模原题要求严格上升所以用bisect_left没错但很多人不看题目直接套模板遇到“非递减”就错。5.2 一道经典DP的逐步推导最大子数组和是另一道高频DP题描述是给一个数组找连续子数组的最大和。这题最经典的解法是cur max(x, cur x)每一步都决策是延续前面的子数组还是从当前位置重新开始。def max_subarray_sum(nums): cur best nums[0] for x in nums[1:]: cur max(x, cur x) best max(best, cur) return best为什么这么写是对的关键在于状态定义cur以当前元素结尾的子数组的最大和要么是当前元素自己要么是上一个cur加上当前元素。如果之前是负数加进来只会拖累不如从头开始。这个“要么自己单干要么加入团队”的类比我当时就是靠这个想明白的。best滚动记录全局最大值防止答案出现在数组中间而不是末尾。这题最容易犯的错是初始值设置成0。如果数组全是负数正确结果是最大的那个负数但初始化为0会导致输出0。把cur和best都设成nums[0]从第二个元素开始遍历就可以避免这个坑。一模就有人在这里丢了分因为样例恰好给了正数自测时没暴露负数全为负的情况。5.3 贪心和动态规划的区别很多同学分不清贪心与DP其实一句话贪心是每一步只做局部最优选择后续不被前面的决策限制DP是当前状态由前面多个状态转移而来需要保存中间结果。举一模出现过的经典例子跳台阶最少步数问题。如果每个位置能跳的最大步数固定求最少跳几次能到终点这个可以用贪心每次尽量选能跳最远的但如果是问“走到每个台阶有多少种方式”就必须用DP因为中间状态是累积的。判断方法很简单如果题目问“最大、最小、最长、最短”优先想贪心如果贪心验证后发现有反例就转DP。验证反例的办法是拿一小撮数据手动走一遍看看局部最优会不会导致全局变差。一模现场时间紧不建议从头证明贪心正确性但至少要用一两个边缘用例自测一下。我在现场就吃过亏想当然用了贪心解一道题提交后发现第3个用例就挂了改成DP才过。6. 考场常见报错、超时与边界问题排查6.1 本地能过就不代表能AC牛客OJ和本地跑有三点明显差异运行内存受限、时间限制更严格、输入输出有严格格式要求。本地跑通但OJ报错八成的可能是数组越界或递归深度超限。Python默认递归深度在1000左右如果DFS递归树比较深recursionError直接让程序挂掉。处理办法要么改用栈模拟要么在顶部加sys.setrecursionlimit(1000000)。一模有一道图遍历题我本地数据量小没崩溃提交后直接Runtime Error最后追到就是这一行的问题。另一个高频报错是IndexError发生在边界条件没判断的时候。尤其是二分、双指针类题循环里访问nums[i 1]或nums[left]前先确认下标没越界。老手写代码会自动带上l r或i n - 1这样的约束条件新手最容易忽略这一块扣分非常可惜。6.2 超时优化的三个优先手段如果题目提示运行超时优先检查三件事。第一是不是用了双层循环处理了n超过10的4次方的数据是的话想想能不能双指针或哈希化单层。第二是不是在循环里反复调用耗时函数比如字符串拼接或count改成计数数组或列表收集再join。第三是不是频繁使用input()读多行数据改成整块读入再按行处理会快很多。以下是一段常见的输入优化模板import sys data sys.stdin.read().strip().split() if not data: sys.exit() n int(data[0])这套模板的好处是无论输入在哪些行全部拆成列表后按位置取即可。对多组数据的题还可以把data当作一个队列用指针依次取。我自己一模后养成了习惯所有OI式题都用这个模板不再一行行input()速度和稳定性都上来了。6.3 边界条件自查清单我每次提交前都会再过一遍这道题的边界情况。列一个简版清单参考价值很高输入长度为1时能否正确处理数组为空时题目是否有定义代码是否报错数组中所有元素都相同结果是什么数字极大会不会溢出输出浮点数时小数位是否符合格式是否需要处理多组输入读完所有行后程序是否正常退出检查的时候不要只看题目样例要自己构造一两个反例。比如最大子数组和那题构造全是负数的数组合并区间题构造[1, 4]和[2, 3]这种完全包含的情况。很多题不是算法不会而是样例刚好没覆盖到你的logical bug一埋一个准。7. 我个人的考场复盘与技术扩展建议一模之后我最大的改变是开始整理“题型-解法”对照表。每当新做一道题就去归类它属于模拟、字符串、排序、双指针、二分、数学、DP还是贪心然后在标签下补充新的细节。这样做的效果很明显再看到新题时不会从零开始想而是按类别直接套用已有模板。后来几年我还尝试用Python参加各类编程等级考试和算法训练营发现牛客一模打下的基础在Python编码上很通用。字符串处理、位运算、动态规划这些核心模块不管换什么平台解题思路都是一样的。差别只在输入输出和环境配置而那些恰恰是练出来的不是看出来的。建议大家考前一晚把各自习惯的输入模板、排序模板、DP模板抄一遍第二天上考场手感会顺很多。最后分享一个小技巧牛客模考结束后系统会给你一份复盘报告里面可以看到每个测试点通过情况别只盯着总分一定要看是哪个用例挂了。按我的经验多半是边界条件问题而不是思路整体错误。把每次模拟考错的边界条件加进自己的自查清单里下一次一模你就会发现错误正在肉眼可见地减少。