2017春招笔试真题编程题复盘：从排序到动态规划

最近整理刷题仓库的时候，把某度2017春招笔试真题编程题集合重新撸了一遍。这套题是我当年准备春招时反复练过的一个合集，提交记录里的 ID 还留着：Apare_xzc。现在回头看，这套题最好的地方在于覆盖面非常典型：排序、模拟、枚举、贪心、动态规划全都有，难度也从一个简单到中等，适合正处于笔试冲刺期的同学拿来当“体检题”。如果你准备参加校招或者找暑期实习，又没太多时间刷海量题目，我建议你花一到两周把这套题吃透，效果比漫无目的刷几十道要实在得多。

很多刚接触笔试的人会误以为春招真题都是难题，实际并不是。这套题里真正需要绕几个弯的题目大概只有三分之一，剩下的更像是“能不能写对边界条件”的考察。换句话说，笔试除了考算法思维，更多是考你有没有把一道题做完整、做严谨。这也是我写这篇复盘的原因：把每一道值得展开的题掰开揉碎，讲讲我当时是怎么想的，中间踩过哪些坑，以及最后稳定通过测试的写法。

1. 这套题是什么：写在刷题之前

1.1 题目背景与适合人群

某度2017春招笔试真题编程题集合，本质上是一套面向应届生的在线笔试题目合集。它不像竞赛题那样烧脑，也不像课后作业那样简单，而是非常典型的“校招笔试题”：每道题都有明确输入输出约束，难度控制在大多数计算机专业学生能在一小时内完成两三道的水平。我当时刷它的目的很简单，就是想验证自己准备得够不够，结果发现第一遍做的时候，好几道题都在小细节上翻车，比如数组越界、浮点数精度、去重逻辑理解错。

这套题适合三类人：第一类是即将参加春招或暑期实习笔试的应届生，用来查漏补缺；第二类是刚开始刷题、想建立笔试节奏感的人，可以先通过这套题感受真实笔试难度；第三类是已经有一定刷题量，但总在边界条件上丢分的人，这套题里大量隐藏的“坑”非常适合用来训练严谨性。如果你已经是竞赛水平，这套题可能偏简单，但仍然可以快速过一遍，就当热身。

1.2 整体题型分布与难度画像

整个集合里我印象比较深的题目大概有五六道，知识点分布大致可以拆成下面这个表。注意，这里不是官方题单，是我根据自己的训练记录重新整理的，原题顺序和具体题号可能和网上流传的版本有差异，但不影响练习价值。

这套题的难度曲线并不是完全递增的，中间突然出现动态规划，很容易让人心态波动。我第一遍做的时候，习惯从第一题顺序做，结果在“有趣的排序”那题卡了很久，后来学乖了：先整体扫一遍题目，把容易拿分的题先做掉，再集中啃难题。这个策略在真实笔试里非常有用，建议你现在就养成习惯。

1.3 我为什么选这套题来练

说实话，市面上编程题合集非常多，但很多合集要么太偏竞赛，要么就是简单到没营养。这套题吸引我的地方在于它“刚好卡在笔试水位线上”。所谓笔试水位线，就是说题目能一眼看出解法，但实现起来总有那么一两个细节在等着你。比如“买帽子”看似只是排序，但如果把“第K便宜的价格”理解错，去不去重就是完全不同的答案。这种题对思维严谨性的考察，比难题更贴近真实笔试。

另外，这套题还有一个隐藏价值：它涉及到的算法组合很标准。枚举、排序、贪心、DP、几何，这些正好是技术岗笔试的高频模型。我把这套题刷熟之后，再去打其他公司的模拟笔试，明显感觉遇到类似题型时反应速度快了很多。所以对我来说，它不只是应付某一场笔试，更像是一套“算法基础体检套餐”。

2. 题型拆解：从暴力到最优

2.1 买帽子：排序题的两种理解

先说说最简单的一道“买帽子”。题意大致是：商场里有N顶帽子，有些帽子价格相同，现在想知道第K便宜的价格是多少元，如果不存在就输出-1。这道题如果只看前半句，很多人第一反应是排序后直接输出第K个元素，比如sort完之后取a[k-1]。

