网易2017秋招编程题集深度拆解：从模拟到矩阵快速幂的算法主线

网易2017秋招编程题集合，这份题单在牛客网上流传了好几年，到现在还经常被拿出来当作校招笔试的入门材料。我当年第一次完整刷校招编程题，用的就是这套题，后来帮别人做笔试辅导时又反复带刷过两三轮。它最大的价值在于难度梯度非常典型：从读题就能动手的模拟题，到需要仔细设计状态的动态规划，再到压轴的矩阵快速幂，基本覆盖了互联网公司笔试最常考的算法主线。这篇文章不打算把每道题逐个贴一遍毫无营养的答案，而是以这套题集为引子，把每类题背后的考点、易错点、以及当时真实考场上容易踩的坑都拆开讲清楚。无论你是正在准备秋招的应届生，还是想系统补算法的同学，这份拆解应该都能帮到你。

1. 先说清楚：这套题到底在考什么

1.1 笔试的“筛人”逻辑：不是让你拿满分

很多人第一次做这套题会有一个误区，以为笔试的目的是“把所有题做完、做对”。实际上，像网易这种体量的公司，秋招笔试的核心作用是在海量简历里做第一轮筛选，题目设计者根本不指望大部分人AC（Accepted，完全通过）。正常情况下，一套题里会有两三道送分题、两道需要动脑子的中等题、以及一道只有少数人能完整写出来的压轴题。你只要能稳定拿到前面几道的分，再在中等题上撕开一道口子，笔试这关基本就稳了。这套2017年的题目正好完美体现了这个设计思路：简单题让你拿基础分，中档题筛出算法能力，压轴题筛出真正的竞赛型选手。

1.2 考点分布：一条很典型的校招算法主线

我按自己的理解把整套题涉及的考点整理了一下：

这里面的动态规划和矩阵快速幂，是后来几年所有大厂笔试的高频重点。从2017年到现在，算法题的趋势一直是往“更难、更综合”的方向走，但这套题却意外地适合作为学习基准：它没有堆砌冷门数据结构，也不靠偏题怪题为难人，每一道都能在《算法竞赛入门经典》或者常见的算法模板里找到对应方法。刷完这套，你对校招笔试的“难度上限”会有一个比较准确的感知。

2. 简单题也不简单：模拟与数学题的细节陷阱

2.1 小易的升级之路：模拟过程里藏着gcd

这道题应该是整套题单里最友好的第一题。题意大致是：初始有一个角色能力值，面对一排怪物，每个怪物有防御力。如果角色能力值大于怪物防御力，能力值就加上怪物防御力除以2后向下取整的结果；否则能力值就加上当前能力值和怪物防御力的最大公约数。给定怪物顺序，求最终能力值。

思路其实就是一个纯模拟，按顺序遍历怪物，用if分支判断走哪条升级路线。能让你拿不到分的点只有一个：最大公约数有没有背熟。我见过不少同学现场写GCD时用for循环从min(a,b)往下试，这在小数据下确实能过，但一旦数据范围拉大就会超时，而且笔试现场手写一个低效的辗转相除版本也容易出边界问题。最稳的写法是递归或循环的欧几里得算法：

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

另一个不值得犯的错是把能力值和怪物防御力当成浮点数处理。题目里明确说了向下取整，也就是说攻击成功时加的是怪物防御力 / 2的整数部分，直接用整数除法就行，不需要引入double。你一旦用了浮点数，取整、精度、边界全都会变成隐患，纯粹给自己挖坑。

2.2 计算糖果：方程组解完必须回代

“计算糖果”这道题，乍一看完全是一道初中数学题。输入四个整数，分别是A-B、B-C、A+B、B+C，让你推出A、B、C。很多人的第一反应是直接解方程，小学二年级就会的事情，但为什么这题还能有经典一挂？因为它考的其实是“验证”。

