腾讯2018春招编程题解析：二分、贪心、区间DP与组合计数

腾讯2018春招技术类编程题汇总这份题库，我到现在还会翻出来看。原因很简单：它不像很多压轴竞赛题那样劝退，但又能把二分、贪心、区间DP、组合计数这几个校招最高频的考点都考到位，题量不大，难度梯度合理，非常适合拿来摸底和找手感。无论你是准备腾讯的正式批，还是想用一套高质量题目检验自己的算法底子，这十几道题都值得认真过一遍。

这套题最大的价值在于“用得上”：每道题背后都是一个可以迁移到别家笔试的解题模型。我把当年考过的核心题目按考点拆开，结合我自己的实现过程，把解题思路、代码细节、容易踩的坑全部过一遍。即便你不是应届生，把这些模型吃透，应付大多数公司的线上笔试也够用了。

1. 2018腾讯春招编程题的整体设计思路

1.1 题型分布与考点盘点

2018年腾讯春招技术类笔试的编程题部分，整体风格是“短题干、多约束、重边界”。题目往往用一个小故事包装，去掉包装后就是个经典算法模型。这一点和LeetCode的风格有点像，但比LeetCode更强调“能不能在短时间内想清楚数据范围和边界条件”。

把这批题目过一遍，考点可以归成这么几类：

你会发现，这些题目没有特别冷门的算法，也没有变态的数学构造题。它考的恰恰是校招生最该有的基本功：二分边界会不会写、组合数取模会不会预处理、区间DP的状态转移能不能想清楚、贪心策略能不能证明。

1.2 为什么这套题值得反复刷

我开始带新人之后，经常用这套题当“面试前置热身”。原因有三个。

第一，题目覆盖面广但不偏门。二分、DP、贪心、组合计数，这四样几乎是所有大厂笔试的通用考点。把这套题刷透，等于给算法基础做了一次系统体检，哪块薄弱一目了然。

第二，题目难度适合“限时训练”。每道题单独拿出来，给到30到40分钟，正好模拟面试笔试的节奏。如果你能在45分钟内AC三道以上，说明基本功已经达到一个比较稳的水平。

第三，题目背后的坑非常典型。比如二分边界、组合数取模、long long溢出、区间DP的循环顺序，这些坑在真实笔试里每年都有人踩。这套题的设置恰好把这些细节暴露得很充分，刷一遍能积累不少避坑经验。

2. 核心题目解析与解题思路

2.1 贪吃的小Q：二分答案的经典模板

题目大概是这样的：小Q的父母出差N天，走之前给他留了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天的一半，且每天至少吃1块，但他又不想在父母回来之前断粮。问小Q第一天最多能吃多少块巧克力。

这道题的突破口在于“第一天吃的数量”和“能否撑过N天”之间是单调关系：第一天吃越多，后面每天的消耗也越高，越容易断粮。所以可以二分答案，枚举第一天的数量x，然后check一下按照规则能不能撑满N天。

check函数的写法是核心，我贴一下我常用的实现：

