大厂真题 / 拼多多

拼多多算法工程师 2026-10-18 笔试真题

本场考试概述

考试时间：2026 年 10 月 18 日

考试岗位：算法工程师

难度评级：中等

考点分析：

第一题：按中转城市拆分最优费用，哈希表聚合。
第二题：整数闭区间、离散事件与扫描线。
第三题：带结尾颜色状态的最长公共子序列。
第四题：迭代 DFS、子树区间与树状数组。

建议策略：先完成覆盖计数，再处理航线方向；动态规划先写清状态含义，树上询问先转化为子树求和。注意负权、闭区间右端点和链状树的递归深度。

第 1 题：至多一次中转的最低运费

题目描述

将一件包裹从城市 $S$ 运到城市 $T$。共有 $N$ 家物流公司，每家公司提供一条有方向的航线，航线中的城市按经过顺序给出，同一航线内城市不会重复。

使用一条航线时，可以从其中任意城市上货，在严格排在它后面的城市下货；不论运输距离多远，都支付该航线的固定费用 $C$。同一家公司的航线最多使用一次。包裹全程最多使用两条航线，即可以直达，也可以在某个城市换乘一次。求最低总费用，无可行方案则输出 -1。

输入描述

第一行输入 $S,T,N$。随后每条航线用两行表示：第一行输入固定费用 $C$ 和城市数 $M$，第二行输入按航行顺序排列的 $M$ 个城市编号。

数据范围：

$1\le S,T\le 10000$，$1\le N\le 1000$。
$1\le C,M\le 10000$，所有城市编号介于 $1$ 和 $10000$。
航线内城市互不相同；城市编号的数值大小不代表航行方向。

输出描述

输出最低运费，无法到达时输出 -1。

样例

输入

输出

第一条航线直达需要 4。先用第二条航线从 5 到 2，再用第三条从 2 到 3，费用为 $2+1=3$。

思路分析

第一步：用中转城市代替航线对。

枚举两家公司还需要检查它们是否存在方向正确的公共城市，重复工作很多。固定中转城市 $x$ 后，前半程只关心从 $S$ 到 $x$ 的最低单航线费用，后半程只关心从 $x$ 到 $T$ 的最低单航线费用。

分别用 from_s[x]、to_t[x] 保存这两个值。不存在的路径视为无穷大。另用 best 保存最低直达费用。

第二步：逐条航线更新。

找出 $S,T$ 在当前航线中的位置 $p_s,p_t$：

若二者存在且 $p_s<p_t$，当前航线可以直达。
若 $S$ 存在，$S$ 后面的每个城市都可作为第一程终点。
若 $T$ 存在，$T$ 前面的每个城市都可作为第二程起点。

每次用当前固定费用更新对应最小值。最后枚举两个字典共有的城市，比较两段费用之和。整个过程不需要保存全部航线。

第三步：说明为什么不用记录公司编号。

两个最小值可能来自同一家公司。此时该航线上必然依次出现 $S,x,T$，直接使用这条航线只需 $C$，而重复组合需要 $2C$。由于费用为正，直达方案严格更便宜，因此非法的重复组合不可能降低最终答案。

正确性证明

任意合法运输方案要么只用一条航线，要么经过某个中转城市。前者会在直达检查中被考虑；后者在对应城市处，两段分别取最小费用不会比该方案更贵。反过来，每个被记录的单程都满足城市顺序；两段属于不同公司时可以直接拼接，属于同一公司时有费用更低的合法直达方案替代。因此最终最小值恰为合法方案的最优值。

题解代码

import sys

input = sys.stdin.readline


def cheapest(s, t, routes):
    inf = float('inf')
    from_s = {}
    to_t = {}
    best = inf
    for cost, cities in routes:
        pos_s = pos_t = -1
        for i, city in enumerate(cities):
            if city == s:
                pos_s = i
            if city == t:
                pos_t = i
        if 0 <= pos_s < pos_t:
            best = min(best, cost)
        if pos_s >= 0:
            for i in range(pos_s + 1, len(cities)):
                city = cities[i]
                from_s[city] = min(from_s.get(city, inf), cost)
        if pos_t >= 0:
            for i in range(pos_t):
                city = cities[i]
                to_t[city] = min(to_t.get(city, inf), cost)
    for city, cost in from_s.items():
        best = min(best, cost + to_t.get(city, inf))
    return -1 if best == inf else best