但这里有个关键陷阱：“第K便宜的价格”到底要不要去重？如果价格相同的帽子算同一个“价格档位”，那要去重后再取第K个；如果算不同帽子，那直接按下标取。原题意更接近前者，因为问的是“价格”，不是“帽子”。我第一次做的时候没有去重，样例能过，但换一组测试数据就错了，就是因为对“价格”这个关键词理解不到位。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; int k; cin >> k; sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); if (k <= 0 || k > (int)a.size()) cout << -1 << '\n'; else cout << a[k - 1] << '\n'; return 0; }

这里的sort加unique是C++里非常经典的去重组合。sort把相同元素聚在一起，unique把相邻重复元素移到末尾并返回新结尾迭代器，再用erase去掉尾巴。需要注意unique只去除“相邻重复”，所以必须先排序。另外，k可能小于等于0，虽然题目通常保证k是正整数，但笔试输入偶尔会玩文字游戏，我习惯性把非法k也判掉，能少一次WA就少一次。

2.2 度度熊回家：枚举删除点的数学推导

“度度熊回家”这道题是典型的模拟题，但如果你想清楚原理，写起来会非常快。题意大致是：一维数轴上有N个点，按顺序排列成一个路径，度度熊从第一个点出发，沿顺序走到最后一个点，现在可以选择删除中间某一个点，问删除后从起点到终点的总路程最短是多少。

最暴力的做法是枚举删除哪个点，然后把剩下的相邻点距离全部加起来，复杂度O(N^2)。N小的时候没问题，但题目如果给到10^5量级就扛不住了。优化的核心是：先算出不删除任何点时的总路程，再计算删除某个点后“省掉”的距离。

对于点i，原本会走三段相关路程：

• 从i-1到i的距离：|a[i] - a[i-1]|
• 从i到i+1的距离：|a[i+1] - a[i]|
• 删除i后，这两段会合并成直接从i-1到i+1的距离：|a[i+1] - a[i-1]|

注意，这些距离本身可能不相等，因为是数轴上的点。所以删除点i后，总路程的变化量是： saved = |a[i] - a[i-1]| + |a[i+1] - a[i]| - |a[i+1] - a[i-1]|

答案就是总路程total减去所有saved中的最大值。由于saved一定是非负的，所以保留saved最大的删除方式就是最优方案。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; if (n <= 2) { cout << 0 << '\n'; return 0; } int total = 0; for (int i = 0; i + 1 < n; ++i) { total += abs(a[i + 1] - a[i]); } int maxSaved = 0; for (int i = 1; i + 1 < n; ++i) { int saved = abs(a[i] - a[i - 1]) + abs(a[i + 1] - a[i]) - abs(a[i + 1] - a[i - 1]); maxSaved = max(maxSaved, saved); } cout << total - maxSaved << '\n'; return 0; }

这段代码有一个容易忽略的坑：当n等于1或2时，根本没有“中间点”可以删除，直接输出0。很多人在大样例上WA，不是公式错，而是没处理这种小数据边界。笔试里这种边界不起眼，但往往就藏在第一组测试数据里。

2.3 寻找三角形：叉积与浮点精度

“寻找三角形”是这套题里最早让我意识到“会数学和会编程是两回事”的题目。题目给了若干个三维空间中的点，每个点有一个颜色值，可能是R、G、B中的一种，要求选出三个点组成三角形，且三个点颜色要么完全相同，要么两两不同，然后求这些合法三角形里面积的最大值。

解法非常直接：三重循环枚举所有三元组，先判断颜色条件，再计算面积。枚举复杂度O(N^3)，如果N在几十到几百量级，完全可行。

面积计算是这里的重点。三维空间三角形的面积可以用向量叉积的模长来求。假设三个点分别是A、B、C，令向量u = B - A，向量v = C - A，则叉积的模长|u × v|等于以AB、AC为边的平行四边形面积，三角形面积就是它的一半。

