企业官网建设流程全解析

翻出2017年牛客模考（一模）的编程题集合时，我第一反应不是题目本身，而是那年的备战状态：一边啃剑指offer，一边在牛客上掐表做模拟卷，生怕机考翻车。牛客一模这套题，难度放在当年不算低，现在回头看却很有意思——它考的东西大多不是“模板”，而是数学思维和边界处理。哪怕到了2025年，再以老题新做的视角去拆它，依然能榨出不少东西。

这篇文章不是官方题解，而是我作为一个当年被这套题锤过的人，重新复盘后的完整记录。每道题我会先讲清楚题目在问什么，再拆解题思路，给出能直接跑的代码，最后把当年容易踩的坑单独拎出来说。适合正在准备校招机考、想补算法基础、或者单纯想找几道经典题练手的读者。

1. 2017年牛客一模：一份“思维大于模板”的卷子

1.1 当年的备考生态：为什么模拟卷比刷单题更有用

2017年正是校招机考开始普及的年份。那个时候“刷题”还没有现在这么体系化，大家更多是在牛客、LeetCode上零散地刷，很少有人系统地模拟过真实机考环境。牛客的模拟考试功能一出，很多人第一次意识到：原来机考不是“会做就行”，还要在有限时间内完成读题、编码、调试、提交。

一模这套题，就是在那个背景下出现的。它的意义不在于题目本身有多难，而在于它第一次逼着大家把刷题状态切换成“考试状态”。我记得当时做完模拟卷，最大的收获不是哪道题会了，而是发现自己读题太慢、边界条件老漏、一紧张连循环都写不利索。这些能力，靠平时一道一道刷题是练不出来的。

到现在我也会跟学弟学妹说：如果你从来没掐表做过一套完整机考题，那你对“自己准备好了”这件事的判断，大概率是错的。牛客一模恰好提供了这样一个参照系，这是它时至今日仍有价值的第一个原因。

1.2 整体观感：好几道题都在考“想明白再动手”

我印象里这套卷子一共五道编程题，分别是数根、变态跳台阶、字符串归一化、彩色瓷砖、星际密码。单看题目类型，几乎没有冷门算法，全是基础题。但妙就妙在，每道题都有两种写法：一种是一眼暴力、代码长、边界多；另一种是想清楚规律后，几行代码就能过。

这种出题思路，其实是故意在筛选“能不能快速看穿问题本质”的人。比如数根这题，你要是真去循环求和，也能过，但遇到超大数就会慌；可你要是知道数根和模9之间的关系，那就是一道口算题。再比如变态跳台阶，很多人条件反射写DP，但推两行就能发现答案是 (2^{n-1})，直接位运算解决。

所以我一直觉得，2017年牛客一模的出题人很懂校招。校招机考从来不指望你掌握多冷门的算法，它考的是你在有限时间内，能不能把常见问题用最干净的方式解出来。这套卷子里的每一道题，都在反复敲打这件事。

2. 数根与变态跳台阶：两道送分题里的数学规律

2.1 数根：模拟不是不行，但模9才是正解

先看数根。题目描述很直白：给定一个正整数，反复计算各位数字之和，直到结果变成一位数，这个一位数就是原数的“数根”。比如9876，先算9+8+7+6=30，再算3+0=3，所以数根是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。当年真有同学写出了递归版，对着 n=20 就开始卡顿，心态直接崩了。

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[i+1]，那就必须改其中一块。改哪块？改后面那一块，因为改前面会影响已经处理好的区域。改完s[i+1]之后，由于它已经变了，它和s[i+2]是否相同需要重新判断，所以这时候应该直接跳到i+2；如果没遇到相同，就i++。

s = list(input().strip()) n = len(s) ans = 0 i = 0 while i < n - 1: if s[i] == s[i+1]: ans += 1 # 把 s[i+1] 改成一个和前后都不相同的颜色 # 这里简单用 '#' 代替，实际只要和 s[i]、s[i+2] 不同即可 s[i+1] = '#' i += 2 else: i += 1 print(ans)

注意代码里i += 2这个细节。很多第一次写的人会写成i += 1，结果同一个位置被重复判断，答案偏大。为什么可以跳两个？因为当前这一对已经通过改后面那块处理完了，下一对应当从i+1和i+2开始看，但s[i+1]已经变成新颜色，不可能再和s[i]相同了，所以直接从i+2和i+3比较即可。

也有人用另一种贪心：遇到连续相同段，答案加上len // 2。这个做法在只有一段连续相同时是对的，比如aaaa答案是2，aaa答案是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_{x+1} & F_x \ F_x & F_{x-1} \end{bmatrix} ]

所以问题本质上就是：输入一组x，输出 (F_{x+1} \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_{x+1}) 还是 (F_x)。如果方向搞反了，全错。我自己的习惯是拿小数据验一下：当 x=1 时，(A^1) 就是[[1,1],[1,0]]，左上角是1，而 (F_1=1, F_2=1)，所以此时左上角等于 (F_2)，也就是 (F_{x+1})。验完这个，后面下标就不会写错。

然后就是输出格式的两个坑。第一个是补零，用%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(x+1) 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，碰到交叉数据直接翻车。这些错误，多年后再看，反而成了我最深的记忆点。所以我特别建议你也找一套老模拟题，别急着看答案，先掐表做一遍。你可能会发现，有些题现在的自己依然会写错，而有些题，你已经能一眼看穿出题人想考什么。这种对比，就是成长最直观的证据。