拼多多9月22日机考笔试真题与解析

《面试题目》

1. 工位等量连搬：装配车间里 m 个工位排成一行，第 i 个工位待下线的零件个数是 a_i。夹具每次勾取只能框住下标连续的一段 [L,R]，并且这段里各个工位的零件个数必须彼此相等；被勾中的工位只是零件清零，工位仍留在原处，因此左右两段不会贴合。每个工位上的零件必须整批勾走，不能拆成两次。求清空整行所需的最少勾取次数。输入有 q 组询问，每组先给整数 m 再紧跟 m 个整数（q ≤ 10^5，m ≤ 10^5），要求在同一行输出 q 个整数，空格分隔。

2. 双色条码最长保留：一条双色条码的每颗墨点要么是浅色 a、要么是深色 b。称一条条码合格，是指它能从左到右切成三段相接的部分——靠前那段里出现过的墨点全是 a，正中那段里全是 b，靠后那段里全是 a，三段都允许一颗墨点都没有。质检员可以擦掉任意几颗墨点（一颗都不擦也行），擦完后留下的墨点仍保持原来从左往右的相对次序。问擦完后合格条码最多能留下几颗墨点（1 ≤ m ≤ 5000）。

3. 货格最少框边：冷链仓被切成边长为 1 的方格，仓内摆着 p 件货，每件独占一格，位置用列号、行号标出（列号、行号均在 1 到 1000 之间，货的位置互不相同）。巡检只允许框一次，框是边长为 s 的正方形，里面正好盖住 s² 个完整方格，框中的货会一次读完；框越大越费电。要求读出不少于 k 件货，求最小的 s。输入依次是 k、p、p 个列号、p 个行号，输出一个整数。

---

《参考解析》

1. 第 1 题的关键结论：答案就是极大等值段的段数：先把整行切成若干「连续且数值相同」的极大等值段。下界：任何一次勾取覆盖的是一段连续下标，且段内各工位在那一刻的零件个数必须两两相等；而每个工位只被勾走一次，在被勾之前它的数值恒等于初始的 a_i，所以同一次勾取里的工位一定有相同的 a_i，即整次勾取只能落在某一个等值段内部。每个工位至少要被覆盖一次、段与段之间无法合并，故次数 ≥ 段数。上界：每个等值段整体勾一次即可清空，恰好用掉段数。上下界相等，答案 = 段数。注意这个结论依赖「工位不撤走、左右不贴合」这一设定；如果清空后左右会贴合，问题就变成另一套合并结构，段数就不再是答案。

2. 第 1 题的实现、边界与 IO 细节：实现不需要真的切段，从左到右扫一遍即可：初始 runs = 1（m ≥ 1），当 a_i ≠ a_{i-1} 就加一。三种自测形态要背下来：单工位答案 1；全部相等答案 1；严格交替的序列答案 m。时间复杂度 O(Σm)，空间 O(1)（边读边算）。真正容易翻车的是 IO：q 最多 10^5，C++ 必须 ios::sync_with_stdio(false) 且 cin.tie(nullptr)；Java 别用 Scanner 逐 token 读；Python 不要按行 split 再按 m 切片——评测数据经常把一组询问折成多行，稳妥做法是把输入整体按空白切分后用游标取数（sys.stdin.buffer.read().split()）。输出要攒在一个列表里一次写出，每组询问单独 print 会超时。另外 q 与 m 同时给到 10^5 量级，说明 Σm 受输入总数据量约束，不能把两者相乘当规模。

3. 第 2 题：把「擦墨点」翻译成「保留全部 a + 改造一个窗口」：留下的点必须重新排成 aba*，且保持原有先后顺序，这等价于选一个下标区间 [i,j)：区间内的 a 全擦掉、区间内的 b 全留下，区间外的 b 全擦掉、区间外的 a 全留下。之所以「同色只留一部分」永远不会更优，是因为在自己所属的那一段里多留一颗合法墨点只会让长度变大，不会破坏形态。于是答案 = A(m) + [(B(j) − B(i)) − (A(j) − A(i))]，即「先保留全部 a」再加上窗口内 b 比 a 多的净增益（增益为负时不设中段，取 0）。把 a 记作 −1、b 记作 +1，问题就退化成对一个 ±1 序列求最大子段和（允许空段）。这一步转化是整题的核心，先想清楚它，后面的枚举、前缀和、Kadane 才是顺理成章的。

