刷过牛客网“网易2017内推笔试编程题合集二”的人应该都有同感前面几道像下厨房、藏宝图五分钟就能交卷后面撞上合唱团、幸运的袋子、魔力手环脑子就开始不够用了。这套题收录的是网易当年内推批次的在线笔试真题覆盖动态规划、深搜剪枝、BFS、矩阵快速幂这些高频考点难度梯度拉得很开。不管你是正在准备校招的应届生还是想系统练算法的大二大三学生把它当作一场模拟考来做价值比零散刷题高得多。这篇文章我挑其中四道最有代表性的题逐层拆解剩下的送分题也会一起讲清楚顺便聊聊面对这种“看起来简单、AC率不高”的题目到底该怎么分配那几十分钟。1. 从这套题看网易笔试的选题偏好和时间分配1.1 整套题的难度分布与算法地图“合集二”这套题最典型的特点是把简单题和难题混在一起不给你任何难度提示。按照常见收录版本题目大致可以分成这么几个档位题目核心考点难度下厨房集合去重 / 哈希表送分藏宝图字符串子序列匹配送分星际穿越数学 / 二分答案简单数列还原全排列 预处理统计中等地牢逃脱BFS 最短路径中等合唱团动态规划最大值与最小值同时维护较难幸运的袋子DFS 剪枝较难魔力手环矩阵快速幂较难认真看这份列表你会发现问题网易笔试的知识点并不偏动态规划、搜索、图论、数学、字符串都是常规内容但它在常规知识上加了很刁钻的条件。合唱团里可正可负的能力值、幸运的袋子里“和大于积”的反直觉判断、地牢逃脱里出口判定细节每一个都能让只会背模板的人直接翻车。所以这套题考的不是“你知不知道 BFS”而是“你能否在紧张状态下把 BFS 用对”。1.2 我的作答顺序策略我刷完整套题之后最大的感触是按题目顺序做是最亏的。前面几道简单题会给你一种“今天状态很好”的错觉然后在合唱团上卡 20 分钟导致后面的地牢逃脱和魔力手环连读题时间都不够。合理的策略是先花 3 分钟把所有题目扫一遍划出两道送分题下厨房、藏宝图立刻做掉稳一稳心态。然后做星际穿越和数列还原这种模型清晰、思路固定但需要一点计算量的题。接下来处理地牢逃脱和合唱团。最后剩多少时间都给魔力手环和幸运的袋子——如果 15 分钟内没有明确思路果断放弃把自己会的部分写上去哪怕只过掉一部分用例也比交白卷强。这套做题节奏说起来简单实际执行时很容易被“再想五分钟就能想出来”的心理带偏。我的经验是定一个硬性闹钟每道题最多 15 分钟到点没进展就跳。笔试不是竞赛拿分效率远比单题死磕重要。2. 合唱团乘积最大子序列的动态规划问题2.1 题目理解与朴素思路为什么不行合唱团这题给你的是一排学生每个学生有一个能力值能力值可以是正数也可以是负数。要求从 n 个学生里选出 k 个使得这 k 个学生的能力值乘积最大并且相邻两个被选中的学生在原序列中的编号差不能超过 d。很多人第一反应是“把所有能力值排序取最大的 k 个相乘”。这个想法有两个致命问题。一是题目要求相邻被选学生的编号差不超过 d排序之后位置关系全乱了原先后面的学生可能被排到前面距离约束根本没法保证。二是能力值有正有负比如能力值是 -5 和 -3两个负数相乘得到 15比很多正数组合都大。如果只用“取最大的几个”会把负数直接排除恰好丢掉负负得正的最优解。所以这题必须用动态规划而且状态设计要同时考虑正负两个方向。我之前第一次做的时候只维护了“以某个学生结尾选 j 个人的最大乘积”样例能过一到负数的测试用例就挂。就是因为没想清楚负数乘法的符号翻转问题。2.2 dp 状态设计与转移方程推演先定义状态dpMax[i][j]表示以第 i 个学生作为最后一个被选中的学生一共选了 j 个学生时能得到的最大乘积。dpMin[i][j]表示以第 i 个学生作为最后一个被选中的学生一共选了 j 个学生时能得到的最小乘积。为什么一定要两个数组因为当前的a[i]可能是负数。如果上一个状态是一个很大的正数乘以负数会变成很大的负数反之如果上一个状态是一个很小的负数乘以负数反而会变成很大的正数。所以转移时必须同时考虑上一个状态的最大值和最小值。转移方程可以写成dpMax[i][j] max( dpMax[p][j-1] * a[i], dpMin[p][j-1] * a[i] ) dpMin[i][j] min( dpMax[p][j-1] * a[i], dpMin[p][j-1] * a[i] )其中p是所有满足max(j-1, i-d) p i的下标。这个范围的含义是前一个被选中的学生必须在 i 前面且与 i 的距离不超过 d。同时要选 j-1 个人最后一个人下标至少是 j-1所以下界取max(j-1, i-d)可以顺便跳过那些不合法的小状态。边界条件很简单每个学生单独选 1 个人的时候dpMax[i][1] dpMin[i][1] a[i]。最后答案就是所有dpMax[i][k]的最大值。2.3 一个容易忽略的边界细节除了负数还要注意结果可能非常大。学生能力值的绝对值可能到很大选 10 个人连乘之后直接超出 int 范围。我习惯无脑用long long初始化用-INF和INF不要用INT_MIN去乘否则整型溢出会变成 undefined behavior。另外转移循环里别偷懒从i-d开始枚举。如果p j-1说明以 p 结尾不可能选出 j-1 个人dpMax[p][j-1]还停留在初始化的无穷小值直接拿它去乘a[i]轻则算错重则溢出。从max(j-1, i-d)开始枚举既保证状态合法又能少算几轮。2.4 完整实现#include bits/stdc.h using namespace std; typedef long long ll; const ll INF 0x3f3f3f3f3f3f3f3fLL; int main() { int n, k, d; while (cin n) { vectorll a(n 1); for (int i 1; i n; i) cin a[i]; cin k d; vectorvectorll dpMax(n 1, vectorll(k 1, -INF)); vectorvectorll dpMin(n 1, vectorll(k 1, 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(j - 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])); } } } ll ans -INF; for (int i k; i n; i) ans max(ans, dpMax[i][k]); cout ans endl; } return 0; }复杂度是 O(n * k * d)n 不超过 50完全够用。3. 幸运的袋子深搜剪枝到底剪在哪里3.1 题目目标和暴力枚举的代价袋子里有 n 个球每个球上有一个正整数。如果一个袋子中所有球上的数字之和大于这些数字的乘积就称它是幸运的。你可以从袋子中丢掉一些球也可以一个都不丢问一共有多少种不同的幸运袋子。相同数字组成的袋子只算一种。暴力思路是枚举所有子集判断每个子集是否满足sum mul。集合大小为 n 时子集数是 2^nn 稍微大一点直接爆炸。这道题如果没有剪枝基本只能过 n 20 的弱数据。而网易给的 n 可以到 1000 甚至更高必须想清楚剪枝条件。3.2 排序之后为什么可以果断 break核心思路是把球按数字从小到大排序然后 DFS 枚举组合。每进入一个状态维护当前已经选中的球的sum和mul然后尝试加入下一个球。关键判断在这里如果当前状态已经出现了sum mul那么继续加入后面的球还有没有可能变成sum mul我们先考虑一般情况也就是当前准备加入的球上的数字大于 1。排序后后面所有球都不小于当前这个球。加入一个正数会让sum增加这个数本身而mul变成原来的mul * x。当mul已经大于sum时每乘一个大于 1 的数乘积的增长速度远超线性增加的速度差距只会越拉越大不可能翻盘。所以一旦遇到sum mul当前分支可以直接 break连后面的数都不用看了。但这里有个特殊情况数字 1。乘 1 不会改变mul但sum会加 1也就是说加入 1 反而可能让一个不幸运的袋子变得幸运。比如集合 {2}sum2mul2恰好相等不幸运再加入一个 1变成 {2,1}sum3 mul2就幸运了。因为排序后 1 会排在最前面DFS 时 1 都是先被处理的但只要做好判断遇到 1 时不能直接 break要继续递归。3.3 去重逻辑与代码实现题目说“相同数字组成的袋子只算一种”所以 DFS 时要做去重在同一层循环里如果当前数字和上一个数字相同就跳过。这个去重去掉的是重复的枚举分支不影响正确性。#include bits/stdc.h using namespace std; typedef long long ll; int n; vectorint a; ll ans 0; void dfs(int idx, ll sum, ll mul) { if (idx n) return; for (int i idx; i n; i) { if (i idx a[i] a[i - 1]) continue; ll ns sum a[i]; ll nm mul * a[i]; if (ns nm) { ans; dfs(i 1, ns, nm); } else if (a[i] 1) { // 1 不改变乘积但增加和后续可能让状态变幸运 dfs(i 1, ns, nm); } else { // 后面的数都不小于当前数差距只会越来越大 break; } } } int main() { cin n; a.resize(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); dfs(0, 0, 1); cout ans endl; return 0; }这里的初始mul设为 1sum设为 0因为没有选任何球时乘积为单位元 1。空集本身不算幸运袋子所以只有选入第一个球后满足ns nm才会ans空集不会被计数这个细节是安全的。另外需要提醒的是如果你的题面把相同数字的球视为不同个体也就是按球的编号计数那就把if (i idx a[i] a[i - 1]) continue;这一行去掉。不同题目口径不同刷题时一定要先看清楚。4. 地