叉积公式用行列式表示： u × v = (u.y * v.z - u.z * v.y, u.z * v.x - u.x * v.z, u.x * v.y - u.y * v.x)

模长就是三个分量平方和的平方根。代码实现时要小心坐标是整数，但面积可能是浮点数。我建议先算出面积平方，最后再开根号，可以减少一部分精度问题。

struct Point { char color; double x, y, z; }; double crossArea(const Point& a, const Point& b, const Point& c) { double ux = b.x - a.x, uy = b.y - a.y, uz = b.z - a.z; double vx = c.x - a.x, vy = c.y - a.y, vz = c.z - a.z; double cx = uy * vz - uz * vy; double cy = uz * vx - ux * vz; double cz = ux * vy - uy * vx; double square = cx * cx + cy * cy + cz * cz; return sqrt(square) / 2.0; }

颜色判断同样有坑。满足条件的情况只有两种：三个颜色完全相同，例如RRR；或者三个颜色两两不同，例如RGB。有同学会写“三色不同”时直接判断c1 != c2 && c2 != c3，结果漏了c1 == c3这种情况，比如RGR看起来是“不一样”，但实际出现了两个R，不合法。必须写成三条件同时满足： (c1 == c2 && c2 == c3) || (c1 != c2 && c2 != c3 && c1 != c3)

这种逻辑判断本身不难，难的是在写三重循环的时候保持清醒。我建议把颜色判断抽成单独的函数，能少很多意外错误。

2.4 有趣的排序：先想清楚“哪些元素不用动”

“有趣的排序”是这套题里很能考验理解能力的一道。题意大概是：给定一个从1到N的排列，你可以把任意一个元素移动到序列最前面或最后面，问最少需要移动多少次才能让整个序列升序有序。

如果你直接想“模拟移动”，会掉进一个很大的坑，因为移动顺序会影响结果，很难模拟出最优解。换一个角度想：如果最终序列要变成1,2,3,...,N，那么序列中已经有一部分元素是“相对位置正确”的，这部分元素可以完全不动，只需要把其余元素逐个移到开头或结尾。因此问题变成：原序列中最长有多少个值连续递增的元素，它们的相对位置本来就是对的。

这里的关键是“值连续递增且相对顺序不变”。比如序列3 1 2 4，里面1 2 4在数组中的先后顺序正好是递增的，且数值连续吗？不是，1、2、4中间少了3。真正连续的是1、2，长度为2，所以答案是4 - 2 = 2，需要移动两个元素。

实现思路：记录每个值在数组中的下标，比如pos[x]表示值x出现的位置。然后扫描值1到N，判断pos[i]和pos[i+1]的关系：如果pos[i+1] > pos[i]，说明i和i+1在原序列中相对顺序正确，可以连成一段连续递增序列；否则就断开，重新计数。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n + 1), pos(n + 1); for (int i = 1; i <= n; ++i) { cin >> a[i]; pos[a[i]] = i; } int len = 1, best = 1; for (int i = 1; i < n; ++i) { if (pos[i + 1] > pos[i]) { ++len; best = max(best, len); } else { len = 1; } } cout << n - best << '\n'; return 0; }

第一次做这题时，我尝试用最长上升子序列的长度作为“不用动的元素”，结果WA了。因为LIS虽然保证相对顺序，但不保证数值连续。而我们的最终序列是1到N的连续整数，所以只有值连续递增的子段，才能真正做到让未移动元素刚好占据最终序列中连续的一段。这个区别非常重要。

3. 核心难点逐个击破

3.1 不等式数列：动态规划与组合意义

这套题里最硬核的当属“不等式数列”。题意大致是：长度为n的排列中，有若干对相邻数字之间可能是小于号或大于号，现在问恰好有k个小于号的排列一共有多少个，结果对题目给定模数取模。

直接枚举所有排列肯定不行，n稍大就是灾难。当时我花了一段时间才理解动态规划的转移，这里我把完整推导讲清楚，因为它是整道题的核心。

设dp[i][j]表示由数字1到i组成的所有排列中，恰好有j个小于号的排列数量。初始状态dp[1][0] = 1，因为只有一个数字，没有相邻关系，更谈不上小于号。