4. 第 2 题：前缀和公式与 best_diff 的线性维护：设 A(x)、B(x) 分别为前 x 颗墨点里 a、b 的个数（前缀计数），切分点满足 i ≤ j 时保留长度为 A(i) + (B(j) − B(i)) + (A(m) − A(j))，整理成 [A(i) − B(i)] + B(j) + [A(m) − A(j)]。右端点 j 固定时，后两项只与 j 有关，只需要在 i ∈ [0, j] 里取 A(i) − B(i) 的最大值。做法是从 j = 0 扫到 m：先算当前 diff = A(j) − B(j) 并更新 best，再用 cur = best + B(j) + (A(m) − A(j)) 更新答案。i ≤ j 这个约束不需要额外的判断，因为我们只把已经扫过（含当前）的 diff 拿去更新 best。前缀数组完全可以边扫边算，只留 totalA 和当前 diff 就够，空间能从 O(m) 降到 O(1)。样例 aabba 在 j = 4 时取到 5，正好对应 aa + bb + a 这一最优切分。

5. 第 2 题：最大子段和视角与三种写法的取舍：把「窗口内 b 减 a 的净增益」直接看成最大子段和，代码可以短到一行：gain = max(0, gain + (t[i] == 'b' ? 1 : -1))，答案就是 cnt_a + 全程最大 gain，时间 O(m)、空间 O(1)，本质是 Kadane。这条写法比维护 best_diff 少一个前缀数组，讲解时也更好说清楚，推荐作为最终提交版本。三种写法的定位：O(m²) 枚举 i、j 在 m ≤ 5000 时约 2500 万次运算，勉强能过，最适合用来对拍；前缀和 + best_diff 是标准 O(m)；Kadane 同阶但常数最小。笔试卷面上建议按「先写 O(m²) 暴力过样例 → 再换 O(m) → 用暴力对拍随机小数据」推进，这是最省时间的自检路径，也能防止公式推错方向。

6. 第 2 题的边界与易错点：① 三段都允许为空，所以「全留 a」「全留 b」「先 a 后 b」都合法，答案的下界是 max(cnt_a, cnt_b)，可以拿它一眼看出输出是否偏小。② 增益为负时必须放弃中段（取 0），否则会白擦掉一批 a 却补不回等量的 b，例如 t = “aa” 的正确输出是 2 而不是 1。③ 「保持相对次序」意味着只能取子序列、不能重排，所以窗口必须是原串上的连续区间；写成「统计 b 的总数再加上 a 的总数」是错的，中间段的 b 必须真的连成一段。④ 输入给出的 m 与字符串长度不一致时以字符串长度为准，Python 里对 input() 记得 strip 掉行尾空白与 \r。⑤ m ≤ 5000 时答案不超过 m，int 足够，不需要 64 位，但用 Python 写 O(m²) 时要注意常数，必要时换成 O(m) 版本。

7. 第 3 题：为什么可以二分答案，以及上界能收到多小：记 f(s) 为「存在边长 s 的正方形框住不少于 k 件货」。f 单调：边长 s+1 的框 [c, c+s] × [r, r+s] 本身就完整包含一个边长 s 的框（左上角相同），所以 f(s) 为真时 f(s+1) 必为真，于是可以二分最小可行的 s。下界是 1：k = 1 时框住任意一件货即可。上界不必取 1000，最优框一定可以贴着被读到的那些货向里收缩——左边界取这些货的最小列号、上边界取最小行号，收缩后框内的货一件不少，边长只会变小，因此答案不超过 max(列最大 − 列最小, 行最大 − 行最小) + 1（坐标在 1..1000，所以这个值最多 1000）。把二分区间设成 [1, 该上界] 能显著减少 check 的枚举量。另外 k > p 时无解，题面通常保证 k ≤ p，实现里直接特判更稳。

