2016年秋招那会儿室友笔试回来在草稿纸上默写了整套“百度2016研发工程师笔试题二”我们宿舍几个人围着那几张草稿纸研究到半夜。我到现在还记得那天晚上讨论的热闹劲——题目出得确实干净选择题不偏编程题也不算难但每一道都能精准戳到当时我们的知识短板上。后来工作了几年见识过各种千奇百怪的笔试题再回头看这套题反而更觉得它值得好好拆一拆。如果你正在准备大厂校招或者工作几年后想重新检验一下自己的基础功底这套题是特别好的“体检项目”。它考的不是刷题量也不是奇技淫巧而是C/C底层理解、边界条件敏感度、经典算法模板熟练度这些真正决定开发水平的东西。这篇文章我挑三道编程题和一道关键的C语言指针选择题完整还原解题过程附带当年我们踩过的坑和现在回头看的一些反思。文章的代码统一用C写这也是当年百度研发岗笔试的主流语言。1. 这套题的整体气质题型分布与考察重点先说说整套题的结构。网上流传的版本大致是二十多道选择题加三道编程题的配置。选择题里C语言指针、运算符优先级、static关键字的语义这些题反复出现数据结构考察的是栈、队列、二叉树遍历这些最基础的东西操作系统和网络部分也是常规题型进程线程区别、死锁条件、TCP三次握手之类的。整体看下来没有那种“考完就骂出题人”的偏题怪题难度控制得非常克制但克制不代表简单——它考的是你脑子里有没有形成一张清晰的知识网络。编程题我印象最深的是三道一道跟几何坐标有关一道是数组连续段求和一道是统计乘法表。这三道题分别对应了三种不同的能力边界处理能力、经典算法模板的熟练度、以及从问题描述中抽象出数学模型的能力。三道题没有一道需要你背什么冷门算法但如果你平时只刷LeetCode高频题、对基础概念一知半解考场上大概率会卡住。这也是我为什么说这套老题到今天依然值得刷的原因它更像一场“基本功考试”而不是“技巧炫技赛”。现在的笔试题多少有点内卷动不动就是状态压缩DP、线段树、树上启发式合并难度上去了但考察的东西反而越来越偏离工程实际。2016年的这套题没这么花哨每一道都能跟日常开发里某个具体场景对应上数组越界、滑动窗口统计、二分查找边界判断这些都是工作后每天都在面对的事情。所以我的观点很明确别小看这套老题它筛的不是智商是习惯。2. 数组名与a一道C语言指针题当年筛掉大半人这套题的选择题里有一道让我印象极其深刻因为几乎每个考完的人都在讨论它。题目大概长这样#include stdio.h int main() { int a[5] {1, 2, 3, 4, 5}; int *p (int *)(a 1); printf(%d, %d\n, *(a 1), *(p - 1)); return 0; }问你输出是什么。评论区争议最大的是第二项很多人觉得既然p指向了a1那p-1指向的应该是a[0]所以输出5还是说p-1指向了数组末尾越界了答案是2和5。我记得当年宿舍里争论了快一个小时核心分歧其实就一句话a和a到底是不是同一个东西。先说结论a是数组首元素的地址类型是int*所以a1指向a[1](a1)等于2这没什么争议。a取的是整个数组的地址类型是int()[5]一个指向“包含5个int的数组”的指针。指针加减运算的单位是指向类型的大小a1会跳过整个5个元素的数组——也就是从a[0]直接跳到a[5]即数组末尾之后的位置。把它强转成int*赋给p之后p指向的是a[5]这个“假想”元素p-1往前挪一个int正好落在a[4]上值就是5。这道题的精髓在于数组名a在绝大多数表达式中都会退化成首元素地址但a不会。很多人记住了“数组名是常量指针”这个结论却没搞明白“数组名”和“取地址”之间的类型差异一遇到组合拳就懵。我把常考的几个表达式整理成一个表方便对照记忆表达式类型含义加1跳过的字节数32位intaint*数组首元素的地址4a[0]int*第0个元素的地址4aint(*)[5]整个数组的地址20a1int*指向a[1]4a1int(*)[5]跳过整个数组20你把这个表看懂了基本就能理解为什么(int)(a 1)是往数组末尾后面指。面试里如果考二维数组还会在这个基础上继续加码。比如定义一个int a[3][4]然后问你a、a、a[0]、a[0]、a这五个表达式有什么区别。规律还是同一个a的类型是int()[4]指向第0行a的类型是int()[3][4]指向整个二维数组a[0]和a在数值上跟a一模一样但类型是int指向第0行第0列元素。搞懂这一层后面再考a[1][2]的等价写法*(*(a1)2)就不怕了。这道选择题给我的教训是C语言基础不是“背多分”而是真的要理解内存布局和类型系统。现在很多笔试直接改成Java或者Python题但只要你面的是C开发岗这类指针题始终是高频考点。别以为工作后用不到就跳过底层系统、性能优化、疑难Bug排查全都要靠这点底子。3. 裁减网格纸从“最小矩形”到“正方形”的思路陷阱编程题第一道我记得是“裁减网格纸”题目复述一下有一张网格纸上面散布着n个点每个点有一个整数坐标(x, y)。现在要沿着网格线裁下一块正方形把这n个点全部覆盖住求这个正方形的最小面积。输出面积值即可。输入输出格式大概是输入 2 0 0 3 3 输出 9两个点分别是(0,0)和(3,3)覆盖它们的最小正方形边长是3面积9。这个示例本身不难但恰恰是它把很多人带沟里了。我当年第一次做这道题第一反应是求所有点x坐标的最小值和最大值、y坐标的最小值和最大值然后算(x_max - x_min) * (y_max - y_min)输出9——看起来没问题但如果测试数据是(0,0)、(1,3)、(3,1)x方向跨度是3y方向跨度也是3面积还是9好像也没问题。那问题出在哪儿呢出在题目要求的是正方形。如果x方向跨度是2y方向跨度是5你的矩形面积是10但正方形边长必须同时覆盖2和5所以边长是max(2, 5)5面积是25。直接用乘积就漏掉了“正方形”这个约束条件。这一下就把“只是套公式”和“真正理解题意”的人区分开了。正确做法是先分别求x方向和y方向的最大跨度然后取较大值作为正方形边长再平方。坐标全是整数跨度也是整数所以不需要考虑向上取整。这里有一个容易忽略的边界情况如果n1只有一个点x方向跨度和y方向跨度都是0max(0, 0)0面积就是0。但按常理裁一块正方形覆盖一个点面积至少应该是1。当年网上对这个边界有两种说法有的版本认为输出0也行有的版本要求边长至少为1。从实际做题角度我建议代码里加一句特判边长算出来是0就置为1这样最稳妥。代码很简单#include iostream #include algorithm #include climits using namespace std; int main() { int n; cin n; int min_x INT_MAX, max_x INT_MIN; int min_y INT_MAX, max_y INT_MIN; for (int i 0; i n; i) { int x, y; cin x y; min_x min(min_x, x); max_x max(max_x, x); min_y min(min_y, y); max_y max(max_y, y); } int len_x max_x - min_x; int len_y max_y - min_y; int edge max(len_x, len_y); if (edge 0) edge 1; cout edge * edge endl; return 0; }这道题如果跳出来看其实是在考察两件事第一你能不能从题目描述里准确提取约束条件尤其是“正方形”这个关键词第二你会不会处理极端输入。很多人一看到“覆盖所有点”下意识就往最近点对、凸包那些复杂算法上想完全忽视了这道题只需要扫一遍数组、记录四个极值就行。这种“想太多”在笔试里是大忌。我的习惯是拿到题先写暴力解再想优化千万不要一上来就套高深算法。暴力解往往是最容易发现题目隐含条件的方式。4. 罪犯转移滑动窗口暴力解为什么必然超时第二道编程题是“罪犯转移”题干大概是这样的C市有n名罪犯编号1到n每名罪犯有一个犯罪值v[i]。现在要连续转移m名罪犯要求这m名罪犯的犯罪值之和不超过t问一共有多少种不同的转移方案。这里的“连续转移”指的是必须挑选编号连续的一段罪犯。比如n5m3犯罪值是[2, 3, 1, 1, 1]t3那么连续3个罪犯的组合有[2,3,1]、[3,1,1]、[1,1,1]、[1,1,?]——只有[3,1,1]和[1,1,1]的和不超过3等下[2,3,1]和是6超了[1,1,1]和是3刚好等于t算满足所以答案是2。不对[3,1,1]和是5也超了。那满足的就只有最后一个[1,1,1]方案数1。具体数据不重要核心是连续子段和不超过某个阈值求方案数。最直观的暴力做法是枚举所有长度为m的连续子段对每个子段求一遍和复杂度是O(n*m)。如果n和m的范围是1e5这就完蛋了肯定超时。所以标准解法是滑动窗口或者叫尺取法——先算出第一个窗口的和然后每次窗口往右滑动一个位置用sum减去滑出的那个元素加上滑入的那个元素。变化量是O(1)的整体只需要O(n)的时间。我第一次写这道题时犯了个低级错误没有考虑n m的情况。如果罪犯总数本身就小于要转移的人数显然方案数是0但暴力代码里直接取前m个元素求和数组越界立刻崩了。这类条件在笔试题里特别常见要么是n m要么是m0要么是数组为空总之出题人就是喜欢在数据范围的边缘埋雷。我的建议是写完核心逻辑后专门花一分钟检查一下所有输入边界尤其是n和m的相对大小。代码也不复杂#include iostream #include vector using namespace std; int main() { int n, m, t; while (cin n m t) { vectorint v(n); for (int i 0; i n; i) cin v[i]; if (n m) { cout 0 endl; continue; } int sum 0; for (int i 0; i m; i) sum v[i]; int count (sum t) ? 1 : 0; for (int i m; i n; i) { sum sum - v[i - m] v[i]; if (sum t) count; } cout count endl; } return 0; }如果你想从思路上更清晰一点也可以改写成前缀和数组prefix[i]表示前i个元素的和那么连续m个元素的和就是prefix[i] - prefix[i-m]枚举i从m到nO(1)判断每个子段。两种写法本质一样滑动窗口省空间前缀和更直白笔试时看你哪个顺手就用哪个。需要注意的另一个坑是累加和可能超出int范围尤其是n比较大的时候保险起见用long long反正又不损失性能。这道题放到今天看就是滑动窗口的模板题但当年考场上还真有不少人卡住。原因在于很多人刷题时习惯了“给定一个窗口求窗口内最大值/最小值”这种有明确提示的题遇到“连续子段和不超过t”反而会对不上号。其实它们的底层逻辑一样维护一段连续的区间随着右端点移动左端点也跟着移动从而把暴力枚举的O(n²)优化成O(n)。理解了这个本质以后再遇到“长度固定的连续子段最值”“和不超过k的最长子数组”这些变体就都能一眼看穿。5. 乘法表从“第k大”到二分答案中间只差一个单调性第三道编程题是“乘法表”原题大概是给定正整数n和m有一个n行m列的乘法表第i行第j列的值是i*ji从1到nj从1到m把这个乘法表里的所有数字按从大到小排序问第k大的数字是多少。n和m的范围可能到1e5所以绝对不能真的生成这张表然后排序。我拿到这道题的第一反应是这能二分后来想明白了关键要抓住一个性质——给定一个数x我可以快速统计乘法表中有多少个数字大于等于x或小于等于x。这个统计是单调的x越大大于等于x的数字越少x越小大于等于x的数字越多。于是“第k大的数是多少”就可以转换成“找一个最小的x使得乘法表中大于等于x的数字个数至少为k”或者“找一个最大的x使得小于等于x的数字个数不超过total-k”之类。这个思路就是二分答案。实际计算某个x有多少个数字小于等于x时可以逐行看第i行的数字是i1, i2, ..., im要满足ij xj最多取floor(x / i)但也不能超过m所以第i行小于等于x的数字个数是min(m, x/i)。把i从1到n累加一遍就是整个乘法表中小于等于x的数字总数。这个统计函数的复杂度是O(n)。如果n是1e5log(n*m)大约34次运算量在340万左右完全可行。二分答案的边界写法有一个经典细节如果要求第k大我习惯先转成第total-k1小total n*m。这样二分条件就统一成“小于等于mid的个数 目标”继续收缩右边界否则收缩左边界。为什么能这么转因为“第k大”就是从大到小排的第k个“第total-k1小”就是从小到大排的同一位置两者是同一个元素。很多同学在这个转换上绕不清楚干脆直接判断大于等于mid的个数其实也行但容易把方向搞反。我建议固定一种写法多练几道类似题形成肌肉记忆。#include iostream #include algorithm using namespace std; long long n, m, k; long long count_less_equal(long long x) { long long cnt 0; for (long long i 1; i n; i) { cnt min(m, x / i); } return cnt; } int main() { cin n m k; long long total n * m; long long target total - k 1; // 转为第target小 long long left 1, right n * m; while (left right) { long long mid (left right) / 2; if (count_less_equal(mid) target) { right mid; } else { left mid 1; } } cout left endl; return 0; }代码里有两个地方特别提醒一下。第一是long longn和m都可能到1e5nm直接到1e10int根本装不下用int的人会直接溢出得到完全错误的答案。第二是乘法表里的数字是允许重复的因为ij和ji可能一样所以total就是nm不用去重二分答案的计数法天然支持重复值你不需要额外处理。这道题拓展出来其实是一个很泛用的思想当你想在一个无法全部枚举的集合里找某个排名的值而你又有一个快速计数函数时就可以二分这个值本身。类似的题还有“有序矩阵中第k小的元素”“两个有序数组的第k大”等等本质上都是二分答案而不是二分下标。这个思维转变很关键我当年就是通过这类题才真正看懂了“二分答案”和“二分查找”的区别。6. 复盘这套老题留给我的几个教训把这四道题放在一起复盘一下我最大的感受是这套题几乎不做无用功每道题都在精准地考察一个具体能力。题目核心考察点我踩过的典型错误数组名与aC语言类型系统与内存模型以为a和a是同一个地址就完事忽略类型差异裁减网格纸提取约束、极值枚举、边界处理按矩形面积算忘了“正方形”约束忘了单点特判罪犯转移滑动窗口/前缀和的熟练度没处理nm导致数组越界暴力O(n*m)超时乘法表二分答案、计数函数、单调性用int存n*m溢出第k大/第k小方向搞反再看深一层这些错误其实反映了三类常态问题对语言底层理解浮于表面、对边界条件不够敏感、对算法模板只会背不会用。这三个问题恰恰是日常开发中最容易埋雷的地方。数组越界、溢出、没考虑空输入这些听起来像新手才会犯的错但实际上就算工作了几年的老手在赶工时也经常在边界上翻车。笔试题帮你把这些毛病提前暴露出来其实是一件好事。现在备考我不建议一上来就刷难题。把2016年这类经典老题拿出来每一道都逼自己写出完整可运行的代码并且自己造几个边界测试用例跑一遍收获比盲目刷二十道新题更大。做题的时候也别急着看题解先想想暴力解法怎么写再看看能不能优化最后才对照标准解法看差距。这套流程走下来你会发现自己对“为什么这么写”的理解完全不一样了。我自己后来面试别人时也喜欢拿类似难度的题去考察候选人看对方拿到题之后是直接套模板还是会先分析、再设计、最后写代码。说到底笔试只是第一道门槛它筛掉的是那些基础不牢、思维混乱、手底下没活的人。而这套2016年的老题恰好就是把这三件事精准地测出来了。 
长河君 · 2026/8/30 16:11:19 · 阅读 1.2k 百度2016研发笔试题精讲：C语言指针、滑动窗口与二分答案
2016年秋招那会儿室友笔试回来在草稿纸上默写了整套“百度2016研发工程师笔试题二”我们宿舍几个人围着那几张草稿纸研究到半夜。我到现在还记得那天晚上讨论的热闹劲——题目出得确实干净选择题不偏编程题也不算难但每一道都能精准戳到当时我们的知识短板上。后来工作了几年见识过各种千奇百怪的笔试题再回头看这套题反而更觉得它值得好好拆一拆。如果你正在准备大厂校招或者工作几年后想重新检验一下自己的基础功底这套题是特别好的“体检项目”。它考的不是刷题量也不是奇技淫巧而是C/C底层理解、边界条件敏感度、经典算法模板熟练度这些真正决定开发水平的东西。这篇文章我挑三道编程题和一道关键的C语言指针选择题完整还原解题过程附带当年我们踩过的坑和现在回头看的一些反思。文章的代码统一用C写这也是当年百度研发岗笔试的主流语言。1. 这套题的整体气质题型分布与考察重点先说说整套题的结构。网上流传的版本大致是二十多道选择题加三道编程题的配置。选择题里C语言指针、运算符优先级、static关键字的语义这些题反复出现数据结构考察的是栈、队列、二叉树遍历这些最基础的东西操作系统和网络部分也是常规题型进程线程区别、死锁条件、TCP三次握手之类的。整体看下来没有那种“考完就骂出题人”的偏题怪题难度控制得非常克制但克制不代表简单——它考的是你脑子里有没有形成一张清晰的知识网络。编程题我印象最深的是三道一道跟几何坐标有关一道是数组连续段求和一道是统计乘法表。这三道题分别对应了三种不同的能力边界处理能力、经典算法模板的熟练度、以及从问题描述中抽象出数学模型的能力。三道题没有一道需要你背什么冷门算法但如果你平时只刷LeetCode高频题、对基础概念一知半解考场上大概率会卡住。这也是我为什么说这套老题到今天依然值得刷的原因它更像一场“基本功考试”而不是“技巧炫技赛”。现在的笔试题多少有点内卷动不动就是状态压缩DP、线段树、树上启发式合并难度上去了但考察的东西反而越来越偏离工程实际。2016年的这套题没这么花哨每一道都能跟日常开发里某个具体场景对应上数组越界、滑动窗口统计、二分查找边界判断这些都是工作后每天都在面对的事情。所以我的观点很明确别小看这套老题它筛的不是智商是习惯。2. 数组名与a一道C语言指针题当年筛掉大半人这套题的选择题里有一道让我印象极其深刻因为几乎每个考完的人都在讨论它。题目大概长这样#include stdio.h int main() { int a[5] {1, 2, 3, 4, 5}; int *p (int *)(a 1); printf(%d, %d\n, *(a 1), *(p - 1)); return 0; }问你输出是什么。评论区争议最大的是第二项很多人觉得既然p指向了a1那p-1指向的应该是a[0]所以输出5还是说p-1指向了数组末尾越界了答案是2和5。我记得当年宿舍里争论了快一个小时核心分歧其实就一句话a和a到底是不是同一个东西。先说结论a是数组首元素的地址类型是int*所以a1指向a[1](a1)等于2这没什么争议。a取的是整个数组的地址类型是int()[5]一个指向“包含5个int的数组”的指针。指针加减运算的单位是指向类型的大小a1会跳过整个5个元素的数组——也就是从a[0]直接跳到a[5]即数组末尾之后的位置。把它强转成int*赋给p之后p指向的是a[5]这个“假想”元素p-1往前挪一个int正好落在a[4]上值就是5。这道题的精髓在于数组名a在绝大多数表达式中都会退化成首元素地址但a不会。很多人记住了“数组名是常量指针”这个结论却没搞明白“数组名”和“取地址”之间的类型差异一遇到组合拳就懵。我把常考的几个表达式整理成一个表方便对照记忆表达式类型含义加1跳过的字节数32位intaint*数组首元素的地址4a[0]int*第0个元素的地址4aint(*)[5]整个数组的地址20a1int*指向a[1]4a1int(*)[5]跳过整个数组20你把这个表看懂了基本就能理解为什么(int)(a 1)是往数组末尾后面指。面试里如果考二维数组还会在这个基础上继续加码。比如定义一个int a[3][4]然后问你a、a、a[0]、a[0]、a这五个表达式有什么区别。规律还是同一个a的类型是int()[4]指向第0行a的类型是int()[3][4]指向整个二维数组a[0]和a在数值上跟a一模一样但类型是int指向第0行第0列元素。搞懂这一层后面再考a[1][2]的等价写法*(*(a1)2)就不怕了。这道选择题给我的教训是C语言基础不是“背多分”而是真的要理解内存布局和类型系统。现在很多笔试直接改成Java或者Python题但只要你面的是C开发岗这类指针题始终是高频考点。别以为工作后用不到就跳过底层系统、性能优化、疑难Bug排查全都要靠这点底子。3. 裁减网格纸从“最小矩形”到“正方形”的思路陷阱编程题第一道我记得是“裁减网格纸”题目复述一下有一张网格纸上面散布着n个点每个点有一个整数坐标(x, y)。现在要沿着网格线裁下一块正方形把这n个点全部覆盖住求这个正方形的最小面积。输出面积值即可。输入输出格式大概是输入 2 0 0 3 3 输出 9两个点分别是(0,0)和(3,3)覆盖它们的最小正方形边长是3面积9。这个示例本身不难但恰恰是它把很多人带沟里了。我当年第一次做这道题第一反应是求所有点x坐标的最小值和最大值、y坐标的最小值和最大值然后算(x_max - x_min) * (y_max - y_min)输出9——看起来没问题但如果测试数据是(0,0)、(1,3)、(3,1)x方向跨度是3y方向跨度也是3面积还是9好像也没问题。那问题出在哪儿呢出在题目要求的是正方形。如果x方向跨度是2y方向跨度是5你的矩形面积是10但正方形边长必须同时覆盖2和5所以边长是max(2, 5)5面积是25。直接用乘积就漏掉了“正方形”这个约束条件。这一下就把“只是套公式”和“真正理解题意”的人区分开了。正确做法是先分别求x方向和y方向的最大跨度然后取较大值作为正方形边长再平方。坐标全是整数跨度也是整数所以不需要考虑向上取整。这里有一个容易忽略的边界情况如果n1只有一个点x方向跨度和y方向跨度都是0max(0, 0)0面积就是0。但按常理裁一块正方形覆盖一个点面积至少应该是1。当年网上对这个边界有两种说法有的版本认为输出0也行有的版本要求边长至少为1。从实际做题角度我建议代码里加一句特判边长算出来是0就置为1这样最稳妥。代码很简单#include iostream #include algorithm #include climits using namespace std; int main() { int n; cin n; int min_x INT_MAX, max_x INT_MIN; int min_y INT_MAX, max_y INT_MIN; for (int i 0; i n; i) { int x, y; cin x y; min_x min(min_x, x); max_x max(max_x, x); min_y min(min_y, y); max_y max(max_y, y); } int len_x max_x - min_x; int len_y max_y - min_y; int edge max(len_x, len_y); if (edge 0) edge 1; cout edge * edge endl; return 0; }这道题如果跳出来看其实是在考察两件事第一你能不能从题目描述里准确提取约束条件尤其是“正方形”这个关键词第二你会不会处理极端输入。很多人一看到“覆盖所有点”下意识就往最近点对、凸包那些复杂算法上想完全忽视了这道题只需要扫一遍数组、记录四个极值就行。这种“想太多”在笔试里是大忌。我的习惯是拿到题先写暴力解再想优化千万不要一上来就套高深算法。暴力解往往是最容易发现题目隐含条件的方式。4. 罪犯转移滑动窗口暴力解为什么必然超时第二道编程题是“罪犯转移”题干大概是这样的C市有n名罪犯编号1到n每名罪犯有一个犯罪值v[i]。现在要连续转移m名罪犯要求这m名罪犯的犯罪值之和不超过t问一共有多少种不同的转移方案。这里的“连续转移”指的是必须挑选编号连续的一段罪犯。比如n5m3犯罪值是[2, 3, 1, 1, 1]t3那么连续3个罪犯的组合有[2,3,1]、[3,1,1]、[1,1,1]、[1,1,?]——只有[3,1,1]和[1,1,1]的和不超过3等下[2,3,1]和是6超了[1,1,1]和是3刚好等于t算满足所以答案是2。不对[3,1,1]和是5也超了。那满足的就只有最后一个[1,1,1]方案数1。具体数据不重要核心是连续子段和不超过某个阈值求方案数。最直观的暴力做法是枚举所有长度为m的连续子段对每个子段求一遍和复杂度是O(n*m)。如果n和m的范围是1e5这就完蛋了肯定超时。所以标准解法是滑动窗口或者叫尺取法——先算出第一个窗口的和然后每次窗口往右滑动一个位置用sum减去滑出的那个元素加上滑入的那个元素。变化量是O(1)的整体只需要O(n)的时间。我第一次写这道题时犯了个低级错误没有考虑n m的情况。如果罪犯总数本身就小于要转移的人数显然方案数是0但暴力代码里直接取前m个元素求和数组越界立刻崩了。这类条件在笔试题里特别常见要么是n m要么是m0要么是数组为空总之出题人就是喜欢在数据范围的边缘埋雷。我的建议是写完核心逻辑后专门花一分钟检查一下所有输入边界尤其是n和m的相对大小。代码也不复杂#include iostream #include vector using namespace std; int main() { int n, m, t; while (cin n m t) { vectorint v(n); for (int i 0; i n; i) cin v[i]; if (n m) { cout 0 endl; continue; } int sum 0; for (int i 0; i m; i) sum v[i]; int count (sum t) ? 1 : 0; for (int i m; i n; i) { sum sum - v[i - m] v[i]; if (sum t) count; } cout count endl; } return 0; }如果你想从思路上更清晰一点也可以改写成前缀和数组prefix[i]表示前i个元素的和那么连续m个元素的和就是prefix[i] - prefix[i-m]枚举i从m到nO(1)判断每个子段。两种写法本质一样滑动窗口省空间前缀和更直白笔试时看你哪个顺手就用哪个。需要注意的另一个坑是累加和可能超出int范围尤其是n比较大的时候保险起见用long long反正又不损失性能。这道题放到今天看就是滑动窗口的模板题但当年考场上还真有不少人卡住。原因在于很多人刷题时习惯了“给定一个窗口求窗口内最大值/最小值”这种有明确提示的题遇到“连续子段和不超过t”反而会对不上号。其实它们的底层逻辑一样维护一段连续的区间随着右端点移动左端点也跟着移动从而把暴力枚举的O(n²)优化成O(n)。理解了这个本质以后再遇到“长度固定的连续子段最值”“和不超过k的最长子数组”这些变体就都能一眼看穿。5. 乘法表从“第k大”到二分答案中间只差一个单调性第三道编程题是“乘法表”原题大概是给定正整数n和m有一个n行m列的乘法表第i行第j列的值是i*ji从1到nj从1到m把这个乘法表里的所有数字按从大到小排序问第k大的数字是多少。n和m的范围可能到1e5所以绝对不能真的生成这张表然后排序。我拿到这道题的第一反应是这能二分后来想明白了关键要抓住一个性质——给定一个数x我可以快速统计乘法表中有多少个数字大于等于x或小于等于x。这个统计是单调的x越大大于等于x的数字越少x越小大于等于x的数字越多。于是“第k大的数是多少”就可以转换成“找一个最小的x使得乘法表中大于等于x的数字个数至少为k”或者“找一个最大的x使得小于等于x的数字个数不超过total-k”之类。这个思路就是二分答案。实际计算某个x有多少个数字小于等于x时可以逐行看第i行的数字是i1, i2, ..., im要满足ij xj最多取floor(x / i)但也不能超过m所以第i行小于等于x的数字个数是min(m, x/i)。把i从1到n累加一遍就是整个乘法表中小于等于x的数字总数。这个统计函数的复杂度是O(n)。如果n是1e5log(n*m)大约34次运算量在340万左右完全可行。二分答案的边界写法有一个经典细节如果要求第k大我习惯先转成第total-k1小total n*m。这样二分条件就统一成“小于等于mid的个数 目标”继续收缩右边界否则收缩左边界。为什么能这么转因为“第k大”就是从大到小排的第k个“第total-k1小”就是从小到大排的同一位置两者是同一个元素。很多同学在这个转换上绕不清楚干脆直接判断大于等于mid的个数其实也行但容易把方向搞反。我建议固定一种写法多练几道类似题形成肌肉记忆。#include iostream #include algorithm using namespace std; long long n, m, k; long long count_less_equal(long long x) { long long cnt 0; for (long long i 1; i n; i) { cnt min(m, x / i); } return cnt; } int main() { cin n m k; long long total n * m; long long target total - k 1; // 转为第target小 long long left 1, right n * m; while (left right) { long long mid (left right) / 2; if (count_less_equal(mid) target) { right mid; } else { left mid 1; } } cout left endl; return 0; }代码里有两个地方特别提醒一下。第一是long longn和m都可能到1e5nm直接到1e10int根本装不下用int的人会直接溢出得到完全错误的答案。第二是乘法表里的数字是允许重复的因为ij和ji可能一样所以total就是nm不用去重二分答案的计数法天然支持重复值你不需要额外处理。这道题拓展出来其实是一个很泛用的思想当你想在一个无法全部枚举的集合里找某个排名的值而你又有一个快速计数函数时就可以二分这个值本身。类似的题还有“有序矩阵中第k小的元素”“两个有序数组的第k大”等等本质上都是二分答案而不是二分下标。这个思维转变很关键我当年就是通过这类题才真正看懂了“二分答案”和“二分查找”的区别。6. 复盘这套老题留给我的几个教训把这四道题放在一起复盘一下我最大的感受是这套题几乎不做无用功每道题都在精准地考察一个具体能力。题目核心考察点我踩过的典型错误数组名与aC语言类型系统与内存模型以为a和a是同一个地址就完事忽略类型差异裁减网格纸提取约束、极值枚举、边界处理按矩形面积算忘了“正方形”约束忘了单点特判罪犯转移滑动窗口/前缀和的熟练度没处理nm导致数组越界暴力O(n*m)超时乘法表二分答案、计数函数、单调性用int存n*m溢出第k大/第k小方向搞反再看深一层这些错误其实反映了三类常态问题对语言底层理解浮于表面、对边界条件不够敏感、对算法模板只会背不会用。这三个问题恰恰是日常开发中最容易埋雷的地方。数组越界、溢出、没考虑空输入这些听起来像新手才会犯的错但实际上就算工作了几年的老手在赶工时也经常在边界上翻车。笔试题帮你把这些毛病提前暴露出来其实是一件好事。现在备考我不建议一上来就刷难题。把2016年这类经典老题拿出来每一道都逼自己写出完整可运行的代码并且自己造几个边界测试用例跑一遍收获比盲目刷二十道新题更大。做题的时候也别急着看题解先想想暴力解法怎么写再看看能不能优化最后才对照标准解法看差距。这套流程走下来你会发现自己对“为什么这么写”的理解完全不一样了。我自己后来面试别人时也喜欢拿类似难度的题去考察候选人看对方拿到题之后是直接套模板还是会先分析、再设计、最后写代码。说到底笔试只是第一道门槛它筛掉的是那些基础不牢、思维混乱、手底下没活的人。而这套2016年的老题恰好就是把这三件事精准地测出来了。