我们先看推导：把第一个和第三个等式相加，可以得到(A-B) + (A+B) = 2A，所以A就是两个数的和除以2。同理，第二个和第四个相加得到2B，第四个减第二个得到2C。到这里，很多人的代码就结束了，直接输出A、B、C，结果提交之后发现大面积WA。问题出在：你计算出来的结果必须满足给定的四个等式，而且A、B、C还必须是合法的非负整数。举个极端的例子，如果输入是1 1 3 2，解出来A=2，B=1，C=0.5，C不是整数，这组输入就没有合法解，应当输出No。

正确的做法是解完以后，把A、B、C代回四个等式逐一校验，同时检查每个等式是否成立、每个数是否为整数。如果输入数据本身不保证能整除，也要先判断(y1 + y3) % 2这些条件，避免出现小数。这道题真正的考点不在解方程，而在“检查解的合理性”——这种必须在输出前做回代验证的意识，在很多题目里都会用到。

2.3 数字翻转：别被“反转”两个字绕晕

“数字翻转”属于签到题，但它的题意描述经常把第一次做的人绕进去。题目给了两个整数x和y，让你求rev(rev(x) + rev(y))，其中rev表示把一个数字倒过来读。

比如x=123，rev(x)=321；y=456，rev(y)=654；rev(x)+rev(y)=975，再rev一次得到579。问题在于很多人会在第一步就多想：rev(x)之后可能有前导零吗？比如x=120，rev(x)=21，多余的0在整数表示里自然消失了，完全不用手动处理。你只需要保证两个东西：一是rev函数对0要能正确返回0，二是整个过程里所有变量都控制在int范围内，如果x和y能到10^9以上，反转后的x也可能很大，该用long long就用long long。

int rev(int x) { int r = 0; while (x) { r = r * 10 + x % 10; x /= 10; } return r; }

这道题的价值不在难度，而在于帮你建立“读题要抓本质”的意识。面试官不是要考你字符串处理，也不是考前导零处理，就是看你能不能稳定地把一个简单函数写对。

3. 动态规划是重头戏：状态定义决定成败

3.1 暗黑的字符串：计数类DP的状态设计

“暗黑的字符串”是我认为整套题里最适合用来练DP状态设计的一道题。题意大致是：只使用A、B、C三种字符构造长度为n的字符串，要求任意连续三个字符都不能刚好是由A、B、C各一个组成（也就是不能出现ABC、ACB、BAC这种全排列），问一共有多少种合法字符串。

如果你在考场上直接尝试用组合数学推导通项，大概率会卡住。正确的打开方式是用递推：一个长度为n的合法串，是在一个长度为n-1的合法串末尾追加一个字符得到的。追加时是否合法，只取决于原串末尾两个字符的情况。因此我们设两个状态：same[i]表示长度为i的合法串中，末尾两个字符相同的数量；diff[i]表示末尾两个字符不同的数量。

转移关系我推一遍，你可以看到这里面的逻辑：

• 如果原串末尾两个字符相同，比如AA，那么追加B得到AAB，追加C得到AAC，都合法且末尾不同；追加A得到AAA，也合法且末尾相同。所以这个状态能贡献给diff2种、贡献给same1种。
• 如果原串末尾两个字符不同，比如AB，那么追加C会凑成ABC，非法；追加A得到ABA，合法且末尾不同；追加B得到ABB，合法且末尾相同。

于是可以得到递推式：

same[i] = same[i-1] + diff[i-1]; diff[i] = 2 * same[i-1] + diff[i-1];

初始化时，长度为2的字符串里，AA、BB、CC三种算same，剩下6种算diff。最后答案为same[n] + diff[n]。我当时第一次写这题时，死活没想到用“末尾两位是否相同”做状态，而是去记录最后一位字符和倒数第二位的具体值，导致状态爆炸。后来想明白了，DP的核心是找到“当前局面中影响后续决策的最小信息量”。对于相邻三字符约束，末两位的“相同性”已经足以决定下一步是否合法，不需要关心具体是A还是B。把这个想通之后，代码本身十分钟就能写完。

3.2 合唱团：带正负号的乘积最值DP

