大厂真题 / 拼多多
拼多多技术岗 2026-09-22
内容边界：概述列出 4 道编程题，原始正文实际披露 4 道，题意、约束及正式样例均已核对，未发现列出而未展开的编程题；不补充材料未披露的其他内容。
本场考试概述
考试时间：2026-09-22
考试岗位：技术岗
难度评级：中等偏难
考点分析：等值段计数、三态 DP、二分扫描线、括号懒标记线段树。
建议策略：前两题先证明等值段下界和阶段 DP；第三题注意单元格跨度的加一，第四题区分括号取反与字符顺序反转。
第 1 题：货架最少搬运次数
题目描述
有 $N$ 个固定位置的货架，第 $i$ 个有 $A_i$ 件商品。一次操作可以选择连续区间 $[l,r]$，前提是区间内所有货架的商品数完全相同，然后一次搬空。搬空后货架仍留在原位，商品数变为零，不会把两侧货架拼接。求搬空全部货架的最少次数。
输入格式：首行测试组数 $1\le T\le10$；每组先读 $1\le N\le10^5$，再读 $N$ 个数，$1\le A_i\le10^5$。
输出格式：每组一个整数，表示最少搬运次数。
样例 1
输入
1
8
2 2 3 3 3 1 1 2
输出
4
思路分析
先按相邻数是否相等把数组划分成极大等值段。一个合法操作不能跨越不同数的交界，因此起初最多处理其中一段。即使先清空中间的货架，中间也变成零而不会消失，仍不能将两侧非零的同值段合并搬走。
因此答案等于极大等值段数：
\[1+\sum_{i=2}^{N}[A_i\ne A_{i-1}].\]方括号为指示函数，条件成立取 $1$，否则取 $0$。从左到右遇到一个新段就加一。样例被分成 $[2,2]$、$[3,3,3]$、$[1,1]$、$[2]$，共 $4$ 段。
正确性证明
每个最初的非零等值段至少需要一次操作，清空别的段只会留下零，不能降低这个下界。对每个极大等值段整体搬运一次可恰好达到下界，所以计数即最优。原输入全为正数；这里没有将初始零货架的扩展规则混入题意。
题解代码
import sys
input = sys.stdin.readline
def count_moves(values):
return 1 + sum(values[i] != values[i - 1] for i in range(1, len(values)))
def solve():
tests = int(input())
for _ in range(tests):
n = int(input())
values = list(map(int, input().split()))
print(count_moves(values))
solve()
复杂度分析
时间复杂度：每组 $O(N)$；多组为 $O(\sum N)$。
空间复杂度：每组 $O(N)$，读入当前数组；计数本身只需 $O(1)$ 辅助空间。
第 2 题：多多字符串
题目描述
字符串只含小写 a 和 b。若它可分成连续三段，依次只含 a、只含 b、只含 a，且任一段允许为空，则称为多多字符串，即形如 $a^{\ast}b^{\ast}a^{\ast}$。
可以删除任意字符，但不能改变剩余字符顺序。求最长多多子序列的长度。
输入格式：一行非空字符串 $s$，$1\le\lvert s\rvert\le5000$。
输出格式：最长可得长度。
样例 1
输入
abba
输出
4
样例 2
输入
bab
输出
2
思路分析
第一步：用阶段描述合法形状。 枚举全部子序列需要指数时间，但“前段 a、中段 b、后段 a”的阶段只能向右移动。扫描前缀后，只需知道目前处在哪个阶段以及最长长度，不必保存具体选中的位置。
第二步：写出三态递推。 令 $F_i^0,F_i^1,F_i^2$ 分别为前 $i$ 个字符停在三个阶段的最长长度，初值全为零。设当前字符为 $c$，则
\[F_i^0=F_{i-1}^0+[c=a],\] \[F_i^1=\max(F_{i-1}^0,F_{i-1}^1)+[c=b],\] \[F_i^2=\max(F_{i-1}^1,F_{i-1}^2)+[c=a].\]当前字符不匹配时即删除，匹配时保留不会损失最优性。答案取三个状态的最大值。中段为空的全 a 子序列由第一态覆盖，因此不显式跳过中态也不漏解。
第三步：滚动保存。 每层只依赖上一层，三个整数足够。Python 的同时赋值先计算右侧全部表达式，再更新左侧，避免同一字符被跨阶段重复使用。
正确性证明
对扫描长度归纳。任意合法子序列在当前阶段只能延续，或从紧邻前一阶段转来；当前字符匹配时可以追加，否则只能删除。递推枚举这两种来源并取最大，因此每态正确。所有合法结果要么停在某一阶段，要么三段全空，对三态取最大覆盖全部答案。
abba 本身合法，结果为 $4$；bab 需删除一个 b，得到 ab 或 ba，结果为 $2$。全 a、全 b 也允许，因为其他段可为空。
题解代码
import sys
input = sys.stdin.readline
def longest_duoduo(text):
first = middle = last = 0
for char in text:
is_a = int(char == 'a')
is_b = int(char == 'b')
first, middle, last = (first + is_a,
max(first, middle) + is_b,
max(middle, last) + is_a)
return max(first, middle, last)
def solve():
print(longest_duoduo(input().strip()))
solve()
复杂度分析
时间复杂度：$O(\lvert s\rvert)$，单次扫描。
空间复杂度：$O(\lvert s\rvert)$，保存输入字符串；DP 辅助空间为 $O(1)$。
第 3 题：果园最小收集边长
题目描述
果园由边长为 $1$ 的正方形单元格组成，$n$ 个苹果位于互不相同的整数坐标单元格。收集器一次选择一个由 $m^2$ 个完整单元格组成的正方形，收集其中全部苹果。要求至少收集 $c$ 个，求最小整数边长 $m$。
输入格式：首行 $n,c$，$1\le c\le n\le10^3$；后续 $n$ 行坐标 $x_i,y_i$，$1\le x_i,y_i\le10^9$，所有点两两不同。部分数据坐标不超过 $1000$。
输出格式：最小正整数边长。覆盖坐标差为 $d$ 的两个单元格需要 $d+1$ 格，判定必须使用坐标差小于 $m$，不能把格子问题当作连续几何点问题。
样例 1
输入
10 3
47 66
33 81
30 90
27 86
30 76
49 47
55 76
12 76
11 98
19 59
输出
10
样例 2
输入
15 15
64 81
17 55
58 5
51 8
26 31
42 61
79 97
98 50
68 42
55 57
26 87
83 67
25 52
53 26
83 61
输出
93
思路分析
第一步：二分边长。 可行边长增大后仍可行。下界为 $1$，上界可取全体点横纵跨度较大值加一，保证能覆盖全部点。
第二步：横向滑动窗口。 按 $x$ 排序，扫描右端点；移走所有与当前最右点满足 $x_{right}-x_{left}\ge m$ 的点。剩下的点可同时放入宽 $m$ 格的竖条中。只需判断这些点是否能在某个高 $m$ 格的区间内达到 $c$ 个。
第三步：纵向转成区间加。 任意可行纵向区间可将下边界上移到其中最小的苹果 $y$，不会丢点，所以只枚举所有已知 $y$ 作为下边界候选。一个纵坐标为 $y$ 的活跃点会覆盖候选下边界
\[y-m+1\le b\le y.\]离散化 $y$ 后，加入一个点就对上述候选范围加一，移走就减一；线段树根节点的最大值即为当前竖条中某个正方形最多能覆盖的苹果数。达到 $c$ 就可返回可行。每次二分重新建立计数树。
正确性证明
对固定 $m$，任何线段树达到 $c$ 的候选都对应同一横向窗口和某个纵向区间，因而确实存在覆盖至少 $c$ 个点的正方形。反过来，取任意可行正方形内最右的苹果，扫描至它时，窗口一定包含该正方形内所有横向坐标合格的点；将下边界移至其中最小 $y$ 后，它属于离散候选，计数不少于 $c$。故判定充分且必要，再由单调性二分得到最小边长。
样例 1 用横坐标 $27$ 至 $36$、纵坐标 $81$ 至 $90$ 的十格正方形，覆盖 $(33,81),(30,90),(27,86)$。样例 2 必须收集全部苹果，纵向 $5$ 至 $97$ 共 $93$ 格，大于横向的 $82$ 格，答案为 $93$。
此实现使用确定性的扫描线判定，不依赖随机枚举顺序。材料中没有可核对的时限，不能仅凭循环次数断言某种 Python 实现必然超时。
题解代码
import sys
from bisect import bisect_left
input = sys.stdin.readline
def min_side(points, target):
points = sorted(points)
ys = sorted({y for _, y in points})
index = {y: i for i, y in enumerate(ys)}
size = len(ys)
def feasible(side):
maximum = [0] * (4 * size)
lazy = [0] * (4 * size)
ranges = [(bisect_left(ys, y - side + 1), index[y]) for _, y in points]
def add(node, left, right, ql, qr, value):
if ql <= left and right <= qr:
maximum[node] += value
lazy[node] += value
return
middle = (left + right) // 2
if ql <= middle:
add(node * 2, left, middle, ql, qr, value)
if qr > middle:
add(node * 2 + 1, middle + 1, right, ql, qr, value)
maximum[node] = lazy[node] + max(maximum[node * 2], maximum[node * 2 + 1])
left = 0
for right, (x, _) in enumerate(points):
lo, hi = ranges[right]
add(1, 0, size - 1, lo, hi, 1)
while x - points[left][0] >= side:
lo, hi = ranges[left]
add(1, 0, size - 1, lo, hi, -1)
left += 1
if maximum[1] >= target:
return True
return False
low = 1
high = max(points[-1][0] - points[0][0], ys[-1] - ys[0]) + 1
while low < high:
middle = (low + high) // 2
if feasible(middle):
high = middle
else:
low = middle + 1
return low
def solve():
n, target = map(int, input().split())
points = [tuple(map(int, input().split())) for _ in range(n)]
print(min_side(points, target))
solve()
复杂度分析
时间复杂度：$O(n\log n\log V)$，$V$ 为初始可行边长且 $V\le10^9$；每次判定中每个点至多加入、移除一次。
空间复杂度：$O(n)$，坐标、区间索引和懒标记线段树。
第 4 题：括号串翻转与合法查询
题目描述
给定只含 (、) 的长度 $n$ 字符串，执行 $q$ 个操作：
F l r：将下标 $l$ 到 $r$ 的每个括号替换为相反括号，即左变右、右变左，字符顺序不变。Q l r：判断该子串是否为合法括号序列，是则输出YES，否则输出NO。
输入格式：首行 $n,q$，$1\le n,q\le200000$；第二行字符串；后续 $q$ 行操作。下标从 $1$ 开始，$1\le l\le r\le n$。
输出格式：每个查询输出一行，翻转不产生输出。合法示例为 ()、(())、()()、((()))；)(、(()、())( 不合法。
样例 1
输入
6 5
(()())
Q 1 6
F 2 5
Q 1 6
F 3 4
Q 1 6
输出
YES
YES
NO
思路分析
第一步：把匹配转成前缀和。 左括号记 $+1$，右括号记 $-1$。合法当且仅当总和为零且所有前缀和非负。只看总和不够，例如 )( 总和为零却在第一步就失配。
第二步：维护可合并的信息。 每段保存总和 $s$、最小前缀 $a$、最大前缀 $b$，把空前缀也算进去。两段左右拼接时：
\[s=s_L+s_R,\quad a=\min(a_L,s_L+a_R),\quad b=\max(b_L,s_L+b_R).\]右段前缀必须加左段总和，因此合并有顺序，不能交换左右。
第三步：推导整段翻转。 所有数同时取负，前缀和也取负，故
\[s'=-s,\qquad a'=-b,\qquad b'=-a.\]这解释了为何还需最大前缀。懒标记使用布尔取反，两次翻转会抵消；部分覆盖前下传标记，修改后重新合并。
正确性证明
叶节点信息由单个 $+1$ 或 $-1$ 直接计算。合并公式完整覆盖“停在左段”和“经过左段进入右段”的所有前缀，因此保持正确；整段取负公式保持翻转后的正确性。懒标记仅延迟子节点更新，不改变节点代表的真实区间信息。查询按左右次序合并，得到目标子串准确的总和和最小前缀，最终判定正好是括号合法性的充要条件。
样例中 (()()) 经 F 2 5 变为 ()()()，仍合法；再执行 F 3 4 变为 ())(()，第三个字符处前缀和为负，输出 NO。
题解代码
import sys
input = sys.stdin.readline
class BracketTree:
def __init__(self, text):
self.n = len(text)
size = 4 * self.n
self.total = [0] * size
self.minimum = [0] * size
self.maximum = [0] * size
self.lazy = [False] * size
self.build(1, 0, self.n - 1, text)
def pull(self, node):
left, right = 2 * node, 2 * node + 1
self.total[node] = self.total[left] + self.total[right]
self.minimum[node] = min(self.minimum[left], self.total[left] + self.minimum[right])
self.maximum[node] = max(self.maximum[left], self.total[left] + self.maximum[right])
def build(self, node, left, right, text):
if left == right:
value = 1 if text[left] == '(' else -1
self.total[node] = value
self.minimum[node] = min(0, value)
self.maximum[node] = max(0, value)
return
middle = (left + right) // 2
self.build(node * 2, left, middle, text)
self.build(node * 2 + 1, middle + 1, right, text)
self.pull(node)
def apply(self, node):
self.total[node] = -self.total[node]
self.minimum[node], self.maximum[node] = -self.maximum[node], -self.minimum[node]
self.lazy[node] = not self.lazy[node]
def push(self, node):
if self.lazy[node]:
self.apply(node * 2)
self.apply(node * 2 + 1)
self.lazy[node] = False
def flip(self, node, left, right, ql, qr):
if ql <= left and right <= qr:
self.apply(node)
return
self.push(node)
middle = (left + right) // 2
if ql <= middle:
self.flip(node * 2, left, middle, ql, qr)
if qr > middle:
self.flip(node * 2 + 1, middle + 1, right, ql, qr)
self.pull(node)
def query(self, node, left, right, ql, qr):
if ql <= left and right <= qr:
return self.total[node], self.minimum[node]
self.push(node)
middle = (left + right) // 2
if qr <= middle:
return self.query(node * 2, left, middle, ql, qr)
if ql > middle:
return self.query(node * 2 + 1, middle + 1, right, ql, qr)
a = self.query(node * 2, left, middle, ql, qr)
b = self.query(node * 2 + 1, middle + 1, right, ql, qr)
return a[0] + b[0], min(a[1], a[0] + b[1])
def solve():
n, q = map(int, input().split())
tree = BracketTree(input().strip())
for _ in range(q):
operation, raw_left, raw_right = input().split()
left, right = int(raw_left) - 1, int(raw_right) - 1
if operation == 'F':
tree.flip(1, 0, n - 1, left, right)
else:
total, minimum = tree.query(1, 0, n - 1, left, right)
print('YES' if total == 0 and minimum >= 0 else 'NO')
solve()
复杂度分析
时间复杂度：$O(n+q\log n)$，建树为 $O(n)$，每次修改或查询为 $O(\log n)$。
空间复杂度：$O(n)$，保存输入及四个线段树数组，递归深度为 $O(\log n)$。
小结
- 货架最少搬运次数：先证明次数下界，再给出达到下界的搬运方案。
- 多多字符串：固定形状的子序列可以压缩为少量阶段。
- 果园最小收集边长：整数格子的跨度需要加一，横向窗口与纵向计数共同判定。
- 括号串翻转与合法查询：区间取反需要同时保留最大和最小前缀和。