bool check(int x, int n, int m) { long long total = 0; int cur = x; for (int i = 0; i < n; i++) { total += cur; if (total > m) return false; cur = (cur + 1) / 2; // 向上取整的一半 if (cur == 1) { // 从第 i+1 天起到最后，每天都是1块 total += (n - i - 1); return total <= m; } } return total <= m; }

有几个细节必须强调。第一，cur = (cur + 1) / 2，这个写法等价于向上取整，因为巧克力数量必须是整数。第二，一旦cur变成1，后面每天都是1块，后续可以直接用乘法算完，不要再进循环里模拟，否则容易在n很大的时候超时。第三，累加值total必须用long long，M的上限如果给到2^31，int在累加过程中可能溢出。

二分部分比较简单：

int l = 1, r = m, ans = 1; while (l <= r) { int mid = (l + r) / 2; if (check(mid, n, m)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << endl;

这里注意先判断check成功再更新ans，保证ans始终是可行解中的最大值。

我第一次做这道题的时候犯了个低级错误：check里没有处理cur==1后的尾巴，导致n很大的时候TLE。后来才意识到，这个优化不只是锦上添花，而是这道题的一个隐藏考点，数据一大，不加这个优化就可能超时。

2.2 小Q的歌单：组合计数与取模陷阱

第二道经典题是歌单问题：小Q有X首长度为A的歌和Y首长度为B的歌，现在要从里面选一些歌组成一个总长度恰好为K的歌单，每首歌只能用一次，问一共有多少种组合方案，结果对1e9+7取模。

这道题的核心是枚举。假设选i首长度为A的歌，剩余长度K-iA必须能被B整除，而且剩余部分对应的歌数量不能超过Y。满足条件时，方案数就是C(X, i) * C(Y, j)，其中j = (K - iA) / B。

实现上需要预处理组合数。C++我一般用二维数组杨辉三角，因为这道题的数据范围通常不会太大，n最多几百到一千：

const int MOD = 1e9 + 7; const int MAXN = 105; long long C[MAXN][MAXN]; void init() { for (int i = 0; i < MAXN; i++) { C[i][0] = C[i][i] = 1; for (int j = 1; j < i; j++) { C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD; } } }

然后枚举i：

long long ans = 0; for (int i = 0; i <= X; i++) { if (i * A > K) break; int remain = K - i * A; if (remain % B != 0) continue; int j = remain / B; if (j > Y) continue; ans = (ans + C[X][i] * C[Y][j]) % MOD; } cout << ans << endl;

易错点主要有两个。第一，C数组类型用long long，但乘完之后要立刻取模，否则两个大数相乘可能溢出。第二，C[i][0]和C[i][i]都要初始化为1，不初始化或者漏掉一个，边界用例就会错。另外，i的枚举可以提前剪枝，一旦i * A > K就能break，这个优化虽然小，但能让逻辑更清晰。

2.3 纸牌游戏：区间DP的入门佳例

题目是经典的取纸牌问题：N张纸牌排成一排，两个人轮流从最左端或最右端取走一张牌，都采取最优策略，问先手最终能拿到的最大分数总和。

这道题我当初做的版本要求输出先手最多能拿到多少分。可以用区间DP，设dp[i][j]表示在区间[i, j]内，当前玩家能拿到的最大分数。转移的时候，当前玩家要么拿左端的牌，要么拿右端的牌，拿完之后剩下的区间交给对手，而对手也会最优地拿。

状态转移方程：

dp[i][j] = max( a[i] + sum(i+1, j) - dp[i+1][j], a[j] + sum(i, j-1) - dp[i][j-1] )

这里的sum(i+1, j) - dp[i+1][j]的含义是：当前玩家拿走a[i]后，剩余区间[i+1, j]在“最优策略下”对手会拿走dp[i+1][j]，剩下的sum(i+1, j) - dp[i+1][j]就是当前玩家后续还能拿到的分数。

实现时先预处理前缀和数组，方便O(1)求区间和：

vector<int> a(n+1), pre(n+1, 0); for (int i = 1; i <= n; i++) pre[i] = pre[i-1] + a[i]; vector<vector<int>> dp(n+2, vector<int>(n+2, 0)); for (int len = 1; len <= n; len++) { for (int i = 1; i + len - 1 <= n; i++) { int j = i + len - 1; int sumL = pre[j] - pre[i]; // (i+1)到j的和 int sumR = pre[j-1] - pre[i-1]; // i到(j-1)的和 dp[i][j] = max(a[i] + sumL - dp[i+1][j], a[j] + sumR - dp[i][j-1]); } } cout << dp[1][n] << endl;

关键点在于区间长度从小往大枚举，确保dp[i+1][j]和dp[i][j-1]已经算出来。这个循环顺序在二维DP里特别容易写反，一旦反了，结果全是错的。我第一次写的时候用左端点i从1到n、右端点j从i到n的顺序枚举，结果子区间的dp还没算就用了。后来改成按len枚举才AC。

2.4 安排机器：贪心排序的细节处理

这题是2018腾讯春招里区分度比较高的一道。题意大致是：有n台机器和m个任务，机器有运行时间和等级，任务也有运行时间和等级。一台机器只能执行一个任务，且机器的运行时间和等级都要不小于任务的要求。每完成一个任务，收益是200 * 任务时间 + 3 * 任务等级。问最多能完成多少个任务，最大收益是多少。

首先要想明白贪心策略。因为收益中时间占比高达200倍，所以优先处理时间长的任务；对于同一个任务，要选择满足要求的机器中等级最低的那台，把高等级机器留给后面可能要求更高的任务。两个条件结合起来，就是先按时间降序处理任务，同时用双指针把时间足够的机器筛选出来，再按等级匹配。

我用一个等级计数数组来管理候选机器，因为等级范围通常在0到100之间，数组比multiset更轻量：

struct Item { int time, level; bool operator<(const Item& other) const { return time > other.time; // 按时间降序 } }; vector<Item> machines(n), tasks(m); sort(machines.begin(), machines.end()); sort(tasks.begin(), tasks.end()); vector<int> cnt(105, 0); int machineIdx = 0; long long ansCnt = 0, ansProfit = 0; for (auto& task : tasks) { while (machineIdx < n && machines[machineIdx].time >= task.time) { cnt[machines[machineIdx].level]++; machineIdx++; } for (int lv = task.level; lv <= 100; lv++) { if (cnt[lv] > 0) { cnt[lv]--; ansCnt++; ansProfit += 200LL * task.time + 3LL * task.level; break; } } }

这题有几个容易翻车的点。第一，收益必须用long long，因为任务时间和等级累计之后很容易超过int范围。第二，机器按时间降序排序后，用machineIdx维护所有时间足够的机器，之后不要再回头处理之前跳过的机器。第三，找等级匹配时要从任务等级往上找，找到的第一个就是“刚刚好”的机器，这样能最大化保留高等级机器。

我有一次在真实笔试里遇到类似的题，因为贪心顺序反了，先按等级排，导致收益少了一大截。后来复盘才意识到，这种“时间权重远大于等级”的收益设计，本身就是在暗示你要优先处理时间维度。

3. 实操过程与稳定落地的刷题准备

3.1 搭一个顺手的本地刷题环境

刷题环境不需要太复杂，但一定要顺手。我个人的习惯是本地用VS Code配C++17，再开一个Python3终端备用。C++用来写对性能要求高的题，Python用来快速验证思路。

VS Code里我会装C/C++扩展，配置好Code Runner，这样写完后一键运行。另外，一定要开“编译输出”窗口，方便看到编译错误。如果你用的是Mac或者Linux，直接用g++编译也完全没问题，关键是调试断点要会用。

环境这块有个容易被忽视的点：在线笔试的编译器版本可能比较老，C++11/14是最稳妥的。像auto、vector初始化列表这些语法可以用，但那些C++17才有的特性，比如if constexpr、string_view，最好别在笔试里用。

3.2 输入输出模板与调试技巧

很多笔试的输入输出是不给文件名的，直接标准输入输出。你要保证代码能在“一段测试数据到EOF，或者第一行给一个T表示测试组数”这两种模式下都能快速切换。

我常用的C++模板长这样：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; while (cin >> n >> m) { // 单组数据逻辑 } return 0; }

ios::sync_with_stdio(false)和cin.tie(nullptr)这两行，可以显著提升cin的读取速度，避免因为输入量过大导致TLE。不过要注意，关掉同步之后，不能混用scanf和cin。

写二分这类题，我强烈建议先写一个暴力算法，再用随机数据对比验证。比如二分答案题，可以先写一个从1到M逐个枚举的暴力版本，然后用小数据随机对比，一旦结果不一致，马上就能定位是check函数的问题还是二分边界的问题。

3.3 预判数据范围，选对算法复杂度

每道题拿到手，先看数据范围。我用一个简单粗暴的判断标准：n <= 10^5，O(n log n)基本稳；n <= 5000，O(n^2)可以接受；n <= 20，可以直接上状态压缩；n >= 10^9，就要考虑数学公式或者二分答案。

2018这套题里的二分答案题，M可以达到10^9甚至更大，但check函数里cur每轮除以2，实际循环也就几十次，所以完全不慌。而组合数的题，数据范围通常限制在1000以内，用O(n^2)预处理组合数就是最优解。不需要上逆元那套高级操作。

有时候题目没有明确给数据范围，这种时候要靠经验和试探。遇到一道看起来需要DP的题，我会先写一个O(n^3)的版本，跑一遍示例，再根据实际执行时间判断要不要优化。做法虽笨，但省时间。

4. 常见问题与避坑实录

4.1 笔试现场最容易翻车的三个点

第一个是读题不清。2018这套题里的“贪吃的小Q”，题目说“每天吃的巧克力数量不少于前一天的一半”，很多人以为是向下取整，实际上必须是向上取整。如果按向下取整实现，样例可能还是过的，但大数据一定挂。读题时遇到“不少于”“不超过”这类字眼，一定要在草稿纸上把不等式写出来，然后确认整除方向。

第二个是long long溢出。纸牌游戏的分数、安排机器的收益、歌单的方案数，这类涉及累加和乘法的题，答案轻松超出int范围。我有个习惯：只要题目里出现10^9级别的数值，或者存在乘法运算，先默认用long long。即使最后答案在int范围内，多写一个LL后缀也不会扣分。

第三个是单调栈和双指针类题目的死循环。安排机器这题，如果machineIdx没有正确递增，或者内层找等级的循环忘了break，就很容易死循环。调试时最有效的方法是打印关键变量，比如machineIdx、当前任务等级、cnt数组的状态。

4.2 从2018春招题看腾讯笔试的演变趋势

现在回头看2018年这批题，能明显感觉到时代变化。那时候的编程题偏重“算法基本功”，题目短、模型清晰、一眼能看出考什么。近几年的大厂笔试，包括腾讯的，越来越喜欢把算法题包装在具体业务场景里，比如音视频处理、地图坐标转换、云资源调度这类话题。表面上是个业务题，骨子里还是算法和数据结构。

这意味着什么？意味着你不能只背模板，还得学会“翻译”。遇到一道很长的业务背景题，先划掉无关描述，把约束条件抽象成输入变量，把目标抽象成最优化或计数问题。这个能力刷题是练得出来的，尤其是通过2018年这种题干简洁的题目把模型基础打牢，再去看长题干题目，反而会轻松很多。

4.3 刷完这套题之后的扩展路径

如果你把这套题吃透了，下一步我建议按专题刷，而不是按题库刷。今天只练二分答案，做三五道；明天只练区间DP，再做三五道。这种“短周期、重复刺激”的刷法，比每天做一套完整试卷更容易形成肌肉记忆。

专题之外，每周再做一套限时的往年真题，模拟真实的笔试环境。我一般用手机计时，定50分钟，到点就收，写完的代码再回头分析，看是卡在思路还是卡在实现细节。坚持一个月，手感和自信都会明显提升。

我个人在实际操作中最深的体会是：刷题的数量不重要，复盘的质量才重要。每道题做完，不管AC没有，都要给自己留一句总结，比如“这道题的坑在于向上取整”“这类区间题用长度枚举最稳”。等到笔试前，翻这些总结比重新刷一遍题库效率高得多。

最后分享一个我一直在用的小技巧：把容易出错的边界测试用例单独存在一个文件里，比如二分题的n=1, m=1、DP题的n=2、组合数的K=0。每次写完代码，先把这些边界用例跑一遍，再跑示例。这个习惯帮我避开了至少一半的罚时。