1. 为什么2016年的网易编程题到现在还值得拿出来啃先交代一下背景。我前后参加过几次校招技术面试也当过一段时间的笔试阅卷人2016年网易研发工程师这套编程题是我印象里风格非常正的一套。不偏不怪、不炫技每道题都能看出出题人想考察的基本功而且这些基本功到现在依然是研发岗笔试的核心。简单说一下这套题给我的整体感受它不像某些厂的笔试题那样追求偏难怪也不像竞赛题那样需要大量高级数据结构堆积。它更看重的是你能不能把一个实际问题抽象成正确的模型能不能把边界条件处理干净能不能在限定时间内写出可读、可跑的代码。这些能力恰恰是实际工程里最需要的。如果你是正在准备校招的同学或者工作几年后想检验一下自己的基本功有没有退化这套题都值得静下心来完整做一遍。我这次复盘不是简单地把题解贴一遍而是把每道题的思考过程、常见错法、以及从题目里延伸出来的工程经验一起讲清楚。我挑了这套题里最有代表性的四道一道模拟、一道图论搜索、一道动态规划、一道贪心字符串。覆盖了校招笔试最常见的四类题型把这四道吃透比盲目刷两百道题有用得多。2. 从题目看考察面一套题里藏着的四种基本功2.1 模拟题考察的是耐心和细致度第一类典型题是模拟题。这类题不会涉及高深的算法但特别容易在细节上翻车。网易这套题里有道打怪升级的题大意是小易初始有一个能力值按顺序遇到若干个怪物每个怪物有防御力根据当前能力值和怪物防御力的大小关系能力值的增加方式不同最终求打完所有怪物后的能力值。这类题的考察点很明确你能不能把题目的规则准确翻译成逻辑分支。很多人觉得模拟题简单其实恰恰相反模拟题是笔试里最容易因为想当然丢分的题型。你以为你理解了规则但往往漏了某个边界分支。比如怪物防御力等于当前能力值时走哪个分支这种看似无关紧要的等于号在实际代码里就是截然不同的两条路径。2.2 图论搜索题考察的是建模能力第二类是图论搜索题网易这套题里有一道关于从家到公司最短时间的题目涉及步行、公交站、打车多种方式组合。这道题表面看是行程问题本质上是图论里的最短路径问题或者更准确地说是一个带权图的路径规划问题。这种题真正难的不是写BFS或Dijkstra而是你能否意识到它是一道图论题。很多人被公交站打车这些生活化描述绕进去了一直在穷举各种方案却没想到把它抽象成图模型。这就是建模能力的差距。在真实工程里这种能力同样重要——你面对的是一个模糊的业务需求第一步永远是把它抽象成清晰的技术模型而不是急着写代码。2.3 动态规划题考察的是状态定义能力第三类是动态规划题这也是校招笔试的分水岭题型。网易这套题里的合唱团问题非常经典从n个学生里选k个使能力值乘积最大同时要求相邻两个被选学生的编号差不超过d能力值有正有负。动态规划题的核心永远不是转移方程本身而是状态定义。状态定义对了转移方程自然就出来了状态定义错了写再多代码都是白费。这道题还有一个非常关键的坑能力值可能是负数如果只维护最大值负负得正的情况就会被漏掉所以必须同时维护最大值和最小值。这个细节几乎每年都能筛掉一大片人。2.4 贪心与字符串题考察的是简单问题的最优解意识第四类是贪心与字符串处理题网易这套题里有一道关于调整队形的题目一个由B和G组成的字符串通过交换相邻两个字符使得所有B都在G的左边或所有G都在B的左边求最少交换次数。这类题的特点是暴力解法很容易想到但最优解法需要一点贪心直觉。很多人在笔试时会选择模拟冒泡排序这在数据量小的时候能过但一旦数据量变大就会超时。懂得用目标位置偏移量之和来直接计算最少交换次数才是出题人真正想看到的。这种用数学直觉优化暴力解法的意识在工程里的价值不亚于任何高深算法。3. 逐题复盘思路推演、完整代码与易错点警示3.1 打怪升级模拟题的边界处理与递归gcd隐患先看这道打怪升级题。题目我复述一下小易初始能力值为a有n个怪物依次出现防御力分别为b1到bn。如果怪物防御力bi小于等于当前能力值c则打败后能力值增加bi否则能力值只增加bi和c的最大公约数。求最终能力值。核心逻辑并不复杂就是一个循环每一步根据当前能力值和怪物防御力的关系决定能力值增量。但这里有两个非常容易踩的坑。第一个坑是等于号的归属。题目说的是防御力小于等于当前能力值时增加bi有些同学一紧张就写成了小于于是能力值刚好等于怪物防御力时走了另一个分支整个答案就错了。这种等于号错一个结果全错的情况在模拟题里太常见了。第二个坑是求最大公约数时的性能隐患。虽然这道题的数据范围用递归gcd没问题但需要注意如果怪物数量很大而能力值增长很慢gcd的递归深度可能会影响性能。在实际笔试中建议直接用循环实现gcd既避免递归栈溢出风险也比递归更直观。#include cstdio #include algorithm using namespace std; int gcd(int a, int b) { while (b) { int t a % b; a b; b t; } return a; } int main() { int n, a; while (scanf(%d%d, n, a) ! EOF) { for (int i 0; i n; i) { int b; scanf(%d, b); if (b a) a b; else a gcd(a, b); } printf(%d\n, a); } return 0; }这个代码里有一个笔试时特别容易忽略的惯例多组输入。网易这套题的判题系统通常支持多组测试数据所以while (scanf(...) ! EOF)这个写法几乎是必须的。我见过太多同学在本地单测通过结果提交上去就是0分一问才知道根本没写循环读入。这不是算法问题是经验问题。3.2 赶去公司最短路径模型的识别与实现选择这道题的题目描述比较长大意是小易从家到公司可以全程步行也可以先步行到任意一个公交站然后打车去公司。给定了步行速度、出租车速度以及每个公交站距离家的距离和距离公司的距离求最短时间。很多人第一反应是穷举对每个公交站计算步行到站时间 打车到公司时间然后和全程步行时间比大小取最小值。这个思路本身没错因为公交站数量有限穷举完全可行。但如果你能一眼看出这是图论里的最短路问题就能更清晰地理解为什么这样做是对的——本质上每个公交站是一个中转节点我们求的是从家到公司经过至多一个中转节点的最短路径。不过这道题有个细节值得玩味公交站是步行到站还是可以坐公交到站在2016年这道题的设定里小易到公交站只能步行所以每个方案的实际耗时就是步行距离除以步行速度加上剩余距离除以出租车速度。计算时要注意单位统一速度给的是米/分钟距离给的是米直接相除就能得到分钟数。如果用最短路模型来理解家是一个源点每个公交站是一个中间节点公司是终点。从家到公交站的边权是步行时间从公交站到公司的边权是打车时间。因为只能打一次车所以从家到公司至多经过一个中间节点求所有路径中的最小值。这样一看题目就变得非常清晰了。#include cstdio #include vector #include algorithm using namespace std; int main() { int n; while (scanf(%d, n) ! EOF) { vectorint x(n), y(n); for (int i 0; i n; i) scanf(%d, x[i]); for (int i 0; i n; i) scanf(%d, y[i]); int walkSpeed, taxiSpeed; scanf(%d%d, walkSpeed, taxiSpeed); double ans 1e18; for (int i 0; i n; i) { double t (double)x[i] / walkSpeed (double)y[i] / taxiSpeed; ans min(ans, t); } printf(%.2f\n, ans); } return 0; }这个题还有一个隐藏考察点全程步行。有些同学只顾着枚举公交站忘了把全程步行这个方案纳入比较导致答案偏大。这提醒我们读题时一定要把所有可行方案列全一个都不能漏。3.3 合唱团为什么必须同时维护最大和最小合唱团这道题是整套题里区分度最高的一道也是我认为最值得反复咀嚼的一道。题目是有n个学生站成一排每个学生有一个能力值可能为负数现在需要从这n个学生中选出k个学生使得这k个学生的能力值乘积最大并且任意两个相邻被选中的学生的编号之差的绝对值不超过d求最大乘积。这是典型的动态规划问题。状态定义是dpMax[i][j]表示以第i个学生为最后一个人一共选了j个学生时乘积的最大值dpMin[i][j]表示同样的条件下的乘积最小值。为什么需要最小值因为能力值可能是负数而负数乘以负数会变成正数——两个很小的负数相乘可能得到比任何正数乘积都大的结果。如果只维护最大值就会漏掉负负得正这条路径。这个坑在实际笔试中非常经典。统计数据显示绝大多数在合唱团这题上拿不到满分的同学不是不会动态规划而是没有考虑到负数的存在。很多人看到乘积最大就只维护一个最大值数组结果遇到包含偶数个负数的最大乘积组合时直接算错。转移的时候要在满足距离约束的前提下枚举上一个被选中的学生p。也就是说dpMax[i][j]可以由dpMax[p][j-1] * a[i]或dpMin[p][j-1] * a[i]转移而来只要i - p d且p i。枚举p的过程就是动态规划中决策的部分。#include cstdio #include algorithm using namespace std; const long long NEG_INF -1e18; int main() { int n; scanf(%d, n); long long a[55]; for (int i 1; i n; i) scanf(%lld, a[i]); int k, d; scanf(%d%d, k, d); long long dpMax[55][15], dpMin[55][15]; for (int i 0; i n; i) for (int j 0; j k; j) dpMax[i][j] NEG_INF, dpMin[i][j] NEG_INF; for (int i 1; i n; i) { dpMax[i][1] a[i]; dpMin[i][1] a[i]; } for (int j 2; j k; j) { for (int i j; i n; i) { for (int p max(1, i - d); p i; 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])); } } } long long ans NEG_INF; for (int i k; i n; i) ans max(ans, dpMax[i][k]); printf(%lld\n, ans); return 0; }我特别想强调这个状态转移里的一个细节枚举p的时候起点是max(1, i - d)而不是1。这是距离约束的直接体现也是很多人容易写错的地方。如果你把p的枚举范围写成了1到i-1那么当数据中出现超过距离限制的组合时你的答案就会偏大——因为你在考虑一个实际上不合法的方案。笔试时这种错误非常隐蔽因为小数据测试可能正好不触发这个约束。3.4 调整队形从冒泡排序到贪心计算的思维跃迁这道题的题目很短一个由B和G组成的字符串每次可以交换相邻两个字符求最少交换多少次能让所有B都在G的左边或者所有G都在B的左边。暴力的做法是模拟冒泡排序把目标顺序当作最终状态统计相邻交换次数。这个思路对但效率不高而且代码写起来很容易出错。更聪明的方法是直接计算。以所有B都在G左边为目标为例从左到右扫描字符串用一个计数器记录已经遇到的B的数量。每遇到一个B它最终应该待的位置是已经排好的B之后所以它需要移动的次数是当前索引 - 已经遇到的B的数量。把所有B的移动次数加总就是最少交换次数。为什么这个计算是对的因为交换相邻两个字符本质上就是让每个字符向目标位置穿过其他字符。B向左移动时每穿过一个G就消耗一次交换。所以总交换次数等于所有B需要穿过的G的总数也就是每个B的目标位置与当前位置的偏移量之和。#include cstdio #include cstring #include algorithm using namespace std; int minSwapToBLeft(char* s) { int len strlen(s); int bCount 0; int swaps 0; for (int i 0; i len; i) { if (s[i] B) { swaps i - bCount; bCount; } } return swaps; } int minSwapToGLeft(char* s) { int len strlen(s); int gCount 0; int swaps 0; for (int i 0; i len; i) { if (s[i] G) { swaps i - gCount; gCount; } } return swaps; } int main() { char s[55]; while (scanf(%s, s) ! EOF) { int ans min(minSwapToBLeft(s), minSwapToGLeft(s)); printf(%d\n, ans); } return 0; }这个题让我想起很多工程里的看似需要复杂操作其实可以用数学直接求解的场景。就像重构一段混乱的代码看起来很复杂但如果你能识别出核心的复杂度来源往往能用一个简单的公式或者结构调整直接解决而不是绕着一大圈修补。4. 这些题目背后真正想考察的工程素养4.1 输入输出的稳定性笔试里最不值钱的失分点我在前面反复提到多组输入的问题这里再展开说说。网易2016年的判题系统一组输入是一整套测试数据程序需要对每组数据都做出正确输出。很多同学本地测试时只跑了一组数据没有写while(scanf(...) ! EOF)这种循环读入的写法结果提交后只能通过部分用例白白丢分。这个问题在真实工程里也有对应你的服务上线后不可能只处理一个请求。如果代码只能处理一组数据就退出放在工程里就是只能跑一次就挂了的脚本。所以从笔试阶段就养成处理多组输入的习惯本质上是在培养写可复用代码的意识。4.2 复杂度的预判为什么调整队形不能无脑冒泡有些同学会说调整队形这道题我直接模拟冒泡排序一样能过啊。没错在小数据范围内确实能过。但如果你看一眼数据范围n可能在几千甚至几万冒泡排序的O(n^2)复杂度就会超时。这就引出了一个非常重要的工程素养在动手写代码之前先估算一下你的算法在最大数据范围内能不能跑完。笔试通常限时1到2秒如果你的算法复杂度是O(n^2)而n是10^5那基本就是超时。这种先估算再动手的习惯在真实工程里同样关键——尤其在处理大规模数据时一个低效的算法可能导致线上服务响应缓慢甚至雪崩。4.3 边界条件的敏感度从合唱团的负数到打怪升级的等于号如果让我总结这套题最大的价值那就是它集中训练了你对边界条件的敏感度。合唱团题里能力值可能是负数的设定、打怪升级题里等号归属的细节、赶去公司题里全程步行这个容易被忽略的方案——每一个都是看起来不起眼但错了就全错的典型。这种敏感度怎么训练只有一个办法多踩坑然后把坑记录下来。我在刷题初期也经常在这些地方翻车后来养成一个习惯——每道题AC之后再想想如果数据里出现负数、零、重复值、边界最大值我的代码还能不能跑对然后故意构造这些测试用例去试自己的代码。这个习惯基本覆盖了我在笔试和面试中遇到的绝大多数边界问题。5. 以这套题为镜校招备考到底该怎样刷题说实话我不太建议一上来就追求刷题数量。你把这道2016网易研发工程师编程题做透比囫囵吞枣刷五十道题更有价值。什么叫做透不是AC了就完事而是做完之后能回答这几个问题这道题用了什么算法这个算法为什么适用如果数据范围扩大十倍还能不能跑如果条件稍作修改比如合唱团里把乘积改成和解法要怎么变这套题覆盖的四种题型——模拟、图论搜索、动态规划、贪心字符串——正是校招笔试里最高频的四种类型。把这四种题型的基本功练扎实胜过去背一百道模板题。我的建议是分专题刷题每个专题先做两三道经典题然后总结归纳这一类题的通用解题框架。比如动态规划题你做完合唱团之后应该总结出先定义状态、再写转移方程、最后初始化的标准流程以及如果数据有负数要考虑维护最大值和最小值这类重要经验。当你把每个专题的套路都沉淀成自己的笔记再遇到新题时就能更快地识别出它属于哪个专题进而调用对应的解题框架。作为经历过校招、也作为面试官看过不少候选人笔试表现的人我想说一句真心话笔试成绩好的人往往不是刷题最多的而是总结最到位、基础最扎实的。2016年的网易题放到今天来看依然是一套非常优秀的基本功体检题。如果你能把这四道题完全吃透并且理解了它们背后的考察逻辑那你的校招笔试就已经有了一个非常扎实的起点。剩下的就是在一次次实战中不断验证和修正自己的解题框架而已。
网易2016研发工程师编程题复盘：四大经典题型解析
1. 为什么2016年的网易编程题到现在还值得拿出来啃先交代一下背景。我前后参加过几次校招技术面试也当过一段时间的笔试阅卷人2016年网易研发工程师这套编程题是我印象里风格非常正的一套。不偏不怪、不炫技每道题都能看出出题人想考察的基本功而且这些基本功到现在依然是研发岗笔试的核心。简单说一下这套题给我的整体感受它不像某些厂的笔试题那样追求偏难怪也不像竞赛题那样需要大量高级数据结构堆积。它更看重的是你能不能把一个实际问题抽象成正确的模型能不能把边界条件处理干净能不能在限定时间内写出可读、可跑的代码。这些能力恰恰是实际工程里最需要的。如果你是正在准备校招的同学或者工作几年后想检验一下自己的基本功有没有退化这套题都值得静下心来完整做一遍。我这次复盘不是简单地把题解贴一遍而是把每道题的思考过程、常见错法、以及从题目里延伸出来的工程经验一起讲清楚。我挑了这套题里最有代表性的四道一道模拟、一道图论搜索、一道动态规划、一道贪心字符串。覆盖了校招笔试最常见的四类题型把这四道吃透比盲目刷两百道题有用得多。2. 从题目看考察面一套题里藏着的四种基本功2.1 模拟题考察的是耐心和细致度第一类典型题是模拟题。这类题不会涉及高深的算法但特别容易在细节上翻车。网易这套题里有道打怪升级的题大意是小易初始有一个能力值按顺序遇到若干个怪物每个怪物有防御力根据当前能力值和怪物防御力的大小关系能力值的增加方式不同最终求打完所有怪物后的能力值。这类题的考察点很明确你能不能把题目的规则准确翻译成逻辑分支。很多人觉得模拟题简单其实恰恰相反模拟题是笔试里最容易因为想当然丢分的题型。你以为你理解了规则但往往漏了某个边界分支。比如怪物防御力等于当前能力值时走哪个分支这种看似无关紧要的等于号在实际代码里就是截然不同的两条路径。2.2 图论搜索题考察的是建模能力第二类是图论搜索题网易这套题里有一道关于从家到公司最短时间的题目涉及步行、公交站、打车多种方式组合。这道题表面看是行程问题本质上是图论里的最短路径问题或者更准确地说是一个带权图的路径规划问题。这种题真正难的不是写BFS或Dijkstra而是你能否意识到它是一道图论题。很多人被公交站打车这些生活化描述绕进去了一直在穷举各种方案却没想到把它抽象成图模型。这就是建模能力的差距。在真实工程里这种能力同样重要——你面对的是一个模糊的业务需求第一步永远是把它抽象成清晰的技术模型而不是急着写代码。2.3 动态规划题考察的是状态定义能力第三类是动态规划题这也是校招笔试的分水岭题型。网易这套题里的合唱团问题非常经典从n个学生里选k个使能力值乘积最大同时要求相邻两个被选学生的编号差不超过d能力值有正有负。动态规划题的核心永远不是转移方程本身而是状态定义。状态定义对了转移方程自然就出来了状态定义错了写再多代码都是白费。这道题还有一个非常关键的坑能力值可能是负数如果只维护最大值负负得正的情况就会被漏掉所以必须同时维护最大值和最小值。这个细节几乎每年都能筛掉一大片人。2.4 贪心与字符串题考察的是简单问题的最优解意识第四类是贪心与字符串处理题网易这套题里有一道关于调整队形的题目一个由B和G组成的字符串通过交换相邻两个字符使得所有B都在G的左边或所有G都在B的左边求最少交换次数。这类题的特点是暴力解法很容易想到但最优解法需要一点贪心直觉。很多人在笔试时会选择模拟冒泡排序这在数据量小的时候能过但一旦数据量变大就会超时。懂得用目标位置偏移量之和来直接计算最少交换次数才是出题人真正想看到的。这种用数学直觉优化暴力解法的意识在工程里的价值不亚于任何高深算法。3. 逐题复盘思路推演、完整代码与易错点警示3.1 打怪升级模拟题的边界处理与递归gcd隐患先看这道打怪升级题。题目我复述一下小易初始能力值为a有n个怪物依次出现防御力分别为b1到bn。如果怪物防御力bi小于等于当前能力值c则打败后能力值增加bi否则能力值只增加bi和c的最大公约数。求最终能力值。核心逻辑并不复杂就是一个循环每一步根据当前能力值和怪物防御力的关系决定能力值增量。但这里有两个非常容易踩的坑。第一个坑是等于号的归属。题目说的是防御力小于等于当前能力值时增加bi有些同学一紧张就写成了小于于是能力值刚好等于怪物防御力时走了另一个分支整个答案就错了。这种等于号错一个结果全错的情况在模拟题里太常见了。第二个坑是求最大公约数时的性能隐患。虽然这道题的数据范围用递归gcd没问题但需要注意如果怪物数量很大而能力值增长很慢gcd的递归深度可能会影响性能。在实际笔试中建议直接用循环实现gcd既避免递归栈溢出风险也比递归更直观。#include cstdio #include algorithm using namespace std; int gcd(int a, int b) { while (b) { int t a % b; a b; b t; } return a; } int main() { int n, a; while (scanf(%d%d, n, a) ! EOF) { for (int i 0; i n; i) { int b; scanf(%d, b); if (b a) a b; else a gcd(a, b); } printf(%d\n, a); } return 0; }这个代码里有一个笔试时特别容易忽略的惯例多组输入。网易这套题的判题系统通常支持多组测试数据所以while (scanf(...) ! EOF)这个写法几乎是必须的。我见过太多同学在本地单测通过结果提交上去就是0分一问才知道根本没写循环读入。这不是算法问题是经验问题。3.2 赶去公司最短路径模型的识别与实现选择这道题的题目描述比较长大意是小易从家到公司可以全程步行也可以先步行到任意一个公交站然后打车去公司。给定了步行速度、出租车速度以及每个公交站距离家的距离和距离公司的距离求最短时间。很多人第一反应是穷举对每个公交站计算步行到站时间 打车到公司时间然后和全程步行时间比大小取最小值。这个思路本身没错因为公交站数量有限穷举完全可行。但如果你能一眼看出这是图论里的最短路问题就能更清晰地理解为什么这样做是对的——本质上每个公交站是一个中转节点我们求的是从家到公司经过至多一个中转节点的最短路径。不过这道题有个细节值得玩味公交站是步行到站还是可以坐公交到站在2016年这道题的设定里小易到公交站只能步行所以每个方案的实际耗时就是步行距离除以步行速度加上剩余距离除以出租车速度。计算时要注意单位统一速度给的是米/分钟距离给的是米直接相除就能得到分钟数。如果用最短路模型来理解家是一个源点每个公交站是一个中间节点公司是终点。从家到公交站的边权是步行时间从公交站到公司的边权是打车时间。因为只能打一次车所以从家到公司至多经过一个中间节点求所有路径中的最小值。这样一看题目就变得非常清晰了。#include cstdio #include vector #include algorithm using namespace std; int main() { int n; while (scanf(%d, n) ! EOF) { vectorint x(n), y(n); for (int i 0; i n; i) scanf(%d, x[i]); for (int i 0; i n; i) scanf(%d, y[i]); int walkSpeed, taxiSpeed; scanf(%d%d, walkSpeed, taxiSpeed); double ans 1e18; for (int i 0; i n; i) { double t (double)x[i] / walkSpeed (double)y[i] / taxiSpeed; ans min(ans, t); } printf(%.2f\n, ans); } return 0; }这个题还有一个隐藏考察点全程步行。有些同学只顾着枚举公交站忘了把全程步行这个方案纳入比较导致答案偏大。这提醒我们读题时一定要把所有可行方案列全一个都不能漏。3.3 合唱团为什么必须同时维护最大和最小合唱团这道题是整套题里区分度最高的一道也是我认为最值得反复咀嚼的一道。题目是有n个学生站成一排每个学生有一个能力值可能为负数现在需要从这n个学生中选出k个学生使得这k个学生的能力值乘积最大并且任意两个相邻被选中的学生的编号之差的绝对值不超过d求最大乘积。这是典型的动态规划问题。状态定义是dpMax[i][j]表示以第i个学生为最后一个人一共选了j个学生时乘积的最大值dpMin[i][j]表示同样的条件下的乘积最小值。为什么需要最小值因为能力值可能是负数而负数乘以负数会变成正数——两个很小的负数相乘可能得到比任何正数乘积都大的结果。如果只维护最大值就会漏掉负负得正这条路径。这个坑在实际笔试中非常经典。统计数据显示绝大多数在合唱团这题上拿不到满分的同学不是不会动态规划而是没有考虑到负数的存在。很多人看到乘积最大就只维护一个最大值数组结果遇到包含偶数个负数的最大乘积组合时直接算错。转移的时候要在满足距离约束的前提下枚举上一个被选中的学生p。也就是说dpMax[i][j]可以由dpMax[p][j-1] * a[i]或dpMin[p][j-1] * a[i]转移而来只要i - p d且p i。枚举p的过程就是动态规划中决策的部分。#include cstdio #include algorithm using namespace std; const long long NEG_INF -1e18; int main() { int n; scanf(%d, n); long long a[55]; for (int i 1; i n; i) scanf(%lld, a[i]); int k, d; scanf(%d%d, k, d); long long dpMax[55][15], dpMin[55][15]; for (int i 0; i n; i) for (int j 0; j k; j) dpMax[i][j] NEG_INF, dpMin[i][j] NEG_INF; for (int i 1; i n; i) { dpMax[i][1] a[i]; dpMin[i][1] a[i]; } for (int j 2; j k; j) { for (int i j; i n; i) { for (int p max(1, i - d); p i; 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])); } } } long long ans NEG_INF; for (int i k; i n; i) ans max(ans, dpMax[i][k]); printf(%lld\n, ans); return 0; }我特别想强调这个状态转移里的一个细节枚举p的时候起点是max(1, i - d)而不是1。这是距离约束的直接体现也是很多人容易写错的地方。如果你把p的枚举范围写成了1到i-1那么当数据中出现超过距离限制的组合时你的答案就会偏大——因为你在考虑一个实际上不合法的方案。笔试时这种错误非常隐蔽因为小数据测试可能正好不触发这个约束。3.4 调整队形从冒泡排序到贪心计算的思维跃迁这道题的题目很短一个由B和G组成的字符串每次可以交换相邻两个字符求最少交换多少次能让所有B都在G的左边或者所有G都在B的左边。暴力的做法是模拟冒泡排序把目标顺序当作最终状态统计相邻交换次数。这个思路对但效率不高而且代码写起来很容易出错。更聪明的方法是直接计算。以所有B都在G左边为目标为例从左到右扫描字符串用一个计数器记录已经遇到的B的数量。每遇到一个B它最终应该待的位置是已经排好的B之后所以它需要移动的次数是当前索引 - 已经遇到的B的数量。把所有B的移动次数加总就是最少交换次数。为什么这个计算是对的因为交换相邻两个字符本质上就是让每个字符向目标位置穿过其他字符。B向左移动时每穿过一个G就消耗一次交换。所以总交换次数等于所有B需要穿过的G的总数也就是每个B的目标位置与当前位置的偏移量之和。#include cstdio #include cstring #include algorithm using namespace std; int minSwapToBLeft(char* s) { int len strlen(s); int bCount 0; int swaps 0; for (int i 0; i len; i) { if (s[i] B) { swaps i - bCount; bCount; } } return swaps; } int minSwapToGLeft(char* s) { int len strlen(s); int gCount 0; int swaps 0; for (int i 0; i len; i) { if (s[i] G) { swaps i - gCount; gCount; } } return swaps; } int main() { char s[55]; while (scanf(%s, s) ! EOF) { int ans min(minSwapToBLeft(s), minSwapToGLeft(s)); printf(%d\n, ans); } return 0; }这个题让我想起很多工程里的看似需要复杂操作其实可以用数学直接求解的场景。就像重构一段混乱的代码看起来很复杂但如果你能识别出核心的复杂度来源往往能用一个简单的公式或者结构调整直接解决而不是绕着一大圈修补。4. 这些题目背后真正想考察的工程素养4.1 输入输出的稳定性笔试里最不值钱的失分点我在前面反复提到多组输入的问题这里再展开说说。网易2016年的判题系统一组输入是一整套测试数据程序需要对每组数据都做出正确输出。很多同学本地测试时只跑了一组数据没有写while(scanf(...) ! EOF)这种循环读入的写法结果提交后只能通过部分用例白白丢分。这个问题在真实工程里也有对应你的服务上线后不可能只处理一个请求。如果代码只能处理一组数据就退出放在工程里就是只能跑一次就挂了的脚本。所以从笔试阶段就养成处理多组输入的习惯本质上是在培养写可复用代码的意识。4.2 复杂度的预判为什么调整队形不能无脑冒泡有些同学会说调整队形这道题我直接模拟冒泡排序一样能过啊。没错在小数据范围内确实能过。但如果你看一眼数据范围n可能在几千甚至几万冒泡排序的O(n^2)复杂度就会超时。这就引出了一个非常重要的工程素养在动手写代码之前先估算一下你的算法在最大数据范围内能不能跑完。笔试通常限时1到2秒如果你的算法复杂度是O(n^2)而n是10^5那基本就是超时。这种先估算再动手的习惯在真实工程里同样关键——尤其在处理大规模数据时一个低效的算法可能导致线上服务响应缓慢甚至雪崩。4.3 边界条件的敏感度从合唱团的负数到打怪升级的等于号如果让我总结这套题最大的价值那就是它集中训练了你对边界条件的敏感度。合唱团题里能力值可能是负数的设定、打怪升级题里等号归属的细节、赶去公司题里全程步行这个容易被忽略的方案——每一个都是看起来不起眼但错了就全错的典型。这种敏感度怎么训练只有一个办法多踩坑然后把坑记录下来。我在刷题初期也经常在这些地方翻车后来养成一个习惯——每道题AC之后再想想如果数据里出现负数、零、重复值、边界最大值我的代码还能不能跑对然后故意构造这些测试用例去试自己的代码。这个习惯基本覆盖了我在笔试和面试中遇到的绝大多数边界问题。5. 以这套题为镜校招备考到底该怎样刷题说实话我不太建议一上来就追求刷题数量。你把这道2016网易研发工程师编程题做透比囫囵吞枣刷五十道题更有价值。什么叫做透不是AC了就完事而是做完之后能回答这几个问题这道题用了什么算法这个算法为什么适用如果数据范围扩大十倍还能不能跑如果条件稍作修改比如合唱团里把乘积改成和解法要怎么变这套题覆盖的四种题型——模拟、图论搜索、动态规划、贪心字符串——正是校招笔试里最高频的四种类型。把这四种题型的基本功练扎实胜过去背一百道模板题。我的建议是分专题刷题每个专题先做两三道经典题然后总结归纳这一类题的通用解题框架。比如动态规划题你做完合唱团之后应该总结出先定义状态、再写转移方程、最后初始化的标准流程以及如果数据有负数要考虑维护最大值和最小值这类重要经验。当你把每个专题的套路都沉淀成自己的笔记再遇到新题时就能更快地识别出它属于哪个专题进而调用对应的解题框架。作为经历过校招、也作为面试官看过不少候选人笔试表现的人我想说一句真心话笔试成绩好的人往往不是刷题最多的而是总结最到位、基础最扎实的。2016年的网易题放到今天来看依然是一套非常优秀的基本功体检题。如果你能把这四道题完全吃透并且理解了它们背后的考察逻辑那你的校招笔试就已经有了一个非常扎实的起点。剩下的就是在一次次实战中不断验证和修正自己的解题框架而已。