大厂真题 / 拼多多

拼多多 4.26 笔试真题

本场考试概述

考试时间：2026年4月26日 考试岗位：通用 难度评级：中等偏难

考点分析：

第一题：二维费用背包（难度中等）
第二题：贪心 + 二分查找（难度中等）
第三题：BFS 坐标重建（难度中等）
第四题：二分答案 + 树上贪心（难度困难）

建议策略：

前三题属于经典模型题，建议优先拿下，重点在于快速建模和实现
第四题是二分答案套树上贪心的组合技，平时需要多练习树形 DP 和贪心的结合

第一题：多多的Token

题目描述

$n$ 个任务，每个可以不执行、以常规模式执行（花费 $a_i$ token + $b_i$ 时间）或以降耗模式执行（花费 $c_i$ token + $d_i$ 时间）。总 token 预算 $m$，总时间预算 $t$。求最多完成多少个任务。

$n \leq 100$，$m \leq 200$，$t \leq 200$。

样例

输入

输出

思路分析

第一步：识别二维费用背包

每个任务独立三选一（不做/常规/降耗），同时受 token 和时间两种资源约束。这是经典的二维费用背包。

第二步：状态定义

$f[j][k]$ = 恰好使用 $j$ 个 token、完成恰好 $k$ 个任务所需的最小时间。我们把 token 和任务数作为下标，最小化时间，最后检查时间是否 $\leq t$。

第三步：转移与答案

对每个任务，逆序枚举 $j$ 和 $k$（01 背包性质），尝试常规模式和降耗模式两种选择。最终从 $k = n$ 到 $0$ 逆序扫描，找到第一个存在 $j$ 使得 $f[j][k] \leq t$ 的 $k$。

题解代码

import sys
input = sys.stdin.readline

n, m, t = map(int, input().split())
tasks = []
for _ in range(n):
    a, b, c, d = map(int, input().split())
    tasks.append((a, b, c, d))

INF = 10 ** 9
f = [[INF] * (n + 1) for _ in range(m + 1)]
f[0][0] = 0

for a, b, c, d in tasks:
    for j in range(m, -1, -1):
        for k in range(n, 0, -1):
            if j >= a:
                f[j][k] = min(f[j][k], f[j - a][k - 1] + b)
            if j >= c:
                f[j][k] = min(f[j][k], f[j - c][k - 1] + d)

ans = 0
for k in range(n, -1, -1):
    for j in range(m + 1):
        if f[j][k] <= t:
            ans = k
            break
    if ans > 0:
        break

print(ans)

复杂度分析

时间复杂度：$O(n^2 \times m)$，外层遍历 $n$ 个任务，内层枚举 $m$ 种 token 用量和至多 $n$ 种任务数。 空间复杂度：$O(n \times m)$，DP 数组。

第二题：多多的推荐位

题目描述

$n$ 条内容各有可接受热度范围 $[l_i, r_i]$，$m$ 个推荐位各有热度值 $h_j$。每个推荐位最多放一条内容，每条内容最多占一个推荐位。求最多匹配多少条内容。

多组测试数据，$n, m \leq 10^5$。

样例

输入

输出

思路分析

第一步：贪心策略

$r_i$ 越小的内容可选余地越小，应优先处理。对每条内容，选尽可能小的可用推荐位，为后续内容保留更大的推荐位。

第二步：排序 + 线段树

将所有内容按 $r_i$ 升序排列，推荐位坐标压缩后用线段树维护。对当前内容 $[l_i, r_i]$，在线段树中查询 $[l_i, r_i]$ 范围内最小的可用推荐位。找到则匹配并移除。

第三步：正确性（交换论证）

假设某个最优解中，$r$ 较小的内容匹配了较大推荐位，$r$ 较大的内容匹配了较小推荐位。由于 $r$ 较大的内容对推荐位的约束更宽松，交换后仍合法，匹配数不变。

题解代码

import sys
from bisect import bisect_left
input = sys.stdin.readline