def solve():
    s, t, n = map(int, input().split())

    def read_routes():
        for _ in range(n):
            cost, m = map(int, input().split())
            cities = list(map(int, input().split()))
            yield cost, cities

    print(cheapest(s, t, read_routes()))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：期望 $O(H+V)$，其中 $H=\sum M_i$，$V$ 为出现过的城市数。每条航线只扫描常数次，字典操作按均摊常数时间计。

空间复杂度：$O(V+M_{\max})$，保存两个费用字典和当前航线；生成器不会缓存所有航线。

易错点

必须按航线下标判断方向，不能仅判断两个城市是否同时出现。
费用按整条航线收取，不乘经过的边数。
本题按实际运输航段建模；若另行允许起终点相同且零次运输，应将该扩展情形的答案定义为 0，不要与至少经过一个有向航段混淆。

第 2 题：至少被申请 K 次的整数位置

题目描述

有 $N$ 个部门申请走廊区域。第 $i$ 个申请覆盖整数闭区间 $[L_i,R_i]$，包含左右端点。求被至少 $K$ 个申请同时覆盖的整数位置总数。统计的是整数坐标数量，而不是连续线段的几何长度。

输入描述

第一行输入 $N,K$；接下来 $N$ 行，每行输入一个申请的 $L_i,R_i$。

约束为 $1\le N\le 100000$，$1\le K\le 10^9$，$1\le L_i\le R_i\le 10^9$。

输出描述

输出满足覆盖次数要求的整数位置数量。

样例 1

输入

输出

整数位置 2 到 6 均被至少两个申请覆盖，共 5 个。

样例 2

输入

输出

三个申请覆盖了 1 到 9 的所有整数位置。

样例 3

输入

3
10
10

输出

只有两个申请，覆盖数不可能达到 3。

思路分析

第一步：把闭区间改成两个事件。

若对每个位置逐一计数，坐标达到 $10^9$ 时不可行。但覆盖数只在区间端点变化：在 $L_i$ 处加一，在 $R_i+1$ 处减一。减一必须放在右端点的下一格，否则会漏掉 $R_i$ 本身。

第二步：只扫描事件间的整段。

把全部事件按坐标排序。处理坐标 $x$ 前，变量 cover 表示从上一个事件坐标 previous 到 $x-1$ 的覆盖数。若它不少于 $K$，一次性将 $x-previous$ 加入答案，然后处理当前事件的增量。

同一坐标可能出现多个事件，逐个处理也没有问题：同坐标事件之间的长度为零；开始下一段时，该坐标全部增量已累加完成。

正确性证明

每个申请的加一事件恰好使它在 $L_i$ 开始生效，减一事件恰好使它在 $R_i+1$ 失效，所以事件增量的前缀和就是实际覆盖数。相邻不同事件坐标之间不存在变化，每段或者全部满足要求，或者全部不满足。算法统计所有达标段的整数长度，各段互不重叠且覆盖全部可能被申请的位置，因此结果正确。

题解代码

import sys

input = sys.stdin.readline


def count_hot(segments, k):
    events = []
    for left, right in segments:
        events.append((left, 1))
        events.append((right + 1, -1))
    events.sort()
    cover = answer = 0
    previous = events[0][0]
    for position, delta in events:
        if cover >= k:
            answer += position - previous
        cover += delta
        previous = position
    return answer


def solve():
    n, k = map(int, input().split())
    segments = (tuple(map(int, input().split())) for _ in range(n))
    print(count_hot(segments, k))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(N\log N)$，排序 $2N$ 个事件后线性扫描。

空间复杂度：$O(N)$，存储事件及排序辅助空间。

易错点

$K>N$ 时答案自然为 0；单点区间 $L_i=R_i$ 仍贡献一个整数位置。不能把答案写成所有达标闭区间端点差的简单相加。

第 3 题：将两条彩灯带删成相同交替序列

题目描述

两条彩灯带分别由字符串 $S,T$ 表示，每个字符为 R、G、B 中的一种。一次操作可以从任意一条灯带删除一盏灯，剩余灯按原顺序重新连接。

要求最终两条灯带完全相同，并且相邻灯的颜色不同。求两条灯带合计最少删除多少盏灯。可以保留空序列；“交替”仅要求相邻不同，不要求严格重复 RGB 或仅使用两种颜色。

输入描述

第一行输入 $S$，第二行输入 $T$。两串仅含大写字母 R、G、B，且 $1\le\lvert S\rvert,\lvert T\rvert\le 2000$。

输出描述

输出最少删除总数。

样例 1

输入

RRGG
RGRG

输出

两串均可留下 RG，各删除两盏。第一串无法形成长度大于 2 的相邻异色子序列。

