拼多多服务端9月22日笔试复盘

《面试题目》

1. 第一题：直接暴力找连续子串即可，每遍历到下一个数字与当前不同就记录一次（作者最初误读成了「区间内相同数量的货品」，想成前缀和，差点放弃）。
2. 第二题：三段最长连续子序列的分段 DP，需要设 dp1、dp2、dp3 三个状态，转移方程要仔细想，dp2 从 dp1 流转、dp3 从 dp1 和 dp2 流转。
3. 第三题：能直接 A 出来的大概都是资深 ACMer，属于一眼复杂度超限的题目。
4. 第四题：同第三题，大概需要线段树这类比较 high-level 的数据结构。

《参考解析》

第一题：先读题，再动手。这类题的标准形态就是”统计相邻相同元素构成的连续段”，一次线性扫描即可，O(n) 时间、O(1) 空间：

ans = 0
for i, ch in enumerate(s):
    if i == 0 or ch != s[i-1]:
        ans += 1

作者的失分过程非常有代表性——把「相邻相同的连续段」误读成「区间内相同数量的货品」，脑补成前缀和问题，看到第一题就这么难差点放弃。笔试里第一题通常就是签到题，如果读完觉得异常难，第一反应应该是回去重读题面而不是硬推。这条经验值得写进肌肉记忆。

第二题：三段最长连续子序列的分段 DP。和第 2915684 批次的第二题是同一类题（形如 a…ab…ba…a 的最长子序列，允许某段长度为 0）。设 dp1 表示只取第一段时的最大长度、dp2 表示取到第二段、dp3 表示取到第三段，扫描时按字符更新：

dp1 = dp2 = dp3 = 0
for ch in s:
    if ch == 'a':
        dp3 = max(dp3, dp2) + 1   # 用上一轮的 dp2
        dp1 = dp1 + 1
    else:
        dp2 = max(dp2, dp1) + 1

作者说的”dp2 从 dp1 流转、dp3 从 dp1 和 dp2 流转”就是这个意思。两个必须注意的点：①dp3 要用更新前的 dp2，否则同一个字符会被第二段和第三段同时使用，答案偏大；②状态之间是”可以进行到下一段”，所以 max(dp2, dp1) + 1 这种写法天然涵盖了”第二段为空、直接从第一段跳过来”的情况，不需要为”某段长度为 0”单独写分支。这类分段 DP 的通用套路是：给每个段设一个状态，遇到属于该段的字符，要么延长本段、要么从上一段转过来。

第三、四题：一眼超限，说明该上数据结构了。作者判断得很准——“一眼复杂度超限”。所谓”一眼超限”就是看数据范围估复杂度：如果 n, q ≤ 2×10^5，那么 O(nq) 是 4×10^10，必然超时；O(n log n)、O((n+q) log n) 才是目标。在这种约束下，常见的信号对应关系是：

• 区间查询 + 单点/区间修改，且要维护「可合并」的信息（和、最值、最大子段和、括号合法性）→ 线段树，有时配懒标记做区间赋值/反转；
• 只有前缀查询 + 单点修改 → 树状数组；
• 求第 k 大 / 最小最大值 / 满足单调性的最小答案 → 二分答案（判定函数要能 O(n) 或 O(n log n) 做完）；
• 区间众数、区间不同数个数这类不可合并的信息 → 莫队。

拿第四题（括号区间查询 + 区间反转）举例：把 ( 记 +1、) 记 -1，合法区间等价于「区间和为 0 且区间最小前缀和 ≥ 0」。线段树每个节点维护 sum、min_prefix、max_prefix、max_suffix；区间反转（左右括号互换且顺序颠倒）对应的懒标记变换是 sum' = -sum、min_prefix' = -max_suffix、max_prefix' = -min_suffix，同时交换左右子树。想清楚这一步，Q 和 F 就都是 O(log n)。这正是作者说的”high-level 数据结构”——难点不在代码模板，而在把题目条件翻译成可合并的节点信息。

关于”暴力混分”的策略：作者用暴力模拟拿到大约 0.5/2 的分数后立刻提交，这个决策本身没有错——笔试按通过率给分，把没思路的题暴力写稳、保证不超时不报错，是标准的性价比打法。可以再优化两点：①暴力之前先看清楚部分分的子任务规模（很多题的 30% 数据 n ≤ 1000，O(n²) 完全够）；②同一题里”特判 + 暴力”往往比纯暴力多拿一档（比如全是左括号、长度很小、无修改操作等特殊情况）。但要注意别在混分上花掉太多时间，导致有思路的题没时间写。

整体复盘：四道题的分工很清楚——签到题考读题、DP 题考状态设计、后两题考数据结构的识别能力。“识别”比”实现”更关键：知道什么时候该上线段树，比默写线段树模板更有价值。建议按专题刷（DP 分段型、线段树区间合并、二分答案），并且养成拿到题先看数据范围估复杂度的习惯。