class SegTree:
    def __init__(self, n):
        self.n = n
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.tree = [0] * (2 * self.size)

    def update(self, pos, val):
        pos += self.size
        self.tree[pos] += val
        pos >>= 1
        while pos >= 1:
            self.tree[pos] = self.tree[2 * pos] + self.tree[2 * pos + 1]
            pos >>= 1

    def query_first(self, ql, qr, node=1, lo=0, hi=None):
        if hi is None:
            hi = self.size - 1
        if lo > qr or hi < ql or self.tree[node] == 0:
            return -1
        if lo == hi:
            return lo
        mid = (lo + hi) // 2
        left = self.query_first(ql, qr, 2 * node, lo, mid)
        if left != -1:
            return left
        return self.query_first(ql, qr, 2 * node + 1, mid + 1, hi)

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    contents = []
    for i in range(n):
        l, r = map(int, input().split())
        contents.append((r, l))
    slots = list(map(int, input().split()))

    all_vals = sorted(set(slots))
    val_to_idx = {v: i for i, v in enumerate(all_vals)}
    M_size = len(all_vals)

    seg = SegTree(M_size)
    for s in slots:
        seg.update(val_to_idx[s], 1)

    contents.sort()
    ans = 0
    for r, l in contents:
        lo = bisect_left(all_vals, l)
        hi = bisect_left(all_vals, r + 1) - 1
        if lo > hi or lo >= M_size:
            continue
        idx = seg.query_first(lo, min(hi, M_size - 1))
        if idx != -1:
            seg.update(idx, -1)
            ans += 1

    print(ans)

复杂度分析

时间复杂度：$O((n + m) \log m)$，排序 $O(n \log n)$，每个推荐位至多入/出线段树一次，每次 $O(\log m)$。 空间复杂度：$O(m)$，线段树大小。

第三题：多多玩拼图

题目描述

$n \times m$ 的拼图，碎片编号 $1$ 到 $n \times m$。给出 $K$ 条方向邻接关系：a b d 表示碎片 $a$ 在碎片 $b$ 的 $d$ 方向（U/B/L/R 分别为上/下/左/右）。保证连通且无矛盾，还原完整矩阵。

样例

输入

2
4
3 U
4 R
1 L
2 L

输出

4 1
3 2

思路分析

第一步：方向映射为坐标偏移

每条关系 a b d（$a$ 在 $b$ 的 $d$ 方向）确定了从 $b$ 到 $a$ 的坐标偏移：

U（$a$ 在上）：$a$ 行号比 $b$ 小 → 从 $b$ 看 $a$ 偏移 $(-1, 0)$
B（$a$ 在下）：偏移 $(+1, 0)$
L（$a$ 在左）：偏移 $(0, -1)$
R（$a$ 在右）：偏移 $(0, +1)$

同时建反向边，偏移取反。

第二步：BFS 分配坐标

任取一个碎片作为起点，坐标设为 $(0, 0)$。BFS 遍历所有碎片，用偏移量计算每个碎片的绝对坐标。

第三步：归一化输出

BFS 结束后将最小行和最小列平移至 $(0, 0)$，填入矩阵按行输出。

题解代码

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
k = int(input())
total = n * m

from_a = {'U': (1, 0), 'B': (-1, 0), 'L': (0, 1), 'R': (0, -1)}
from_b = {'U': (-1, 0), 'B': (1, 0), 'L': (0, -1), 'R': (0, 1)}

adj = [[] for _ in range(total + 1)]
first = 0
for _ in range(k):
    parts = input().split()
    a, b, d = int(parts[0]), int(parts[1]), parts[2]
    if first == 0:
        first = a
    dr1, dc1 = from_a[d]
    adj[a].append((b, dr1, dc1))
    dr2, dc2 = from_b[d]
    adj[b].append((a, dr2, dc2))

row = [0] * (total + 1)
col = [0] * (total + 1)
visited = [False] * (total + 1)
visited[first] = True
queue = deque([first])