现在考虑从长度i-1的排列扩展到长度i的排列：把数字i插入到原来i-1个数字形成的排列中。注意数字i是当前最大的数，所以插入的位置不同，小于号数量变化不同。

如果插入到原来某个“小于号”的位置，例如a < b，插入最大数i后变成a < i > b，原来的1个小于号还是1个小于号，数量不变。如果插入到原来某个“大于号”的位置，例如a > b，变成a < i > b，原来是0个小于号，现在变成了1个，数量增加1。

除了插入到相邻符号位置，还可以插入到最左端和最右端。最左端插入时，最大数在第一个位置，它和右边第一个数之间一定是大于号，所以小于号数量不变。最右端插入时，左边最后一个数和最大数之间一定是小于号，所以小于号数量增加1。

于是转移公式就清楚了。要得到dp[i][j]，有两种来源：

• 从dp[i-1][j]转移：原来已经有j个小于号，插入到不增加小于号的位置。不增加小于号的位置有原来的j个小于号位置，外加最左端1个，共j+1个位置。
• 从dp[i-1][j-1]转移：原来有j-1个小于号，插入到增加小于号的位置。原排列中大于号数量为(i-2)-(j-1)=i-j-1个，再加最右端1个，共i-j个位置。

所以： dp[i][j] = dp[i-1][j] * (j + 1) + dp[i-1][j-1] * (i - j)

这里很容易记混第二个系数，我自己也错过很多次。可以这样理解：i-j表示“当前还缺多少个小于号”，当目标从小到大时，这个位置数量会逐渐减少。验证方式很简单：对所有j求和，结果应该是i!，因为dp[i]的所有状态加起来就是全排列数量。用这个性质对拍检查，能立刻发现转移写没写错。

#include <bits/stdc++.h> using namespace std; const int MOD = 2017; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0)); dp[1][0] = 1; for (int i = 2; i <= n; ++i) { for (int j = 0; j < i; ++j) { long long cur = 0; if (j < i - 1) { cur += 1LL * dp[i - 1][j] * (j + 1) % MOD; } if (j > 0) { cur += 1LL * dp[i - 1][j - 1] * (i - j) % MOD; } dp[i][j] = cur % MOD; } } cout << dp[n][k] << '\n'; return 0; }

边界条件也要注意：j的范围是0到i-1，因为i个数字之间最多只有i-1对相邻关系，不可能出现i个小于号。循环里加if判断就是为了防止越界。取模的时机尽量提前，中间结果用long long暂存，不然溢出会让你调半天。

3.2 进制转换与字符串处理的小模板

这套题里还有几道和进制、字符串相关的题，难度不大但很能考察基础。比如十进制转任意进制，用“除基取余”法处理时，要特别注意进制大于10的情况，可能需要用A、B等字母表示10以上的数字。还有可能遇到反向问题：把一个表示任意进制数的字符串转换为十进制，需要从高位往低位累加。

这类题我建议准备一个通用模板，笔试时直接套用：

string toBase(int num, int base) { if (num == 0) return "0"; string res = ""; bool neg = false; if (num < 0) { neg = true; num = -num; } while (num > 0) { int digit = num % base; res += (digit < 10) ? char('0' + digit) : char('A' + digit - 10); num /= base; } if (neg) res += '-'; reverse(res.begin(), res.end()); return res; }

注意负数和0这两个边界。很多人在进制题上丢分不是因为不会转换，而是忘记处理num等于0的情况。如果你直接进while循环，0会变成空字符串，输出就错了。字符串处理题则要小心大小写、空格、前导零，这些细节几乎每套笔试题都会出现。

3.3 边界条件与输入输出陷阱

刷这套题给我最大的教训是：边界条件不是靠聪明，而是靠经验积累。很多题你思路完全正确，但WA在n=1、空集合、重复元素、浮点数精度这些地方。

我把自己在这套题里踩过的边界问题整理成了一份自查清单，现在每次提交前都会过一遍：