8. 第 3 题：check(s) 的二维前缀和实现与下标陷阱：把每件货打到 1001 × 1001 的方格表上，行列都用 1-based，而下标 0 的那一行一列留作前缀和的零边界；再做二维前缀和 P[c][r] = 前 c 列、前 r 行里的货数。左上角在 (c, r) 的边长 s 方框覆盖列 [c, c+s−1]、行 [r, r+s−1]，件数为 P[c+s−1][r+s−1] − P[c+s−1][r−1] − P[c−1][r+s−1] + P[c−1][r−1]，四项容斥的符号写错或上下标写反是最典型的 WA。枚举的左上角必须收在 c, r ≤ 1001 − s 之内，越界会读到无效格子。check 内部一旦统计到 ≥ k 就立刻 return true，这种早停在实际数据上命中率很高；把 P 展成一维数组（下标 c * 1001 + r）既省内存也更快，Java 里还能免掉大量二级数组访问与边界检查。

9. 第 3 题：复杂度核算与语言选择：建前缀和 O(V²) ≈ 10^6，二分约 10 轮，每轮最坏枚举约 (1001 − s)² 个左上角，总量约 10^7 次 O(1) 查询；空间是 1001 × 1001 的 int 数组，约 4 MB。这个量级 C++ 是毫秒级，Java 用 BufferedReader / StreamTokenizer 加一维数组也在预算内；但 Python 里 10^7 次带容斥的四则运算通常要十几秒，基本必然 TLE，得改走 numpy（按候选 s 对整片切片做向量化容斥）或换更省的枚举方式，否则就该换语言。一般的估算习惯是先数「最坏循环次数」再动手：Python 的临界线大致在 10^7，10^8 以上必须换语言或换算法，笔试选语言前先估一遍能省掉一次重写。

10. 第 3 题的边界与常见错因：① k = 1 时答案恒为 1，直接特判能省掉最坏的一轮 check。② 货的位置互不相同只保证不重合，同一列或同一行可以有很多件（样例里 (1,1)、(1,2) 就在同一列），所以按格打点是对的，千万别先对列号、行号去重再统计，那会漏解。③ 二分模板要写死成 while (low < high) { mid = (low + high) / 2; if (ok(mid)) high = mid; else low = mid + 1; }，把 else 分支写成 low = mid 会死循环。④ 样例 (1,1)、(1,2)、(5,5) 配 k = 2 输出 2，正好覆盖「同一列相邻两行」这种最容易写错的情形，值得手工推一遍。⑤ 输出只有一个整数加换行，别被多组询问的题带偏写成一行多个数。

11. 第 3 题：不二分也能做的方向与工程取舍：答案一定是「某 k 件货的最小包围正方形的边长」，也就是某组货的 max(Δ列, Δ行) + 1，这提示另一条路：把货按列排序，用双指针枚举列跨度不超过 s 的列窗口，再在窗口内的行号上用有序结构维护长度不超过 s 的滑窗计数，配合外层二分可把复杂度压到 O(p log p log V) 量级，在 p 远小于 V² 时更快。但本题 p 最大 10^5、V 只有 1000，网格法在实现难度和调试成本上明显占优，笔试时应当先交前缀和版本，把上面的优化留作「确认 TLE 再换」的备选。这也是通用的取舍原则：值域小就按值域建表，点数小才按点枚举，动手前把两条路的循环次数各估一遍。

12. 三题共通的套路与笔试策略：这三题正好覆盖机考最常出现的三类骨架——第 1 题是「找不变量，把答案化简成一个计数」（先证下界、再给构造，两界相等即最优）；第 2 题是「先做等价转化，再在一维序列上扫一遍」（前缀和 / 最大子段和）；第 3 题是「答案可二分 + 小值域建表做 O(1) 判定」（二分答案 + 二维前缀和）。拿到题先自问三句：答案单调吗，能不能二分？值域有多小，能不能建表？有没有形式更简单、等价且好验证的问法？然后按「写暴力 → 过样例 → 造边界数据对拍 → 换正解」的顺序推进。每题的边界至少自测三种：最小规模（m = 1、k = 1）、极端形态（全相等 / 全同色 / 点全在一条线上）、以及答案恰好取到上界的情况。这三条做完，机考的失误基本只剩实现手滑。