while queue:
    u = queue.popleft()
    for v, dr, dc in adj[u]:
        if not visited[v]:
            visited[v] = True
            row[v] = row[u] + dr
            col[v] = col[u] + dc
            queue.append(v)

min_r = min(row[i] for i in range(1, total + 1))
min_c = min(col[i] for i in range(1, total + 1))

grid = [[0] * m for _ in range(n)]
for i in range(1, total + 1):
    grid[row[i] - min_r][col[i] - min_c] = i

for i in range(n):
    print(' '.join(map(str, grid[i])))

复杂度分析

时间复杂度：$O(n \times m + K)$，建图 $O(K)$，BFS $O(n \times m)$。 空间复杂度：$O(n \times m + K)$，邻接表和结果矩阵。

第四题：多多的审批链

题目描述

以 1 号节点为根的 $n$ 节点树，选至多 $k$ 个关键审批节点。节点 $v$ 被覆盖当且仅当 $v$ 向上走不超过 $D$ 条边能到达某关键节点。求最小的 $D$ 使得所有节点都被覆盖。

多组测试数据，$n \leq 10^5$。

样例

输入

1
7 2
1 1 2 2 3 3

输出

思路分析

第一步：二分答案

$D$ 越大覆盖越容易，具有单调性。存在一个最小临界值，可以二分。二分区间为 $[0, n-1]$。

第二步：check 函数——树上贪心

给定 $D$，用后序遍历贪心计算最少需要多少个关键节点。

对每个节点 $u$ 维护 $\text{max_dist}[u]$：子树中距离 $u$ 最远的未覆盖后代有多远。叶节点初始值为 0。

后序遍历时，$u$ 从子节点收集信息：$\text{max_dist}[u] = \max(\text{max_dist}[c] + 1)$。若 $\text{max_dist}[u] \geq D$，说明再往上传就超出覆盖范围，必须在 $u$ 放置关键节点，将其置为 $-1$ 表示已覆盖。

根节点特殊处理：若遍历结束后 $\text{max_dist}[1] \geq 0$，必须额外放一个。

第三步：二分过程

若 $\text{check}(D) \leq k$ 则 $D$ 够用，尝试更小；否则 $D$ 太小。

题解代码

import sys
input = sys.stdin.readline

def check(D, n, children):
    count = 0
    max_dist = [0] * (n + 1)
    order = []
    stk = [1]
    while stk:
        u = stk.pop()
        order.append(u)
        for c in children[u]:
            stk.append(c)
    for u in reversed(order):
        md = 0
        for c in children[u]:
            if max_dist[c] >= 0:
                md = max(md, max_dist[c] + 1)
        if md >= D:
            count += 1
            max_dist[u] = -1
        else:
            max_dist[u] = md
    if max_dist[1] >= 0:
        count += 1
    return count

T = int(input())
for _ in range(T):
    n, k = map(int, input().split())
    children = [[] for _ in range(n + 1)]
    if n > 1:
        parents = list(map(int, input().split()))
        for i, p in enumerate(parents, 2):
            children[p].append(i)
    lo, hi = 0, n - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid, n, children) <= k:
            hi = mid
        else:
            lo = mid + 1
    print(lo)

复杂度分析

时间复杂度：$O(n \log n)$，二分 $O(\log n)$ 轮，每轮后序遍历 $O(n)$。 空间复杂度：$O(n)$，存储树结构和遍历用的临时数组。

小结

第一题是二维费用背包，以 token 和任务数为下标、最小化时间，最后验证时间约束
第二题的贪心关键是按右端点排序后优先匹配最小可用推荐位，线段树支持高效的区间最左查询
第三题利用方向关系建图后 BFS 分配坐标，归一化后填入矩阵即可还原拼图
第四题是经典的”二分答案 + 树上贪心”组合——二分覆盖距离 $D$，check 函数用后序遍历贪心放置关键节点

这篇文章有帮助吗？

| GitHub 留言