• 数组长度为0或者1时，代码是否还能正常运行？
• 如果结果可能为负数，输出格式是否允许负号？
• 取模运算中，减操作会不会产生负数？需不需要加MOD再取模？
• 浮点数比较时，是否用了eps？是否因为误差导致答案偏了一点点？
• 输入是否可能包含多组数据？题目有没有说读到EOF结束？
• 输出格式是否要求保留固定小数位？题目说保留两位，就不能输出3.1这种格式。

这些看起来是细节，但在真实笔试里，一个边界问题可能让你丢掉整道题的分数。建议你在刷题时，不只是让代码通过样例，还要主动构造极端数据测试。

4. 实操过程：我的练习流程与代码模板

4.1 准备环境与刷题节奏

我刷这套题的时候，用的是本地编辑环境加终端编译，工具倒没什么特别。关键是我给自己定了节奏：拿到一道题，先读题三遍，确认输入输出格式，然后给自己10分钟想暴力解法，如果暴力可行就先用暴力把答案跑出来，再去思考优化。这样做的目的是保证至少有一版正确代码可以用来对拍。

每道题我给自己30分钟，超过30分钟还卡住就看题解思路，但看完之后不是直接抄代码，而是关掉题解，自己重新写一遍。这个过程比刷十道简单题还有用。整套题我分了三天完成，每天两到三道。第一天做简单题找状态，第二天集中攻克中等题，第三天专门做动态规划和几何题，并且把所有AC代码重新整理了一遍。

环境上我强烈建议开启编译警告，比如g++加上-Wall -Wextra。很多潜在问题，比如变量未初始化、有符号数和无符号数比较，编译器都会给警告。笔试时虽然可能不允许改编译选项，但平时把这些习惯养好，考场上犯错的概率就小很多。

4.2 典型题的完整代码复盘

这里我把“寻找三角形”的完整写法再放一次，因为我当时在这道题上花费了不少时间，而且最终AC的代码里有很多值得学习的地方。完整的结构包括：读入点信息、三重循环枚举、颜色合法性判断、面积计算、更新最大值、控制输出精度。

#include <bits/stdc++.h> using namespace std; struct Point { char color; double x, y, z; }; bool validColor(char a, char b, char c) { if (a == b && b == c) return true; if (a != b && b != c && a != c) return true; return false; } double calcArea(const Point& p1, const Point& p2, const Point& p3) { double ux = p2.x - p1.x; double uy = p2.y - p1.y; double uz = p2.z - p1.z; double vx = p3.x - p1.x; double vy = p3.y - p1.y; double vz = p3.z - p1.z; double cx = uy * vz - uz * vy; double cy = uz * vx - ux * vz; double cz = ux * vy - uy * vx; return sqrt(cx * cx + cy * cy + cz * cz) / 2.0; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<Point> pts(n); for (int i = 0; i < n; ++i) { cin >> pts[i].color >> pts[i].x >> pts[i].y >> pts[i].z; } double ans = 0.0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (!validColor(pts[i].color, pts[j].color, pts[k].color)) continue; ans = max(ans, calcArea(pts[i], pts[j], pts[k])); } } } cout << fixed << setprecision(5) << ans << '\n'; return 0; }

三重循环枚举时用i、j、k递增的方式，能保证同一个三角形只被计算一次。如果一开始用三层从0到n-1的全枚举，不仅效率低，而且可能出现同一个三角形因为顶点顺序不同被重复计算的情况。虽然最终面积一样，但浪费了时间。

4.3 对拍与测试脚本的实用技巧

笔试刷题时最怕“样例过了但提交WA”，这时候对拍是最高效的定位手段。所谓对拍，就是写一个暴力解作为标准答案，写一个优化解作为待测代码，再写一个随机数据生成器，批量跑随机数据，比较两份输出。

我常用Python写数据生成器，然后在一个bash循环里反复对拍。以“度度熊回家”为例，数据生成器可以随机生成数组长度和数值，然后同时跑暴力程序和优化程序，一旦输出不一致就停下来查看输入数据。

