每年春招季牛客网上都会被“腾讯2018春招技术类编程题汇总”这套题刷屏。别以为过去了五六年就没参考价值恰恰相反这几道题几乎把大厂笔试最爱考的几类算法模型全串了一遍数学规律、组合计数、贪心匹配、二分答案、博弈Nim、二分图匹配。我当年就是把这套题翻来覆去刷了三遍后来面其他厂笔试时碰上不少变形题基本都能一眼看穿考点。这篇文章不打算做干巴巴的题解罗列而是按我实际刷题的复盘顺序把每道题的思考过程、正确解法和最容易踩的坑一起聊透。1. 腾讯2018春招这套题到底在考什么能力1.1 回看六道题的知识点分布先列一下这套题里比较有代表性的六道题方便后面逐题展开题目核心考点难度翻转数列数学规律、等差数列求和简单小Q的歌单组合数计数、取模运算中等偏易安排机器贪心策略、有序容器匹配中等贪吃的小Q二分答案、最优性判定中等纸牌游戏质因数分解、Nim博弈中等偏难画家小Q连续段划分、二分图最小点覆盖难从这张表能看出来腾讯笔试不像某些厂喜欢堆冷门数据结构它更看重你把一个实际问题抽象成经典模型的能力。六道题里没有一道需要手写红黑树或者后缀自动机但每道题都需要你在几分钟内想清楚“这题本质是什么”。1.2 题面风格与笔试节奏40分钟要做到什么程度当时腾讯春招技术岗的笔试时长一般是90到120分钟编程题通常有3到5道有的岗位还会带客观选择题。这套汇总里的题单看难度梯度设计得很有意思前两道属于“热身题”保证基础扎实的同学能拿分中间两道需要一点算法思维但模板化程度高最后两道是拉分题用来区分真正有竞赛思维和只刷过模板的候选人。我自己的切身体会是笔试现场最怕的不是题不会做而是前面简单题写太慢导致最后没时间碰难题。正常情况下翻转数列应该在5分钟内拿下小Q的歌单控制在10分钟左右安排机器和贪吃的小Q各留15分钟最后两道题如果没思路至少要把暴力解法写上拿部分分。这个时间分配是很多过来人用血泪换来的经验后面我还会细说。2. 送分题里的陷阱翻转数列与小Q的歌单2.1 翻转数列看着像模拟实际上是等差数列求和这道题的题面很短给定整数n和m满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4...每隔m个符号翻转一次最初符号为负号。求这串数列的前n项和。看一眼题目很多人第一反应是直接模拟开一个循环从1遍历到n根据当前下标判断符号累加求和。这种写法在n比较小的时候没问题但这道题真正的坑就在这里——题面故意没有给数据范围实际测试数据里n可能达到10的9次方级别。如果按模拟写要么超时要么long long溢出处理不当直接WA。正确做法是先找规律。把数列按每2m个数分一组观察每一组的符号分布。以n8, m2为例-1 -2 3 4 -5 -6 7 8每一组4个数的和是(-1-234) 4也就是m的平方。这个规律可以严格推导每组前m个数为负后m个数为正把对应位置的数配对比如第一组里-1和3、-2和4每一对差值正好是m一共m对所以每组和是m乘以m等于m的平方。于是答案就变成了共有n/(2m)组每组和m²总答案为 n/(2m) * m²化简一下就是 n*m/2。这里要注意用long long因为n和m的乘积可能超出int范围。#include iostream using namespace std; int main() { long long n, m; cin n m; cout n * m / 2 endl; return 0; }这道题给我们的启发是遇到“数列求和”类题目先别急着模拟多列几组数据找规律尤其是当数据范围没有明确给出时O(1)公式往往是出题人的本意。2.2 小Q的歌单组合数预处理和取模的细节小Q有X首长度为A的歌和Y首长度为B的歌现在想用这些歌组成一个总长度恰好为K的歌单每首歌最多用一次问有多少种组合方式。结果对1000000007取模。这题的核心是枚举第一类歌的数量。假设选i首长度为A的歌那么剩余长度K - iA必须由长度为B的歌补足要求(K - iA)能被B整除且对应的数量j不超过Y。对于每一对合法的(i, j)方案数是C(X, i) * C(Y, j)累加所有情况即可。组合数怎么求X和Y的范围是0到100所以直接用杨辉三角预处理组合数就够了复杂度O(100²)。这里有几个容易翻车的地方取模是1000000007不是1000000009抄错模数直接全错K - i*A可能是负数要在循环里判断break不然continue也能造成不必要的计算中间乘法要先对两个组合数取模再相乘最后再取模防止long long溢出。const int MOD 1000000007; const int MAXN 105; long long C[MAXN][MAXN]; void initC() { 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; } } } int main() { int K, A, X, B, Y; cin K A X B Y; initC(); long long ans 0; for (int i 0; i X; i) { int remain K - i * A; if (remain 0) break; 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; return 0; }这类“从物品A中选i件、物品B中选j件”的计数题在大厂笔试里出现频率极高套路非常固定。遇到第一反应一定是枚举一种物品的数量再判断另一种是否合法而不是直接去想什么母函数、生成函数现场笔试没那么多时间给你炫技。3. 经典算法题的正确打开方式安排机器与贪吃的小Q3.1 安排机器贪心顺序为什么是先时间后难度这道题描述起来有点绕但建模之后非常经典有n个任务和m台机器每个任务有两个属性所需时间和难度每台机器也有两个属性可运行时间和级别。一个任务要分配给一台机器必须满足机器运行时间不小于任务时间机器级别不小于任务难度。每个任务的收益等于200任务时间 3任务难度问在收益最大的前提下最多能完成多少任务输出完成任务数和总收益。我一开始的思路是直接按收益从大到小排序任务然后对每个任务找一台满足条件的机器。这个思路方向对但实现上有个关键点机器匹配时要选“时间满足条件且级别刚好够用”的那台而不是随便选一台。标准的贪心做法是任务和机器都按时间从大到小排序遍历每个任务把时间上满足当前任务需求的机器全部加入一个按级别排序的有序集合在当前任务时间一定的情况下从集合里选出级别大于等于任务难度的最小机器。为什么这样做是对的因为收益公式里200是3的好几十倍时间对收益的影响远大于难度所以优先满足时间大的任务。而在同一时间条件下为了不浪费高等级的机器应该选择级别刚好能满足任务需求的最小机器把更高等级的机器留给后面难度更大的任务。#include bits/stdc.h using namespace std; struct Node { int x, y; bool operator (const Node other) const { return x other.x; } }; int main() { int n, m; cin n m; vectorNode task(n), machine(m); for (int i 0; i n; i) cin task[i].x task[i].y; for (int i 0; i m; i) cin machine[i].x machine[i].y; sort(task.begin(), task.end()); sort(machine.begin(), machine.end()); multisetint levels; long long profit 0; int cnt 0; int j 0; for (int i 0; i n; i) { while (j m machine[j].x task[i].x) { levels.insert(machine[j].y); j; } auto it levels.lower_bound(task[i].y); if (it ! levels.end()) { profit 200LL * task[i].x 3LL * task[i].y; cnt; levels.erase(it); } } cout cnt profit endl; return 0; }这里最容易犯的错是把机器按“级别优先”排序或者对每个任务重新扫描所有机器。前者会破坏时间约束后者复杂度太高直接超时。用multiset维护“当前可用的机器级别”每次lower_bound找一个最合适的机器整体复杂度是O((nm) log m)笔试数据量下毫无压力。顺便多说一句multiset的erase方法要传迭代器如果直接erase(it)只删一个元素写成erase(*it)会把所有等值的元素全删掉这个细节我看过不少人踩坑。3.2 贪吃的小Q二分答案的check函数怎么写才不容易错小Q的父母要出差N天走之前留下M块巧克力。小Q给自己定了个规矩每天吃的巧克力数量不能少于前一天的一半但他又不想在父母回来之前把巧克力吃完问第一天最多能吃多少块。注意这道题的问法是“第一天最多能吃多少块”所以核心思路是二分答案。假设第一天吃x块为了能撑过N天后面的每一天都应该吃尽量少也就是严格按“前一天的一半向上取整”来吃也就是ceil(prev/2)块。这样N天总共消耗的巧克力数如果不超过M说明x可行可以尝试更大的x否则就要调小。check函数最稳妥的写法是累加而不是用等比数列公式因为每天的消耗量是向上取整的没法简单地套公式。我见过不少人在这一步翻车试图列方程直接解出最大第一天数量结果边界情况全错。老老实实写循环N的范围通常不会太大二分加模拟完全够用。bool check(long long first, int N, long long M) { long long total 0; long long cur first; for (int i 0; i N; i) { total cur; cur (cur 1) / 2; } return total M; } int main() { int N; long long M; cin N M; long long l 1, r M, ans 1; while (l r) { long long mid (l r) / 2; if (check(mid, N, M)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans endl; return 0; }二分答案最怕的是check函数写错方向。这里判断标准是“每天吃最少的情况下总消耗量不超过M”因为题目要求不能提前吃完所以只要最小消耗都不满足那第一天数量就得减少反过来如果最小消耗能撑过N天哪怕最后一天剩很多巧克力也没关系题目并没有要求必须吃完只要求不提前断粮。4. 两道容易被卡住的进阶题纸牌游戏与画家小Q4.1 纸牌游戏从取约数到Nim博弈的转化过程这道题的题面是有n张纸牌每张牌上写着一个数字a_i。两个玩家轮流操作每次选择一张牌把牌上的数字x替换成x的任意一个约数但不能等于x本身。轮到谁无法操作谁就输。牛牛先手问先手是否有必胜策略。第一次看到这题容易陷入“约数关系”的细节里无法自拔。但仔细想想一个数x的质因数分解是p1^e1 * p2^e2 * ... * pk^ek每次把x变成它的一个约数本质就是从质因数指数的总量中减少至少1个最多可以一次减完。所以每张牌可以看作一堆石子石子数量等于这个数的质因数指数总和记为Ω(x)玩家每次可以从任意一堆中取走至少1个石子可以取完这就是最经典的Nim博弈。Nim博弈的胜负判定规则是把所有堆的石子数异或起来如果异或结果非0则先手必胜否则先手必败。因此这道题就变成对每个a_i做质因数分解统计指数和把所有指数和求异或看结果是否为0。int primeExp(int x) { int cnt 0; for (int i 2; i * i x; i) { while (x % i 0) { cnt; x / i; } } if (x 1) cnt; return cnt; } int main() { int n; cin n; int xo 0; for (int i 0; i n; i) { int a; cin a; xo ^ primeExp(a); } cout (xo ? Yes : No) endl; return 0; }这里有个容易混淆点如果题目把操作限制为“每次只能把x变成x除以某个质因子”那游戏就从Nim退化成了每个数只能减1的普通博弈胜负只看总操作次数的奇偶性。但原题说的是“任意一个约数”所以必须按Nim的异或和来判。我当时就吃过这个亏第一版代码按奇偶判断交了连样例都没过。实际做题时遇到博弈题先搞清楚每一步的决策空间是“任意数量”还是“固定数量”这决定了是完全不同的解法。4.2 画家小Q连续段建图与最小点覆盖画家小Q这道题是整套里最让人纠结的一道因为网上流传的题面版本很多有的说每次可以涂一整行或一整列有的说可以涂任意长度的一段连续格子描述还有歧义。我以出现较多的版本为准给定一个n行m列的网格初始全是白色目标图案用X和.表示每次操作可以选择一行或一列将其中连续的一段涂成蓝色问最少多少次操作能涂出目标图案。如果你以为每次只能涂一整行或一整列那这题会简单到离谱答案就是需要涂色的行数加需要涂色的列数或者直接做个min。但“连续的一段”这个条件让问题性质完全变了一个X格子既可以通过涂它所在行的一个连续段完成也可以通过涂它所在列的一个连续段完成我们要选最少的线段覆盖所有X。这个模型可以转化成二分图最小点覆盖把所有横向的连续X段作为左部顶点所有纵向的连续X段作为右部顶点每个X格子对应一条从它所属横段到它所属纵段的边。每选择一次操作等价于选中一个顶点覆盖所有与它相连的边。用最少的点覆盖所有边这就是二分图最小点覆盖问题。根据柯尼希定理二分图最小点覆盖数等于最大匹配数所以跑一遍匈牙利算法就能得到答案。实现上要注意建图之前先扫描一遍网格把每个X格子所属的横段编号和纵段编号标出来。bool dfs(int u) { for (int v : graph[u]) { if (!vis[v]) { vis[v] true; if (match[v] -1 || dfs(match[v])) { match[v] u; return true; } } } return false; } // 主流程中枚举所有横段顶点尝试匹配纵段顶点 // 答案就是最大匹配数我在刷题群里看到不少人质疑这道题的难度觉得不就是涂格子嘛。实际上能把“连续段”抽象成图顶点、把“格子”抽象成边这层转化能力才是大厂笔试真正想考察的。如果现场想不出来可以退一步写个搜索对纯暴力拿部分分但思路一定要往二分图匹配上靠。5. 复盘这套题留给后来人的刷题方法5.1 笔试现场最容易丢分的三种情况把这套题完整刷完我总结了笔试现场最容易丢分的三种情况基本是血泪教训送分题没看清数据范围。翻转数列如果真按模拟写大样例直接超时你还不知道错在哪。所以读题时看到“求和”优先想数学公式看到“计数”优先想组合数这些思维定式是刷题刷出来的不是天赋。贪心题证明不完整。安排机器那道题很多人贪心方向对了但说不出为什么结果一改排序规则就错。建议平时练习时多问自己一句“这个贪心策略的反例会出现在哪里”能把反例想清楚笔试时就不慌。博弈题把模型判错。纸牌游戏里“任意约数”和“除以质因子”是两种完全不同的模型一个用异或和一个用奇偶性。审题时圈出关键限定词比多刷十道题都管用。5.2 从这套题延伸出的重点刷题方向这套题还有一个作用就是帮你推断出题人的口味。腾讯笔试的编程题通常不会太偏门但特别喜欢考“经典模型加一层包装”的题目翻转数列是数学包装小Q的歌单是计数包装安排机器是贪心加数据结构包装贪吃的小Q是二分包装纸牌游戏是博弈包装画家小Q是图论包装。所以你备考的时候不要沉迷于刷偏难怪题把二分答案、贪心策略、组合数、Nim博弈、二分图匹配这五类核心模板吃透再练习从题面里剥离包装看到本质基本就能覆盖大多数大厂笔试的编程题范围。至于具体怎么练我个人的习惯是每道题做完后用一句话在题目旁边写下“这道题的本质模型是什么”然后每周把这周做过的题翻出来重新归类。坚持一两个月后看到新题时大脑会自动匹配已有模型速度和准确率都会明显上一个台阶。这套腾讯2018春招的题目我到现在都还留着偶尔拿出来给学弟学妹做模拟练手确实是不可多得的经典素材。
腾讯2018春招编程题复盘：六大算法模型一次讲透
每年春招季牛客网上都会被“腾讯2018春招技术类编程题汇总”这套题刷屏。别以为过去了五六年就没参考价值恰恰相反这几道题几乎把大厂笔试最爱考的几类算法模型全串了一遍数学规律、组合计数、贪心匹配、二分答案、博弈Nim、二分图匹配。我当年就是把这套题翻来覆去刷了三遍后来面其他厂笔试时碰上不少变形题基本都能一眼看穿考点。这篇文章不打算做干巴巴的题解罗列而是按我实际刷题的复盘顺序把每道题的思考过程、正确解法和最容易踩的坑一起聊透。1. 腾讯2018春招这套题到底在考什么能力1.1 回看六道题的知识点分布先列一下这套题里比较有代表性的六道题方便后面逐题展开题目核心考点难度翻转数列数学规律、等差数列求和简单小Q的歌单组合数计数、取模运算中等偏易安排机器贪心策略、有序容器匹配中等贪吃的小Q二分答案、最优性判定中等纸牌游戏质因数分解、Nim博弈中等偏难画家小Q连续段划分、二分图最小点覆盖难从这张表能看出来腾讯笔试不像某些厂喜欢堆冷门数据结构它更看重你把一个实际问题抽象成经典模型的能力。六道题里没有一道需要手写红黑树或者后缀自动机但每道题都需要你在几分钟内想清楚“这题本质是什么”。1.2 题面风格与笔试节奏40分钟要做到什么程度当时腾讯春招技术岗的笔试时长一般是90到120分钟编程题通常有3到5道有的岗位还会带客观选择题。这套汇总里的题单看难度梯度设计得很有意思前两道属于“热身题”保证基础扎实的同学能拿分中间两道需要一点算法思维但模板化程度高最后两道是拉分题用来区分真正有竞赛思维和只刷过模板的候选人。我自己的切身体会是笔试现场最怕的不是题不会做而是前面简单题写太慢导致最后没时间碰难题。正常情况下翻转数列应该在5分钟内拿下小Q的歌单控制在10分钟左右安排机器和贪吃的小Q各留15分钟最后两道题如果没思路至少要把暴力解法写上拿部分分。这个时间分配是很多过来人用血泪换来的经验后面我还会细说。2. 送分题里的陷阱翻转数列与小Q的歌单2.1 翻转数列看着像模拟实际上是等差数列求和这道题的题面很短给定整数n和m满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4...每隔m个符号翻转一次最初符号为负号。求这串数列的前n项和。看一眼题目很多人第一反应是直接模拟开一个循环从1遍历到n根据当前下标判断符号累加求和。这种写法在n比较小的时候没问题但这道题真正的坑就在这里——题面故意没有给数据范围实际测试数据里n可能达到10的9次方级别。如果按模拟写要么超时要么long long溢出处理不当直接WA。正确做法是先找规律。把数列按每2m个数分一组观察每一组的符号分布。以n8, m2为例-1 -2 3 4 -5 -6 7 8每一组4个数的和是(-1-234) 4也就是m的平方。这个规律可以严格推导每组前m个数为负后m个数为正把对应位置的数配对比如第一组里-1和3、-2和4每一对差值正好是m一共m对所以每组和是m乘以m等于m的平方。于是答案就变成了共有n/(2m)组每组和m²总答案为 n/(2m) * m²化简一下就是 n*m/2。这里要注意用long long因为n和m的乘积可能超出int范围。#include iostream using namespace std; int main() { long long n, m; cin n m; cout n * m / 2 endl; return 0; }这道题给我们的启发是遇到“数列求和”类题目先别急着模拟多列几组数据找规律尤其是当数据范围没有明确给出时O(1)公式往往是出题人的本意。2.2 小Q的歌单组合数预处理和取模的细节小Q有X首长度为A的歌和Y首长度为B的歌现在想用这些歌组成一个总长度恰好为K的歌单每首歌最多用一次问有多少种组合方式。结果对1000000007取模。这题的核心是枚举第一类歌的数量。假设选i首长度为A的歌那么剩余长度K - iA必须由长度为B的歌补足要求(K - iA)能被B整除且对应的数量j不超过Y。对于每一对合法的(i, j)方案数是C(X, i) * C(Y, j)累加所有情况即可。组合数怎么求X和Y的范围是0到100所以直接用杨辉三角预处理组合数就够了复杂度O(100²)。这里有几个容易翻车的地方取模是1000000007不是1000000009抄错模数直接全错K - i*A可能是负数要在循环里判断break不然continue也能造成不必要的计算中间乘法要先对两个组合数取模再相乘最后再取模防止long long溢出。const int MOD 1000000007; const int MAXN 105; long long C[MAXN][MAXN]; void initC() { 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; } } } int main() { int K, A, X, B, Y; cin K A X B Y; initC(); long long ans 0; for (int i 0; i X; i) { int remain K - i * A; if (remain 0) break; 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; return 0; }这类“从物品A中选i件、物品B中选j件”的计数题在大厂笔试里出现频率极高套路非常固定。遇到第一反应一定是枚举一种物品的数量再判断另一种是否合法而不是直接去想什么母函数、生成函数现场笔试没那么多时间给你炫技。3. 经典算法题的正确打开方式安排机器与贪吃的小Q3.1 安排机器贪心顺序为什么是先时间后难度这道题描述起来有点绕但建模之后非常经典有n个任务和m台机器每个任务有两个属性所需时间和难度每台机器也有两个属性可运行时间和级别。一个任务要分配给一台机器必须满足机器运行时间不小于任务时间机器级别不小于任务难度。每个任务的收益等于200任务时间 3任务难度问在收益最大的前提下最多能完成多少任务输出完成任务数和总收益。我一开始的思路是直接按收益从大到小排序任务然后对每个任务找一台满足条件的机器。这个思路方向对但实现上有个关键点机器匹配时要选“时间满足条件且级别刚好够用”的那台而不是随便选一台。标准的贪心做法是任务和机器都按时间从大到小排序遍历每个任务把时间上满足当前任务需求的机器全部加入一个按级别排序的有序集合在当前任务时间一定的情况下从集合里选出级别大于等于任务难度的最小机器。为什么这样做是对的因为收益公式里200是3的好几十倍时间对收益的影响远大于难度所以优先满足时间大的任务。而在同一时间条件下为了不浪费高等级的机器应该选择级别刚好能满足任务需求的最小机器把更高等级的机器留给后面难度更大的任务。#include bits/stdc.h using namespace std; struct Node { int x, y; bool operator (const Node other) const { return x other.x; } }; int main() { int n, m; cin n m; vectorNode task(n), machine(m); for (int i 0; i n; i) cin task[i].x task[i].y; for (int i 0; i m; i) cin machine[i].x machine[i].y; sort(task.begin(), task.end()); sort(machine.begin(), machine.end()); multisetint levels; long long profit 0; int cnt 0; int j 0; for (int i 0; i n; i) { while (j m machine[j].x task[i].x) { levels.insert(machine[j].y); j; } auto it levels.lower_bound(task[i].y); if (it ! levels.end()) { profit 200LL * task[i].x 3LL * task[i].y; cnt; levels.erase(it); } } cout cnt profit endl; return 0; }这里最容易犯的错是把机器按“级别优先”排序或者对每个任务重新扫描所有机器。前者会破坏时间约束后者复杂度太高直接超时。用multiset维护“当前可用的机器级别”每次lower_bound找一个最合适的机器整体复杂度是O((nm) log m)笔试数据量下毫无压力。顺便多说一句multiset的erase方法要传迭代器如果直接erase(it)只删一个元素写成erase(*it)会把所有等值的元素全删掉这个细节我看过不少人踩坑。3.2 贪吃的小Q二分答案的check函数怎么写才不容易错小Q的父母要出差N天走之前留下M块巧克力。小Q给自己定了个规矩每天吃的巧克力数量不能少于前一天的一半但他又不想在父母回来之前把巧克力吃完问第一天最多能吃多少块。注意这道题的问法是“第一天最多能吃多少块”所以核心思路是二分答案。假设第一天吃x块为了能撑过N天后面的每一天都应该吃尽量少也就是严格按“前一天的一半向上取整”来吃也就是ceil(prev/2)块。这样N天总共消耗的巧克力数如果不超过M说明x可行可以尝试更大的x否则就要调小。check函数最稳妥的写法是累加而不是用等比数列公式因为每天的消耗量是向上取整的没法简单地套公式。我见过不少人在这一步翻车试图列方程直接解出最大第一天数量结果边界情况全错。老老实实写循环N的范围通常不会太大二分加模拟完全够用。bool check(long long first, int N, long long M) { long long total 0; long long cur first; for (int i 0; i N; i) { total cur; cur (cur 1) / 2; } return total M; } int main() { int N; long long M; cin N M; long long l 1, r M, ans 1; while (l r) { long long mid (l r) / 2; if (check(mid, N, M)) { ans mid; l mid 1; } else { r mid - 1; } } cout ans endl; return 0; }二分答案最怕的是check函数写错方向。这里判断标准是“每天吃最少的情况下总消耗量不超过M”因为题目要求不能提前吃完所以只要最小消耗都不满足那第一天数量就得减少反过来如果最小消耗能撑过N天哪怕最后一天剩很多巧克力也没关系题目并没有要求必须吃完只要求不提前断粮。4. 两道容易被卡住的进阶题纸牌游戏与画家小Q4.1 纸牌游戏从取约数到Nim博弈的转化过程这道题的题面是有n张纸牌每张牌上写着一个数字a_i。两个玩家轮流操作每次选择一张牌把牌上的数字x替换成x的任意一个约数但不能等于x本身。轮到谁无法操作谁就输。牛牛先手问先手是否有必胜策略。第一次看到这题容易陷入“约数关系”的细节里无法自拔。但仔细想想一个数x的质因数分解是p1^e1 * p2^e2 * ... * pk^ek每次把x变成它的一个约数本质就是从质因数指数的总量中减少至少1个最多可以一次减完。所以每张牌可以看作一堆石子石子数量等于这个数的质因数指数总和记为Ω(x)玩家每次可以从任意一堆中取走至少1个石子可以取完这就是最经典的Nim博弈。Nim博弈的胜负判定规则是把所有堆的石子数异或起来如果异或结果非0则先手必胜否则先手必败。因此这道题就变成对每个a_i做质因数分解统计指数和把所有指数和求异或看结果是否为0。int primeExp(int x) { int cnt 0; for (int i 2; i * i x; i) { while (x % i 0) { cnt; x / i; } } if (x 1) cnt; return cnt; } int main() { int n; cin n; int xo 0; for (int i 0; i n; i) { int a; cin a; xo ^ primeExp(a); } cout (xo ? Yes : No) endl; return 0; }这里有个容易混淆点如果题目把操作限制为“每次只能把x变成x除以某个质因子”那游戏就从Nim退化成了每个数只能减1的普通博弈胜负只看总操作次数的奇偶性。但原题说的是“任意一个约数”所以必须按Nim的异或和来判。我当时就吃过这个亏第一版代码按奇偶判断交了连样例都没过。实际做题时遇到博弈题先搞清楚每一步的决策空间是“任意数量”还是“固定数量”这决定了是完全不同的解法。4.2 画家小Q连续段建图与最小点覆盖画家小Q这道题是整套里最让人纠结的一道因为网上流传的题面版本很多有的说每次可以涂一整行或一整列有的说可以涂任意长度的一段连续格子描述还有歧义。我以出现较多的版本为准给定一个n行m列的网格初始全是白色目标图案用X和.表示每次操作可以选择一行或一列将其中连续的一段涂成蓝色问最少多少次操作能涂出目标图案。如果你以为每次只能涂一整行或一整列那这题会简单到离谱答案就是需要涂色的行数加需要涂色的列数或者直接做个min。但“连续的一段”这个条件让问题性质完全变了一个X格子既可以通过涂它所在行的一个连续段完成也可以通过涂它所在列的一个连续段完成我们要选最少的线段覆盖所有X。这个模型可以转化成二分图最小点覆盖把所有横向的连续X段作为左部顶点所有纵向的连续X段作为右部顶点每个X格子对应一条从它所属横段到它所属纵段的边。每选择一次操作等价于选中一个顶点覆盖所有与它相连的边。用最少的点覆盖所有边这就是二分图最小点覆盖问题。根据柯尼希定理二分图最小点覆盖数等于最大匹配数所以跑一遍匈牙利算法就能得到答案。实现上要注意建图之前先扫描一遍网格把每个X格子所属的横段编号和纵段编号标出来。bool dfs(int u) { for (int v : graph[u]) { if (!vis[v]) { vis[v] true; if (match[v] -1 || dfs(match[v])) { match[v] u; return true; } } } return false; } // 主流程中枚举所有横段顶点尝试匹配纵段顶点 // 答案就是最大匹配数我在刷题群里看到不少人质疑这道题的难度觉得不就是涂格子嘛。实际上能把“连续段”抽象成图顶点、把“格子”抽象成边这层转化能力才是大厂笔试真正想考察的。如果现场想不出来可以退一步写个搜索对纯暴力拿部分分但思路一定要往二分图匹配上靠。5. 复盘这套题留给后来人的刷题方法5.1 笔试现场最容易丢分的三种情况把这套题完整刷完我总结了笔试现场最容易丢分的三种情况基本是血泪教训送分题没看清数据范围。翻转数列如果真按模拟写大样例直接超时你还不知道错在哪。所以读题时看到“求和”优先想数学公式看到“计数”优先想组合数这些思维定式是刷题刷出来的不是天赋。贪心题证明不完整。安排机器那道题很多人贪心方向对了但说不出为什么结果一改排序规则就错。建议平时练习时多问自己一句“这个贪心策略的反例会出现在哪里”能把反例想清楚笔试时就不慌。博弈题把模型判错。纸牌游戏里“任意约数”和“除以质因子”是两种完全不同的模型一个用异或和一个用奇偶性。审题时圈出关键限定词比多刷十道题都管用。5.2 从这套题延伸出的重点刷题方向这套题还有一个作用就是帮你推断出题人的口味。腾讯笔试的编程题通常不会太偏门但特别喜欢考“经典模型加一层包装”的题目翻转数列是数学包装小Q的歌单是计数包装安排机器是贪心加数据结构包装贪吃的小Q是二分包装纸牌游戏是博弈包装画家小Q是图论包装。所以你备考的时候不要沉迷于刷偏难怪题把二分答案、贪心策略、组合数、Nim博弈、二分图匹配这五类核心模板吃透再练习从题面里剥离包装看到本质基本就能覆盖大多数大厂笔试的编程题范围。至于具体怎么练我个人的习惯是每道题做完后用一句话在题目旁边写下“这道题的本质模型是什么”然后每周把这周做过的题翻出来重新归类。坚持一两个月后看到新题时大脑会自动匹配已有模型速度和准确率都会明显上一个台阶。这套腾讯2018春招的题目我到现在都还留着偶尔拿出来给学弟学妹做模拟练手确实是不可多得的经典素材。
