大厂真题 / 拼多多
拼多多 2026-8-23 笔试真题 - 研发岗
本场考试概述
考试时间：2026 年 8 月 23 日
考试岗位：研发岗
难度评级：中等
考点分析：
- 第 1 题：二分答案、差分贪心（中等）
- 第 2 题：贪心、翻转奇偶性（简单）
- 第 3 题：状态扩展、Dijkstra 最短路（困难）
- 第 4 题：带权并查集、仿射关系（中等）
第 1 题：跑道平整度优化
题目描述
训练场由从左到右排列的 $n$ 段连续跑道组成，第 $i$ 段跑道的初始平整度为 $a_i$。平整度越高，运动员经过该路段时越不容易受到影响。
最多可以进行 $m$ 次修整。每次修整可以选择一个连续区间 $[l,r]$，满足
\[1\le l\le r\le n,\qquad r-l+1\le k,\]并令区间中每一段的平整度增加 $1$，即对所有 $l\le i\le r$ 执行 $a_i\leftarrow a_i+1$。
求最多进行 $m$ 次操作后，所有跑道路段平整度最小值的最大可能值。
输入描述
第一行输入三个整数 $n,m,k$，分别表示跑道段数、最多操作次数和一次操作最多覆盖的连续路段数。
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各段跑道的初始平整度。
原页面给出的数据范围为：
\[1\le n\le10^9,\quad 0\le m\le10^9,\quad 1\le k\le10^9,\quad 0\le a_i\le10^9.\]注：原页面确实将 $n$ 标为 $10^9$，但输入需要显式给出 $n$ 个数，且参考解法也需要线性扫描，因此该上限很可能是原题整理时的笔误；下述算法的复杂度按实际输入长度 $n$ 计算。
输出描述
输出一个整数，表示最终最小平整度能够达到的最大值。
样例
输入
5 4 3
1 2 1 2 1
输出
3
思路分析
这是“最大化最小值”的典型二分答案问题。设想判断某个目标值 $x$ 是否可达：只需计算把每一段都提高到至少 $x$ 所需的最少操作数，并检查它是否不超过 $m$。
从左向右扫描。到达位置 $i$ 时，此后能改变 $a_i$ 的操作，其左端点不能在 $i$ 的右侧。如果当前位置实际高度低于 $x$，缺少的
\[need=x-(a_i+add)\]次操作必须立即补上。每次操作都从 $i$ 开始并尽量向右覆盖 $k$ 段，即覆盖 $[i,\min(n,i+k-1)]$。这样既满足当前位置，又为尚未处理的右侧位置提供尽可能多的帮助。
用变量 add 维护当前仍生效的历史增量，用差分数组记录增量在何处到期。补上 need 后令 add += need，并在位置 $i+k$ 记录 -need。如此一次可行性检查只需 $O(n)$。
可行性关于 $x$ 单调：若 $x$ 可达，则任何不大于 $x$ 的目标也可达。答案下界为 $\min a_i$；每次操作对任一位置至多增加 $1$，故上界可取 $\min a_i+m$。在这个区间二分最大的可行值即可。
正确性证明
引理 1：扫描到位置 $i$ 时，若当前高度比目标 $x$ 少 need，任何可行方案都至少还要执行 need 次覆盖位置 $i$ 的操作。
证明：一次操作对位置 $i$ 的贡献至多为 $1$。此前操作已经固定，当前位置仍差 need，所以至少需要 need 次新操作，否则位置 $i$ 无法达到 $x$。
引理 2：需要覆盖位置 $i$ 时，将操作区间取为 $[i,\min(n,i+k-1)]$ 不劣于其他选择。
证明：位置 $i$ 左侧均已处理，新的操作再覆盖左侧不会改善后续可行性。所有覆盖 $i$、长度不超过 $k$ 且不浪费在左侧的区间中，以 $i$ 为左端点覆盖到的右侧最远，因此对未处理位置的帮助最多。
引理 3：可行性检查使用的操作数是达到目标 $x$ 的最少操作数。
证明：由引理 1，每次补上的数量是任何方案都不可避免的；由引理 2，算法对右侧提供了不小于任何其他同数量选择的帮助。逐位置归纳，算法既不会少补导致当前位置不达标，也不会做可省略的操作。因此总操作数最少。
定理：算法输出最终最小平整度的最大可能值。
证明：由引理 3，检查函数当且仅当目标值能在 $m$ 次操作内达到。可行性具有单调性，二分最终停在最大的可行目标值，因此该值正是答案。
ACM Python 代码
import sys
def can_reach(a, operations, width, target):
n = len(a)
expire = [0] * (n + 1)
active_add = 0
used = 0
for i, value in enumerate(a):
active_add += expire[i]
current = value + active_add
if current < target:
need = target - current
used += need
if used > operations:
return False
active_add += need
if i + width < n:
expire[i + width] -= need
return True
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
n, m, k = data[:3]
a = data[3:3 + n]
low = min(a)
high = low + m
while low < high:
middle = (low + high + 1) // 2
if can_reach(a, m, k, middle):
low = middle
else:
high = middle - 1
print(low)
if __name__ == "__main__":
solve()
复杂度分析
设值域二分轮数为 $O(\log(m+1))$。
时间复杂度：$O(n\log(m+1))$。
空间复杂度：$O(n)$。
易错点
- 一次操作覆盖长度是“不超过 $k$”，贪心时应尽量覆盖恰好 $k$ 段，末尾自然截断。
- 差分撤销位置是
i + k，不是i + k - 1。 active_add表示当前仍生效的增量；应先加入当前位置的差分，再判断缺口。- 二分取上中位数，否则
low = middle可能死循环。 - $a_i+m$ 可能超过 32 位整数范围；其他语言需使用 64 位整数。
第 2 题：灯柱按钮状态
题目描述
有 $n$ 个从左到右编号为 $1$ 到 $n$ 的机柜，每个机柜有一盏状态灯，亮起记为 $1$，熄灭记为 $0$。
第 $i$ 个机柜旁有一个按钮。按下该按钮会翻转第 $i$ 盏到第 $n$ 盏灯的状态，即 $0$ 变为 $1$，$1$ 变为 $0$。
从第 $1$ 个机柜开始依次向右巡检。到达第 $i$ 个机柜时，可以选择是否按下此处按钮；离开后不能返回。求使所有灯最终都亮起的最少按钮次数。
输入描述
第一行输入一个整数 $n$，表示机柜数量。
第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i\in{0,1}$。
数据范围：
\[1\le n\le100000,\qquad a_i\in\{0,1\}.\]输出描述
输出一个整数，表示使所有灯变为 $1$ 的最少操作次数。
样例
输入
2
1 0
输出
1
解释：只需按下第 $2$ 个按钮，状态由 1 0 变为 1 1。
思路分析
从左到右处理第 $i$ 盏灯时，之后编号更大的按钮都无法再影响它，因此当前灯若为 $0$ 就必须按按钮，若为 $1$ 就不能按。这使每一步决策都是唯一的。
不必真正翻转整个后缀。位置 $i$ 会被此前每次按钮操作翻转一次，只需维护已按次数的奇偶性 parity。当前真实状态为
若它为 $0$，答案加一并翻转 parity。
正确性证明
引理：处理到位置 $i$ 时，按钮 $i$ 的选择由当前灯状态唯一确定。
证明：位置 $i$ 之后的按钮作用区间均从更右侧开始，无法改变位置 $i$。若当前为 $0$，不按按钮就永远无法变成 $1$；若当前为 $1$，按下后会变成 $0$ 且无法恢复。因此分别必须按和必须不按。
定理：算法得到使所有灯亮起的最少操作次数。
证明：算法用翻转次数奇偶性准确计算每盏灯的当前状态，并按引理作出唯一能使该位置最终为 $1$ 的决定。依次处理后所有位置均为 $1$。由于任意合法方案在每个位置都必须作出同样决定，算法的操作数不仅可行，而且是唯一的，因而最少。
ACM Python 代码
import sys
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
lights = data[1:1 + n]
answer = 0
parity = 0
for state in lights:
if (state ^ parity) == 0:
answer += 1
parity ^= 1
print(answer)
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(n)$。
空间复杂度：$O(n)$（读取输入数组）；若流式读取灯的状态，额外占用可降至 $O(1)$。
易错点
- 第 $i$ 个按钮翻转的是后缀 $[i,n]$，不是只有当前灯，也不是固定长度区间。
- 判断的是经过此前操作后的真实状态，而不是初始的 $a_i$。
- 只需维护奇偶性，不应真的逐个翻转后缀，否则最坏为 $O(n^2)$。
- 全部初始为 $1$ 时答案为 $0$；只有最后一盏为 $0$ 时答案为 $1$。
第 3 题：货车司机最短路径
题目描述
有 $N$ 个城市和 $M$ 条双向道路。第 $i$ 条道路由四个整数 $u_i,v_i,c_i,t_i$ 描述，表示道路连接城市 $u_i$ 与 $v_i$，通过它消耗 $c_i$ 单位燃油并花费 $t_i$ 分钟。
货车从城市 $1$ 出发，目标是城市 $N$。油箱容量为 $F$，出发时油箱已加满，即初始油量也是 $F$。在城市 $i$ 可以加油，每增加 $1$ 单位燃油需要 $p_i$ 分钟，油量不能超过 $F$。
求从城市 $1$ 到城市 $N$ 的最短总时间；若无法到达，输出 $-1$。
输入描述
第一行输入三个整数 $N,M,F$，分别表示城市数、双向道路数和油箱容量。
第二行输入 $N$ 个整数 $p_1,p_2,\ldots,p_N$，其中 $p_i$ 表示在城市 $i$ 加一单位燃油所需时间。
接下来 $M$ 行，每行输入四个整数 $u_i,v_i,c_i,t_i$，描述一条双向道路。
数据范围：
\[2\le N\le1000,\quad 1\le M\le10000,\quad 1\le F\le100,\] \[0\le p_i\le100,\quad 1\le c_i\le100,\quad 1\le t_i\le1000.\]输出描述
输出一个整数，表示从城市 $1$ 到城市 $N$ 的最短时间；无法到达则输出 $-1$。
样例 1
输入
3 3 3
2 3 5
1 2 1 10
1 3 1 100
2 3 3 1
输出
14
解释：先从 $1$ 到 $2$，耗油 $1$、耗时 $10$；在城市 $2$ 加 $1$ 单位油，耗时 $3$；再从 $2$ 到 $3$，耗油 $3$、耗时 $1$。总时间为 $14$。
样例 2
输入
2 1 5
1 10
1 2 10 5
输出
-1
思路分析
仅记录所在城市不足以描述状态：到达同一城市时剩余油量不同，后续可走的道路也不同。因此将状态定义为
\[(u,f),\qquad 1\le u\le N,\quad0\le f\le F.\]状态图中有两类转移：
- 若 $f<F$，可在城市 $u$ 加一单位油： \((u,f)\to(u,f+1),\quad\text{代价 }p_u.\)
- 对道路 $(u,v,c,t)$，若 $f\ge c$，可以行驶： \((u,f)\to(v,f-c),\quad\text{代价 }t.\)
全部边权非负，可以从初始状态 $(1,F)$ 运行 Dijkstra。第一次从小根堆弹出终点城市的任意状态时，其距离就是答案；若堆清空仍未到达终点，则无解。
正确性证明
引理 1：任意合法运输方案都对应状态图中一条从 $(1,F)$ 出发的路径，且路径权值等于方案耗时。
证明：每加一单位油对应第一类边，每通过一条道路对应第二类边；油箱容量与道路油耗条件正是这些边的可用条件。逐个操作映射后状态和耗时均完全一致。
引理 2：状态图中任意从 $(1,F)$ 到城市 $N$ 某状态的路径都对应一个合法运输方案，耗时等于路径权值。
证明：第一类边只在未满油时增加一单位，第二类边只在油量足够时扣除道路油耗，因此沿路径执行各操作始终满足题目限制，并到达相同城市和油量。
定理：算法输出最短运输时间，或在不可达时输出 $-1$。
证明：由引理 1、2，原问题与状态图最短路等价。状态图边权均非负，Dijkstra 正确求出从 $(1,F)$ 到所有可达状态的最短距离。第一次弹出的终点状态具有所有未处理状态中的最小距离，故也是到终点城市的全局最短时间。若不存在终点状态可达，堆最终为空，输出 $-1$ 正确。
ACM Python 代码
import sys
import heapq
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
iterator = iter(data)
n = next(iterator)
m = next(iterator)
capacity = next(iterator)
price = [next(iterator) for _ in range(n)]
graph = [[] for _ in range(n)]
for _ in range(m):
u = next(iterator) - 1
v = next(iterator) - 1
fuel_cost = next(iterator)
travel_time = next(iterator)
graph[u].append((v, fuel_cost, travel_time))
graph[v].append((u, fuel_cost, travel_time))
inf = float("inf")
dist = [[inf] * (capacity + 1) for _ in range(n)]
dist[0][capacity] = 0
heap = [(0, 0, capacity)]
while heap:
time, city, fuel = heapq.heappop(heap)
if time != dist[city][fuel]:
continue
if city == n - 1:
print(time)
return
if fuel < capacity:
new_time = time + price[city]
if new_time < dist[city][fuel + 1]:
dist[city][fuel + 1] = new_time
heapq.heappush(heap, (new_time, city, fuel + 1))
for next_city, fuel_cost, travel_time in graph[city]:
if fuel >= fuel_cost:
next_fuel = fuel - fuel_cost
new_time = time + travel_time
if new_time < dist[next_city][next_fuel]:
dist[next_city][next_fuel] = new_time
heapq.heappush(
heap, (new_time, next_city, next_fuel)
)
print(-1)
if __name__ == "__main__":
solve()
复杂度分析
状态数为 $O(NF)$。加油转移有 $O(NF)$ 条，按各油量枚举道路产生至多 $O(MF)$ 条行驶转移。使用二叉堆后，时间复杂度：
\[O\bigl((NF+MF)\log(NF)\bigr),\]空间复杂度：$O(NF+M)$。
易错点
- 出发时油箱是满的，初始状态为 $(1,F)$，不是 $(1,0)$。
- 道路是双向的，邻接表必须加入两个方向。
- 行驶耗时与油耗是两个不同字段，不能混用。
- 加油应建成逐单位转移；只建“一次加满”会漏掉只加部分油的最优方案。
- $p_i$ 可以为 $0$，Dijkstra 允许零权边；判断过期堆元素时不要依赖“严格正权”。
- 油耗超过容量的道路永远不可走，但无需预先删除。
第 4 题：区域仓库存差判定
题目描述
有 $n$ 个区域仓，第 $i$ 个仓库的实际库存为整数 $x_i$，库存可以为任意整数，包括负数。现有 $m$ 条线索，每条为以下两种形式之一：
D a b d：$x_a-x_b=d$；S a b s：$x_a+x_b=s$。
判断是否存在一组整数库存同时满足全部线索。若存在，求最少需要直接盘点多少个仓库，才能唯一确定所有仓库的库存。
输入描述
第一行输入整数 $T$，表示测试组数。
对每组测试数据：
- 第一行输入两个整数 $n,m$；
- 接下来 $m$ 行，每行输入
D a b d或S a b s。
原页面的数据范围公式显示为 $\sum n\le10^5$、$\sum m\le10^5$（指数在页面中以上标渲染）。
输出描述
对每组测试数据输出两行：
- 若存在整数解，第一行输出
YES，第二行输出最少盘点数； - 若不存在整数解，第一行输出
NO，第二行输出-1。
若线索已经唯一确定全部库存，最少盘点数为 $0$。
样例
输入
1
3 3
D 1 2 4
D 2 3 -1
D 1 3 3
输出
YES
1
解释：前两条线索可推出 $x_1-x_3=3$，第三条是冗余线索。三个库存由一个自由整数决定，盘点其中任意一个仓库即可推出其余库存，所以答案为 $1$。
思路分析
将两类线索统一写成
\[x_a=\varepsilon x_b+w,\]其中差关系取 $\varepsilon=1,w=d$，和关系取 $\varepsilon=-1,w=s$。
使用带权并查集。对每个节点 $i$，维护它相对父节点的仿射表达式
\[x_i=sign_i\cdot x_{parent_i}+offset_i, \qquad sign_i\in\{-1,1\}.\]路径压缩后可得到节点对根的表达式
\[x_i=s_iR+o_i.\]若一条新线索连接两个不同连通块，将两端表达式代入即可推出两个根之间的关系，再按集合大小合并。若两个点已经同属一块，代入线索得到
\[(s_a-\varepsilon s_b)R =\varepsilon o_b+w-o_a.\]左侧系数只有 $0$ 或 $\pm2$：
- 系数为 $0$ 时，右侧必须也为 $0$，否则矛盾；
- 系数为 $\pm2$ 时，这条线索会唯一确定根 $R$。右侧必须能被系数整除，才能得到整数库存；若该根此前已被定值，新旧值还必须相同。
每个未定值连通块保留一个自由整数。盘点块内任意一个仓库就能确定该自由量并推出整块；已定值连通块则无需盘点。因此答案是未被定值的连通块数量。
正确性证明
引理 1：并查集维护的表达式 $x_i=s_iR+o_i$ 与所有已处理的跨块合并线索等价。
证明：初始时每个点自成一块，表达式 $x_i=x_i$ 成立。合并两个块时，算法把两端表达式代入 $x_a=\varepsilon x_b+w$，精确解出一个根关于另一个根的仿射式，并将其记录在新父边上。路径压缩只复合仿射式，不改变关系。因此归纳成立。
引理 2：同块线索的矛盾与定值判定正确。
证明：同块两端均可表示为同一根 $R$ 的仿射式，代入后得到上述一元方程。系数为 $0$ 时，方程有解当且仅当右侧为 $0$；系数为 $\pm2$ 时，整数根存在当且仅当右侧整除系数，并且根值唯一。若同一根被要求取不同值则显然无解。这恰好覆盖全部情况。
引理 3：若线索无矛盾，每个未定值连通块恰有一个自由整数，而每个已定值连通块没有自由量。
证明：由引理 1，块内所有节点都由根 $R$ 唯一表示。若 $R$ 未定，任取一个整数 $R$ 都得到一组整数库存，因此恰有一个自由量；若 $R$ 已定，所有节点随之唯一确定。
定理：算法正确判断是否存在整数解，并在有解时输出最少盘点数。
证明：由引理 2，算法报告 NO 当且仅当某条线索与已有关系矛盾或要求非整数库存。无矛盾时，由引理 3，每个未定值块至少要盘点一个点，否则其自由量无法确定；盘点块内任意一个点又足以求出根并确定整块。各块相互独立，故最少盘点数正是未定值连通块数。
ACM Python 代码
import sys
class WeightedDSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
# x_i = sign[i] * x_parent[i] + offset[i]
self.sign = [1] * n
self.offset = [0] * n
self.fixed = [False] * n
self.value = [0] * n
self.ok = True
def find(self, x):
if self.parent[x] == x:
return x
parent = self.parent[x]
root = self.find(parent)
self.offset[x] += self.sign[x] * self.offset[parent]
self.sign[x] *= self.sign[parent]
self.parent[x] = root
return root
def nail(self, root, value):
if self.fixed[root]:
if self.value[root] != value:
self.ok = False
else:
self.fixed[root] = True
self.value[root] = value
def add_relation(self, a, b, epsilon, weight):
# x_a = epsilon * x_b + weight
root_a = self.find(a)
root_b = self.find(b)
sa, oa = self.sign[a], self.offset[a]
sb, ob = self.sign[b], self.offset[b]
if root_a == root_b:
coefficient = sa - epsilon * sb
right = epsilon * ob + weight - oa
if coefficient == 0:
if right != 0:
self.ok = False
elif right % coefficient != 0:
self.ok = False
else:
self.nail(root_a, right // coefficient)
return
# 推出 x_root_b = link_sign * x_root_a + link_offset
link_sign = epsilon * sb * sa
link_offset = epsilon * sb * (oa - epsilon * ob - weight)
if self.size[root_a] >= self.size[root_b]:
# root_b 挂到 root_a
old_fixed = self.fixed[root_b]
old_value = self.value[root_b]
self.parent[root_b] = root_a
self.sign[root_b] = link_sign
self.offset[root_b] = link_offset
self.size[root_a] += self.size[root_b]
if old_fixed:
# old_value = link_sign * x_root_a + link_offset
root_value = link_sign * (old_value - link_offset)
self.nail(root_a, root_value)
else:
# 反解 x_root_a = link_sign * x_root_b
# - link_sign * link_offset
old_fixed = self.fixed[root_a]
old_value = self.value[root_a]
self.parent[root_a] = root_b
self.sign[root_a] = link_sign
self.offset[root_a] = -link_sign * link_offset
self.size[root_b] += self.size[root_a]
if old_fixed:
# x_root_b = link_sign * x_root_a + link_offset
root_value = link_sign * old_value + link_offset
self.nail(root_b, root_value)
def solve():
tokens = sys.stdin.buffer.read().split()
iterator = iter(tokens)
test_cases = int(next(iterator))
output = []
for _ in range(test_cases):
n = int(next(iterator))
m = int(next(iterator))
dsu = WeightedDSU(n)
for _ in range(m):
relation_type = next(iterator)
a = int(next(iterator)) - 1
b = int(next(iterator)) - 1
weight = int(next(iterator))
if dsu.ok:
epsilon = 1 if relation_type == b"D" else -1
dsu.add_relation(a, b, epsilon, weight)
if not dsu.ok:
output.extend(("NO", "-1"))
continue
roots = {dsu.find(i) for i in range(n)}
answer = sum(not dsu.fixed[root] for root in roots)
output.extend(("YES", str(answer)))
print("\n".join(output))
if __name__ == "__main__":
solve()
复杂度分析
设一组数据有 $n$ 个仓库、$m$ 条线索。
时间复杂度：$O((n+m)\alpha(n))$，其中 $\alpha$ 为反阿克曼函数。
空间复杂度：$O(n)$。
易错点
S a b s也会连接两个仓库，只是符号为 $-1$，不能只校验而不合并。- 库存必须是整数。同块方程出现 $2R=\text{奇数}$ 时应判无解。
- 连通不等于已经唯一确定：只含差关系的连通块通常仍有一个自由量。
- 合并两个块时，若其中一个根已被定值，必须把定值换算到新根；若两块都已定值，还要检查是否冲突。
- 自环线索也需处理。例如
S 1 1 3表示 $2x_1=3$，不存在整数解。 - 输入含负数，解析时不能遗漏符号。