拼多多 服务端工程师 秋招笔试：四道编程题复盘

《面试题目》

1. 编程题一：缓存型问题的变体——对调相邻指令，求合法方案个数。
2. 编程题二：开闭区间变体——可以忽略一个区间，求有共同交集的连续区间的最大个数。
3. 编程题三：无向图，给定一张连通图，每条边和每个顶点都有代价，选中顶点就能打通它周围的边，求使图连通的最小代价。
4. 编程题四：有向图，一个人按规则在图上行走（题面未展开）。

---

《参考解析》

整场形式本身就是一条策略

整场只有编程一个题型、四道小题，前两道 medium、后两道 hard，而且没有「提交后锁定」的限制——一道题可以做到一半切到另一道再回来。这条规则对做题顺序的影响很直接：开考先把四道题都读一遍，用暴力解法在每道题上保底拿分（多数平台的分数按通过用例数给），再回头逐个优化；卡住时切题比原地硬想省时间，最后留十分钟收尾。四道题的分布是「两道常规套路 + 两道需要一点建模」，把前两道的分拿稳、后两道争取部分分，通常比平均分配时间划算。多组数据、大数据量的题别忘了写快读，输出用 \n。

编程题一：对调相邻指令，求合法方案个数

这道题给的信息只有一句，但能确定它的落点是计数而不是模拟。「对调相邻指令」这类设定一般有两种建模方式。一是把「一次相邻交换」看成排列上的邻接操作，合法性条件会变成相邻元素之间的偏序约束（哪些指令允许互换），于是问题要么是 DAG 上的拓扑序计数（按位置做 DP，状态里带上一个元素是什么），要么是求把序列变成目标序列的最少交换次数——后者等价于逆序对计数，用树状数组或归并排序在 O(n log n) 内解决。二是按缓存的行为直接建模，用 DP 逐位推进、状态里带缓存当前内容。判断走哪条的依据是「合法性」是怎么定义的：如果合法性只取决于相邻两个元素能不能换，就是偏序/逆序对模型；如果合法性取决于整个序列的状态（缓存命中与否），只能上带状态的 DP。另外要留意计数题的取模，以及「合法方案个数」包不包括交换零次的原序列。

编程题二：可以忽略一个区间，求有共同交集的连续区间最大个数

先解决基础版：一组区间有公共交集的充要条件是「所有区间左端点的最大值 ≤ 所有区间右端点的最小值」，所以求「最多能取多少个有公共交集的区间」是个滑窗问题——把区间按左端点排序，用双指针维护窗口、用一个最小堆或有序结构维护窗口内右端点的最小值，当 max(left) > min(right) 时移动左指针，窗口大小就是当前答案，复杂度 O(n log n)。

加上「可以忽略一个区间」之后，相当于在原问题外面套一层：枚举被忽略的那一个区间，取所有情况里的最大值。直接枚举是 O(n² log n)，数据量小可以直接过；要优化就做前后缀预处理——窗口统计依赖的只是「左端点最大值」和「右端点最小值」这类可以增量合并的信息，对每个前缀、每个后缀各算一遍，枚举忽略点时把前缀与后缀合并即可，复杂度降到 O(n log n)。这道题最容易读错的是「连续区间个数」：如果要求选出的区间在原始顺序上必须连续，那就不允许排序，得改成枚举起点做双指针，或者对每个位置预处理它向左、向右各能扩展到多远——排序版和顺序版是两种完全不同的写法，读题时先把这一条确认掉。

编程题三：点权加边权的无向图求连通最小代价

这是四道里最有建模味道的一道：选中一个顶点就能打通它周围的边，而边自己也带代价，求连通的最小总代价——也就是点权与边权要同时计入。常见有两条路。

第一条是点权摊进边权再跑最小生成树：如果能确认「选中一个顶点的代价只付一次、且被所有用到它的边共享」，那么对每条边 (u,v) 可以按某种分摊方式（例如把两端点权各取一半加到边权上）构造新权重，再求 MST；这个做法在点权可共享时并不严格精确，只适合点权确实等同于一次性的接入费用的情形，所以用它之前必须先把题意确认清楚，别默认。

第二条是把状态放进最短路或 DP 里：让进入顶点 v 的代价额外加上 c(v)，即 dist[v] = min(dist[u] + w(u,v) + c(v))，用 Dijkstra 松弛；如果题目要求的是「让指定的若干个顶点互相连通」，那就是标准的斯坦纳树 DP：dp[mask][v] 表示已连通点集为 mask、当前根在 v 的最小代价，先按边松弛（最短路），再按子集合并（dp[mask][v] = min(dp[sub][v] + dp[mask^sub][v] - c(v))，注意点权只算一次要减掉重复项），复杂度约为 O(3^k n + 2^k n log n)，k 是必须连通的特殊点个数。判断走哪条路的信号是数据范围：n 不大而特殊点很少，上斯坦纳树；n 很大、点权共享关系又很明确，才考虑点权转边权的 MST。

编程题四：有向图上的行走

这道题的题面没有展开，只能定方向：有向图 + 「散步」通常是给定起点沿有向边走，求路径条数、最大收益或固定步数后的分布。实现上第一件事是判有没有环——DAG 可以直接按拓扑序 DP；有环且步数固定，用矩阵快速幂做路径计数；有环且步数不限，要考虑环上的收益能不能无限累积（能就变成「最优路径」的正环检测）以及概率转移是否收敛。这类题的失分点几乎都在「没有先判环就开始 DP」上。