拼多多 PDD 9-22 笔试：四道编程题题解与代码

轮次: 笔试
时间: 2026-09
来源: 牛客网

《面试题目》

Q1：给定数组 a，统计相邻元素不相同的次数再加一（即数组连续相同段的段数），多组数据。帖中只保留了题解代码，题面未完整留存。
Q2：给定只含 a、b 两种字符的字符串，按题解代码的四个状态转移看，是求形如 a…a b…b a…a 的最长子序列长度。题面同样未完整留存。
Q3：有 n 个点，求一个最小的正方形，使它包含至少 c 个点在内（含边界）。
Q4：给一个只含 ( 和 ) 的字符串，要求支持两种操作：一是区间翻转（左括号变右括号、右括号变左括号）；二是检查区间 [L, R] 的子串是否为合法括号序列。

《参考解析》

Q1：连续段计数

解法就是把数组扫一遍，看相邻两个元素是否相同，不同就让答案加一，最后加一得到段数（单元素数组和全相等的数组都至少是一段）。难点只在于多组数据下输入输出要快，Python 用 sys.stdin.readline 逐行读、把结果攒起来一次输出，别用 input()。

import sys
def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    ans = 1
    for i in range(1, n):
        if a[i] != a[i - 1]:
            ans += 1
    print(ans)

这类题真正的坑是边界：n == 1 时答案必须是 1（如果写成「从 ans = 0 开始数不同对」再 +1，逻辑上也等价，但要确认不会输出 0）；以及输入可能跨多行，稳妥写法是一次读够 n 个数后再继续。

Q2：a/b 字符串的三段式最长子序列 DP

帖中给出的状态设计是 4 个状态 dp[i][0..3]：状态 0 是「还没取任何字符」，状态 1 是「正在取第一段 a」，状态 2 是「正在取 b 段」，状态 3 是「已经回到 a 段」。转移只有两行：

当前字符是 a：dp[i][1] = max(dp[i][1] + 1, dp[i-1][0] + 1)，dp[i][3] = max(dp[i][3], dp[i-1][3] + 1, dp[i-1][2] + 1)；
当前字符是 b：dp[i][2] = max(dp[i][2], dp[i-1][1] + 1, dp[i-1][2] + 1)。

也就是说，遇到 a 可以继续留在第一段或第三段，遇到 b 只能待在第二段；答案为所有状态在所有位置上的最大值。这样做的妙处是——不需要真的去划分三段，把「子序列形态」编码进状态里，一遍扫描 O(n)、O(1) 空间（滚动数组）就解决了。两个实现细节值得记住：一是状态 0 永远为 0，它的存在只是给状态 1 一个合法起点；二是 Python 里 dp[i-1] 在 i == 0 时会取到 dp[-1]（即最后一行），帖中这段代码靠「最后一行此时全为 0」侥幸正确，正式写的时候应该显式处理 i == 0 或把 dp 下标整体右移一位，否则等第 0 行不是 0 就会出错。

Q3：离散化 + 二维前缀和 + 二分答案

题意是「找最小的正方形，使其内部点数 ≥ c」。关键观察是单调性：如果边长 m 的正方形能装下 c 个点，那么边长更大的正方形一定也能，所以可以对边长二分答案。

check(m) 怎么判？把每个点的坐标离散化：把所有点的 x、y 收集排序去重得到数组 z，映射函数 Z(v) 用 lower_bound 找到它在 z 中的下标。然后在一个 (N+1) × (N+1) 的网格上打点并求二维前缀和，这样任意矩形区域内的点数都能 O(1) 求出。枚举正方形的左边界下标 i 和右边界下标 j，那么正方形的上/右边界坐标分别是 z[i] + m、z[j] + m（边长相同，所以两个方向的 offset 一样），它们在离散数组里的位置同样用 Z 求出来，再用前缀和查这个矩形内的点数是否 ≥ c。

这里有个容易被忽略的细节：帖中的离散化把 x 和 x - 1（y 同理）都塞进了 z。原因是正方形边界取在某个点坐标上时，z[i] + m 落点也必须能在离散数组里找到下标，多放一个 x - 1 是为了让「边界贴着某个点左侧」这种情况也有对应的下标可选，避免因为找不到上界而漏掉合法的摆放位置。总复杂度 O(n² log C)，C 是坐标范围（帖中二分区间取到 1e9+1）。注意卡常：n 到 2000 时 n² 已经是 4e6 次枚举再乘 log，Python 基本过不去——帖主也是同一份思路换 C++ 才 AC，这也说明打这类笔试要先按数据范围选语言，别在 Python 上硬耗时间（这次就因此耽误了 Q4 的调试时间，只拿到 44 分）。

Q4：括号序列的区间翻转与合法性查询（分块）

合法括号序列的判别标准只有两条：任意前缀的「左括号数 - 右括号数」始终 ≥ 0，且整个区间最终等于 0。如果没有翻转操作，前缀和 + 线段树/稀疏表就能做；有了「区间翻转」，区间内的 ( ) 互换，balance 整体取反，于是想到分块（O(n√n)）。

每个块维护三个量：sum（块内 balance 总和）、cntl（块内前缀 balance 的最小值取负，即最大「赤字」，也就是该块内最坏情况下右括号比左括号多多少）、cntr（把块内括号视为取反后的最大赤字，即前缀 balance 的最大值）。再给每块一个 tag，表示这块是否被整体翻转：

整块翻转：tag ^= 1，同时 swap(cntl, cntr)、sum = -sum——O(1)，不碰具体字符；
部分翻转 / 查询：先把该块的 tag 下推（真的把块内字符逐个翻转一次再重建统计量），然后暴力处理边缘的零散元素。重建一个块是 O(块长)。
查询：从左往右扫，维护累计 balance cnt。在整块 j 上，要求 cnt ≥ cntl[j]（否则这块内部某个前缀会让 balance 掉到 0 以下，说明不合法），通过后 cnt += sum[j]；零散元素逐个加减并随时判 cnt < 0；最后要求 cnt == 0。

复杂度 O(q·√n)，块长取 √n 时最优。实现上最容易错的地方有三处：翻转后 sum 的符号要一起取反（很多人只改了 cntl/cntr）；边缘块的 tag 必须先下推再做局部修改，否则 restructure 时会把翻转效果丢掉；以及每次零散修改后要重建整个块的统计量，而不是只更新增量。

整体复盘

四道题的信息量分布很典型：Q1、Q2 考「把问题翻译成状态」，Q3 考「二分 + 前缀和」的组合套路与语言选择，Q4 考数据结构设计（分块 + 懒标记）。两条可以直接带走的经验：一是按数据范围和语言特性决定先做哪题——Python 在 n=2000 的二重循环 + 二分上必卡，早点改 C++ 才能给后面的题留时间；二是多组数据 + 大数据量的题目一定要写快读（sys.stdin.readline / ios::sync_with_stdio(false)），输出用 \n 而不是 endl。

《面试题目》

《参考解析》

相关面经