大厂真题 / 拼多多
拼多多 2026-9-13 笔试真题 - 技术岗
本场考试概述
考试时间：2026年9月13日
考试岗位：技术岗
难度评级：中等偏难（按算法建模与实现难度评估）
考点分析：
- 第一题：半开区间、扫描线与峰值时长（简单）。
- 第二题：整数二分答案、前缀和与前缀最小值（中等）。
- 第三题：严格递增转非递减、值域离散化与动态规划（中等）。
- 第四题：KMP 自动机、乘积图、Dijkstra 最短路计数（困难）。
建议策略：先完成扫描线，再用整数判定处理平均值；第三题先证明候选值范围再写 DP；最后为图上路径补充字符串匹配状态。全文包含四道题、七份输入输出样例，其中第二题的一份输入包含三组测试数据。
第 1 题：配送员最少人数与满员时长
题目描述
配送站有若干任务，每个任务必须在指定的开始时刻至结束时刻，由同一名配送员全程执行，不能提前或延后。一名配送员不能同时承担多个任务，但任务结束时可以立即接手另一个任务。
求完成全部任务所需的最少配送员人数，以及采用这一人数时，所有配送员同时忙碌的累计时长。满足条件的时段可能不连续，需要将长度相加。任务对应半开区间 [s,e)，相同的任务记录也分别占用人手。
输入描述
第一行一个整数 $n$，满足 $1\le n\le 200000$。接下来 $n$ 行，每行两个整数 $s,e$，满足 $0\le s<e\le 10^9$。任务以任意顺序给出。
输出描述
输出两个整数：最少人数，以及所有人同时执行任务的累计时长。
样例 1
输入
5
1 4
2 3
3 5
4 6
6 7
输出
2 3
样例 2
输入
5
4 7
1 3
8 9
0 2
5 6
输出
2 2
第一份样例在 [2,5) 始终有两个任务同时执行，累计时长为 3。第二份样例的满员区间为 [1,2) 和 [5,6)，累计时长为 2。
思路分析
第一步：把人员安排转成区间覆盖。 如果某时刻有 $k$ 个任务同时执行，就至少需要 $k$ 人。反过来，按开始时间分配任务，只要有空闲配送员就复用；若最大重叠数为 $k$ 却找不到空闲者，新任务加入后就会形成 $k+1$ 个重叠，产生矛盾。因此答案人数恰好是最大重叠数。
第二步：只处理事件时刻。 时间上界很大，不能逐时刻开数组。在开始位置记 +1，结束位置记 -1，用字典聚合同一时间的净变化，再对所有时间排序。同刻事件一起处理，天然符合结束后立即接手的规则，不会制造虚假的瞬时峰值。
第三步：累计峰值对应的长度。 更新时刻 time 的净变化后，覆盖数在下一个事件之前保持不变。如果发现更大的覆盖数，更新峰值，并把累计时长重置为当前段长度；如果等于现有峰值，就累加长度。最后一个事件之后已经没有任务，不必统计。
正确性证明
上述下界与分配论证说明，最大重叠数等于最少人数。每个相邻事件区间内部没有开始或结束事件，扫描得到的覆盖数正是该整段的任务数。这些区间不重不漏地划分了全部任务活动时间。维护过程中，一旦峰值增大就丢弃旧峰值的时长，峰值相等时才累加，因此结束时保存的恰好是全局最大重叠数及其总持续时间。
题解代码
import sys
input = sys.stdin.readline
def min_couriers(intervals):
events = {}
for start, end in intervals:
events[start] = events.get(start, 0) + 1
events[end] = events.get(end, 0) - 1
times = sorted(events)
current = peak = duration = 0
for i in range(len(times) - 1):
time = times[i]
current += events[time]
length = times[i + 1] - time
if current > peak:
peak, duration = current, length
elif current == peak:
duration += length
return peak, duration
def solve():
n = int(input())
intervals = [tuple(map(int, input().split())) for _ in range(n)]
print(*min_couriers(intervals))
if __name__ == '__main__':
solve()
复杂度分析
时间复杂度：$O(n\log n)$，最多有 $2n$ 个事件时刻，排序主导；字典操作按均摊常数计。
空间复杂度：$O(n)$，用于任务、事件字典和排序后的时间数组。
易错点
- 不要把区间当成两端闭合，同刻交接不需要额外配送员。
- 统计的是达到全局峰值的总时长，不是最长连续满员时段。
- 出现更大峰值时，必须重置此前累积的时长。
第 2 题：连收模式最大平均日产量
题目描述
采摘季有 $n$ 天，第 $i$ 天的净产量为整数 $a_i$，可以为负数，代表运输及损耗造成净亏损。需要选择一段连续日子 $[l,r]$ 开启连收模式，长度至少为 $L$。
该区间的报表平均日产量定义为：
\[\left\lfloor\frac{\sum_{i=l}^{r}a_i}{r-l+1}\right\rfloor.\]向下取整指不大于原数的最大整数，例如 $\lfloor-8/3\rfloor=-3$。求所有合法区间中这一指标的最大值。
输入描述
第一行整数 $T$，满足 $1\le T\le10$。每组数据两行：
- 第一行两个整数 $n,L$，满足 $1\le L\le n\le 2\times10^5$。
- 第二行 $n$ 个整数 $a_i$，满足 $-10^9\le a_i\le10^9$。
所有测试组的 $n$ 之和不超过 $2\times10^5$。
输出描述
每组数据输出一行一个整数，表示最大的向下取整平均日产量。
样例 1
输入
3
5 3
3 -4 5 2 -1
3 2
-5 -3 -8
4 4
7 -2 -3 7
输出
2
-4
2
第一组可取 [5,2,-1]，平均值为 2；第二组取 [-5,-3]，平均值为 -4；第三组必须选全部四天，总和为 9，向下取整后为 2。
思路分析
第一步：把最优化改成判定。 枚举所有区间需要平方级时间。对于整数 $x$，有 $\lfloor avg\rfloor\ge x$ 当且仅当 $avg\ge x$。于是可以二分“是否存在长度至少为 $L$、平均值至少为 $x$ 的区间”。目标越低越容易满足，判定具有单调性。
第二步：把平均值改成区间和。 将每项减去 $x$，条件等价于区间内变换后的和非负。定义前缀和 $S_0=0$，$S_i=\sum_{j=1}^{i}(a_j-x)$。固定右端点 $r$，合法左边界对应的前缀下标为 $0\le j\le r-L$。因此只需检查：
\[S_r-\min_{0\le j\le r-L}S_j\ge0.\]第三步：线性维护最小前缀。 从 $r=L$ 开始扫描，每次先把 $S_{r-L}$ 加入前缀最小值，再判断当前右端点。有任意一个满足即可返回真；无需存每个区间，也无需浮点除法。
第四步：二分最大可行整数。 下界取数组最小值，上界取最大值，使用偏上的中点。可行时保留中点为新下界，否则上界减至中点减一，直到边界重合。
正确性证明
对每个整数候选值，减去该值后区间和非负与原平均值达到该值等价。前缀最小值涵盖且仅涵盖所有长度符合要求的左边界，因此判定函数当且仅当存在合法区间时返回真。可行性随候选值增大只会由真变假，且答案一定在最小元素与最大元素之间；上取中点的二分保留最大可行答案并严格缩小范围，最终输出正确结果。
题解代码
import sys
input = sys.stdin.readline
def max_average(a, limit):
n = len(a)
def feasible(target):
prefix = [0] * (n + 1)
for i, value in enumerate(a, 1):
prefix[i] = prefix[i - 1] + value - target
smallest = 0
for right in range(limit, n + 1):
smallest = min(smallest, prefix[right - limit])
if prefix[right] >= smallest:
return True
return False
low, high = min(a), max(a)
while low < high:
mid = (low + high + 1) // 2
if feasible(mid):
low = mid
else:
high = mid - 1
return low
def solve():
tests = int(input())
for _ in range(tests):
n, limit = map(int, input().split())
a = list(map(int, input().split()))
print(max_average(a, limit))
if __name__ == '__main__':
solve()
复杂度分析
时间复杂度：每组 $O(n\log(V+1))$，其中 $V=\max a-\min a+1$；包含全相等数组时的线性读入成本。
空间复杂度：$O(n)$，保存原数组和当前二分轮次的前缀和。
易错点
- 长度是至少 $L$，不能只枚举恰好 $L$ 的滑动窗口。
- 负数的向下取整不是向零截断；代码避免除法与浮点误差。
- 先加入下标
right-limit，否则会漏掉长度恰好为 $L$ 的区间。 L=n、全负数及全相等数组都必须正常处理。
第 3 题：魔法水晶严格递增最少操作
题目描述
有 $n$ 颗从左到右排列的水晶，初始能量为 $a_1,\ldots,a_n$。每次操作可以任选一颗水晶，使其能量增加 1 或减少 1。求使能量序列严格递增所需的最少操作次数。调整后的能量没有额外范围限制。
输入描述
第一行整数 $n$，满足 $1\le n\le2000$。第二行 $n$ 个整数 $a_i$，满足 $\lvert a_i\rvert\le10^9$。
输出描述
输出一个整数，表示最少操作次数。
样例 1
输入
5
1 1 1 1 1
输出
6
样例 2
输入
4
1 2 3 4
输出
0
第一份样例可调整为 [-1,0,1,2,3]，各位置代价为 2,1,0,1,2，总计 6。第二份样例已经严格递增，无需操作。
思路分析
第一步：消去严格递增中的位置差。 设最终序列为 $c_i$，令 $b_i=a_i-i$、$d_i=c_i-i$，下标从 1 开始。整数的严格递增等价于相邻至少增加 1，因此 $c_i<c_{i+1}$ 恰好等价于 $d_i\le d_{i+1}$。同时 $\lvert a_i-c_i\rvert=\lvert b_i-d_i\rvert$，总操作代价不变。
第二步：将无限值域压成有限候选。 目标变成绝对偏差和最小的非递减序列。存在一个最优解，其中每个值都取自 $b$。把最优序列划分成取值相等的连续块；若某块取值不是任意 $b_i$，其代价在遇到某个 $b_i$ 前是线性函数，可以向不增加代价的方向移动，直到遇到某个数据值或邻块。遇到邻块就合并再考虑。如此消除非候选块，最终取值全部落在数据值上。因此可用 values=sorted(set(b))，候选数记为 $K\le n$。
第三步：按最后一个取值做 DP。 令 $f_i(j)$ 表示处理前 $i$ 项、当前项等于 values[j] 的最小代价。前一项只能选择不大于当前候选的值：
初始化虚拟空序列 $f_0(j)=0$。最终答案为 $\min_j f_n(j)$。
第四步：前缀最小值与滚动数组。 若每次都枚举 $k$，需要立方级时间。按 $j$ 升序扫描，用 best 维护上一行的前缀最小值，每个状态只做常数次计算。原地覆盖前先把旧 dp[j] 纳入 best，不需要额外二维表。
正确性证明
位置变换在原严格递增序列与新非递减序列之间建立保代价双射；候选值论证保证离散化不丢失最优解。对 DP 按已处理项数归纳：当前候选为第 $j$ 个值时，所有合法前驱恰好对应下标不超过 $j$ 的状态，转移枚举这些前驱的最小代价并加入当前修改量，既不漏解也不引入非法解。前缀最小值只是等价加速，故最终最小值就是原问题答案。
题解代码
import sys
input = sys.stdin.readline
def min_operations(a):
b = [value - i for i, value in enumerate(a, 1)]
values = sorted(set(b))
dp = [0] * len(values)
for value in b:
best = dp[0]
for j, candidate in enumerate(values):
# 必须先读取上一行的 dp[j]，再覆盖当前位置。
best = min(best, dp[j])
dp[j] = best + abs(value - candidate)
return min(dp)
def solve():
n = int(input())
a = list(map(int, input().split()))
print(min_operations(a))
if __name__ == '__main__':
solve()
复杂度分析
时间复杂度：$O(n\log n+nK)=O(n^2)$，其中 $K$ 是变换后不同元素个数。
空间复杂度：$O(n)$，保存变换数组、候选数组与滚动 DP。
易错点
- 离散化的是
a[i]-i，不是原数组；直接对原值做非递减 DP 会改变题意。 - 递增针对最终整数序列，不应限制修改只能增加。
- 原地更新时必须先读取旧状态。只把当前相邻逆序对修好并不保证全局代价最小。
- 操作次数可能超过 32 位整数；Python 整数可以直接保存。
第 4 题：合规路线最小费用与方案数
题目描述
物流网络有 $n$ 个仓库和 $m$ 条单向道路。每条道路有正整数费用，以及 A、B、C 中的一个标签。从仓库 $s$ 出发到仓库 $t$，按行驶顺序连接道路标签，得到路线的标签串。
给定非空禁用串 $P$，标签串不得包含连续子串 $P$。车辆可以重复经过仓库和道路，每次经过都支付费用。求合规路线的最小总费用及达到该费用的路线数，路线数对 $1000000007$ 取模。
道路按输入顺序编号。道路编号序列不同就视为不同路线，即使端点、费用和标签全部相同的重边也分别计数。当 $s=t$ 时允许空路线，费用为 0、标签串为空。
输入描述
第一行四个整数 $n,m,s,t$，满足 $1\le n\le5000$、$0\le m\le20000$、$1\le s,t\le n$。
第二行是仅含 A、B、C 的字符串 $P$，满足 $1\le\lvert P\rvert\le50$。
接下来 $m$ 行，每行 u v w ch，表示从 $u$ 到 $v$ 的有向道路，费用为 $w$、标签为 ch。满足 $1\le u,v\le n$、$1\le w\le10^9$，允许重边与自环。
部分数据约束：20% 的数据满足 $n\le10$、$m\le20$、$\lvert P\rvert\le4$，且每条边起点编号小于终点编号；另有 30% 的数据中禁用串只有一个字符；其余 50% 无额外限制。
输出描述
输出最小总费用与最优路线数（取模后），用空格分隔。如果不存在合规路线，输出 -1 0。
样例 1
输入
4 5 1 4
AB
1 2 1 A
2 4 1 B
1 3 1 B
3 4 2 A
1 4 3 C
输出
3 2
样例 2
输入
2 1 1 2
A
1 2 7 A
输出
-1 0
第一份样例中，1→2→4 的费用虽为 2，但标签串 AB 被禁止；1→3→4 的标签串 BA 与直达路线的 C 均合法，费用都是 3，所以输出 3 2。第二份样例的唯一道路标签被禁止，无解。
思路分析
第一步：普通最短路缺少历史信息。 到达同一仓库的两条路线，后缀可能不同，再走相同标签的道路时，可能一条合法、另一条触发禁串。只用仓库作为状态会错误合并路线，而保存全部标签串又没有有限的长度上界。
第二步：用 KMP 后缀匹配长度概括历史。 令 $q=\lvert P\rvert$，记录已走标签串的后缀与 $P$ 的前缀相同的最大长度 $j$，合法状态满足 $0\le j<q$。利用 KMP 失配数组构建 go[j][c]：字符匹配时前进一位，否则复用较短匹配前缀的转移。若新长度等于 $q$，说明刚刚形成完整禁串，该边不能走。三个字符的转移可以按状态从小到大在线性时间填表。
第三步：在乘积图上跑 Dijkstra。 状态为 (u,j)，其中 u 为仓库，j 为匹配长度。原图边 u→v 在标签转移合法时，生成到 (v,go[j][c]) 的同权状态边。只保存原图，扫描邻接表时即时计算状态边；状态编码为 u*q+j，数组保存距离与条数。
第四步：最短距离和条数同步维护。 从 (s,0) 出发，距离设为 0、条数设为 1。发现更短距离时，覆盖距离与条数并入堆；距离相等时，只将前驱条数加到已有条数中，不重复入堆。过期的堆条目直接跳过。
所有边权严格为正，因此一条最短路径的前驱距离严格小于后继距离。状态正式出堆时，所有能为它贡献最短路计数的前驱都已经处理完成，计数可以安全地向后传播。
第五步：汇总所有终点匹配状态。 终点不要求匹配长度为 0，在所有 (t,j) 中取最小距离，并将达到该距离的条数相加。不可达时返回 -1 0。当起终点相同时，正权保证空路线是唯一的零费用路线。
正确性证明
KMP 状态精确记录判定下一字符是否形成禁串所需的最长前缀后缀信息，因此每条被保留的状态边恰好对应一次合法延伸。从 (s,0) 出发，给定道路编号序列会唯一确定自动机状态序列，合法路线与状态路径一一对应，费用保持不变，重边也不会被合并。
状态图边权均为正，Dijkstra 得到所有可达状态的最短距离。按最短距离递增归纳，每个状态出堆时所有最短前驱都已贡献完毕；更短距离覆盖、等长距离相加恰好统计全部最短路线。最后对具有全局最小距离的终点状态求和，不重不漏地得到目标答案。
题解代码
import sys
import heapq
input = sys.stdin.readline
MOD = 1000000007
def automaton(pattern):
size = len(pattern)
fail = [0] * size
for i in range(1, size):
j = fail[i - 1]
while j and pattern[i] != pattern[j]:
j = fail[j - 1]
if pattern[i] == pattern[j]:
j += 1
fail[i] = j
go = [[0] * 3 for _ in range(size)]
for j in range(size):
for c, char in enumerate('ABC'):
if pattern[j] == char:
go[j][c] = j + 1
elif j:
go[j][c] = go[fail[j - 1]][c]
return go
def shortest_routes(n, edges, source, target, pattern):
size = len(pattern)
go = automaton(pattern)
graph = [[] for _ in range(n)]
for u, v, weight, char in edges:
graph[u].append((v, weight, ord(char) - ord('A')))
infinity = float('inf')
dist = [infinity] * (n * size)
count = [0] * (n * size)
start = source * size
dist[start], count[start] = 0, 1
heap = [(0, start)]
while heap:
distance, state = heapq.heappop(heap)
if distance != dist[state]:
continue
u, matched = divmod(state, size)
for v, weight, char in graph[u]:
nxt = go[matched][char]
if nxt == size:
continue
dest = v * size + nxt
candidate = distance + weight
if candidate < dist[dest]:
dist[dest] = candidate
count[dest] = count[state]
heapq.heappush(heap, (candidate, dest))
elif candidate == dist[dest]:
count[dest] = (count[dest] + count[state]) % MOD
answer = min(dist[target * size:(target + 1) * size])
if answer == infinity:
return -1, 0
ways = sum(count[target * size + j] for j in range(size)
if dist[target * size + j] == answer) % MOD
return answer, ways
def solve():
n, m, source, target = map(int, input().split())
pattern = input().strip()
edges = []
for _ in range(m):
u, v, weight, char = input().split()
edges.append((int(u) - 1, int(v) - 1, int(weight), char))
print(*shortest_routes(n, edges, source - 1, target - 1, pattern))
if __name__ == '__main__':
solve()
复杂度分析
令 $q=\lvert P\rvert$，状态数 $N=nq$，候选状态边数 $M=mq$。
时间复杂度：$O(n+m+q+N+M\log(M+2))$。自动机的字母表大小固定为 3；最多扫描 $M$ 条状态边，lazy heap 的成功松弛与堆操作次数为 $O(M+1)$。用 $M+2$ 避免无边图的对数边界问题。
空间复杂度：$O(n+m+q+N+M)$。原图与状态数组分别占 $O(n+m)$、$O(N)$，但 Python heapq 不支持原地 decrease-key，过期条目仍可能滞留，堆最坏占 $O(M+1)$；不能因为未显式建状态边就忽略这一项。
易错点
- 禁止的是连续子串，不是子序列。匹配失败要沿失配链回退，而不是简单清零。
- 必须允许重复仓库和道路，不要在原图层面设置永久访问标记。
- 重边代表不同道路编号，应保留并分别累计；自环也应保留。
- 相等距离只加条数，不再次入堆，否则可能重复向后传播。
- 正权是计数正确性的关键；本题方法不能未经修改套到含零权环的题目。
- 不要只输出
(t,0)的结果，也不要漏掉m=0或s=t的情形。
小结
- 第一题：资源最少需求等于同时进行任务的峰值，时长需要按事件间隔累计。
- 第二题：平均值优化可通过减去候选答案化成区间和判定，再维护合法左端点的最小前缀。
- 第三题：减去位置下标将严格递增转成非递减，绝对偏差的分段线性性质使值域离散化成立。
- 第四题：图上约束依赖路径历史时，可以把有限自动机并入状态；计数还需检查边权与堆实现的前提。