“合唱团”是这套题单里最经典的一道DP，也是很多人在笔试现场卡住的题。题意是：n个学生站成一排，每个学生有一个能力值，可能是负数。要从中按顺序选出k个学生，任意两个相邻被选中的学生在原序列中的位置差不能超过d，求这k个学生能力值乘积的最大值。一句话，“选k个人，间隔有限制，乘积最大”。

如果能力值全是正数，这就是个标准的区间DP：dp[i][j]表示以第i个人为最后被选的人、一共选了j个人的最大乘积，转移时往前看距离不超过d的位置。但能力值可为负，这一下就把题目难度拉高了：当前最优的乘积可能来自前面的“最小乘积”乘以一个负数，负负得正。所以必须同时维护最大值和最小值两个DP数组，转移时把上一步的最大值、最小值分别和当前能力值相乘，再分别更新。

const long long NEG = -1e18; long long dpMax[55][15], dpMin[55][15]; // dpMax[i][j] / dpMin[i][j]: 以第 i 个学生为最后一人，一共选 j 人的最大/最小乘积

转移的核心代码是：

for (int j = 2; j <= k; j++) { for (int i = j; i <= n; i++) { dpMax[i][j] = NEG; dpMin[i][j] = NEG; // 注意这里也可以用一个大数，但必须配合下标限制，避免未初始化值参与运算 for (int p = max(j - 1, i - d); p <= i - 1; p++) { dpMax[i][j] = max(dpMax[i][j], max(dpMax[p][j-1] * a[i], dpMin[p][j-1] * a[i])); dpMin[i][j] = min(dpMin[i][j], min(dpMax[p][j-1] * a[i], dpMin[p][j-1] * a[i])); } } }

这里有一个非常隐蔽的坑：如果只用负无穷去初始化dpMax[p][j-1]，当a[i]本身是负数时，NEG * a[i]会变成一个极大的正数，导致dpMin的更新被污染。正确做法是在下标循环范围上强制p >= j-1，确保取到的都是有意义的前驱状态。这一行很多人没注意，查错能查一个多小时。另外，能力值的乘积可能非常大，必须用long long甚至更高精度类型，否则会在不知不觉中溢出，程序输出的结果完全不可信。

3.3 DP题的边界与初始化：最容易白给的一关

无论是暗黑的字符串还是合唱团，DP的边界初始化都是最容易写错的地方。暗黑字符串的初始条件错一位，后面所有结果全错还很难察觉；合唱团如果忘记把dpMax[i][1]和dpMin[i][1]都初始化为a[i]，第一层转移就会得到一堆奇怪的值。

我这里给一个通用建议：写DP前先花一分钟把“状态含义”和“初始状态”写出来，不要直接敲代码。比如此处的dpMax[i][j]有一个隐含条件：i至少是j，因为选了j个人最后一个人下标不可能小于j。你在循环时把i从j开始遍历，就能天然避开一些无意义状态。另一个经验是，写完递推后，先手动模拟一个很小的用例，比如n=4、k=2、d=2，在纸上把dp表前几行算一遍，再和程序输出对一下。很多边界问题，纸上一算就暴露了，比反复提交判断要快得多。

4. 压轴题的暴力到优雅：二分和矩阵快速幂

4.1 星际穿越：先想数学，再决定要不要二分

“星际穿越”这个题，题面包装得很科幻，但剥开之后就是一个数学问题：给定一个正整数n，求最大的整数x，使得x的平方加x不超过n。直接把x从1开始暴力枚举当然能过小数据，但n的上限较大的时候，枚举就是灾难。解法有三个层次：

• 第一层：暴力while循环，x从1一直试到x*(x+1) > n。能过样例，但在笔试数据下很可能超时。
• 第二层：二分答案。x的范围是1到sqrt(n)左右，用标准二分找最后一个满足条件的x。这样复杂度是O(log n)，非常稳。
• 第三层：直接解一元二次方程。x = floor((sqrt(1 + 4n) - 1) / 2)。

我推荐第二层，因为二分写起来不容易错，而且这个模式能迁移到很多“求满足某条件的最大/最小值”问题。注意mid计算时要用long long，mid * mid在n比较大的时候很容易溢出int。实现上，建议用“左闭右开”或者“答案偏向左侧”的二分写法，配合一个会“向下取整”的边界，避免死循环。

4.2 魔力手环：k次操作背后的矩阵加速

如果整套题只能选一道题推荐，我选“魔力手环”。它基本是这套题集里最能区分水平的一道题。题意大致是：手环上有n个数字，每次操作会生成一个新序列，每个新位置的值等于原序列中该位置和下一个位置的值之和（最后一个位置与第一个位置相加），操作k次后，输出每个数字对100取模的结果。这里的k可以非常大，动辄10^9级别，直接模拟k轮肯定不可行。

这道题的突破点是：每次操作本质上是对原序列左乘一个固定的转移矩阵。构造一个n×n矩阵M，其中第i行第i列和第(i+1) mod n列为1，其余为0，那么一次操作就是res = vector * M。重复k次就是res = vector * (M^k)，矩阵幂可以用快速幂在O(log k)时间内完成。这就是线性代数和算法的经典结合。

void mul(vector<vector<int>>& a, vector<vector<int>>& b, int n) { vector<vector<int>> c(n, vector<int>(n, 0)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int t = 0; t < n; t++) c[i][j] = (c[i][j] + a[i][t] * b[t][j]) % 100; a = c; } void matrixPow(vector<vector<int>>& mat, long long e) { int n = mat.size(); vector<vector<int>> res(n, vector<int>(n, 0)); for (int i = 0; i < n; i++) res[i][i] = 1; while (e) { if (e & 1) mul(res, mat, n); mul(mat, mat, n); e >>= 1; } mat = res; }

在实际实现里，我建议把你的向量也当成n×n矩阵来处理，只是除了第一行之外全是0。这样矩阵乘法函数就能复用同一套逻辑，不容易引入额外bug。矩阵乘法的三层循环里，模100可以放在内层乘法之后，因为100这个模数很小，即使中间多了几次加法也不会溢出，但为了保险起见还是用long long累加更稳妥。

4.3 矩阵快速幂的封装与取模实战

矩阵快速幂是我见过校招笔试里最容易出现“细节翻车”的模块。常见的错误有这么几类：

第一，单位矩阵没初始化对。单位矩阵是对角线上全是1、其他地方是0，漏了res[i][i] = 1这一行，整个快速幂结果就是零矩阵。第二，乘法函数里忘了取模。如果题目要求对100取模，你每一步矩阵乘法之后都要取模，否则中间值可能膨胀得没法看。第三，把“行向量乘矩阵”和“矩阵乘行向量”搞反了方向。这里建议在纸上画一下维度，确认每个位置的转移对应关系，不要靠死记硬背。第四，n比较小的时候，直接暴力模拟k次可能也能过部分数据，但10^9这个量级只要出现，就一定是矩阵快速幂或者别的对数级算法才能通过的题目。

这类题的经验是：只要数据量里出现k <= 10^9，先停一下，别急着写循环，想一想能不能用倍增、快速幂、二分或者矩阵来做。这种对数据规模的敏感度，就是刷题带给你最直接的好处。

5. 笔试现场最容易翻车的环节

5.1 读题漏条件：范围和模数决定写法

我在带人刷题时发现，很多丢分不是算法不会，而是读题时把几个关键约束漏了。比如“输出对100取模”、“结果可能超过int范围”、“输入可能有多个测试用例”等等。这套2017年的题目，几乎每道都有一些需要你仔细抠的措辞。一个比较稳的经验是：在代码里把题目给的约束写成注释放在文件开头。比如看到n <= 50, k <= 10^9，就应该立刻意识到这里不能用模拟，必须走矩阵快速幂；看到“结果需要对100取模”，就应该在写乘法时把取模写进去，而不是最后输出时再处理。

5.2 数据类型：int爆了才反应过来就晚了

校招笔试的编译器一般不会因为你int溢出而报错，它只会给你一个完全错误的结果。这道题集里，合唱团的乘积、星际穿越的平方、计算糖果的中间和，都可能超过int范围。我的建议是所有涉及乘法、求和、二分答案的变量，无脑用long long。反正笔试不考察你省内存的能力，多用几个字节总比WA强。如果你不确定会不会溢出，可以简单估算：int上限大概是21亿，而很多题目的n本身就能到10^9，一个平方运算就超了。

5.3 输出格式与多组输入：最冤的0分

很多人在本地测试完全正常，提交后却是0分，原因往往不是算法错，而是输出格式不对。比如要求每个结果占一行，结果你把多个结果用空格拼在同一行；比如题目要求先输出“Case #1:”这样的前缀，你漏了；比如题目说“如果不存在，输出No”，你输出了“NO”。这些事情听起来很蠢，但每年都有大量学生倒在这里。我自己的习惯是提交前把输出部分反复读三遍，并且至少构造一组肉眼能算出来的样例做比对。

还有一点：牛客网这类OJ的输入跟力扣的模板不一样，它是完整的输入流方式，可能有多组数据。如果不确定是不是多组，可以用while (cin >> n)的写法，这样既能处理单组也能处理多组，代价很小。

5.4 时间分配：先保送分题，再啃中档题

最后聊一下考场上的时间分配。一套笔试往往只有两小时左右，却有5到8道编程题。我的策略永远是：先把所有题都扫一遍，把一眼能看出做法的送分题赶紧写掉，再开始啃中档题，最后剩下时间才碰压轴题。这套2017年的题集，送分题至少有三道，如果你顺序不对，先花四十分钟死磕最后的魔力手环，那前面的分数可能就全丢了。反过来，先把送分题全部稳稳拿到，心里有底之后再去冲难题，效果会好很多。这是笔试里最重要的经验，没有之一。

6. 从这套题延伸出来的刷题路线

6.1 刷题之后的复盘：比刷题本身更重要

把整套题做完之后，别急着换下一套，复盘的价值远远大于刷题数量。我当时的复盘方法是：每道题不看题解重写一遍，直到能流畅写完为止；然后给每道题打标签，标记它的考点、我的第一反应、以及我最后AC用了多长时间。之后每周翻一次这个标签表，你会发现自己的薄弱项非常集中，要么是DP状态转移写不稳，要么是矩阵乘法边界老出错。针对薄弱项再去找对应的专项题目练，而不是永远在舒适区里刷简单题。

具体到这套题，如果你发现合唱团卡了很久，说明你对“最值DP”和“负数参与状态转移”还不够熟，下一步可以刷一些类似“乘积最大子数组”“股票买卖”等题目来巩固。如果你在魔力手环上根本没思路，那就说明你还没把快速幂和矩阵乘法内化，应该先回补线代基础，再回来重刷这道题。

6.2 以这套题为参照的查漏补缺清单

这里插一句我的个人体会：好多同学刷题喜欢按“题号顺序”往后刷，觉得每天刷几道就等于在进步。但真正有效的做法是“按考点刷”，比如连续一周只刷DP题，再连续一周只刷二分和快速幂，让自己在短时间内对同一类题目形成肌肉记忆。网易这套题集恰好是因为它涵盖的考点足够全，反而很适合拿来做阶段性的自测，而不是按顺序硬刷。

最后再分享一个小技巧

无论你是用C++还是Java，笔试前都建议把几个高频模板单独存成一个文件，包括快速幂、矩阵乘法、GCD、二分查找、并查集、最短路。不是让你考场上去复制粘贴，而是通过临考前手敲一遍，把这些模板变成你的条件反射。我在做网易这套题时，魔力手环的矩阵快速幂能一次写对，就是因为前一天刚把矩阵模板手敲了两遍。这种“肌肉记忆”在紧张的笔试环境下，比临时回忆公式要可靠得多。