这套题我印象挺深2017年牛客网组织的模考四模那场编程题集合当时我在准备校招笔试前后刷过两遍。它不像剑指offer那样按知识点分类而是直接模拟真实笔试环境四道题从易到难排下来正好用来检验自己到底能不能在有限时间内把代码写对、写稳。现在回头看这套题对算法基础、代码实现和考场心态的考察都有代表性哪怕放到今天拿来当练习依然不过时。这篇文章我打算从题目结构、考察方向、完整题解思路到实战排错全部过一遍。不是那种只贴个AC代码就完事的写法我会把每道题拿到手之后的分析过程、为什么这么写、边界条件怎么卡全部拆开讲清楚适合正在准备校招笔试或者想系统刷OJ题的读者。1. 拿到这套题先看全局牛客模考的定位与出题逻辑1.1 模考为什么值得刷和普通OJ题单有什么区别平时刷题大家都在LeetCode或者牛客题库里按标签刷比如今天专刷动态规划明天专刷字符串这种刷法适合学知识点但和真实笔试差距很大。真实笔试是四道题混在一起你事先不知道每道题考什么需要在四十分钟到一小时之内分配时间遇到卡住的地方还得学会跳题。牛客模考四模就是模拟这个场景四道题不在tag标签里等你而是随机混编这恰恰是它最大的训练价值。2017年那场四模题目整体风格偏基础没有特别偏难怪的题但这不代表简单。它考察的是你能不能把“会做的题”拿满分。很多人平时刷题能AC一到模考就各种小错误读入格式没处理好、边界条件漏了、数组开小了、循环条件写错一位。这些恰恰是笔试淘汰人的主要方式。1.2 四道题的整体难度梯度和考点分布我复盘了一下这套题出题结构大致是这样的第一题通常是字符串处理类难度较低属于送分题第二题是模拟题考察代码复现能力第三题开始上强度会用到排序、查找或者简单数据结构第四题是算法题动态规划或者贪心属于拉分题。这个难度曲线和大厂校招笔试基本一致前面的题求稳后面的题求突破。更重要的是这套题当时的判题环境是牛客OJ输入输出用标准输入输出不支持图形界面。这意味着所有题都要自己处理读入、自己组织输出格式和现在很多笔试平台一样。如果平时只会在LeetCode里补全函数没练过自己写main函数、自己读标准输入这套题会给你不小的冲击。2. 做题前的通用准备输入输出和复杂度预算2.1 标准输入的几种格式写不对直接0分说实话我见过太多人在这种问题上栽跟头。牛客OJ的输入格式一般有几种情况有明确的多组数据、单组数据、先给一个T表示测试用例组数。2017年这套模考题大部分题目是单组输入但其中有一道题就是典型的“第一行一个整数第二行一个数组”的格式还有一道题涉及多行输入。写Python的话我建议直接用sys.stdin.read或者sys.stdin.readline配合split不要用input()一行一行读因为遇到多行数据时容易读漏。写C的话用cin要加ios::sync_with_stdio(false)和cin.tie(0)否则数据量稍大一点就容易超时。还有一种常见坑是输出格式。牛客OJ对行末空格和多余空行通常判错有些题目要求输出空格分隔且行末无空格有些要求每个结果占一行。我当时的习惯是先把结果存进一个vector或者list统一用join拼好再输出避免最后一刻因为多打一个空格挂掉。2.2 写代码之前先估一下复杂度别等超时了再改四道题里前两道基本是O(n)或者O(n log n)能解决的后两道要稍微注意数据范围。真实笔试不像平时练习提交机会有限超时一次会扣心态分。我现在的习惯是拿到题先看一眼数据范围n小于等于多少如果答案是int还是long long需不需要用long long。这个习惯就是当年刷牛客模考练出来的。特别是模拟题很多人的第一反应是老老实实按题意跑流程。如果n只有100、1000那没问题但如果n是10的5次方O(n^2)的模拟基本必挂。所以做题前30秒一定是看数据范围然后倒推复杂度上限再决定是暴力还是上算法。3. 四道题的完整拆解与实现过程3.1 字符串处理题考察基本功是否扎实这类题在整个笔试里是最不应该丢分的。四模里的第一道字符串题核心操作是统计字符出现次数并按次数排序类似“给定一个字符串输出出现次数最多的前k个字符”的变体。拿到题第一件事不是写代码而是先确认题目要求是按ASCII排序还是按出现次数排序是只输出一个字符还是输出多个大小写是否算不同的字符这些细节直接决定了代码逻辑。思路其实很朴素先用哈希表统计每个字符的频率然后按频率从大到小排序频率相同的按字典序排。要是用Python直接用collections.Counter一行就能统计完然后用sorted排序注意key要写成lambda x: (-x[1], x[0])这种形式先按频率降序再按字符升序。用C的话unordered_map统计后拷贝到vectorpairchar,int再sort自定义比较函数。这里有个很重要的考点是输入里可能有空格比如输入一个英文句子。如果用cin str来读空格会被截断只能读到第一个单词。正确做法是用getline(cin, str)读取整行。我当年就因为这个卡了一会儿后来养成习惯凡是字符串题先判断有没有空格再决定用什么方式读入。代码示例Python版本import sys from collections import Counter def solve(): s sys.stdin.readline().strip() if not s: return cnt Counter(s) # 先按频率降序再按字符升序 items sorted(cnt.items(), keylambda x: (-x[1], x[0])) # 输出格式要看题目要求这里假设输出所有字符和次数 parts [f{ch} {num} for ch, num in items] sys.stdout.write(\n.join(parts)) if __name__ __main__: solve()C版本#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); string s; getline(cin, s); unordered_mapchar, int cnt; for (char c : s) cnt[c]; vectorpairchar, int v(cnt.begin(), cnt.end()); sort(v.begin(), v.end(), [](const auto a, const auto b) { if (a.second ! b.second) return a.second b.second; return a.first b.first; }); for (auto p : v) cout p.first p.second \n; return 0; }一道看起来简单的题实际上已经把哈希表、排序、lambda自定义排序、字符串读入方式全考了一遍。这就是模考题的特点不会考你特别冷门的算法但会在基础操作上做文章。3.2 模拟题把题意翻译成代码的过程模拟题是这套卷子里最容易写长、最考验耐心的题。四模里的第二道模拟题本质上是一个约瑟夫环变种类似n个人围一圈每次数到k的人出列问出列顺序。很多人看到约瑟夫环第一反应是用循环链表模拟但这个思路在笔试里不好写、容易错而且如果n和k都很大时间复杂度也压不住。实际上这类题的经典做法是用数组标记循环遍历下标或者用数学递推直接推最后幸存者。不过题目问的是出列顺序的话数学递推就不行了只能用模拟。我当时用的就是数组标记法开一个vector 长度n初始都是true表示还在队伍里。然后循环n次每次从当前下标开始数k步遇到已经被标记为false的位置就跳过数到第k个true的位置把它标成false记录下来。这里有一个关键细节k可能大于当前剩余人数所以每次都要对剩余人数取模不然会多绕很多圈甚至死循环。还有一种更简洁的做法是用队列模拟。把1到n全部入队然后每次循环k-1次每次把队首元素弹出来放到队尾第k次操作把队首元素弹出并记录出列顺序。这个写法代码量更少思路也更直观我后来更喜欢用这种方式。Python队列模拟代码from collections import deque import sys def solve(): n, k map(int, sys.stdin.readline().split()) q deque(range(1, n 1)) res [] while q: for _ in range(k - 1): q.append(q.popleft()) res.append(q.popleft()) print( .join(map(str, res))) if __name__ __main__: solve()这里有个很容易错的地方当k等于1的时候for循环一次都不执行直接弹队首。这个代码逻辑上是对的但如果后面不小心写成了range(k)而不是range(k-1)那就会多转一轮结果全错。我当年就吃过这个亏后来总结了一个经验模拟题的代码写完以后先拿最简单的小数据手动跑一遍比如n3,k1和n5,k2确认答案跟手算一致再提交。3.3 排序和查找结合题考察数据组织能力第三题开始上一点强度了。这类题通常是给一堆区间或者给一堆查询让你快速判断某个点落在哪个区间或者找满足条件的最接近值。牛客模考里那道题我记得是区间匹配和点查询的变体给你几个分隔点把数轴分成若干段再给你若干要查的数问每个数落在哪一段。这题朴素做法是每来一个数就遍历所有分隔点O(n*m)如果两者都是10的5次方量级直接超时。正解是二分查找先对分隔点排序然后对每个查询数用lower_bound找第一个大于等于它的位置再根据这个位置判断它属于哪一段。C直接用STL的lower_boundPython用bisect模块。Python代码示例import bisect import sys def solve(): data sys.stdin.read().split() idx 0 n int(data[idx]); idx 1 points [] for _ in range(n): points.append(int(data[idx])); idx 1 points.sort() q int(data[idx]); idx 1 res [] for _ in range(q): x int(data[idx]); idx 1 pos bisect.bisect_left(points, x) # 这里具体怎么判断结果取决于题目定义可能是 pos 也可能是 pos-1 res.append(str(pos)) print(\n.join(res)) if __name__ __main__: solve()这道题其实点了我一下让我认识到二分查找在笔试中的地位。很多看似要遍历的题只要数据结构是有序的就能用二分把O(n)降到O(log n)。这个复杂度差距在10的5次方数据量下是几秒和几十毫秒的区别。从那以后我凡是看到“有序数组”和“查找”两个关键词同时出现第一反应就是二分。还有个细节值得说二分查找的边界条件特别容易写错left和right的更新方式、while循环里有没有等于号都会直接影响答案。用Python的bisect其实是最稳的但如果你用C手写二分一定要在提交前用极端数据测一下比如查询数小于最小值、大于最大值、恰好等于某个分隔点这三种情况。这三种情况几乎覆盖了所有边界错误。3.4 动态规划入门题典型的跳台阶变体第四题基本是动态规划了。2017年四模里这道题是一个跳台阶变体大意是一只青蛙一次可以跳1级或者2级台阶问跳上n级台阶一共有多少种跳法。如果再加一点难度可能变成“一次可以跳1级、2级或3级”甚至“某些台阶不能落脚”。这种题拿到手以后不要一上来就列状态转移方程先把问题定义清楚。设dp[i]表示跳到第i级台阶的方法数那么因为最后一步要么是从i-1跳1级上来要么是从i-2跳2级上来所以dp[i] dp[i-1] dp[i-2]。这个递推式就是斐波那契数列初始条件dp[0]1dp[1]1。边界条件非常关键。n等于0的时候你站原地不动也算一种方法n等于1的时候只有跳1级一种方法。如果题目说n大于等于1那就不用处理dp[0]但万一题目给的范围包含0漏掉dp[0]就会直接错。我的建议是写代码时把dp数组长度开到n1并且显式初始化dp[0]1。Python代码import sys def solve(): n int(sys.stdin.readline().strip()) if n 0: print(0) return dp [0] * (n 1) dp[0] 1 dp[1] 1 for i in range(2, n 1): dp[i] dp[i - 1] dp[i - 2] print(dp[n]) if __name__ __main__: solve()但这里有个性能陷阱如果n很大比如到10的6次方dp数组O(n)的空间没问题但如果到10的9次方那就不能开数组了得用滚动变量只用两个变量不断迭代。这时候代码变成if n 0: print(0) return a, b 1, 1 for _ in range(2, n 1): a, b b, a b print(b)滚动变量的本质是状态压缩因为dp[i]只依赖前两个状态不需要把整个数组存下来。这个优化思路在后面做背包问题、路径问题的时候会经常用到尽早养成习惯很重要。有的版本还会要求结果取模比如模1000000007。这种时候一定要在每次加法之后取模不要等到最后再取不然中间结果溢出就全错了。4. 实战中容易翻车的几个细节我的排查经验4.1 本地跑得好好的提交就报错问题多半出在输入这是最让人崩溃的情况。我当年遇到过一次本地IDE里跑样例输出完全正确一模一样的代码提交到牛客OJ就答案错误后来才发现问题出在输入上。我的代码用了sys.stdin.readline()只读了一行但输入数据是多组后面几组直接没读到。排查思路很简单先看题目里的输入描述到底是单组还是多组。多组输入在Python里最好的做法是sys.stdin.read()把全部数据读进来再统一split或者用while True的readline循环读到EOF跳出。C里用while(cin x)处理多组输入。这是笔试题和LeetCode最大的区别之一LeetCode是函数式输入输入早就被框架处理好了而牛客这套模考不是。4.2 数组下标越界不是运行时才发现的很多人以为数组越界只会在运行时报错但在OJ环境里越界访问有时不会直接崩溃而是读到一块脏内存导致答案错误甚至出现完全无法理解的输出。我刷模考题时遇到一个诡异的情况本地反复跑都是对的提交就错最后开了AddressSanitizer才定位到是访问了dp[-1]。这类问题最有效的预防方案只有两个一是写代码时把数组长度开够比如需要访问第n个位置就开到n1二是对所有下标做防御性判断。尤其是二分查找和动态规划这类题目边界处的下标很容易差一个。我现在的习惯是写完之后花30秒检查所有返回数组索引的位置问自己一句这个值会不会等于-1或者等于length。4.3 超时不一定是因为算法差可能是输入输出太慢有一道题我第一版代码用的是Python的print在循环里一行一行输出结果超时。换成先存到列表里最后用join一次性输出之后时间直接降到1秒以内。print本身不是不能用但循环里频繁调用IO开销会累积。C这边同理cout在默认情况下和C的stdio同步速度很慢。加上那两行魔法代码ios::sync_with_stdio(false); cin.tie(0);速度能提升一个量级。这个细节在笔试中太重要了我甚至养成了条件反射写C必加这两行写Python必考虑用sys.stdout.write。4.4 常见问题速查表症状可能原因排查方法本地正确OJ报错输入输出格式不一致确认题干输入描述检查是否有空格、换行、多组数据答案错误差1或差2边界条件漏处理用最小数据、最大数据、极端数据分别测试运行超时算法复杂度过高或IO太慢看数据范围估算复杂度优化输出方式内存超限数组开太大或递归过深换用滚动变量把递归改成迭代结果溢出中间结果超int范围换成long long或者对结果取模4.5 笔试过程中的时间分配建议这套题整体难度适中但限时内做完和慢慢磨完是两个概念。我当时用的策略是前两道简单题争取20分钟内拿下中间两道每题给20到25分钟最后一题如果卡住超过15分钟就先放弃回头检查前面的题有没有低级错误。这个策略源于一次惨痛教训有次模考我在第四题上死磕了半小时结果第一题字符串读入漏了空格白白丢了分。从那以后我就记住了笔试不是做科研目标是在有限时间内拿最多的分不是证明自己所有题都能做出来。稳扎稳打、先易后难永远是对的。回过头来看2017年牛客四模这套题难度放在现在依然不过时。它不是那种难到让你怀疑人生的题也不是那种简单到刷了没感觉的题而是一套能真正检验基础功的卷子。如果你现在正在准备校招笔试拿这套题做一次全真模拟掐着时间做一遍然后对照自己的错误去补知识点效果会比闷头刷几百道标签题好得多。最后分享一个小技巧刷完这套题之后不要急着做下一套把每道题的错因、卡点、优化思路总结成几段话。我的经验是输出一次总结比刷三套新题的价值都大。笔试考的根本不是你做过多少题而是你能不能在下一次遇到相似问题时不再踩同一个坑。