大厂真题 / 拼多多

拼多多 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. 任意两个相邻分界之间（含字符串边界）的整段不存在相邻相同字符，因此整段是神秘子串。
3. 由 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。

依次处理到达包裹：

1. 将当前包裹压栈并记录 I。
2. 只要栈顶等于 need，立刻弹栈、记录 O，并令 need += 1。
3. 全部包裹处理后，如果栈不空则无解，否则输出操作串。

正确性证明

考虑任意时刻：

• 若栈顶不等于 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$ 单位油。

分层图中有两类有向转移：

1. 加油：若 $f<F$，从 $(u,f)$ 到 $(u,f+1)$，代价 $p_u$。
2. 行驶：对道路 $(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 个有序区间组，全部一致；
• 三个给定样例均与预期一致。

对拍只用于验证，不进入提交代码。

算法：霍尔判据 + 扫描线

令

即接受区间被 $[a,b]$ 完全包含的顾客数。区间到点的匹配满足：原问题可行，当且仅当对每个连续时段区间 $[a,b]$，都有

这是霍尔条件在区间邻域上的形式。若预留点 $x$，任何包含 $x$ 的区间可用点数少 1，因此：

• 若存在 $C(a,b)>b-a+1$，原问题已经不可行，所有答案都是 0；
• 在原问题可行时，把满足 $C(a,b)=b-a+1$ 的区间称为紧区间。预留 $x$ 可行，当且仅当 $x$ 不属于任何紧区间。

问题转为求所有紧区间的并。

扫描公式

按右端点 $b=1,2,\ldots,n+1$ 扫描。定义

对 $t=a-1$ 有

因此固定 $b$ 后，所有区间的最小剩余容量为

该值小于 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()