如果你正在准备校招或者已经过了校招季正在准备跳槽那你大概率被“牛客”这两个字支配过。牛客模考这东西说白了就是模拟大厂笔试的一套完整流程限时、在线判题、看不到实时排名交卷之后给你一个通过率的百分比。我当年刷这套题的时候一道题写错排序规则愣是卡了四十分钟那种想砸键盘的感觉现在想起来还特别真实。【2018】牛客模考一模编程题集合B是牛客网在2018年春季招聘季推出的第一轮模拟考的三套卷之一。一模的题目不是随手从题库里捞几道题塞进去而是按照当年各厂笔试题的命题风格、难度曲线、考点分布去设计的。三套卷里B卷的位置很微妙A卷偏基础语法C卷压轴题扎堆B卷则处在中间偏上的位置最适合拿来当完整的自测卷用。无论你是刚开始刷题的小白还是刷了几个月LeetCode但没实际限时做过题的人这套卷都值得认真做一遍——它考的不只是你会不会写代码而是你在“限时陌生环境在线评测”的压力下能不能把自己的真实水平稳定输出出来。1. 一模B卷到底在考什么整体设计与思路拆解1.1 三套卷的难度定位B卷为什么最适合自测我先说一下当年一模三套卷的定位。A卷的目标是通过率大概在六成左右题目以语法题、简单模拟、字符串基础操作为主适合刚学完语言、准备首次参加笔试的人用来找感觉C卷的目标通过率大概只有两成上下线段树、贪心、复杂动态规划都是常客适合已经刷了大量题、想冲击大厂核心岗位的人去挑战B卷夹在中间目标通过率大概在三成五到四成五之间考点覆盖的是笔试中最高频的几类问题字符串处理、排序思想、基础动态规划。这也就是说B卷不会让你在题目阅读上花太多时间但每道题都需要你真正想明白再动手。我用一个比较直观的说法如果A卷是在考你“会不会用语言”B卷是在考你“能不能在笔试现场用最短时间把问题转化成代码”C卷则是在考你“对高级算法的熟练度和临场推导能力”。绝大多数人的校招目标岗位落到笔试环节差不多就是B卷这个难度。所以这套卷的参考价值远不止“一套模拟题”它基本是那几年大厂笔试的缩影。1.2 一套模拟卷覆盖了哪些核心考点拿B卷的编程题来说常见的出题方向其实是可以总结的。字符串拼接、排序变体、数组内求最值、背包类动态规划这四个方向在当年的笔试里出现频率非常高。字符串处理考的是你对底层字典序规则的理解排序变体考的是你能不能打破“直接sort一下就行”的惯性思维数组求最值表面上考算法实际上考的是时间复杂度的权衡背包类动态规划则是笔试里的“定海神针”几乎每家公司的笔试题都绕不开它。除此之外这套卷还隐性地考了两个能力。第一个是输入输出处理牛客的判题系统采用的是标准输入输出不会帮你写好读入和输出所有数据都得你自己解析这个环节就能筛掉一批人第二个是边界条件处理空数组、重复元素、极端数值范围这些用例不会出现在题目描述里但评测机里一定有。能把这种隐性考点纳入统筹的模拟卷才是真正值得刷的模考。1.3 建议的做题顺序与时间分配我自己做题的时候习惯先花三到五分钟把所有题目通读一遍把每道题的预估难度标一下。B卷这种结构通常是一道简单题、一道中等偏难题、一道基础DP做题顺序建议从简单题开始把能拿的分先落袋再啃中等题最后做DP题。如果一道题二十到三十分钟还没有明确思路就先跳过把后面能拿的分拿到回头再补。这套思路在牛客真实的笔试里非常管用因为很多笔试不是按点给分而是按通过的测试用例比例算分你做了一半的题也有部分分数。死磕一道题导致后面全空是最亏的。时间分配上我建议用整块的一个半小时来模拟前五分钟读题和定策略前四十分钟做掉前两题中间四十分钟做第三题最后留十分钟检查边界和读入输出格式。如果中间卡住了先输出样例看看结果排除低级错误再继续。这套时间策略我后来实际笔试时也一直沿用很稳。2. 牛客OJ的裁判规则读题前先读懂判题系统2.1 输入输出是笔试的第一道题很多第一次用牛客做笔试的人代码逻辑明明没问题提交却一直报错后来发现是卡在输入输出上。牛客使用的是标准输入输出也就是通过标准输入流读取数据通过标准输出流打印结果。它和力扣这种“函数式答卷”最大的区别就是所有数据格式、读取顺序、输出格式都要你自己处理。评测机拿到你的输出之后是逐字符和标准答案比对的多一个空格、多一个换行、多打一行调试信息都会判错。所以做题的第一步不是写算法而是先确认输入格式。比如题目说第一行是一个整数n接下来n行每行一个字符串那你就需要一个能完整读入这些数据的模板。我用Python比较多给出一个最常用的读入模板import sys def main(): data sys.stdin.read().split() if not data: return # data 是一个列表已经按空白字符切好 # 手动从 data 中按顺序取数 pass if __name__ __main__: main()这里用sys.stdin.read().split()比一行一行input()稍微快一些尤其在读大量数据时优势明显。用.split()会自动把空格、换行、Tab都切掉也不需要手动处理换行符。需要注意如果题目里的字符串可能包含空格比如地名、句子就不能无脑用split()得按行读取这一点要读题时想清楚。2.2 语言版本与编译环境要提前摸清2018年前后牛客在线评测对Python的支持已经比较成熟了但很多考场同时提供Python2和Python3默认版本可能不一样。现在牛客基本都以Python3为主流大家直接选Python3就行。但如果你当年刷这套B卷或者现在用的还是旧缓存页面一定要确认自己写的代码在当前Python版本下能跑。最典型的就是print语句Python2里print ok能运行Python3会直接报语法错误。C/C用户需要注意编译器版本和STL的可用性牛客多数情况下C环境是支持C11的unordered_map、auto这些语法可以放心用。Java用户则需要把类名写成Main否则评测机会报“找不到主类”。这些细节看上去不起眼但在真实笔试现场任何一个编译错误都会让你心态崩掉。我的建议是正式做题前先在牛客的练习环境里提交一道最基础的AB题目验证自己选的语言环境是否正常顺手把输入输出模板跑通能省去后面很多麻烦。2.3 多组测试用例与评测机制牛客的笔试编程题通常会有很多组测试用例评测机对你的代码会跑多组输入。这意味着代码里不能写“只处理一组数据就结束”的逻辑。有些题面会明确说明“输入包含多组测试用例”这时你的读入模板就不能只读一行而是要循环读到没有数据为止。多组数据处理的常用模板如下import sys def solve(): data sys.stdin.read().split() # 使用指针或迭代器依次读取 i 0 while i len(data): n int(data[i]) i 1 # 处理每组数据 if i len(data): break if __name__ __main__: solve()另外要知道牛客的判题规则里有“部分通过”的概念。如果你的代码只过了60%的测试用例页面会显示“通过率60%”不会直接给你0分。所以在笔试时哪怕你只能写出暴力解法也一定要交上去暴力至少能拿一部分分空着才是真的0分。这也是我认为模考比刷零散题目更有价值的原因之一它能帮你提前摸清这套评分机制不至于正式笔试时手忙脚乱。3. 真题逐题拆解三道题的完整题解与代码实现当年B卷的编程题题型大致可以归为三类。我把三道典型题按原卷的题面风格复现出来每一道都配上完整的输入输出、思路推导和代码实现大家边看边跟着写效果最好。3.1 字符串拼接直接sort一定会错的题题面描述大致是这样给定n个由小写字母组成的字符串要求将它们按某个顺序首尾连接成一个字符串使得最终得到的字符串字典序最小。求这个最小字典序字符串。输入描述第一行一个整数n表示字符串数量接下来n行每行一个字符串。输出描述一行拼接后的最小字典序字符串。样例输入3 b ba bc样例输出babbc这道题最容易踩的坑就是直接对所有字符串按字典序排序然后拼接输出。看起来很有道理因为字典序最小的字符串自然应该放在前面。但这是错的。反例就是样例里的b和bab的字典序比ba小如果按普通排序b排在ba前面拼接结果是bba但ba b babbab的字典序比bba小所以正确的顺序应该是ba在前。正确的比较规则是两个字符串a和b如果ab ba那么a就应该排在b前面。这个规则的本质是在两个字符串的局部顺序影响全局结果时不能孤立的比较单个字符串的字典序而是要比拼接后的结果。为什么这个规则成立因为任意一个合法的最终排列如果存在相邻两个字符串的顺序违反了这个规则那么交换这两个相邻字符串的位置整个结果的字典序一定会变得更小。反复交换直到所有相邻位置都满足规则得到的排列就是全局最优。这个思路在算法上叫“基于交换的贪心证明”是字符串排序类问题的核心。代码实现时Python3里可以用functools.cmp_to_key把自定义比较函数转换成排序的keyimport sys from functools import cmp_to_key def compare(a, b): if a b b a: return -1 if a b b a: return 1 return 0 def main(): data sys.stdin.read().split() if not data: return n int(data[0]) strs data[1:1 n] strs.sort(keycmp_to_key(compare)) sys.stdout.write(.join(strs)) if __name__ __main__: main()时间复杂度方面排序过程最多比较O(n log n)次每次比较拼接后的字符串长度是O(L1 L2)所以整体复杂度是O(n log n * L)其中L是字符串的平均长度。对笔试数据范围来说完全够用。空间复杂度是O(n)主要是存储输入字符串。这道题的经验在于遇到“把若干个元素排成某个顺序使得结果最优”的题先想一想局部交换能否优化结果如果相邻元素顺序错误会导致整个结果变差那往往就是自定义排序规则解决了。3.2 最大相邻差值为什么不能直接排序第二道题也是一个经典中的经典给定一个长度为n的数组要求求出这个数组排序后相邻两个数之间差值的最大值。题目还加了一个条件算法的时间复杂度要求为O(n)。输入描述第一行一个整数n第二行n个整数。输出描述一个整数表示排序后相邻两数的最大差值。样例输入5 7 1 3 2 6样例输出3排序后的数组是[1, 2, 3, 6, 7]相邻差值分别是1、1、3、1最大差值是3。如果你第一反应是“先把数组排个序然后遍历一遍求差值”说明你的思路方向是对的但没满足题目要求的复杂度。常规排序O(n log n)数据范围一大就会超时。这题的正确解法是用“桶”的思想把排序的复杂度降到O(n)。核心思路是这样的先找到数组的最小值min_val和最大值max_val。如果最大值等于最小值说明所有数都一样答案直接是0。然后我们把min_val到max_val这个区间平均分成n个桶每个桶的宽度是(max_val - min_val) / (n - 1)。把n个数放进n个桶之后第0个桶和第n-1个桶一定分别包含最小值和最大值中间至少存在一个空桶。关键结论是最大差值不可能来自同一个桶内的两个数因为同一个桶内的数间距一定小于桶宽最大差值只可能来自相邻两个非空桶之间也就是前一个桶的最大值和后一个桶的最小值的差。每个桶里我们只需要保存这个桶内元素的最小值和最大值其他信息都不需要。然后从左往右扫一遍所有非空桶计算相邻非空桶之间前桶最大值与后桶最小值的差值取最大值即可。这个过程的复杂度是遍历一遍数组O(n)再扫一遍桶O(n)总时间复杂度O(n)空间复杂度O(n)。具体实现时要注意一个细节桶宽要避免浮点数计算否则会有精度问题。我习惯用整数运算来处理代码里这样写import sys def max_gap(nums): n len(nums) if n 2: return 0 min_val min(nums) max_val max(nums) if min_val max_val: return 0 bucket_size max(1, (max_val - min_val) // (n - 1)) bucket_num (max_val - min_val) // bucket_size 1 bucket_min [None] * bucket_num bucket_max [None] * bucket_num for num in nums: idx (num - min_val) // bucket_size if bucket_min[idx] is None or num bucket_min[idx]: bucket_min[idx] num if bucket_max[idx] is None or num bucket_max[idx]: bucket_max[idx] num prev bucket_max[0] ans 0 for i in range(1, bucket_num): if bucket_min[i] is None: continue gap bucket_min[i] - prev if gap ans: ans gap prev bucket_max[i] return ans def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) nums list(map(int, data[1:1 n])) sys.stdout.write(str(max_gap(nums))) if __name__ __main__: main()为什么最大差值不会出现在同一个桶内因为每个桶的宽度是严格小于等于全局平均间隔的而n个元素分布在n个桶里同一个桶内的任意两个元素差值一定小于桶宽。如果答案出现在桶内那它一定小于某个相邻非空桶之间的间隔所以不可能是最大值。这个证明可能有些抽象但属于“先记住结论用几次就理解了”的典型内容。实际笔试时就算你记不住证明只要按这个模板写也能拿到满分。3.3 购物券背包基础动态规划定海神针第三题是一个背包类动态规划题我按当年的常见题面风格整理如下小明有一张价值m元的购物券商场里有n件商品每件商品有一个价格p和一个重要度v小明最多使用购物券购买一次每件商品只能买一件。他想在购物券可支付的范围内让自己买到的商品总价值最大。其中单件商品的价值定义为“价格×重要度”。求最大总价值。输入描述第一行两个整数n和m分别表示商品数量和购物券总额接下来n行每行两个整数p和v。输出描述一个整数表示最大总价值。样例输入4 10 3 2 4 3 5 4 6 5样例输出42这里解释一下样例第2件商品价格4、重要度3价值为12第4件商品价格6、重要度5价值为30两件总价10元总价值42。这个组合是全局最优的。这类题的经典解法是01背包动态规划。定义dp[j]表示购物券已花费不超过j元时能获得的最大总价值。初始化时所有dp[j]都为0。然后依次处理每件商品对于当前商品如果价格是p价值是value我们就从后往前更新所有dp[j]dp[j] max(dp[j], dp[j - p] value)这里为什么要从后往前更新因为每件商品只能用一次。如果从前往后更新dp[j - p]可能已经在同一轮里被当前商品更新过就会出现“同一件商品被买两次”的效果。从后往前更新dp[j - p]还是上一轮的值就能保证每件商品最多被选一次。这是背包问题里特别容易翻车的细节我之前就栽过。代码实现如下import sys def main(): data sys.stdin.read().split() if not data: return it iter(data) n int(next(it)) m int(next(it)) dp [0] * (m 1) for _ in range(n): p int(next(it)) v int(next(it)) value p * v for j in range(m, p - 1, -1): if dp[j - p] value dp[j]: dp[j] dp[j - p] value sys.stdout.write(str(dp[m])) if __name__ __main__: main()时间复杂度是O(n * m)空间复杂度是O(m)。如果商品数量大m作为购物券总额也不会大到离谱这个复杂度在牛客的评测机上是能过的。如果你遇到的是“每件商品能买多件”的变体那就是完全背包内层循环改成从前往后就行如果数量有限比如每件商品最多k件那就先把k件展开成单独的商品再用01背包处理这一套扩展对笔试来说已经覆盖大部分场景。这道题背后的价值在于动态规划的核心不是背模板而是理解状态定义和转移方向。dp[j]从“不超过j元”到“不一定刚好花完”这个状态设计可以灵活迁移到很多现实场景里。我当时做完这道题顺手把牛客上其他几道基础背包题都刷了一遍性价比很高。4. 高频失误与排查技巧实录4.1 一套题做下来最容易翻车的五个点第一字符串拼接题直接sort。这是很多人第一次做这道题时的通病以为是纯字典序排序结果几个特殊用例直接打回原形。记住一点拼接类求最优的题目优先考虑自定义排序规则而不是直接套用默认排序。第二桶排序题里用了浮点数计算。桶宽如果用浮点数会出现桶内元素落错桶、空桶判断错误、边界溢出这些问题。我用整数运算重构一次之后所有边界用例都干净了。实测下来整数除法加max(1, ...)的处理方式最稳妥。第三背包题内层循环方向写反。01背包从后往前完全背包从前往后这个口诀一定要刻在脑子里。我见过不少同学状态转移方程写得完全正确就是循环方向反了样例能过但隐藏用例全错。第四读入时没有处理多组数据。有些题目数据不止一组代码写得再好只处理一组就退出等于白写。用sys.stdin.read()配合迭代器或索引是最稳的通用做法。第五调试输出忘删除。写题时用print打印中间结果很正常但交卷前忘了删输出结果里就会混入调试信息评测机判定答案错误。这种失误在真实笔试中特别冤。我现在的习惯是提交前用快捷键全选代码搜一遍print(确认没有多余输出。4.2 在线笔试应该怎么调试牛客笔试环境通常没有调试器你不能打断点也不能单步执行。这时候最有效的调试手段就是“对拍”这个概念很多人听说过但没落实到习惯里。写一个暴力解法再写一个自以为高效的正确解法用随机生成的小规模数据同时跑这两份代码对比结果是否一致。不一致就缩小数据范围定位是哪组数据出错。比如字符串拼接那道题暴力解法就是全排列所有可能性取字典序最小的结果。高效解法是自定义排序。对拍时随机生成3到5个小写字母组成的字符串跑上千组如果全部一致基本可以确信高效解法的正确性。这个过程看着麻烦实际上能省下大量在评测机上试错的时间。我刷B卷的时候第二道桶排序题就是靠对拍发现了一个边界错误当数组长度为2且两个元素差距为1时桶数量计算会出问题。这个用例极其隐蔽但用对拍一秒就能暴露。对拍的Python脚本我给出一个简化的模板思路是生成随机输入分别调用两份代码逻辑比对输出import random def brute(nums): # 暴力解法正确性优先 pass def solution(nums): # 高效解法 pass for _ in range(10000): n random.randint(1, 8) nums [random.randint(1, 100) for _ in range(n)] if brute(nums) ! solution(nums): print(发现反例:, nums) break笔试时不需要把对拍脚本写到提交代码里它就是你在本地编辑器里的一个验证工具。熟练之后写一个对拍脚本只需要几分钟但能帮你提前拦截掉绝大多数逻辑错误。4.3 常见问题速查表我把刷这套题时最容易遇到的问题整理成了一张表方便你做到一半卡住时快速对照现象常见原因排查思路提交后显示编译错误Python选错版本或Java类名不是Main确认评测环境版本检查类名和语法输出比答案多一行调试print没删或多打印了换行全局搜索print删掉所有调试输出样例能过但通过率0%输入格式没按多组数据处理检查读入代码用sys.stdin.read()重写字符串排序结果不对直接按字典序排序没有用abba规则改用cmp_to_key自定义比较桶排序答案偏小用了浮点数计算桶宽边界元素落错桶改用整数除法计算桶宽背包答案偏大内层循环方向写反同一商品被多次选择01背包必须从后往前遍历j这张表既是刷题避坑指南也可以当成正式笔试前的检查清单。我后来每次参加线上笔试之前都会把这张表过一遍尤其是“调试print没删”和“类名不是Main”这两条几乎每次都能拦住一个低级失误。4.4 关于时间和心态的一些经验刷模考题和刷LeetCode有一个很大的区别模考题是限时的但LeetCode没有时间压力你可以慢慢想一天。很多人在牛客上做题不是算法不会而是时间压力下读题读歪了、边界没考虑全、低级错误反复犯。B这套卷的限时练习恰恰能锻炼这种“在时间压力下保持代码稳定性”的能力。我自己做题的时候给自己定了一个很简单的规矩每道题先花两分钟把输入输出格式和数据范围看清楚再花两分钟想清楚算法剩下的时间全部用来实现和检查。数据范围特别重要如果n是10^5级别基本排除了O(n^2)算法如果n是10^3级别暴力就可能过。很多题不用把最优算法想出来先判断数据范围能不能让暴力通过能过就直接写暴力省下来的时间用来检查其他题。有一道题我当时用暴力方法过了而同一个考场很多人在纠结最优解法最后反而超时没写完。这说明笔试现场的“最优解”不一定是最好的选择在限定时间内“能拿到分的解法”才是好解法。模考的价值就是用低成本的试错帮你建立起这种考场直觉。做B卷的时候多体验几次“暴力过题”和“卡在最优解导致没写出来”的对比正式笔试时你会感谢这段经历。