2017牛客一模编程题复盘：从数学规律到机考实战的算法思维

翻出2017年牛客模考一模的编程题集合时我第一反应不是题目本身而是那年的备战状态一边啃剑指offer一边在牛客上掐表做模拟卷生怕机考翻车。牛客一模这套题难度放在当年不算低现在回头看却很有意思——它考的东西大多不是“模板”而是数学思维和边界处理。哪怕到了2025年再以老题新做的视角去拆它依然能榨出不少东西。这篇文章不是官方题解而是我作为一个当年被这套题锤过的人重新复盘后的完整记录。每道题我会先讲清楚题目在问什么再拆解题思路给出能直接跑的代码最后把当年容易踩的坑单独拎出来说。适合正在准备校招机考、想补算法基础、或者单纯想找几道经典题练手的读者。1. 2017年牛客一模一份“思维大于模板”的卷子1.1 当年的备考生态为什么模拟卷比刷单题更有用2017年正是校招机考开始普及的年份。那个时候“刷题”还没有现在这么体系化大家更多是在牛客、LeetCode上零散地刷很少有人系统地模拟过真实机考环境。牛客的模拟考试功能一出很多人第一次意识到原来机考不是“会做就行”还要在有限时间内完成读题、编码、调试、提交。一模这套题就是在那个背景下出现的。它的意义不在于题目本身有多难而在于它第一次逼着大家把刷题状态切换成“考试状态”。我记得当时做完模拟卷最大的收获不是哪道题会了而是发现自己读题太慢、边界条件老漏、一紧张连循环都写不利索。这些能力靠平时一道一道刷题是练不出来的。到现在我也会跟学弟学妹说如果你从来没掐表做过一套完整机考题那你对“自己准备好了”这件事的判断大概率是错的。牛客一模恰好提供了这样一个参照系这是它时至今日仍有价值的第一个原因。1.2 整体观感好几道题都在考“想明白再动手”我印象里这套卷子一共五道编程题分别是数根、变态跳台阶、字符串归一化、彩色瓷砖、星际密码。单看题目类型几乎没有冷门算法全是基础题。但妙就妙在每道题都有两种写法一种是一眼暴力、代码长、边界多另一种是想清楚规律后几行代码就能过。这种出题思路其实是故意在筛选“能不能快速看穿问题本质”的人。比如数根这题你要是真去循环求和也能过但遇到超大数就会慌可你要是知道数根和模9之间的关系那就是一道口算题。再比如变态跳台阶很多人条件反射写DP但推两行就能发现答案是 (2^{n-1})直接位运算解决。所以我一直觉得2017年牛客一模的出题人很懂校招。校招机考从来不指望你掌握多冷门的算法它考的是你在有限时间内能不能把常见问题用最干净的方式解出来。这套卷子里的每一道题都在反复敲打这件事。2. 数根与变态跳台阶两道送分题里的数学规律2.1 数根模拟不是不行但模9才是正解先看数根。题目描述很直白给定一个正整数反复计算各位数字之和直到结果变成一位数这个一位数就是原数的“数根”。比如9876先算987630再算303所以数根是3。最诚实的解法就是模拟def digit_root(num): while num 10: num sum(int(ch) for ch in str(num)) return num这代码没毛病也能过。但如果输入是一个特别长的数字甚至是以字符串形式给出的超大整数模拟起来就会有点心虚。更优雅的做法是直接用数学规律一个数的数根等于它对9取模的结果只有一种特殊情况就是当数根为9时取模结果是0。def digit_root(num): if num 0: return 0 return 9 if num % 9 0 else num % 9为什么是这个规律因为 (10^k \equiv 1 \pmod 9)也就是说任何一个整数和它的各位数字之和在模9意义下是相等的。反复求和并不改变模9的结果所以最终的一位数就是原数对9取模的余数余数为0时对应数根9。这个推导过程看起来很数学其实特别好理解。你可以把“模9”想象成一种标记方式每次把各位加起来虽然数字变小了但那个标记一直没变。最后一位数就是这个标记的具象化。机考里如果遇到超大数输入直接用字符串处理s input().strip() total sum(int(ch) for ch in s) print(9 if total % 9 0 and total ! 0 else total % 9)就算题目给的是几千位的数字也能O(n)跑完。这个思路后来我在不少初级编程考试里也见过比如Python一级考级的数字统计类题目基本就是同一套思维。2.2 变态跳台阶DP推到底就成了 (2^{n-1})变态跳台阶是当年牛客上的常见题。一只青蛙一次可以跳上1级台阶也可以跳上2级……它也可以跳上n级台阶。求这只青蛙跳上一个n级台阶总共有多少种跳法。大多数人看到这题的第一反应是DP。设 (f(n)) 表示跳上n级台阶的方法数那么最后一次跳跃可以是1级、2级、……、n级所以[ f(n) f(n-1) f(n-2) \dots f(1) 1 ]后面那个 1 代表一次直接跳n级的情况。看起来这是一个O(n²)的递推但如果你把 (f(n-1)) 也展开[ f(n-1) f(n-2) f(n-3) \dots f(1) 1 ]会发现 (f(n) 2 \times f(n-1))。这就是等比数列。又因为 (f(1)1)所以[ f(n) 2^{n-1} ]代码直接变成一行def jump_ways(n): return 1 (n - 1)当年很多人不理解为什么答案是 (2^{n-1})其实可以换个角度想对于除了最后一级台阶之外的每一级青蛙都有“踩”和“不踩”两种选择而每一种选择组合都唯一对应一种跳法。所以总共就是 (2^{n-1}) 种。这个解释比递推更直观。这题的坑主要在两点。第一递归写法如果不记忆化n稍微大一点就会爆栈或超时。第二n可能很大输出要用大整数Python无所谓但C要注意别用int。当年真有同学写出了递归版对着 n20 就开始卡顿心态直接崩了。3. 字符串归一化与彩色瓷砖机考基础题的两种打开方式3.1 字符串归一化统计题的高分写法字符串归一化是这套卷子里最像“送分题”的题。我看到的版本是输入一串由小写字母组成的字符串按字典序输出每个字符以及它出现的次数没有出现的字符不输出。比如输入abca输出a2b1c1。思路没有悬念用一个长度26的数组做计数import sys data sys.stdin.read().split() if not data: sys.exit() s .join(data) cnt [0] * 26 for ch in s: cnt[ord(ch) - ord(a)] 1 res [] for i in range(26): if cnt[i] 0: res.append(chr(ord(a) i) str(cnt[i])) print(.join(res))这里有一个值得养成的好习惯用sys.stdin.read()而不是input()。因为机考环境里有些题虽然看起来是单组输入但实际测试数据可能有多组或者字符串里有换行。sys.stdin.read()一次性读进来再处理能避免很多输入上的坑。为什么推荐数组而不是字典因为字符范围固定只有26个数组索引天然有序省掉了排序步骤。虽然字典加排序也能过但在机考里能少写一行是一行能少一次排序就少一分风险。这道题真正容易挂的地方是输出格式。有人把a2b1c1输出成了a:2 b:1 c:1有人把没出现的字符也输出了还有人没处理输入为空的情况。都是小细节但机考判题就是这么无情。3.2 彩色瓷砖贪心能过但边界要小心彩色瓷砖这题我记得描述大致是有一排瓷砖每块瓷砖有一个颜色用字母表示现在可以修改任意一块瓷砖的颜色问最少修改多少次能让任意相邻两块瓷砖的颜色都不同。这题我最开始想复杂了试图用动态规划。后来才发现简单贪心就能过。核心思路从左到右扫描如果发现s[i] s[i1]那就必须改其中一块。改哪块改后面那一块因为改前面会影响已经处理好的区域。改完s[i1]之后由于它已经变了它和s[i2]是否相同需要重新判断所以这时候应该直接跳到i2如果没遇到相同就i。s list(input().strip()) n len(s) ans 0 i 0 while i n - 1: if s[i] s[i1]: ans 1 # 把 s[i1] 改成一个和前后都不相同的颜色 # 这里简单用 # 代替实际只要和 s[i]、s[i2] 不同即可 s[i1] # i 2 else: i 1 print(ans)注意代码里i 2这个细节。很多第一次写的人会写成i 1结果同一个位置被重复判断答案偏大。为什么可以跳两个因为当前这一对已经通过改后面那块处理完了下一对应当从i1和i2开始看但s[i1]已经变成新颜色不可能再和s[i]相同了所以直接从i2和i3比较即可。也有人用另一种贪心遇到连续相同段答案加上len // 2。这个做法在只有一段连续相同时是对的比如aaaa答案是2aaa答案是1。但如果是aaabaaa这种你把中间那个b算进去就不能简单用段长度整除2了。所以老老实实从左到右扫最稳。还有一个小陷阱如果题目限定只能改成给定的几种颜色并且颜色总数只有2种那贪心就不能用了。但按我记忆中2017年这道题的数据范围颜色可以被改成一个和前后都不同的新颜色所以贪心没问题。如果在面试里遇到这题建议你要么先问清楚字符集范围要么直接补上一个DP版本显得更稳。4. 星际密码从矩阵快速幂到循环节的演进4.1 题目本身在考什么星际密码是这套卷子里最有“压轴感”的一道题。题目背景大概是这样某个防御系统的密码由一个矩阵的幂次决定矩阵是[ A \begin{bmatrix} 1 1 \ 1 0 \end{bmatrix} ]输入若干个整数每个整数代表一个幂次要求输出 (A^x) 中某个特定元素的十进制后四位并且多个结果连成一个字符串输出不足四位左边补0。如果你熟悉斐波那契数列一眼就能看出来这个矩阵不一般。(A) 的幂次结果其实落在斐波那契数列上[ A^x \begin{bmatrix} F_{x1} F_x \ F_x F_{x-1} \end{bmatrix} ]所以问题本质上就是输入一组x输出 (F_{x1} \bmod 10000)每条结果固定四位连续拼接。很多人在这一步就栽了。因为他们只盯着“矩阵快速幂”忘了题目要的是“后四位”。直接算真实斐波那契数再取后四位x稍微大一点就会溢出而且在 Python 里大整数虽然不溢出但算那么大的数纯属浪费。4.2 快速幂实现与补零的坑标准做法是矩阵快速幂。先写一个2×2矩阵乘法再套快速幂def mat_mul(a, b): return [ [(a[0][0]*b[0][0] a[0][1]*b[1][0]) % 10000, (a[0][0]*b[0][1] a[0][1]*b[1][1]) % 10000], [(a[1][0]*b[0][0] a[1][1]*b[1][0]) % 10000, (a[1][0]*b[0][1] a[1][1]*b[1][1]) % 10000] ] def mat_pow(mat, power): res [[1, 0], [0, 1]] base mat while power: if power 1: res mat_mul(res, base) base mat_mul(base, base) power 1 return res A [[1, 1], [1, 0]] n int(input()) nums list(map(int, input().split())) ans [] for x in nums: R mat_pow(A, x) val R[0][0] % 10000 ans.append(f{val:04d}) print(.join(ans))这段代码有个非常容易错的地方R[0][0]到底是 (F_{x1}) 还是 (F_x)。如果方向搞反了全错。我自己的习惯是拿小数据验一下当 x1 时(A^1) 就是[[1,1],[1,0]]左上角是1而 (F_11, F_21)所以此时左上角等于 (F_2)也就是 (F_{x1})。验完这个后面下标就不会写错。然后就是输出格式的两个坑。第一个是补零用%04d或者 Python 的f{val:04d}否则1会输出成1而不是0001。第二个是拼接所有结果要连成一个大字符串输出中间没有空格没有换行。当年真有人每行输出一个结果最后全判错特别冤。4.3 吃透循环节比套模板更值钱矩阵快速幂是标准答案但说实话到了考场上矩阵乘法2×2还好万一题目换成3×3或者更高维手写矩阵乘法很容易出bug。所以这道题我更推荐另一种思路利用斐波那契数列模10000的循环节。斐波那契数列对某个数取模后会呈现周期性。对10000取模周期是15000。也就是说[ F_{n} \bmod 10000 F_{n % 15000} \bmod 10000 ]预先把fib[0]到fib[15000]全部算出来之后每个输入x直接查表O(1) 搞定。MOD 10000 CYCLE 15000 fib [0] * (CYCLE 1) fib[0] 0 fib[1] 1 for i in range(2, CYCLE 1): fib[i] (fib[i-1] fib[i-2]) % MOD n int(input()) nums list(map(int, input().split())) ans [] for x in nums: val fib[(x 1) % CYCLE] # 因为矩阵左上角对应 F(x1) ans.append(f{val:04d}) print(.join(ans))这个写法比矩阵快速幂更不容易出错而且速度更快。你不用记矩阵乘法方向不用处理单位矩阵只要算一遍斐波那契表就行。唯一需要记的是周期15000这个数字。如果你记不住也没关系可以在程序里动态找循环节从(fib[0], fib[1]) (0, 1)开始当后面再次出现(0, 1)这一对时就说明找到了周期。从这题我得到一个很重要的经验机考里“能跑”和“能稳”是两回事。矩阵快速幂能跑但一旦你矩阵下标写反调试时间可能超过10分钟而预计算循环节虽然看起来没那么“高级”但在考场上是最稳的选择。后来我刷题越来越倾向于优先选择代码最简单、最难写错的做法而不是理论最优解。5. 翻旧题的正确姿势复盘方法与复习建议5.1 先独立重做再对答案很多人“刷题”实际上是“看题解”。打开一道题看两分钟没思路就直接点开答案看完觉得自己会了然后下一道。这样刷一个月感觉做了几百题真到机考还是不会。翻旧题也一样如果你直接看我的解析那这套题对你来说就只是“看过”不是“做过”。我建议你把这套2017年一模当成一次真实模拟考。定好90分钟闹钟关掉一切能搜答案的窗口只留一个编辑器老老实实把五道题写完。写完之后再拿着你的代码和我上面的代码逐题对比重点看三件事你的思路为什么绕了远路你的边界条件有没有全考虑到你的代码在数据最大时会不会超时或溢出这个过程比单纯看五篇题解有价值得多。因为只有经过独立思考你才会发现自己的思维盲区。比如你可能从来没意识到数根能用模9也从来没想过彩色瓷砖的贪心要跳两个位置。这些“啊原来是这样”的瞬间才是刷题真正的收获。5.2 一道题做三遍暴力、优化、推导我有一套自己的刷题方法尤其适合这种经典老题第一遍写暴力解确保能过样例第二遍优化让它能过大数据第三遍从数学层面推导搞清楚为什么优化是对的。拿数根来说。第一遍就是那个while num 10的模拟循环第二遍发现可以直接用字符串处理超大数第三遍理解模9原理以后见到任何数字根问题都能秒杀。再比如变态跳台阶第一遍写递归或DP第二遍发现规律改成2^(n-1)第三遍从“每个台阶踩或不踩”的角度给出组合解释。这三遍下来一道题的价值至少翻三倍。你不仅会做这道题还理解了这一类题。以后碰到“矩形覆盖”“铺瓷砖”这类换个马甲的跳台阶题你也能迅速看穿。这正是2017年牛客一模这套题的隐藏价值它不考偏题怪题每道题都能延伸出一类常见题型非常适合用来做这种三遍训练。5.3 老模拟题对未来校招的参考价值有人可能会问2017年的题放到2025年还有用吗我的看法是校招机考的题型核心并没有变太多。数根、字符串统计、区间贪心、斐波那契变形这些依然是笔试里的常客。变的只是题目包装更复杂、数据范围更大、有时候会套一层更长的题面但底层考察的还是这些基础能力。而且不只是校招。现在很多编程考级比如Python一级考试里也能看到“统计字符出现次数”“求数字各位之和”这类题目。它们本质上就是当年牛客一模的简化版。所以把这套老题吃透不仅对校招有帮助对打基础阶段的学习同样适用。复盘的时候我建议你建一个自己的错题文档不用分类太细只要记清楚三件事题目要我做什么、我当时卡在哪、正确思路是什么。别用收藏夹收藏夹只会吃灰。把题重新做一遍、在文档里写一遍它才会真正长在你脑子里。写到最后说点个人体会吧。2017年我做这套卷子的时候星际密码用的是最笨的逐项矩阵乘法虽然过了样例但心里一点底都没有彩色瓷砖第一次写成统计连续段长度除以2碰到交叉数据直接翻车。这些错误多年后再看反而成了我最深的记忆点。所以我特别建议你也找一套老模拟题别急着看答案先掐表做一遍。你可能会发现有些题现在的自己依然会写错而有些题你已经能一眼看穿出题人想考什么。这种对比就是成长最直观的证据。