样例 2

输入

RGB
RGB

输出

思路分析

第一步：把最少删除转成最长保留。

若最终公共序列长度为 $L$，删除数为

\[\lvert S\rvert+\lvert T\rvert-2L.\]

因此要找相邻颜色不同的最长公共子序列。普通 LCS 只记长度，不知道能否继续接某种颜色，需要增加“末尾颜色”状态。

第二步：定义状态并转移。

令 $f[i][j][c]$ 表示从两串长度分别为 $i,j$ 的前缀中，能得到的以颜色 $c$ 结尾的合法公共子序列最大长度；没有这种非空序列时记为 0，作为启动新序列的哨兵。

跳过一边末尾字符时：

\[f[i][j][c]=\max(f[i-1][j][c],f[i][j-1][c]).\]

如果 $S_{i-1}=T_{j-1}=c$，还可以选择这对字符：

\[f[i][j][c]=\max\left(f[i][j][c],1+\max_{d\ne c}f[i-1][j-1][d]\right).\]

最后一项为 1 时表示从单个字符开始，并不意味着空串真的具有末尾颜色。最终 $L$ 是三种颜色状态的最大值。

第三步：只更新当前字符对应的颜色行。

处理 $S$ 的一个新字符 ch 时，若一个公共子序列不以 ch 结尾，就不可能使用这个新位置，因而其他两种颜色的整行保持不变。只需为 ch 新建一行，同时从旧行、当前新行左侧、另外两种颜色旧行的左上角转移。不能提前覆盖另外两行，也不能从当前新行接同色。

把较短的字符串作为列方向，可将空间缩至较短串长度。

正确性证明

考虑任意最优合法公共子序列。若它未同时使用两个前缀的末尾位置，则至少有一边的末尾可以跳过，由上方或左方状态覆盖。若它使用了这两个位置，则字符必须相同，去掉末尾后得到一个末尾颜色不同的合法公共子序列，属于左上角的另外两种颜色状态。两类情况覆盖所有可能；每条转移也只跳过字符或接上异色的相同字符，因此不会产生非法序列。按前缀长度归纳，所有状态与最终答案正确。

题解代码

import sys

input = sys.stdin.readline


def min_deletions(s, t):
    if len(s) < len(t):
        s, t = t, s
    m = len(t)
    rows = {color: [0] * (m + 1) for color in 'RGB'}
    for color in s:
        other_colors = [c for c in 'RGB' if c != color]
        other_a = rows[other_colors[0]]
        other_b = rows[other_colors[1]]
        old = rows[color]
        new = [0] * (m + 1)
        for j in range(1, m + 1):
            best = max(old[j], new[j - 1])
            if t[j - 1] == color:
                best = max(best, 1 + max(other_a[j - 1], other_b[j - 1]))
            new[j] = best
        rows[color] = new
    length = max(row[m] for row in rows.values())
    return len(s) + len(t) - 2 * length


def solve():
    s = input().strip()
    t = input().strip()
    print(min_deletions(s, t))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(\lvert S\rvert\cdot\lvert T\rvert)$，每对前缀位置只进行常数次比较。

空间复杂度：辅助空间 $O(\min(\lvert S\rvert,\lvert T\rvert))$；若计入两个输入字符串，总空间为 $O(\lvert S\rvert+\lvert T\rvert)$。

易错点

公共子序列不要求连续；不能先求普通 LCS 再删除重复颜色，因为某一条普通 LCS 不一定包含最优的交替公共子序列。两串没有公共颜色时 $L=0$，需全部删除。

第 4 题：动态点权树的断边乘积询问

题目描述

给定一棵有 $N$ 个节点、$N-1$ 条边的树，节点编号为 $1$ 到 $N$，初始点权为 $a_i$。依次处理 $Q$ 次操作：

1 u x：将节点 $u$ 的点权增加 $x$，允许负增量。
2 u v：对树中已有边 $(u,v)$ 进行假想断开，求两部分点权和的乘积。含节点 1 的部分记为 $A$，另一部分记为 $B$。

询问不会真的删除边，也不会影响后续操作。每个乘积对 $P=10^9+7$ 取模，输出 $[0,P-1]$ 内的非负余数。

输入描述

第一行输入 $N,Q$；第二行输入 $N$ 个初始点权；接下来 $N-1$ 行输入边的两个端点；最后 $Q$ 行输入上述操作。

约束为：

