网易2017秋招编程题集合这份题单在牛客网上流传了好几年到现在还经常被拿出来当作校招笔试的入门材料。我当年第一次完整刷校招编程题用的就是这套题后来帮别人做笔试辅导时又反复带刷过两三轮。它最大的价值在于难度梯度非常典型从读题就能动手的模拟题到需要仔细设计状态的动态规划再到压轴的矩阵快速幂基本覆盖了互联网公司笔试最常考的算法主线。这篇文章不打算把每道题逐个贴一遍毫无营养的答案而是以这套题集为引子把每类题背后的考点、易错点、以及当时真实考场上容易踩的坑都拆开讲清楚。无论你是正在准备秋招的应届生还是想系统补算法的同学这份拆解应该都能帮到你。1. 先说清楚这套题到底在考什么1.1 笔试的“筛人”逻辑不是让你拿满分很多人第一次做这套题会有一个误区以为笔试的目的是“把所有题做完、做对”。实际上像网易这种体量的公司秋招笔试的核心作用是在海量简历里做第一轮筛选题目设计者根本不指望大部分人ACAccepted完全通过。正常情况下一套题里会有两三道送分题、两道需要动脑子的中等题、以及一道只有少数人能完整写出来的压轴题。你只要能稳定拿到前面几道的分再在中等题上撕开一道口子笔试这关基本就稳了。这套2017年的题目正好完美体现了这个设计思路简单题让你拿基础分中档题筛出算法能力压轴题筛出真正的竞赛型选手。1.2 考点分布一条很典型的校招算法主线我按自己的理解把整套题涉及的考点整理了一下题目类型代表考点难度模拟题最大公约数、整数运算、过程模拟入门数学题方程组求解、整数反转、回代验证入门到进阶动态规划状态定义、线性计数DP、乘积最值DP进阶二分搜索数值二分、边界收敛进阶矩阵快速幂矩阵乘法、二进制幂、取模压轴这里面的动态规划和矩阵快速幂是后来几年所有大厂笔试的高频重点。从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、AB、BC让你推出A、B、C。很多人的第一反应是直接解方程小学二年级就会的事情但为什么这题还能有经典一挂因为它考的其实是“验证”。我们先看推导把第一个和第三个等式相加可以得到(A-B) (AB) 2A所以A就是两个数的和除以2。同理第二个和第四个相加得到2B第四个减第二个得到2C。到这里很多人的代码就结束了直接输出A、B、C结果提交之后发现大面积WA。问题出在你计算出来的结果必须满足给定的四个等式而且A、B、C还必须是合法的非负整数。举个极端的例子如果输入是1 1 3 2解出来A2B1C0.5C不是整数这组输入就没有合法解应当输出No。正确的做法是解完以后把A、B、C代回四个等式逐一校验同时检查每个等式是否成立、每个数是否为整数。如果输入数据本身不保证能整除也要先判断(y1 y3) % 2这些条件避免出现小数。这道题真正的考点不在解方程而在“检查解的合理性”——这种必须在输出前做回代验证的意识在很多题目里都会用到。2.3 数字翻转别被“反转”两个字绕晕“数字翻转”属于签到题但它的题意描述经常把第一次做的人绕进去。题目给了两个整数x和y让你求rev(rev(x) rev(y))其中rev表示把一个数字倒过来读。比如x123rev(x)321y456rev(y)654rev(x)rev(y)975再rev一次得到579。问题在于很多人会在第一步就多想rev(x)之后可能有前导零吗比如x120rev(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个人间隔有限制乘积最大”。如果能力值全是正数这就是个标准的区间DPdp[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开始遍历就能天然避开一些无意义状态。另一个经验是写完递推后先手动模拟一个很小的用例比如n4、k2、d2在纸上把dp表前几行算一遍再和程序输出对一下。很多边界问题纸上一算就暴露了比反复提交判断要快得多。4. 压轴题的暴力到优雅二分和矩阵快速幂4.1 星际穿越先想数学再决定要不要二分“星际穿越”这个题题面包装得很科幻但剥开之后就是一个数学问题给定一个正整数n求最大的整数x使得x的平方加x不超过n。直接把x从1开始暴力枚举当然能过小数据但n的上限较大的时候枚举就是灾难。解法有三个层次第一层暴力while循环x从1一直试到x*(x1) n。能过样例但在笔试数据下很可能超时。第二层二分答案。x的范围是1到sqrt(n)左右用标准二分找最后一个满足条件的x。这样复杂度是O(log n)非常稳。第三层直接解一元二次方程。x floor((sqrt(1 4n) - 1) / 2)。我推荐第二层因为二分写起来不容易错而且这个模式能迁移到很多“求满足某条件的最大/最小值”问题。注意mid计算时要用long longmid * mid在n比较大的时候很容易溢出int。实现上建议用“左闭右开”或者“答案偏向左侧”的二分写法配合一个会“向下取整”的边界避免死循环。4.2 魔力手环k次操作背后的矩阵加速如果整套题只能选一道题推荐我选“魔力手环”。它基本是这套题集里最能区分水平的一道题。题意大致是手环上有n个数字每次操作会生成一个新序列每个新位置的值等于原序列中该位置和下一个位置的值之和最后一个位置与第一个位置相加操作k次后输出每个数字对100取模的结果。这里的k可以非常大动辄10^9级别直接模拟k轮肯定不可行。这道题的突破点是每次操作本质上是对原序列左乘一个固定的转移矩阵。构造一个n×n矩阵M其中第i行第i列和第(i1) mod n列为1其余为0那么一次操作就是res vector * M。重复k次就是res vector * (M^k)矩阵幂可以用快速幂在O(log k)时间内完成。这就是线性代数和算法的经典结合。void mul(vectorvectorint a, vectorvectorint b, int n) { vectorvectorint c(n, vectorint(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(vectorvectorint mat, long long e) { int n mat.size(); vectorvectorint res(n, vectorint(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状态设计线性DP、计数DP合唱团复杂DP最大/最小双状态DP、区间约束魔力手环高级算法矩阵快速幂、倍增思想这里插一句我的个人体会好多同学刷题喜欢按“题号顺序”往后刷觉得每天刷几道就等于在进步。但真正有效的做法是“按考点刷”比如连续一周只刷DP题再连续一周只刷二分和快速幂让自己在短时间内对同一类题目形成肌肉记忆。网易这套题集恰好是因为它涵盖的考点足够全反而很适合拿来做阶段性的自测而不是按顺序硬刷。最后再分享一个小技巧无论你是用C还是Java笔试前都建议把几个高频模板单独存成一个文件包括快速幂、矩阵乘法、GCD、二分查找、并查集、最短路。不是让你考场上去复制粘贴而是通过临考前手敲一遍把这些模板变成你的条件反射。我在做网易这套题时魔力手环的矩阵快速幂能一次写对就是因为前一天刚把矩阵模板手敲了两遍。这种“肌肉记忆”在紧张的笔试环境下比临时回忆公式要可靠得多。
网易2017秋招编程题集深度拆解：从模拟到矩阵快速幂的算法主线
网易2017秋招编程题集合这份题单在牛客网上流传了好几年到现在还经常被拿出来当作校招笔试的入门材料。我当年第一次完整刷校招编程题用的就是这套题后来帮别人做笔试辅导时又反复带刷过两三轮。它最大的价值在于难度梯度非常典型从读题就能动手的模拟题到需要仔细设计状态的动态规划再到压轴的矩阵快速幂基本覆盖了互联网公司笔试最常考的算法主线。这篇文章不打算把每道题逐个贴一遍毫无营养的答案而是以这套题集为引子把每类题背后的考点、易错点、以及当时真实考场上容易踩的坑都拆开讲清楚。无论你是正在准备秋招的应届生还是想系统补算法的同学这份拆解应该都能帮到你。1. 先说清楚这套题到底在考什么1.1 笔试的“筛人”逻辑不是让你拿满分很多人第一次做这套题会有一个误区以为笔试的目的是“把所有题做完、做对”。实际上像网易这种体量的公司秋招笔试的核心作用是在海量简历里做第一轮筛选题目设计者根本不指望大部分人ACAccepted完全通过。正常情况下一套题里会有两三道送分题、两道需要动脑子的中等题、以及一道只有少数人能完整写出来的压轴题。你只要能稳定拿到前面几道的分再在中等题上撕开一道口子笔试这关基本就稳了。这套2017年的题目正好完美体现了这个设计思路简单题让你拿基础分中档题筛出算法能力压轴题筛出真正的竞赛型选手。1.2 考点分布一条很典型的校招算法主线我按自己的理解把整套题涉及的考点整理了一下题目类型代表考点难度模拟题最大公约数、整数运算、过程模拟入门数学题方程组求解、整数反转、回代验证入门到进阶动态规划状态定义、线性计数DP、乘积最值DP进阶二分搜索数值二分、边界收敛进阶矩阵快速幂矩阵乘法、二进制幂、取模压轴这里面的动态规划和矩阵快速幂是后来几年所有大厂笔试的高频重点。从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、AB、BC让你推出A、B、C。很多人的第一反应是直接解方程小学二年级就会的事情但为什么这题还能有经典一挂因为它考的其实是“验证”。我们先看推导把第一个和第三个等式相加可以得到(A-B) (AB) 2A所以A就是两个数的和除以2。同理第二个和第四个相加得到2B第四个减第二个得到2C。到这里很多人的代码就结束了直接输出A、B、C结果提交之后发现大面积WA。问题出在你计算出来的结果必须满足给定的四个等式而且A、B、C还必须是合法的非负整数。举个极端的例子如果输入是1 1 3 2解出来A2B1C0.5C不是整数这组输入就没有合法解应当输出No。正确的做法是解完以后把A、B、C代回四个等式逐一校验同时检查每个等式是否成立、每个数是否为整数。如果输入数据本身不保证能整除也要先判断(y1 y3) % 2这些条件避免出现小数。这道题真正的考点不在解方程而在“检查解的合理性”——这种必须在输出前做回代验证的意识在很多题目里都会用到。2.3 数字翻转别被“反转”两个字绕晕“数字翻转”属于签到题但它的题意描述经常把第一次做的人绕进去。题目给了两个整数x和y让你求rev(rev(x) rev(y))其中rev表示把一个数字倒过来读。比如x123rev(x)321y456rev(y)654rev(x)rev(y)975再rev一次得到579。问题在于很多人会在第一步就多想rev(x)之后可能有前导零吗比如x120rev(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个人间隔有限制乘积最大”。如果能力值全是正数这就是个标准的区间DPdp[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开始遍历就能天然避开一些无意义状态。另一个经验是写完递推后先手动模拟一个很小的用例比如n4、k2、d2在纸上把dp表前几行算一遍再和程序输出对一下。很多边界问题纸上一算就暴露了比反复提交判断要快得多。4. 压轴题的暴力到优雅二分和矩阵快速幂4.1 星际穿越先想数学再决定要不要二分“星际穿越”这个题题面包装得很科幻但剥开之后就是一个数学问题给定一个正整数n求最大的整数x使得x的平方加x不超过n。直接把x从1开始暴力枚举当然能过小数据但n的上限较大的时候枚举就是灾难。解法有三个层次第一层暴力while循环x从1一直试到x*(x1) n。能过样例但在笔试数据下很可能超时。第二层二分答案。x的范围是1到sqrt(n)左右用标准二分找最后一个满足条件的x。这样复杂度是O(log n)非常稳。第三层直接解一元二次方程。x floor((sqrt(1 4n) - 1) / 2)。我推荐第二层因为二分写起来不容易错而且这个模式能迁移到很多“求满足某条件的最大/最小值”问题。注意mid计算时要用long longmid * mid在n比较大的时候很容易溢出int。实现上建议用“左闭右开”或者“答案偏向左侧”的二分写法配合一个会“向下取整”的边界避免死循环。4.2 魔力手环k次操作背后的矩阵加速如果整套题只能选一道题推荐我选“魔力手环”。它基本是这套题集里最能区分水平的一道题。题意大致是手环上有n个数字每次操作会生成一个新序列每个新位置的值等于原序列中该位置和下一个位置的值之和最后一个位置与第一个位置相加操作k次后输出每个数字对100取模的结果。这里的k可以非常大动辄10^9级别直接模拟k轮肯定不可行。这道题的突破点是每次操作本质上是对原序列左乘一个固定的转移矩阵。构造一个n×n矩阵M其中第i行第i列和第(i1) mod n列为1其余为0那么一次操作就是res vector * M。重复k次就是res vector * (M^k)矩阵幂可以用快速幂在O(log k)时间内完成。这就是线性代数和算法的经典结合。void mul(vectorvectorint a, vectorvectorint b, int n) { vectorvectorint c(n, vectorint(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(vectorvectorint mat, long long e) { int n mat.size(); vectorvectorint res(n, vectorint(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状态设计线性DP、计数DP合唱团复杂DP最大/最小双状态DP、区间约束魔力手环高级算法矩阵快速幂、倍增思想这里插一句我的个人体会好多同学刷题喜欢按“题号顺序”往后刷觉得每天刷几道就等于在进步。但真正有效的做法是“按考点刷”比如连续一周只刷DP题再连续一周只刷二分和快速幂让自己在短时间内对同一类题目形成肌肉记忆。网易这套题集恰好是因为它涵盖的考点足够全反而很适合拿来做阶段性的自测而不是按顺序硬刷。最后再分享一个小技巧无论你是用C还是Java笔试前都建议把几个高频模板单独存成一个文件包括快速幂、矩阵乘法、GCD、二分查找、并查集、最短路。不是让你考场上去复制粘贴而是通过临考前手敲一遍把这些模板变成你的条件反射。我在做网易这套题时魔力手环的矩阵快速幂能一次写对就是因为前一天刚把矩阵模板手敲了两遍。这种“肌肉记忆”在紧张的笔试环境下比临时回忆公式要可靠得多。