大厂真题 / 拼多多
拼多多 2026-08-30 技术岗笔试题解
本文收录 4 道编程题。原始页面中的数学公式以 SVG 字形轮廓保存，纯 Markdown 抽取时部分变量与约束上界丢失；下文只恢复能够由题意、样例和代码相互印证的内容，无法可靠辨认的数值不作猜测。
第 1 题：石板神秘子串
题目描述
给定一个仅由小写英文字母组成的非空字符串 $s$。如果一个非空连续子串中任意两个相邻字符都不同，则称它为“神秘子串”。求 $s$ 中最长神秘子串的长度。
输入描述
一行一个字符串 $s$，仅包含小写英文字母。
输出描述
输出一个整数，表示最长神秘子串的长度。
可恢复约束
- $s$ 非空，只含小写英文字母。
- 原页面的长度上界在抽取时丢失，无法可靠恢复，因此不编造具体数值。
样例 1
输入
abbccd
输出
2
样例 2
输入
aaaa
输出
1
样例 3
输入
abac
输出
4
算法
合法性只取决于相邻字符。每个满足 $s_i=s_{i-1}$ 的位置都会形成一道不能跨越的分界：任何跨过它的子串均不合法。反之，相邻两道分界之间的整段中，相邻字符全部不同，整段本身合法。
从左到右扫描，维护当前合法段的左端点 start。若当前字符和前一字符相同，就令当前字符成为新段起点；随后用当前段长度更新答案。
正确性证明
把所有相邻相同的位置称为分界。
- 任意跨过分界的子串都包含一对相同的相邻字符，因此一定不是神秘子串。
- 任意两个相邻分界之间（含字符串边界）的整段不存在相邻相同字符，因此整段是神秘子串。
- 由 1，任意神秘子串都完全位于某一段内；由 2，该段的最大合法长度就是整段长度。
算法恰好枚举这些段并取最长者，所以输出正确。
复杂度分析
- 时间复杂度：$O(\lvert s\rvert)$。
- 额外空间复杂度：$O(1)$（不计输入字符串）。
易错点
- “相邻字符不同”不等于“所有字符两两不同”，例如
abac整体合法。 - 单个字符没有相邻字符，天然合法，答案至少为 1。
- 遇到相邻相同时，新段起点是当前位置，而不是下一位置。
Python 代码
import sys
def main():
s = sys.stdin.readline().strip()
best = 1
start = 0
for i in range(1, len(s)):
if s[i] == s[i - 1]:
start = i
best = max(best, i - start + 1)
print(best)
if __name__ == "__main__":
main()
第 2 题：分拣站缓冲道装车
题目描述
有 $n$ 个包裹依次到达，第 $i$ 个到达的包裹目的地编号为 $a_i$。序列 $a$ 是 $1,2,\ldots,n$ 的一个排列。所有包裹必须按编号 $1,2,\ldots,n$ 的顺序装车。
缓冲道是一个栈。每次可以：
I（In）：把下一个到达的包裹压入缓冲道；O（Out）：把缓冲道栈顶包裹弹出并装车。
判断能否得到要求的装车顺序。若能，输出操作序列；否则输出 N。合法操作串恰有 $n$ 个 I 和 $n$ 个 O。题面说明可行时操作序列唯一。
输入描述
第一行输入正整数 $n$。
第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，保证它们是 $1$ 到 $n$ 的排列。
输出描述
若存在合法方案，输出由 I、O 组成的操作串；否则输出 N。
可恢复约束
- $n$ 为正整数。
- $a$ 是 $1,2,\ldots,n$ 的排列。
- 合法操作串长度为 $2n$。
- 原页面中 $n$ 的数值上界未能可靠恢复，不补写猜测值。
样例
输入
3
2 1 3
输出
IIOOIO
算法
维护栈 stack 和下一个必须装车的编号 need，初值为 1。
依次处理到达包裹：
- 将当前包裹压栈并记录
I。 - 只要栈顶等于
need，立刻弹栈、记录O，并令need += 1。 - 全部包裹处理后，如果栈不空则无解，否则输出操作串。
正确性证明
考虑任意时刻：
- 若栈顶不等于
need，此时不能执行O，否则装车次序错误，只能继续执行I（如果仍有包裹）。 - 若栈顶等于
need，则必须立即执行O。若先压入后续包裹，need会被压住；压在它上面的包裹编号都大于need，在need发出前又不能弹出，于是再也无法完成。
因此每一步动作均被当前状态唯一决定，算法的贪心动作是任何合法方案都必须采取的动作。若最终栈为空，构造出的出栈序列恰为 $1,2,\ldots,n$；若最终仍有残留，则被迫动作已经无法继续，依据上述必要性，不存在其他合法方案。故算法正确。
复杂度分析
- 时间复杂度：$O(n)$，每个包裹恰好入栈一次、至多出栈一次。
- 空间复杂度：$O(n)$，包括栈与输出串。
易错点
I表示压栈，不是“直接装车”；每个包裹均需一次I和一次O。- 栈顶等于当前所需编号时必须持续弹出，不能只弹一次。
- 不要逐字符输出；先构造列表，最后一次性拼接。
- 输入如
2 3 1无解：弹出 1 后，3 压在 2 上方，2 无法先出。
Python 代码
import sys
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
arrival = data[1:1 + n]
stack = []
operations = []
need = 1
for package in arrival:
stack.append(package)
operations.append("I")
while stack and stack[-1] == need:
stack.pop()
operations.append("O")
need += 1
print("N" if stack else "".join(operations))
if __name__ == "__main__":
main()
第 3 题：货车加油最短耗时
题目描述
有 $n$ 座城市和 $m$ 条双向道路。每条道路由四个整数 $(u,v,c,t)$ 描述：连接城市 $u,v$，通过道路消耗 $c$ 单位燃油并花费 $t$ 分钟。
货车油箱容量为 $F$，从城市 1 出发时油箱已满，即初始油量为 $F$。在城市 $i$ 每加 1 单位燃油需要 $p_i$ 分钟，油量不能超过 $F$。求从城市 1 到城市 $n$ 的最短总时间；无法到达则输出 -1。
输入描述
- 第一行：三个整数 $n,m,F$。
- 第二行：$n$ 个整数 $p_1,p_2,\ldots,p_n$。
- 接下来 $m$ 行：每行四个整数 $u,v,c,t$，表示一条双向道路。
输出描述
输出最短时间；无法到达输出 -1。
可恢复约束
- 道路为双向道路。
- 油量与道路耗油均按整数单位计；油量状态为 $0,1,\ldots,F$。
- 道路通行时间和加油时间为非负量，满足 Dijkstra 的使用条件。
- 题解文字说明状态规模可到约 $10^5$ 量级。
- 原页面中的各变量精确上下界在 Markdown 抽取时丢失，无法可靠恢复。
样例 1
输入
3 3 3
2 3 5
1 2 1 10
1 3 1 100
2 3 3 1
输出
14
解释：从 1 到 2 花 10 分钟并消耗 1 单位油；在城市 2 加 1 单位油花 3 分钟；再到城市 3 花 1 分钟，总计 14 分钟。
样例 2
输入
2 1 5
1 10
1 2 10 5
输出
-1
算法：分层图 + Dijkstra
只记录城市不足以描述后续选择，因为到达同一城市时剩余油量不同，可走的边不同。将状态定义为 $(u,f)$：货车位于城市 $u$，剩余 $f$ 单位油。
分层图中有两类有向转移：
- 加油：若 $f<F$，从 $(u,f)$ 到 $(u,f+1)$，代价 $p_u$。
- 行驶：对道路 $(u,v,c,t)$，若 $f\ge c$，从 $(u,f)$ 到 $(v,f-c)$，代价 $t$；反向同理。
从状态 $(1,F)$ 出发，在隐式分层图上运行 Dijkstra。首次从堆中取出城市 $n$ 的任意油量状态时，其距离就是答案。
源代码曾把 (距离, 状态) 打包到一个整数中，并固定使用 17 位保存状态。这隐含要求状态编号小于 $2^{17}$；由于可靠约束缺失且题解只说状态可达 $10^5$ 量级，边界变化会造成截断风险。下面独立实现使用标准 (distance, state) 元组堆，不依赖位宽假设。
正确性证明
引理 1：每条实际行程都对应分层图中一条同代价路径。
每加一单位油对应一条加油边；每经过一条道路对应一条行驶边。容量约束由 $f<F$ 保证，油量足够条件由 $f\ge c$ 保证，因此状态油量与实际油量始终一致，累计边权也等于总耗时。
引理 2：分层图中每条路径都对应一条合法实际行程。
加油边只会在未满时增加一单位油，行驶边只会在油量足够时消耗相应燃油；故逐边执行即可得到合法行程，且耗时相同。
定理：算法返回最短总时间。
由两个引理，实际方案与分层图路径在可行性和代价上等价。所有转移权重非负，Dijkstra 能求出从 $(1,F)$ 到各状态的最短距离。终点允许任意剩余油量，因此所有 $(n,f)$ 中的最小距离就是答案；Dijkstra 首次弹出的终点状态具有该最小距离。若没有终点状态可达，则实际也无法到达，输出 -1 正确。
复杂度分析
令状态数 $V’=n(F+1)$。隐式分层图至多包含 $nF$ 条加油转移和 $2m(F+1)$ 次道路转移检查。
- 时间复杂度：$O((nF+mF)\log(nF))$，也可写作 $O(F(n+m)\log(nF))$。
- 空间复杂度：$O(nF+m)$，分别用于距离数组、堆和原图邻接表。
易错点
- 初始油量是满箱 $F$，不是 0。
- 道路是双向的，邻接表要加入两个方向。
- 加油要允许加任意单位数，拆成反复“加 1”才能完整枚举。
- 耗油量大于容量的道路永远不能通过，但无需特判，状态转移自然会跳过。
- 堆中会存在过期条目，弹出后必须和
dist比较。 - 不要用固定 17-bit 或其他未经约束证明安全的位打包；元组堆更稳妥。
Python 代码
import heapq
import sys
def main():
input = sys.stdin.buffer.readline
n, m, capacity = map(int, input().split())
refuel_time = list(map(int, input().split()))
graph = [[] for _ in range(n)]
for _ in range(m):
u, v, fuel_cost, travel_time = map(int, input().split())
u -= 1
v -= 1
graph[u].append((v, fuel_cost, travel_time))
graph[v].append((u, fuel_cost, travel_time))
width = capacity + 1
state_count = n * width
infinity = float("inf")
dist = [infinity] * state_count
start = capacity # (city 0, full tank)
dist[start] = 0
heap = [(0, start)]
while heap:
current_time, state = heapq.heappop(heap)
if current_time != dist[state]:
continue
city, fuel = divmod(state, width)
if city == n - 1:
print(current_time)
return
if fuel < capacity:
next_state = state + 1
next_time = current_time + refuel_time[city]
if next_time < dist[next_state]:
dist[next_state] = next_time
heapq.heappush(heap, (next_time, next_state))
for next_city, fuel_cost, travel_time in graph[city]:
if fuel_cost > fuel:
continue
next_state = next_city * width + fuel - fuel_cost
next_time = current_time + travel_time
if next_time < dist[next_state]:
dist[next_state] = next_time
heapq.heappush(heap, (next_time, next_state))
print(-1)
if __name__ == "__main__":
main()
第 4 题：饮品店预留试做时段
题目描述
有 $n$ 位预约顾客，营业时间被划分为 $n+1$ 个整数编号时段 $1,2,\ldots,n+1$。第 $i$ 位顾客能接受闭区间 $[l_i,r_i]$ 中任意一个时段。每位顾客必须恰好安排一次，同一时段至多接待一位顾客。
对每个时段 $x$ 独立判断：若要求时段 $x$ 不接待任何顾客，是否仍能安排全部顾客？不同 $x$ 可以使用完全不同的安排方案。
输入描述
第一行输入整数 $n$。
接下来 $n$ 行，第 $i$ 行输入两个整数 $l_i,r_i$。
本题只有一组测试数据。
输出描述
输出长度为 $n+1$ 的 01 串。第 $x$ 个字符为 1 当且仅当预留时段 $x$ 后仍存在合法安排，否则为 0。
可恢复约束
- 顾客数为 $n$，时段数恰为 $n+1$。
- $1\le l_i\le r_i\le n+1$。
- 每位顾客的可选时段是连续闭区间。
- 只有一组测试数据。
- 原页面中 $n$ 的精确上界未能可靠恢复；题解目标复杂度为近线性，不能据此反推并编造上界。
样例 1
输入
2
1 3
2 2
输出
101
样例 2
输入
2
1 2
2 3
输出
111
样例 3
输入
3
1 1
1 2
1 2
输出
0000
算法审查：先暴力对拍
在采用近线性算法前，先独立实现小规模基准：对每个待预留时段删掉该点，再用增广路二分图匹配判断所有顾客能否匹配。将优化算法与基准在所有/大量小实例上比较。
审查结果：
- $n=1,2,3,4$：分别穷举 3、36、1000、50625 个有序区间组，全部一致；
- $n=5,6$：各检查 200000 个有序区间组，全部一致；
- 三个给定样例均与预期一致。
对拍只用于验证，不进入提交代码。
算法：霍尔判据 + 扫描线
令
\[C(a,b)=\#\{i\mid a\le l_i\le r_i\le b\},\]即接受区间被 $[a,b]$ 完全包含的顾客数。区间到点的匹配满足：原问题可行，当且仅当对每个连续时段区间 $[a,b]$，都有
\[C(a,b)\le b-a+1.\]这是霍尔条件在区间邻域上的形式。若预留点 $x$，任何包含 $x$ 的区间可用点数少 1，因此：
- 若存在 $C(a,b)>b-a+1$，原问题已经不可行，所有答案都是
0； - 在原问题可行时，把满足 $C(a,b)=b-a+1$ 的区间称为紧区间。预留 $x$ 可行，当且仅当 $x$ 不属于任何紧区间。
问题转为求所有紧区间的并。
扫描公式
按右端点 $b=1,2,\ldots,n+1$ 扫描。定义
\[P_b(t)=t-\#\{i\mid r_i\le b,\ l_i\le t\}.\]对 $t=a-1$ 有
\[(b-a+1)-C(a,b)=P_b(b)-P_b(a-1).\]因此固定 $b$ 后，所有区间的最小剩余容量为
\[P_b(b)-\max_{0\le t<b}P_b(t).\]该值小于 0 说明全局无解；等于 0 说明存在以 $b$ 为右端点的紧区间。若最大值最左取到位置为 $t_0$，那么这些紧区间在本轮的并就是 $[t_0+1,b]$，用差分数组标记。
维护最大值
扫描推进时，新位置 $t=b-1$ 加入候选。所有满足 $r_i=b$ 的顾客会使 $P_b(t)$ 在后缀 $[l_i,n+1]$ 上减 1。
代码用一条链维护“严格前缀最大值记录”。相邻记录值之差 delta 为正。一次后缀减一只会影响第一个落入后缀的有效记录与其前驱的差；若差降到 0，该记录不再严格，便从链中删除。并查集维护“当前位置及其右侧第一个仍有效记录”，从而跳过已删除位置。每个位置至多加入和删除一次。
正确性证明
引理 1（区间霍尔判据）：全部顾客可安排，当且仅当任意 $[a,b]$ 中被完全包含的顾客数不超过区间长度。
必要性显然：这些顾客只能占用 $[a,b]$ 内的点。充分性来自霍尔定理；任意顾客子集的可选点之并可拆成若干不相交连续段，落在各段中的相关顾客分别受对应区间不等式约束，求和即可得到霍尔条件。
引理 2：原问题可行时，预留点 $x$ 后不可行，当且仅当 $x$ 被某个紧区间覆盖。
删除 $x$ 只会让包含 $x$ 的区间可用长度减 1。不包含 $x$ 的不等式不变。原本有至少 1 余量的区间删除后仍满足不等式；原本等号成立的紧区间若包含 $x$，删除后立即违反霍尔条件。故结论成立。
引理 3：固定右端点 $b$ 时，扫描公式正确给出最小余量；若最小余量为 0，算法标记段恰为本轮所有紧区间的并。
由公式，余量等于 $P_b(b)-P_b(a-1)$，取所有 $a$ 的最小值等价于减去所有 $t=a-1$ 中的最大 $P_b(t)$。等号成立的左端点对应所有最大值位置；取最左最大位置 $t_0$ 得到最长紧区间 $[t_0+1,b]$，它包含本轮其余紧区间，故该段正是本轮并集。
引理 4：记录链与并查集始终维护当前 $P_b$ 的严格前缀最大值位置及其最大值。
新位置仅在超过旧最大值时成为新记录。后缀统一减一时，后缀内部相邻记录之差不变，前缀内部也不变，只有后缀第一个有效记录与其前驱的差减少 1；差为 0 时它恰好失去“严格”性质并应删除。并查集只跳过永久失效的位置。因此维护不变量成立。
由引理 1 判断全局可行性，由引理 3、4 找出全部紧区间的并，再由引理 2 输出未被覆盖的位置，算法正确。
复杂度分析
令时段数 $m=n+1$。
- 时间复杂度：$O(n\alpha(n))$；每位顾客处理一次，每个记录至多删除一次，并查集路径压缩为反阿克曼复杂度。
- 空间复杂度：$O(n)$。
易错点
- 答案长度是 $n+1$，不是 $n$。
- 每个预留时段独立判断，不能沿用上一次的匹配方案。
- 若原问题已经违反霍尔条件，应直接输出全
0。 - 只有紧区间覆盖的位置不能预留；非紧区间即使包含该点，删除后仍有余量。
- 扫描时必须先加入 $t=b-1$，再处理所有 $r_i=b$ 的区间。
delta[k]降到 0 时记录必须从双向链和并查集结构中同时删除。
Python 代码
import sys
def find_alive(parent, position):
root = position
while parent[root] != root:
root = parent[root]
while parent[position] != root:
parent[position], position = root, parent[position]
return root
def main():
input = sys.stdin.buffer.readline
n = int(input())
slot_count = n + 1
left = [0] * (n + 1)
head = [0] * (slot_count + 2)
next_customer = [0] * (n + 1)
for customer in range(1, n + 1):
l, r = map(int, input().split())
left[customer] = l
next_customer[customer] = head[r]
head[r] = customer
parent = list(range(slot_count + 3))
delta = [0] * (slot_count + 2)
previous = [-1] * (slot_count + 2)
following = [-1] * (slot_count + 2)
difference = [0] * (slot_count + 3)
last_record = -1
maximum = 0
applied = 0
feasible = True
for right in range(1, slot_count + 1):
position = right - 1
value = position - applied
if last_record < 0 or value > maximum:
previous[position] = last_record
if last_record >= 0:
following[last_record] = position
delta[position] = value - maximum
following[position] = -1
last_record = position
maximum = value
else:
parent[position] = position + 1
customer = head[right]
while customer:
record = find_alive(parent, left[customer])
if record <= right - 1:
delta[record] -= 1
maximum -= 1
if delta[record] == 0:
before = previous[record]
after = following[record]
if after >= 0:
previous[after] = before
else:
last_record = before
if before >= 0:
following[before] = after
parent[record] = record + 1
applied += 1
customer = next_customer[customer]
minimum_slack = (right - applied) - maximum
if minimum_slack < 0:
feasible = False
break
if minimum_slack == 0:
difference[last_record + 1] += 1
difference[right + 1] -= 1
if not feasible:
print("0" * slot_count)
return
answer = []
cover = 0
for slot in range(1, slot_count + 1):
cover += difference[slot]
answer.append("0" if cover else "1")
print("".join(answer))
if __name__ == "__main__":
main()