for i in $(seq 1 500); do python3 gen.py > input.txt ./brute < input.txt > output_brute.txt ./fast < input.txt > output_fast.txt if ! diff output_brute.txt output_fast.txt; then echo "Case $i failed" break fi done

对拍时有个细节：浮点数输出不要直接diff，因为精度会导致两个程序输出细微不同。遇到浮点题，我一般会在diff之前先用Python脚本解析两边输出，比较它们差值的绝对值是否小于1e-6。这套流程看起来很原始，但真的能节省大量反复提交试错的时间。

5. 刷题中的常见问题与排查实录

5.1 常见错误速查表

刷完这套题后，我把最容易出现的错误整理成了一张速查表，现在每次笔试前都会扫一眼。常见的坑和排查方法如下：

这张表看起来简单，但每一条都是我实际踩过的坑。尤其是“样例通过但提交WA”这个问题，最让人心态爆炸。我的经验是：不要急着猜隐藏数据，先检查自己有没有处理n=1等边界，如果没有问题，再去检查算法本身的逻辑。

5.2 调试心得：与或非逻辑的坑

在“寻找三角形”这题上，颜色判断的条件我写错过一次。当时我写的是if (a != b && b != c)，漏掉了a == c的情况。样例里给出了一个RGB三角形，我通过了，但换到RGR这种组合时就错了，因为a != b成立，b != c也成立，但a != c不成立，这种颜色组合有三个点但有两个R，并不满足“要么全同，要么全不同”。

这个教训非常典型：逻辑表达式不是“看起来差不多”就行，必须逐项验证。后来我写这类条件判断，都会先在草稿纸上列出所有可能组合，再用真值表核对。看到一个if条件，至少要能说出它排除了哪些情况，保留哪些情况。不要嫌烦，这种习惯能在笔试里救你很多次。

另一个调试技巧是使用cerr输出中间变量。很多OJ对标准输出的格式很严格，但如果用cerr输出调试信息，不会影响最终输出。我在调试“不等式数列”的DP时，就会在每次循环后cerr当前dp数组的一整行，检查是不是符合全排列数总和的规律。发现问题后，先看转移方程，再看循环范围，比盲目调参高效得多。

5.3 为什么建议你也做一次完整复盘

刷题不是把题目AC掉就结束了，真正的提升在于复盘。我会在每道题AC之后，隔几天重新用空白编辑器写一遍，不参考之前的代码。如果能顺利写出来，说明这个知识点真的掌握了；如果卡住，说明之前AC可能只是背下来了，而不是理解了。这套题难度适中，非常适合用来做这种“间隔复写”训练。

我还习惯在题解里记录三件事：第一，这道题最简单的暴力写法是什么；第二，最优解为什么比暴力快，复杂度差在哪里；第三，如果数据范围变大十倍，这道题还能不能用当前解法。第三点对培养算法敏感度特别有好处，它能让你从“会写题”变成“会选题”。

6. 练习这套题后的几点体会

如果让我用一句话总结这套题，我会说它是一套“不偏不怪、处处有坑”的好题。它的每一道题单拿出来都不算难，但组合在一起，恰好把笔试中最容易失分的细节都覆盖了。我把这套题完整刷完再去做其他模拟笔试时，明显感觉到自己读题更仔细了，提交前检查边界条件变成了肌肉记忆。

我个人的一个实操建议是：刷这套题时，别急着看题解。哪怕一道题卡了半小时，也要保持独立思考。你可以借助调试工具、对拍程序、甚至手动用纸笔画状态转移，但一定要先形成自己的思路。因为校招笔试里，你面对的是全新题目，没有人会给你提示，平时怎么依赖题解，考场上就会怎么吃亏。

最后再分享一个我自己用得很顺手的方法：每道题AC之后，把代码按照“题意理解、解法推导、边界清单、代码实现”四段整理成笔记。这套题一共给了我几篇很完整的笔记。后来春招复习时，我没有再去翻新的题库，而是把这些笔记重新过了一遍，效果反而比盲目刷新题好很多。如果你也正准备春招，不妨试试这个方法，把一套有价值的真题吃透，比追求刷题数量更值得。