想进拼多多做后端、算法岗的同学应该多少都翻过这套2019秋招编程题。它在求职圈流传度相当高不是因为题目难到劝退而是因为它非常典型题量不算大代码量不夸张但几乎每一道题里都埋着一两个让你AC不了的细节坑。我当年刷这套题的时候就有个很深的感受——拼多多出题偏爱把算法藏在很生活化的场景里比如分礼物、打骰子、算乘积看起来人都能读懂但一写代码就出问题。这篇文章就把这套题好好复盘一遍。我会先拆解拼多多笔试的出题风格和难度结构然后还原几道高频出现的典型题目逐个讲清解题思路再给出可运行的完整代码和复杂度分析最后把我自己踩过的坑、以及在线笔试平台常见的问题全部整理出来。不管你是刚准备秋招的大三学生还是想转码刷题的在职人士这套复盘都能直接用上。1. 拼多多2019秋招笔试画像出题风格与难度定位1.1 题型分布四道题藏着哪些考点从网上流传的各个版本来看拼多多2019秋招这场笔试的编程题一般是四道考试时间90到120分钟。题目类型相对固定按出现频率排序大概是贪心、模拟、字符串处理、基础数学。这个分布其实很能说明问题——拼多多并不像一些硬核大厂那样上来就甩你一道后缀自动机或者平衡树而是更看重“用常规算法解决实际业务问题”的能力。很多人以为大厂笔试一定全是DP和图论压轴实际上拼多多这套题目的难度曲线是平缓上升的。第一题通常是把一个生活场景简化成数组操作第二题是典型的排序加贪心第三题开始上字符串或者数学第四题才会出现一些需要灵光一现的点。整场笔试不会让你陷入“完全没思路”的绝望但会在你自以为做对的时候通过边界数据狠狠给你上一课。从考点覆盖来看这套题也很适合作为秋招复习的入门材料。它不需要你掌握冷门算法只要你把排序、双指针、模拟乘法、期望计算这些基础功练扎实再加上对边界条件的敏感度就能拿到不错的分数。反过来如果你连这些基础题都会翻车那后面遇到真正的难题会更吃力。1.2 难度梯度与时间分配建议我在复盘这套题的时候把四道题按难度分成了三个梯度。第一梯队的题属于“10分钟内必须AC”的送分题特征是思路直白、代码量小主要考察你敢不敢直接写、会不会被复杂化带偏。第二梯队的题属于“想清楚后20分钟搞定”的常规题需要你识别出贪心或者双指针的模型。第三梯队就是“容易写挂”的题不一定难但很考验细节比如大数乘法里的进位、前导零、数据类型溢出。时间分配上我的建议是第一梯队的题控制在10到15分钟第二梯队的题控制在20分钟第三梯队的题先读题、先想清楚再动键盘不要一上来就写。如果第三梯队卡了15分钟还没进展果断先跳过把后面会做的题稳住最后再回来啃。笔试和面试不一样面试你还有机会解释思路笔试只有AC和没AC两种结果所以“抢分”策略比“炫技”重要得多。另外拼多多的笔试平台在线编辑器通常没有代码补全也不能自动保存。这意味着你的代码必须一遍写对不管是变量名还是分号都不能依赖IDE帮你兜底。所以平时刷题时我建议你尽量用普通文本编辑器或者直接在OJ页面里写别一上来就开IDE自动补全不然考场上会非常不适应。2. 真题拆解四道典型题的还原与解法2.1 最大乘积排序后的一行max为什么能覆盖负数先看一道流传度极高的题目。给你一个整数数组长度在3到10^5之间元素可能是正数、负数、零要求从里面选三个数使得它们的乘积最大输出这个最大乘积。我第一次做这道题的时候第一反应是分类讨论全正怎么办、全负怎么办、有正有负怎么办。讨论了半天写出了七八个if-else结果还是漏了一种情况。后来看到一种特别干净的写法先把数组排序然后最大乘积只会出现在两种情况里——要么是最大的三个数相乘要么是最小的两个负数乘最大的正数。其他任何组合都不可能比这两个候选更大。所以直接取max(最小的两个数 * 最大的数, 最大的三个数相乘)就是答案。这个解法的核心是用排序把“选三个数”的排列组合问题降维。你不需要真的去遍历所有三元组因为排序后极端值已经集中在数组两端。如果数组全是负数最大的三个数也就是最接近0的三个相乘反而是最大的如果数组里恰好有零乘积是零的情况也会被这两个候选中的某一个覆盖。很多人栽在这一题上不是不会排序而是没有意识到“两个负数相乘可以变正”这个小学数学知识点会在考场上被放大成一道AC题和一道WA题的区别。2.2 六一儿童节双指针贪心避免O(n*m)超时这道题也是当年讨论度很高的一道。题目大意是有n个孩子每个孩子有一个期望礼物值有m个礼物每个礼物有一个实际大小。只有当礼物大小不低于某个孩子的期望值时这个礼物才能送给这个孩子。每个孩子最多只能拿一个礼物每个礼物也只能给一个孩子问最多能满足多少个孩子。这道题看起来像二分图匹配很多同学一上来就想用匈牙利算法但实际上数据范围根本不需要。你只要把孩子期望值和礼物大小分别排序然后用两个指针贪心匹配就行。核心逻辑是礼物从小到大枚举孩子也从小到大枚举。如果当前礼物能满足当前孩子就匹配上两个指针同时前进如果当前礼物连当前期望最小的孩子都满足不了那这个礼物对后面期望更大的孩子更不可能直接丢弃礼物指针前进。这样做的复杂度是排序的O(n log n m log m)加一遍扫描的O(n m)比暴力的O(nm)不知道快到哪里去了。我见过有同学在这道题上写了两层for循环本地跑小数据一点问题没有一提交就超时然后开始怀疑评测机有毛病。其实评测机没毛病就是数据量上来了O(nm)撑不住。这道题也是拼多多“把算法藏在节日场景里”的一个典型代表画一个蛋糕或者礼物的皮里面考的还是最朴素的排序贪心。2.3 大整数相乘字符串乘法把进位写对字符串处理的题在拼多多笔试里出现频率很高。这道题让你输入两个可能长达几千位的大整数用字符串表示输出它们的乘积。如果你直接用int或者long long去接那肯定溢出所以必须模拟手工乘法——也就是每个位上的数字逐位相乘再累加进位。具体做法是先把两个字符串反转存成两个int数组第i位和第j位相乘的结果累加到结果的第ij位。所有位乘完之后统一处理进位。这里有个特别容易踩的坑进位不能边乘边处理否则会乱掉。最好先把所有乘积都累加到对应位置上最后再从头到尾扫一遍做进位。进位做完之后结果数组的长度可能比实际需要的长前面会有多余的零输出前要从最高位开始跳过前导零。这道题我当年写的时候犯过一个很蠢的错误进位循环少跑了一位导致类似“999*999”这种数据结果中间少了一个数。后来调了半天才发现进位必须从低位到高位一直处理到结果数组的最高位不能只处理到较短数组的长度就停。这种细节题代码量不大但就是非常考验你对过程的控制力。2.4 骰子期望别写DP用期望线性性还有一道概率题在多个版本的题解里都出现过。题目大概是有一个n面骰子点数从1到n把它抛掷m次求m次点数之和的期望。m和n的范围可能很大大到用DP完全不可能。这题其实是一道典型的“送命题”——看起来像概率DP实际上用期望的线性性质一次就能算完。每次掷骰子的期望是(1 n) / 2m次独立重复实验的总期望就是m乘以单次期望也就是 m * (n 1) / 2。如果你非要写DP去枚举所有可能的和数据范围一大就直接爆炸不仅超时连内存都扛不住。这题给我们的启发是笔试里遇到“看起来很复杂”的概率题先想一想有没有数学上的简化方式而不是急着设状态转移。期望的线性性、前缀和、差分、排序后贪心这些“降维打击”的手段才是笔试真正想考察的东西。拼多多出这套题说到底就是想看你能不能从业务场景里识别出最核心的数学模型。3. 完整代码实现与复杂度复盘3.1 C版最大乘积与大整数相乘先看最大乘积这题。用C写排序用sort最关键的比较逻辑就两行。#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorlong long a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long ans max(a[0] * a[1] * a[n - 1], a[n - 3] * a[n - 2] * a[n - 1]); cout ans endl; } return 0; }注意几个点数组元素要开成long long因为极端情况下三个10^9量级的数相乘结果会远超int范围。排序后a[n-3] * a[n-2] * a[n-1]是最大三个正数或最接近零的三个数的乘积而a[0] * a[1] * a[n-1]是让两个负数相乘变正后乘最大正数的情况。这时候你可能会问如果数组里只有一个负数那a[0]和a[1]两个数相乘不仅不会变正反而可能是很负的数和数相乘别担心结果取max时自然会淘汰掉差的候选。再看大整数相乘的C实现。先写好一个乘法的子函数主函数里读入字符串调用即可。#include bits/stdc.h using namespace std; string multiply(string num1, string num2) { int n num1.size(), m num2.size(); vectorint a(n), b(m), c(n m, 0); for (int i 0; i n; i) a[i] num1[n - 1 - i] - 0; for (int i 0; i m; i) b[i] num2[m - 1 - i] - 0; for (int i 0; i n; i) for (int j 0; j m; j) c[i j] a[i] * b[j]; for (int i 0; i 1 n m; i) { c[i 1] c[i] / 10; c[i] % 10; } int idx n m - 1; while (idx 0 c[idx] 0) idx--; string ans ; for (int i idx; i 0; i--) ans char(0 c[i]); return ans; } int main() { string s1, s2; while (cin s1 s2) { cout multiply(s1, s2) endl; } return 0; }这里最容易出错的位置有两个。第一个是c数组的长度为什么要开n m两个数相乘位数不会超过两个数位数之和。第二个是进位循环的终止条件必须处理到n m - 2下标之后还要继续向高位进位所以循环条件写成i 1 n m这样最高位也能通过进位延伸到数组最后一个位置。最后跳过前导零时如果结果本身就是0while (idx 0 c[idx] 0)会停在第一个0上面不会把输出变成空字符串。3.2 Python版六一儿童节与骰子期望用Python写六一儿童节这道题代码可以非常短。注意处理输入时不要被样例的换行格式迷惑直接用空格分割读取所有数字就好。import sys def solve(): data list(map(int, sys.stdin.read().split())) idx 0 n data[idx] idx 1 need sorted(data[idx:idx n]) idx n m data[idx] idx 1 gift sorted(data[idx:idx m]) ans 0 i j 0 while i n and j m: if gift[j] need[i]: ans 1 i 1 j 1 else: j 1 print(ans) if __name__ __main__: solve()这段双指针逻辑可以配合一个简单例子验证。孩子期望是[1, 3, 5]礼物是[2, 4]排序后i0指向1j0指向2。礼物2能满足孩子1匹配i1j1礼物4能满足孩子3匹配i2j2此时礼物用完循环结束。答案2正确。如果当前礼物连期望最小的孩子都满足不了说明这个礼物对谁都满足不了直接丢弃它也就是j这正是代码里else分支做的事情。这个逻辑很朴素但如果不排序直接暴力写两层for循环数据一大马上就超时。骰子期望的Python实现更短核心就是一行数学公式。n, m map(int, input().split()) ans m * (n 1) / 2 print(f{ans:.2f})这里要注意输出格式。有些题目会要求保留两位小数有些会要求输出分数有些甚至要求对某个模数取余。建议读题时先看输出样例的格式再决定用浮点数还是分数形式。如果你担心浮点数精度可以改用Decimal或者直接用分数计算但正常来说这道题的数值用double已经绰绰有余。3.3 复杂度逐题复盘把这四道题的复杂度放在一起对比能更清楚每个方案的优越性。最大乘积排序O(n log n)空间O(1)。暴力枚举所有三元组是O(n^3)数据量10^5时根本不可行。六一儿童节排序O(n log n m log m)扫描O(n m)空间O(1)。暴力两层循环是O(n*m)当n和m都到10^5时直接爆炸。大整数相乘时间复杂度O(nm)其中n和m是两个字符串的长度。由于两个数都可以长达几千位这个O(nm)已经是最朴素且可用的算法更优的还有FFT优化的乘法但笔试场景下字符串模拟就足够了空间O(nm)。骰子期望时间复杂度O(1)空间O(1)。如果写DP枚举所有可能和复杂度会变成O(nm范围)在n和m很大时不仅超时还会爆内存。这个对比非常直观地说明了为什么做题前要先分析数学模型。4. 实战最常见的五个坑从输入到结果输出4.1 多组输入怎么读才算稳笔试平台经常有多组测试数据的习惯也就是你提交的代码要能处理“输入不知道有多少组”的情况。C里可以用while (cin n)来循环读取读到EOF自动结束Python里可以用sys.stdin.read()一次性把所有数据读进来再按顺序解析。我见过不少同学在本地测试时用交互式输入自己手动敲一遍数据没问题但一提交就变成“输出超限”或者“结果错误”。原因多半是死循环没跳出、或者没有处理多组数据直接只读了一组。这里有个小技巧在线笔试的输入格式如果不是明确只有一组最好都按多组处理这是一种“防御式编程”习惯能避免很多无谓的失分。4.2 溢出不只在极限数据里出现关于溢出我想多说两句。很多人只有在看到题目里出现“10^9”这种字眼时才会想到用long long但像最大乘积这种题单个元素在10^9量级时三个数相乘就稳稳超过int范围。如果你不开long long本地小数据测试全对评测数据一大就WA而且你根本找不到原因因为错误不是语法错误而是静默溢出。还有大整数相乘这道题题目已经说了数字可能超出long long范围所以必须用字符串。可如果输入的数字恰好不大你用long long去转也能过样例这就非常危险——样例只是让你理解题意不代表评测数据的边界。我的建议是只要题目涉及乘法、加法累加、幂运算一律先考虑结果会不会超过int范围再决定用什么类型。4.3 暴力枚举能过样例但过不了评测六一儿童节那道题是最典型的例子。样例数据小两层for循环怎么写都能过。但评测数据里n和m同时到10^5的时候O(n*m)的代码跑起来就是天荒地老。笔试平台一般有时间和内存的双重限制超时和超内存都是直接判零分不会因为“思路对但没优化”而手下留情。这里的教训是写代码之前先看一眼数据范围。数据范围是笔试里最重要的提示信息它直接决定你能不能使用暴力解法。一般看到n在10^5以上就要条件反射地思考O(n log n)或O(n)的解法看到n在20以内那确实可以考虑状态压缩或者全排列。忽略数据范围去写代码等于闭着眼睛开车。4.4 输出格式多一个空格都不行在线评测的比对规则是比较你输出的字符流多一个空格、少一个回车、多一个换行都可能导致Presentation Error或者直接判WA。C的cout ans endl和cout ans 在只有一个答案时没区别但如果是多组答案、每个占据一行就必须严格按格式来。我有一个习惯代码写完后先检查所有cout和print语句确认间距和换行与题目要求完全一致。特别是Python的print默认会加换行C的cout不会二者混用时要格外小心。另外题目要求输出浮点数时保留几位小数只能用printf(%.2f)或Python的格式化字符串不能用cout 3.14159直接输出否则精度差异也会导致WA。4.5 在线笔试平台的考场细节除了代码本身考场上的环境细节也值得提前适应。拼多多的笔试平台一般会在浏览器里运行代码没有IDE的自动补全、没有代码调试器、甚至没有代码格式化工具。这意味着你必须靠“肉眼查错”来保证代码准确率。比较好的做法是写代码时保持变量名短而清晰函数逻辑尽量拆成独立小段这样即使代码有问题也更容易定位。还有一点是网络问题。笔试过程中如果浏览器崩溃或者断网不要慌张先截图保存代码重新进入时粘贴回去继续写。我当年见过有同学因为断网重连后发现代码丢了整个人心态崩掉后面几题直接乱写。这种平台之外的意外虽然不常发生但提前做好心理准备总会比遇到时手足无措强。5. 针对拼多多笔试风格的刷题建议5.1 高频考点优先级贪心和模拟要顺手复盘完这套题你会发现问题方向其实很集中。贪心和排序是出现率最高的两个考点几乎每场笔试都会有一道字符串处理主要考大数运算、进制转换、子串统计这类基础功夫数学题则偏向期望、排列组合、快速幂不需要太高深的数论但对模型的抽象能力有要求。备考时我建议你按这个优先级来分配时间先把排序、二分、双指针、贪心这四个基础模块刷熟再练字符串处理和大数运算然后补基础DP和前缀和。至于AC自动机、后缀数组、网络流这些硬核算法拼多多笔试基本不会碰如果你时间有限可以暂时放一放。这不是说这些算法没有用而是在秋招笔试这个特定场景下性价比不高。5.2 刷题节奏与考场心态如果你离秋招还有三个月前两个月可以按专题刷题每周主攻一个考点做到“看到题目能立刻反应出这个数据范围下最有可能的算法”。最后一个月开始做整套的模拟笔试严格计时90分钟不中断、不查资料把每一次模拟都当真实考场对待。我自己刷这套题时有个体会大部分失分其实不是不会做而是会做但没做对。要么是边界漏了要么是复杂度没算清要么是输出格式没对齐。所以刷题的时候不要只追求“把样例过了”要对每组数据都想一想如果数组里有负数会怎样如果答案是0会怎样如果输入只有一个元素会怎样把这些边边角角都补齐AC率会明显提升。最后再分享一个实用技巧笔试时如果时间还剩十分钟优先检查你已经写好的代码而不是去挑战没做出来的题。把能拿到的分稳稳装进口袋永远比搏一个不确定的AC更划算。这套拼多多2019秋招题本质上考的不是你有多聪明而是你有多稳。稳住你的offer也会更稳。
拼多多2019秋招编程题全复盘：典型算法思路与避坑指南
想进拼多多做后端、算法岗的同学应该多少都翻过这套2019秋招编程题。它在求职圈流传度相当高不是因为题目难到劝退而是因为它非常典型题量不算大代码量不夸张但几乎每一道题里都埋着一两个让你AC不了的细节坑。我当年刷这套题的时候就有个很深的感受——拼多多出题偏爱把算法藏在很生活化的场景里比如分礼物、打骰子、算乘积看起来人都能读懂但一写代码就出问题。这篇文章就把这套题好好复盘一遍。我会先拆解拼多多笔试的出题风格和难度结构然后还原几道高频出现的典型题目逐个讲清解题思路再给出可运行的完整代码和复杂度分析最后把我自己踩过的坑、以及在线笔试平台常见的问题全部整理出来。不管你是刚准备秋招的大三学生还是想转码刷题的在职人士这套复盘都能直接用上。1. 拼多多2019秋招笔试画像出题风格与难度定位1.1 题型分布四道题藏着哪些考点从网上流传的各个版本来看拼多多2019秋招这场笔试的编程题一般是四道考试时间90到120分钟。题目类型相对固定按出现频率排序大概是贪心、模拟、字符串处理、基础数学。这个分布其实很能说明问题——拼多多并不像一些硬核大厂那样上来就甩你一道后缀自动机或者平衡树而是更看重“用常规算法解决实际业务问题”的能力。很多人以为大厂笔试一定全是DP和图论压轴实际上拼多多这套题目的难度曲线是平缓上升的。第一题通常是把一个生活场景简化成数组操作第二题是典型的排序加贪心第三题开始上字符串或者数学第四题才会出现一些需要灵光一现的点。整场笔试不会让你陷入“完全没思路”的绝望但会在你自以为做对的时候通过边界数据狠狠给你上一课。从考点覆盖来看这套题也很适合作为秋招复习的入门材料。它不需要你掌握冷门算法只要你把排序、双指针、模拟乘法、期望计算这些基础功练扎实再加上对边界条件的敏感度就能拿到不错的分数。反过来如果你连这些基础题都会翻车那后面遇到真正的难题会更吃力。1.2 难度梯度与时间分配建议我在复盘这套题的时候把四道题按难度分成了三个梯度。第一梯队的题属于“10分钟内必须AC”的送分题特征是思路直白、代码量小主要考察你敢不敢直接写、会不会被复杂化带偏。第二梯队的题属于“想清楚后20分钟搞定”的常规题需要你识别出贪心或者双指针的模型。第三梯队就是“容易写挂”的题不一定难但很考验细节比如大数乘法里的进位、前导零、数据类型溢出。时间分配上我的建议是第一梯队的题控制在10到15分钟第二梯队的题控制在20分钟第三梯队的题先读题、先想清楚再动键盘不要一上来就写。如果第三梯队卡了15分钟还没进展果断先跳过把后面会做的题稳住最后再回来啃。笔试和面试不一样面试你还有机会解释思路笔试只有AC和没AC两种结果所以“抢分”策略比“炫技”重要得多。另外拼多多的笔试平台在线编辑器通常没有代码补全也不能自动保存。这意味着你的代码必须一遍写对不管是变量名还是分号都不能依赖IDE帮你兜底。所以平时刷题时我建议你尽量用普通文本编辑器或者直接在OJ页面里写别一上来就开IDE自动补全不然考场上会非常不适应。2. 真题拆解四道典型题的还原与解法2.1 最大乘积排序后的一行max为什么能覆盖负数先看一道流传度极高的题目。给你一个整数数组长度在3到10^5之间元素可能是正数、负数、零要求从里面选三个数使得它们的乘积最大输出这个最大乘积。我第一次做这道题的时候第一反应是分类讨论全正怎么办、全负怎么办、有正有负怎么办。讨论了半天写出了七八个if-else结果还是漏了一种情况。后来看到一种特别干净的写法先把数组排序然后最大乘积只会出现在两种情况里——要么是最大的三个数相乘要么是最小的两个负数乘最大的正数。其他任何组合都不可能比这两个候选更大。所以直接取max(最小的两个数 * 最大的数, 最大的三个数相乘)就是答案。这个解法的核心是用排序把“选三个数”的排列组合问题降维。你不需要真的去遍历所有三元组因为排序后极端值已经集中在数组两端。如果数组全是负数最大的三个数也就是最接近0的三个相乘反而是最大的如果数组里恰好有零乘积是零的情况也会被这两个候选中的某一个覆盖。很多人栽在这一题上不是不会排序而是没有意识到“两个负数相乘可以变正”这个小学数学知识点会在考场上被放大成一道AC题和一道WA题的区别。2.2 六一儿童节双指针贪心避免O(n*m)超时这道题也是当年讨论度很高的一道。题目大意是有n个孩子每个孩子有一个期望礼物值有m个礼物每个礼物有一个实际大小。只有当礼物大小不低于某个孩子的期望值时这个礼物才能送给这个孩子。每个孩子最多只能拿一个礼物每个礼物也只能给一个孩子问最多能满足多少个孩子。这道题看起来像二分图匹配很多同学一上来就想用匈牙利算法但实际上数据范围根本不需要。你只要把孩子期望值和礼物大小分别排序然后用两个指针贪心匹配就行。核心逻辑是礼物从小到大枚举孩子也从小到大枚举。如果当前礼物能满足当前孩子就匹配上两个指针同时前进如果当前礼物连当前期望最小的孩子都满足不了那这个礼物对后面期望更大的孩子更不可能直接丢弃礼物指针前进。这样做的复杂度是排序的O(n log n m log m)加一遍扫描的O(n m)比暴力的O(nm)不知道快到哪里去了。我见过有同学在这道题上写了两层for循环本地跑小数据一点问题没有一提交就超时然后开始怀疑评测机有毛病。其实评测机没毛病就是数据量上来了O(nm)撑不住。这道题也是拼多多“把算法藏在节日场景里”的一个典型代表画一个蛋糕或者礼物的皮里面考的还是最朴素的排序贪心。2.3 大整数相乘字符串乘法把进位写对字符串处理的题在拼多多笔试里出现频率很高。这道题让你输入两个可能长达几千位的大整数用字符串表示输出它们的乘积。如果你直接用int或者long long去接那肯定溢出所以必须模拟手工乘法——也就是每个位上的数字逐位相乘再累加进位。具体做法是先把两个字符串反转存成两个int数组第i位和第j位相乘的结果累加到结果的第ij位。所有位乘完之后统一处理进位。这里有个特别容易踩的坑进位不能边乘边处理否则会乱掉。最好先把所有乘积都累加到对应位置上最后再从头到尾扫一遍做进位。进位做完之后结果数组的长度可能比实际需要的长前面会有多余的零输出前要从最高位开始跳过前导零。这道题我当年写的时候犯过一个很蠢的错误进位循环少跑了一位导致类似“999*999”这种数据结果中间少了一个数。后来调了半天才发现进位必须从低位到高位一直处理到结果数组的最高位不能只处理到较短数组的长度就停。这种细节题代码量不大但就是非常考验你对过程的控制力。2.4 骰子期望别写DP用期望线性性还有一道概率题在多个版本的题解里都出现过。题目大概是有一个n面骰子点数从1到n把它抛掷m次求m次点数之和的期望。m和n的范围可能很大大到用DP完全不可能。这题其实是一道典型的“送命题”——看起来像概率DP实际上用期望的线性性质一次就能算完。每次掷骰子的期望是(1 n) / 2m次独立重复实验的总期望就是m乘以单次期望也就是 m * (n 1) / 2。如果你非要写DP去枚举所有可能的和数据范围一大就直接爆炸不仅超时连内存都扛不住。这题给我们的启发是笔试里遇到“看起来很复杂”的概率题先想一想有没有数学上的简化方式而不是急着设状态转移。期望的线性性、前缀和、差分、排序后贪心这些“降维打击”的手段才是笔试真正想考察的东西。拼多多出这套题说到底就是想看你能不能从业务场景里识别出最核心的数学模型。3. 完整代码实现与复杂度复盘3.1 C版最大乘积与大整数相乘先看最大乘积这题。用C写排序用sort最关键的比较逻辑就两行。#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { vectorlong long a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); long long ans max(a[0] * a[1] * a[n - 1], a[n - 3] * a[n - 2] * a[n - 1]); cout ans endl; } return 0; }注意几个点数组元素要开成long long因为极端情况下三个10^9量级的数相乘结果会远超int范围。排序后a[n-3] * a[n-2] * a[n-1]是最大三个正数或最接近零的三个数的乘积而a[0] * a[1] * a[n-1]是让两个负数相乘变正后乘最大正数的情况。这时候你可能会问如果数组里只有一个负数那a[0]和a[1]两个数相乘不仅不会变正反而可能是很负的数和数相乘别担心结果取max时自然会淘汰掉差的候选。再看大整数相乘的C实现。先写好一个乘法的子函数主函数里读入字符串调用即可。#include bits/stdc.h using namespace std; string multiply(string num1, string num2) { int n num1.size(), m num2.size(); vectorint a(n), b(m), c(n m, 0); for (int i 0; i n; i) a[i] num1[n - 1 - i] - 0; for (int i 0; i m; i) b[i] num2[m - 1 - i] - 0; for (int i 0; i n; i) for (int j 0; j m; j) c[i j] a[i] * b[j]; for (int i 0; i 1 n m; i) { c[i 1] c[i] / 10; c[i] % 10; } int idx n m - 1; while (idx 0 c[idx] 0) idx--; string ans ; for (int i idx; i 0; i--) ans char(0 c[i]); return ans; } int main() { string s1, s2; while (cin s1 s2) { cout multiply(s1, s2) endl; } return 0; }这里最容易出错的位置有两个。第一个是c数组的长度为什么要开n m两个数相乘位数不会超过两个数位数之和。第二个是进位循环的终止条件必须处理到n m - 2下标之后还要继续向高位进位所以循环条件写成i 1 n m这样最高位也能通过进位延伸到数组最后一个位置。最后跳过前导零时如果结果本身就是0while (idx 0 c[idx] 0)会停在第一个0上面不会把输出变成空字符串。3.2 Python版六一儿童节与骰子期望用Python写六一儿童节这道题代码可以非常短。注意处理输入时不要被样例的换行格式迷惑直接用空格分割读取所有数字就好。import sys def solve(): data list(map(int, sys.stdin.read().split())) idx 0 n data[idx] idx 1 need sorted(data[idx:idx n]) idx n m data[idx] idx 1 gift sorted(data[idx:idx m]) ans 0 i j 0 while i n and j m: if gift[j] need[i]: ans 1 i 1 j 1 else: j 1 print(ans) if __name__ __main__: solve()这段双指针逻辑可以配合一个简单例子验证。孩子期望是[1, 3, 5]礼物是[2, 4]排序后i0指向1j0指向2。礼物2能满足孩子1匹配i1j1礼物4能满足孩子3匹配i2j2此时礼物用完循环结束。答案2正确。如果当前礼物连期望最小的孩子都满足不了说明这个礼物对谁都满足不了直接丢弃它也就是j这正是代码里else分支做的事情。这个逻辑很朴素但如果不排序直接暴力写两层for循环数据一大马上就超时。骰子期望的Python实现更短核心就是一行数学公式。n, m map(int, input().split()) ans m * (n 1) / 2 print(f{ans:.2f})这里要注意输出格式。有些题目会要求保留两位小数有些会要求输出分数有些甚至要求对某个模数取余。建议读题时先看输出样例的格式再决定用浮点数还是分数形式。如果你担心浮点数精度可以改用Decimal或者直接用分数计算但正常来说这道题的数值用double已经绰绰有余。3.3 复杂度逐题复盘把这四道题的复杂度放在一起对比能更清楚每个方案的优越性。最大乘积排序O(n log n)空间O(1)。暴力枚举所有三元组是O(n^3)数据量10^5时根本不可行。六一儿童节排序O(n log n m log m)扫描O(n m)空间O(1)。暴力两层循环是O(n*m)当n和m都到10^5时直接爆炸。大整数相乘时间复杂度O(nm)其中n和m是两个字符串的长度。由于两个数都可以长达几千位这个O(nm)已经是最朴素且可用的算法更优的还有FFT优化的乘法但笔试场景下字符串模拟就足够了空间O(nm)。骰子期望时间复杂度O(1)空间O(1)。如果写DP枚举所有可能和复杂度会变成O(nm范围)在n和m很大时不仅超时还会爆内存。这个对比非常直观地说明了为什么做题前要先分析数学模型。4. 实战最常见的五个坑从输入到结果输出4.1 多组输入怎么读才算稳笔试平台经常有多组测试数据的习惯也就是你提交的代码要能处理“输入不知道有多少组”的情况。C里可以用while (cin n)来循环读取读到EOF自动结束Python里可以用sys.stdin.read()一次性把所有数据读进来再按顺序解析。我见过不少同学在本地测试时用交互式输入自己手动敲一遍数据没问题但一提交就变成“输出超限”或者“结果错误”。原因多半是死循环没跳出、或者没有处理多组数据直接只读了一组。这里有个小技巧在线笔试的输入格式如果不是明确只有一组最好都按多组处理这是一种“防御式编程”习惯能避免很多无谓的失分。4.2 溢出不只在极限数据里出现关于溢出我想多说两句。很多人只有在看到题目里出现“10^9”这种字眼时才会想到用long long但像最大乘积这种题单个元素在10^9量级时三个数相乘就稳稳超过int范围。如果你不开long long本地小数据测试全对评测数据一大就WA而且你根本找不到原因因为错误不是语法错误而是静默溢出。还有大整数相乘这道题题目已经说了数字可能超出long long范围所以必须用字符串。可如果输入的数字恰好不大你用long long去转也能过样例这就非常危险——样例只是让你理解题意不代表评测数据的边界。我的建议是只要题目涉及乘法、加法累加、幂运算一律先考虑结果会不会超过int范围再决定用什么类型。4.3 暴力枚举能过样例但过不了评测六一儿童节那道题是最典型的例子。样例数据小两层for循环怎么写都能过。但评测数据里n和m同时到10^5的时候O(n*m)的代码跑起来就是天荒地老。笔试平台一般有时间和内存的双重限制超时和超内存都是直接判零分不会因为“思路对但没优化”而手下留情。这里的教训是写代码之前先看一眼数据范围。数据范围是笔试里最重要的提示信息它直接决定你能不能使用暴力解法。一般看到n在10^5以上就要条件反射地思考O(n log n)或O(n)的解法看到n在20以内那确实可以考虑状态压缩或者全排列。忽略数据范围去写代码等于闭着眼睛开车。4.4 输出格式多一个空格都不行在线评测的比对规则是比较你输出的字符流多一个空格、少一个回车、多一个换行都可能导致Presentation Error或者直接判WA。C的cout ans endl和cout ans 在只有一个答案时没区别但如果是多组答案、每个占据一行就必须严格按格式来。我有一个习惯代码写完后先检查所有cout和print语句确认间距和换行与题目要求完全一致。特别是Python的print默认会加换行C的cout不会二者混用时要格外小心。另外题目要求输出浮点数时保留几位小数只能用printf(%.2f)或Python的格式化字符串不能用cout 3.14159直接输出否则精度差异也会导致WA。4.5 在线笔试平台的考场细节除了代码本身考场上的环境细节也值得提前适应。拼多多的笔试平台一般会在浏览器里运行代码没有IDE的自动补全、没有代码调试器、甚至没有代码格式化工具。这意味着你必须靠“肉眼查错”来保证代码准确率。比较好的做法是写代码时保持变量名短而清晰函数逻辑尽量拆成独立小段这样即使代码有问题也更容易定位。还有一点是网络问题。笔试过程中如果浏览器崩溃或者断网不要慌张先截图保存代码重新进入时粘贴回去继续写。我当年见过有同学因为断网重连后发现代码丢了整个人心态崩掉后面几题直接乱写。这种平台之外的意外虽然不常发生但提前做好心理准备总会比遇到时手足无措强。5. 针对拼多多笔试风格的刷题建议5.1 高频考点优先级贪心和模拟要顺手复盘完这套题你会发现问题方向其实很集中。贪心和排序是出现率最高的两个考点几乎每场笔试都会有一道字符串处理主要考大数运算、进制转换、子串统计这类基础功夫数学题则偏向期望、排列组合、快速幂不需要太高深的数论但对模型的抽象能力有要求。备考时我建议你按这个优先级来分配时间先把排序、二分、双指针、贪心这四个基础模块刷熟再练字符串处理和大数运算然后补基础DP和前缀和。至于AC自动机、后缀数组、网络流这些硬核算法拼多多笔试基本不会碰如果你时间有限可以暂时放一放。这不是说这些算法没有用而是在秋招笔试这个特定场景下性价比不高。5.2 刷题节奏与考场心态如果你离秋招还有三个月前两个月可以按专题刷题每周主攻一个考点做到“看到题目能立刻反应出这个数据范围下最有可能的算法”。最后一个月开始做整套的模拟笔试严格计时90分钟不中断、不查资料把每一次模拟都当真实考场对待。我自己刷这套题时有个体会大部分失分其实不是不会做而是会做但没做对。要么是边界漏了要么是复杂度没算清要么是输出格式没对齐。所以刷题的时候不要只追求“把样例过了”要对每组数据都想一想如果数组里有负数会怎样如果答案是0会怎样如果输入只有一个元素会怎样把这些边边角角都补齐AC率会明显提升。最后再分享一个实用技巧笔试时如果时间还剩十分钟优先检查你已经写好的代码而不是去挑战没做出来的题。把能拿到的分稳稳装进口袋永远比搏一个不确定的AC更划算。这套拼多多2019秋招题本质上考的不是你有多聪明而是你有多稳。稳住你的offer也会更稳。