$2\le N,Q\le 2\times10^5$。
$\lvert a_i\rvert\le10^6$，修改量 $\lvert x\rvert\le10^5$。
节点编号在 $[1,N]$ 内，询问的两个端点构成树中的一条边。

输出描述

每次类型 2 操作输出一行乘积的非负余数。

样例 1

输入

输出

6
6
4

三次断边分别得到大小为 2 与 3、3 与 2、4 与 1 的两部分，所有点权均为 1。

样例 2

输入

输出

9
309

第一次两部分点权和均为 3。节点 2 增加 100 后，两部分点权和为 103 和 3，乘积为 309。

思路分析

第一步：将断边对应到一个子树。

以节点 1 为根。边的两个端点必定是父子关系，设子节点为 $w$。断开后，不含根的一侧恰为 $w$ 的整棵子树。若其权值和为 $b$，全树权值和为 total，答案就是

\[b\cdot(\mathrm{total}-b)\bmod P.\]

逐次遍历子树最坏需要 $O(NQ)$；每次修改向所有祖先更新子树和也会在链状树上退化。

第二步：用 DFS 序把子树压成区间。

首次访问节点时分配编号 tin[u]。DFS 会连续处理完一个节点的全部后代，因此子树大小为 size[u] 时，其区间为

\[[\mathrm{tin}[u],\mathrm{tin}[u]+\mathrm{size}[u]-1].\]

实现采用显式栈得到 DFS 先序，避免长链导致递归栈溢出；再逆序遍历，把每个节点的大小累加到父节点。注意先序必须来自深度优先遍历，不能换成 BFS 序。

第三步：树状数组维护点加与区间和。

将点权放到 DFS 编号位置，树状数组支持单点增加和前缀求和。子树和等于两个前缀和之差，同时维护全树总和。初始树状数组可直接由 DFS 序权值数组线性构建。

正确性证明

树中每条边连接一个节点及其父节点，因此断边隔离的恰是子节点的全部后代。DFS 先序的连续性保证算法查询的区间与该子树节点集合完全相同。树状数组初始保存准确点权，每次修改只改变目标位置并同步总和，故归纳可知每次询问时子树和与全树和均准确。将两部分权值和相乘再取模，即得到题意要求的结果。

题解代码

import sys

input = sys.stdin.readline


def process_tree(weights, edges, operations):
    n = len(weights) - 1
    graph = [[] for _ in range(n + 1)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    parent = [0] * (n + 1)
    tin = [0] * (n + 1)
    order = []
    stack = [1]
    while stack:
        u = stack.pop()
        tin[u] = len(order) + 1
        order.append(u)
        for v in graph[u]:
            if v != parent[u]:
                parent[v] = u
                stack.append(v)
    size = [1] * (n + 1)
    for u in reversed(order):
        if parent[u]:
            size[parent[u]] += size[u]
    bit = [0] + [weights[u] for u in order]
    for i in range(1, n + 1):
        j = i + (i & -i)
        if j <= n:
            bit[j] += bit[i]

    def add(i, delta):
        while i <= n:
            bit[i] += delta
            i += i & -i

    def prefix(i):
        result = 0
        while i:
            result += bit[i]
            i -= i & -i
        return result

    total = sum(weights)
    mod = 10**9 + 7
    for kind, u, value in operations:
        if kind == 1:
            add(tin[u], value)
            total += value
        else:
            v = value
            child = u if parent[u] == v else v
            left = tin[child]
            right = left + size[child] - 1
            subtree = prefix(right) - prefix(left - 1)
            yield (subtree % mod) * ((total - subtree) % mod) % mod


def solve():
    n, q = map(int, input().split())
    weights = [0] + list(map(int, input().split()))
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    operations = (tuple(map(int, input().split())) for _ in range(q))
    for answer in process_tree(weights, edges, operations):
        print(answer)


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(N+Q\log N)$。DFS 与线性建树为 $O(N)$，每次操作使用常数次树状数组操作。

空间复杂度：$O(N)$。邻接表、DFS 序、父节点、子树大小、栈和树状数组均为线性大小，操作与答案逐条处理。

易错点

更新是增加而不是赋值；边的输入顺序不代表父子关系；负点权可能使乘积为负，但 Python 对正模数的 % 已返回非负余数。询问不改变树的结构。

小结

航线问题用中转点连接两组局部最优，避免枚举公司对。
大坐标覆盖问题只处理发生变化的事件，不按坐标开数组。
相邻约束可以通过记录序列末尾状态嵌入 LCS。
动态子树统计先建立 DFS 区间，再复用序列数据结构。

这篇文章有帮助吗？

| GitHub 留言