大厂真题 / pinduoduo

拼多多 2026-9-6 笔试真题 - 技术岗

证据边界：本文依据公开题解材料整理。原文中部分数学公式在网页抽取时以 SVG 形式保存，文本版无法可靠恢复的变量、约束或表达式不擅自补写；题面与答案应以实际考试页面为准。

本场考试概述

考试时间 ：2026-9-6 考试岗位 ：技术岗 难度评级 ：中等偏难 考点分析 ：第一题：模拟（简单）第二题：余数计数（简单）第三题：分层 Dijkstra（困难）第四题：二分图最大匹配（困难） 建议策略 ：难度是两易两难，区分度全在后两题。第一题想清楚每趟走到底再掉头不会更差就能写，第二题把”两数之和整除 “翻译成”两个余数互补”，开桶计数一遍过，这两题要稳稳拿下。第三题的难点不在 Dijkstra 本身，而在看出状态要额外带上已用传送次数与上一步是不是传送门；第四题代码只有一个匈牙利算法，吃功夫的是先证明最优对局下赢的场数恰好等于胜负图的最大匹配。两题都属于”想通了代码很短”的类型，建议先花时间在建模上。

第 1 题：传送带开箱最少转向次数

题目描述

假设从左往右的一条传送带上整齐的排列着个箱子，第个箱子需要至少把钥匙才能打开，机器人站在最左边箱子的位置不能移动，传送带一直在运行，初始的方向是向左运行，会带动箱子从左往右依次经过机器人。传送带运行过程中，机器人可以随时控制传送带的开关来改变传送带的方向，例如：向右运行，这样控制之前钥匙不够导致没打开的箱子重新经过机器人再打开。

输入描述

第一行输入数字，表示有组测试用例。对于每组测试用例有行：第行，输入数字，表示箱子的数量。第行，输入个数字，表示第个箱子打开需要的钥匙的数量。

输出描述

对于每组测试用例，输出一个数字，表示打开所有箱子机器人至少需要改变传送带方向的次数。如果无论如何都没有办法打开所有箱子，输出。

样例1

输入

输出

0
-1
1

样例解释 共组测试用例：第个测试用例，从左往右依次有个箱子，打开第个箱子需要把钥匙，直接打开就行，此时机器人会获得把钥匙；第个箱子需要把钥匙，机器人也可以打开。因此不需要改变方向，也就是改变次方向。第个测试用例，只有个箱子，需要把钥匙才能打开，所以无论如何无法打开，输出。第个测试用例，从左往右依次有个箱子，打开第个箱子需要把钥匙，直接打开，此时有了把钥匙；第个箱子需要把钥匙，此时无法打开；第个箱子需要把钥匙，可以打开，打开后有把钥匙了，再改变方向打开第个箱子。因此，输出表示改变了次方向。

题解：模拟（按趟扫描）

题目问题拆解

传送带把个箱子按当前方向依次送过机器人，钥匙够就自动开箱、开完多一把钥匙，问最少掉几次头才能全开，开不完输出。这是一道看着有决策、其实没有决策的模拟题：开箱是自动的，机器人只能决定何时掉头，难点在于说清一趟为什么扫到底就够、以及什么时候可以判死。

算法实现

先看一趟里发生了什么。尚未打开的箱子沿当前方向依次经过机器人，凡的当场被打开并让加一，这把新钥匙对同一趟里排在后面的箱子立刻生效。所以一趟顺着扫一遍就够，不必因为钥匙变多而回头重扫：错过的箱子会在下一趟被反向送回来。再看掉头时机。机器人拦不住任何一个条件已满足的箱子，每趟的开箱结果完全由进入这趟时的决定，唯一的自由度只有在哪掉头。提前掉头只会把本趟本可开的箱子推到更晚，而钥匙数一分不多，所以每趟走到底再掉头不会更差。判死看的是一整趟的产出。若某趟一个箱子都没开，没有变化，下一趟面对同一批箱子和同一个钥匙数，局面原地打转，输出；样例第二组的就是首趟即卡死。计数上要先判全开再判掉头，最后一趟开完人已不用再动，照例加一次转向就会多算。

时空复杂度分析

时间复杂度 ：。每趟要么至少多开一个箱子、要么当场判，故至多趟，每趟扫描；转向次数本身可达量级，趟数省不掉。 空间复杂度 ：，记录每个箱子是否已开。 Python

## 传送带开箱最少转向次数 - 模拟（按趟扫描）


def min_turns(n, a):
    """返回打开全部箱子所需的最少转向次数，无法全开返回 -1"""
    opened = [False] * n     # 每个箱子是否已经被打开
    left = n                 # 还没打开的箱子数量
    keys = 0                 # 机器人当前手上的钥匙数
    turns = 0                # 已经改变传送带方向的次数
    forward = True           # True 表示这一趟从左往右经过机器人

    while left > 0:
        gained = 0
        # 一趟里沿当前方向把所有箱子过一遍；本趟新拿到的钥匙对后面的箱子立即生效，
        # 所以顺着扫一遍就够，不用为"钥匙变多了"重扫
        order = range(n) if forward else range(n - 1, -1, -1)
        for i in order:
            if not opened[i] and a[i] <= keys:
                opened[i] = True
                keys += 1
                left -= 1
                gained += 1
        # 恰好在这一趟结束时全部开完，不需要再掉头，所以先判完成再判转向
        if left == 0:
            break
        # 整趟一个箱子都开不了，说明钥匙数已经卡死，再怎么来回都没用
        if gained == 0:
            return -1
        forward = not forward
        turns += 1

    return turns


## 多组测试数据，逐组读入并直接输出这一组的答案
T = int(input())
for _ in range(T):
    n = int(input())
    a = list(map(int, input().split()))
    print(min_turns(n, a))

第 2 题：盲盒免费配对方案数

题目描述

注意：盲盒虽然价值可能相同，但它们被视为不同的独立个体。也就是说，如果第个盲盒和第个盲盒被选中，这与第个和第个被选中是同一种方案（即不考虑顺序），但下标不同代表不同的方案。

输入描述

第一行包含两个整数，分别表示盲盒的数量和价值之和需要满足的倍数。第二行包含个整数，表示每个盲盒的价值，为非负整数。

输出描述

输出一个整数，表示能够免费拿走两个盲盒的方案总数。

样例1

输入

5 3
1 2 3 4 6

输出

样例解释 盲盒价值为，。下标从开始，即。满足价值之和为的倍数的组合有：下标，，是的倍数；下标，，是的倍数；下标，，是的倍数。共种。

样例2

输入

4 2
2 2 2 2

输出

样例解释 所有盲盒价值均为，。任意两个盲盒价值之和为，均为的倍数。从个盲盒中任选个的方案数为种。

题解：余数计数

题目问题拆解

从个数里挑出两个下标不同的数，要求两数之和是的倍数，问这样的无序对有多少个。这是一道把”看两个数的和”换成”看两个余数的和”的计数题：到，两两枚举是次比较，必须让同余的数抱成一团整批统计。

算法实现

先把判据落到余数上。等价于两个余数之和是的倍数，而余数各自落在，和至多到，能取到的倍数只有和两个值。于是配对条件写成，即：每个余数的搭档是唯一确定的另一个余数。搭档唯一，就只需要知道每种余数各有多少个。记答案随之分成三块。余数的数彼此相加就是的倍数，组内任取两个都成立，贡献；余数与余数是两个不同的桶，跨桶任配一对都成立，贡献；为偶数时余数的搭档还是它自己，得按组内配对算。合起来求和上界取是为了让每一对只被数一次，同时把自配的排除在循环外交给第三项，两处都不重不漏。答案的量级要留意。时全部个数余数都是，答案退化成，时约已经越过，四种语言一律用位整数承接。

时空复杂度分析

时间复杂度 ：。取模统计一遍，按余数扫一遍；瓶颈是读入这个数本身，任何做法都绕不开，故已是下界。 空间复杂度 ：，长度为的计数数组。 Python

## 盲盒免费配对方案数 - 余数计数

def count_pairs(m, a):
    # cnt[r] 记录价值除以 m 余 r 的盲盒有多少个，两个盲盒能配对当且仅当余数之和是 m 的倍数
    cnt = [0] * m
    for x in a:
        cnt[x % m] += 1
    # 余数 0 的盲盒彼此相加就是 m 的倍数，任取两个都算一种方案
    ans = cnt[0] * (cnt[0] - 1) // 2
    # 余数 r 只能和余数 m-r 配对；r 枚举到 (m-1)//2 为止，保证每一对 (r, m-r) 只统计一次
    for r in range(1, (m - 1) // 2 + 1):
        ans += cnt[r] * cnt[m - r]
    # m 是偶数时余数 m/2 的伙伴还是自己，要按组内两两配对单独算
    if m % 2 == 0:
        half = cnt[m // 2]
        ans += half * (half - 1) // 2
    return ans

## 第一行读盲盒个数与倍数 m，第二行读 n 个价值
n, m = map(int, input().split())
a = list(map(int, input().split()))
print(count_pairs(m, a))

第 3 题：魔法迷宫最短耗时

题目描述

普通道路：给定数组，，表示节点和之间有一条耗时为的双向普通道路，。魔法传送门：给定数组，，表示节点和之间有一个双向传送门，使用传送门的耗时为。

1. 整趟旅途中最多使用次传送门。
1. 不能连续使用两次传送门（两次传送门之间必须经过至少一条普通道路）。
1. 从起点出发时，可以直接使用传送门。

给定起点和终点，返回从起点到终点的最短总时间。若等于，输出。如果无法到达，返回。

输入描述

第一行包含两个整数，分别表示节点数量和普通道路数量。接下来行，每行三个整数，表示一条普通道路。下一行包含一个整数，表示传送门数量。接下来行，每行两个整数，表示一个传送门。下一行包含三个整数。普通道路和传送门均可能有重边或自环。答案可能超过 int 范围，建议用 long 存储。

输出描述

输出一个整数，表示从起点到终点的最短总时间。若等于，输出。若无法到达，输出。

样例1

输入

输出

样例解释 从起点直接使用传送门到达节点，耗时，此时已使用次传送门。由于不能连续使用两次传送门，接着走普通道路从到，耗时。总时间为。

样例2

输入

输出

样例解释 等于（均为节点），无需移动，输出。

题解：分层 Dijkstra（按已用传送门次数分层）

题目问题拆解

图上有两种边：普通道路带权，传送门免费但整趟最多用次、且不能连着用两次，求到的最短总耗时。这是一道状态要额外多带两维的最短路题：在原图上直接跑 Dijkstra 既管不住传送次数、也管不住”上一步是不是传送门”，同一个点在两种历史下的可行动作并不相同，得先把历史塞进状态里。

算法实现

把已经用掉次传送门的世界称作第层，共层。层内只有普通道路可走，传送门恰好是层与层之间的一次跳转，于是所求的量是在第层内到达节点的最短耗时同层内部就是一次多源 Dijkstra：把上一层传送过来的点连同各自代价一起入堆当起点，边权非负，点第一次出堆时的值即为最终值。第层的多源集合只有，代价为。 “不能连用两次传送门”这条限制落到层间。它等价于只有末步是普通道路的状态才有资格发起传送，所以每层跑完先扫一遍全部道路，取它是末步必为普通道路时到达的最优代价。第层额外令，对应题面允许一出发就传送。再沿传送门把它零代价映射成下一层的入口值逐层推到第层为止。终点在哪一层被摸到都算合法，答案取各层的最小值，全是无穷大就输出；等于时一步都不用走，直接输出。更直白的写法是把已用次数上一步是否传送三维状态一起塞进同一个堆，状态数与边数都要乘上，堆里最多压着个元素。分层写法把它拆成次普通 Dijkstra 加两次线性扫描，堆里始终只有个点，实测最坏档秒。答案由若干条量级的边相加，最大到，必须用位整数。

时空复杂度分析

时间复杂度 ：。瓶颈是每层的堆操作，层末两次扫描只有；让层数只是一个小常数。 空间复杂度 ：，压平成 CSR 的邻接表加传送门边表。 Python

## 魔法迷宫最短耗时 - 分层 Dijkstra（按已用传送门次数分层）
from heapq import heappush, heappop

## 读入普通道路，同时统计每个点的度数，为下面压平成 CSR 邻接表做准备
n, m = map(int, input().split())
eu = [0] * m
ev = [0] * m
ew = [0] * m
deg = [0] * n
for i in range(m):
    u, v, w = map(int, input().split())
    eu[i] = u
    ev[i] = v
    ew[i] = w
    deg[u] += 1
    deg[v] += 1

## CSR 邻接表：head[u] ~ head[u+1] 是 u 的出边区间。
## n 到 10^5 时用扁平数组比 list of list 常数小得多，Dijkstra 内层循环才跑得动
head = [0] * (n + 1)
s = 0
for i in range(n):
    head[i] = s
    s += deg[i]
head[n] = s
pos = head[:]
to = [0] * (2 * m)
wt = [0] * (2 * m)
for i in range(m):
    u = eu[i]
    v = ev[i]
    w = ew[i]
    j = pos[u]
    to[j] = v
    wt[j] = w
    pos[u] = j + 1
    j = pos[v]
    to[j] = u
    wt[j] = w
    pos[v] = j + 1

## 传送门只在层与层之间用一次，不进 Dijkstra 的松弛循环，所以存成边表即可
p = int(input())
pu = [0] * p
pv = [0] * p
for i in range(p):
    u, v = map(int, input().split())
    pu[i] = u
    pv[i] = v
## 最后一行给出传送门次数上限与起终点
k, start, end = map(int, input().split())

INF = float('inf')


def shortest_time():
    """分层最短路：第 j 层代表"恰好用了 j 次传送门"的世界。

    每层只走普通道路（一次 Dijkstra），层与层之间靠传送门跳，
    因为传送门耗时 0 且必须"上一步不是传送门"，天然就是层间的一次性转移。
    """
    # 起点即终点，一步都不用走
    if start == end:
        return 0
    best = INF
    # cur[v] = 刚进入本层时到达 v 的代价（第 0 层就是起点，代价 0）
    cur = [INF] * n
    cur[start] = 0
    for layer in range(k + 1):
        # 本层的多源 Dijkstra：所有从上一层传送过来的点一起当起点
        dist = cur
        # 上一层传送过来的点全部入堆，一起当本层的多源起点
        heap = [(d, v) for v, d in enumerate(dist) if d < INF]
        # 已按 (代价, 点) 升序排好的列表本身就是合法小根堆，省一次 heapify
        heap.sort()
        while heap:
            d, u = heappop(heap)
            # 惰性删除：堆里可能残留同一个点的旧代价，比当前最优大就直接丢
            if d > dist[u]:
                continue
            # 边权非负，点第一次出堆时拿到的就是本层最终代价
            for j in range(head[u], head[u + 1]):
                v = to[j]
                nd = d + wt[j]
                if nd < dist[v]:
                    dist[v] = nd
                    heappush(heap, (nd, v))
        # 终点在任何一层被摸到都是合法答案，取所有层的最小值
        if dist[end] < best:
            best = dist[end]
        if layer == k:
            break
        # d_road[v] = 末步是普通道路时到达 v 的最优代价。
        # 只有这种状态才允许接着用传送门（题面禁止连续两次传送）
        d_road = [INF] * n
        for i in range(m):
            u = eu[i]
            v = ev[i]
            w = ew[i]
            t = dist[u] + w
            if t < d_road[v]:
                d_road[v] = t
            t = dist[v] + w
            if t < d_road[u]:
                d_road[u] = t
        if layer == 0:
            # 起点还没走过任何路，允许一出发就传送
            d_road[start] = 0
        # 走一次传送门进入下一层，耗时 0
        nxt = [INF] * n
        for i in range(p):
            u = pu[i]
            v = pv[i]
            if d_road[u] < nxt[v]:
                nxt[v] = d_road[u]
            if d_road[v] < nxt[u]:
                nxt[u] = d_road[v]
        cur = nxt
    # 所有层都没摸到终点，说明不可达
    return best if best < INF else -1


## 答案是若干条 10^9 量级的边相加，必须按 64 位整数看待
print(shortest_time())

第 4 题：赛马对决最大得分

题目描述

输入描述

第一行为一个整数，表示共有个测试数据。每个测试数据的第一行为一个整数，表示每人拥有的马的数量。

输出描述

样例1

输入

输出

1
0

样例解释

题解：二分图最大匹配（匈牙利算法）

题目问题拆解

算法实现

分数随单调递增，最大化总分就是最大化赢的场数。剩下的活是求匹配：先贪心扫一遍，每匹马能占到空着的对手就直接占上；再对没配上的马跑增广路，沿交替路把已占位的马挤去别的空位，挤成功一次匹配数加一。全的数据没有一条边，输出。

时空复杂度分析

时间复杂度 ：单组。增广至多进行次，每次沿边遍历条边；瓶颈在增广，而边数本身就是量级。、合计约。 空间复杂度 ：，存下胜负图的邻接表。 Python

## 赛马对决最大得分 - 二分图最大匹配（匈牙利算法）

def max_matching(n, adj):
    matchL = [-1] * n
    matchR = [-1] * n

    # 先贪心配一轮：能直接占到空位就占，能大幅减少后面跑增广路的次数
    for i in range(n):
        for j in adj[i]:
            if matchR[j] == -1:
                matchL[i] = j
                matchR[j] = i
                break

    def try_augment(i, visited):
        # 从左部点 i 出发找增广路：抢一个还没访问过的 j，若 j 已被占就让原主人另寻他路
        for j in adj[i]:
            if visited[j]:
                continue
            visited[j] = True                    # 一轮增广里每个 j 只试一次，避免兜圈子
            if matchR[j] == -1 or try_augment(matchR[j], visited):
                matchL[i] = j
                matchR[j] = i
                return True
        return False

    res = sum(1 for i in range(n) if matchL[i] != -1)
    for i in range(n):
        # 只有贪心阶段没配上的点才需要跑增广路，成功一次匹配数就 +1
        if matchL[i] == -1 and try_augment(i, [False] * n):
            res += 1
    return res


def solve(n, mat):
    # 只有 M[i][j]==1（第 i 匹马能赢第 j 匹马）才连边
    adj = [[j for j in range(n) if mat[i][j] == 1] for i in range(n)]
    # 就用匹配里的搭档赢下；否则说明它无法参与最优对局，随便派一匹去输，后续匹配数不减
    w = max_matching(n, adj)
    # 赢 W 场各 +1、输 N-W 场各 -1，总分 = W - (N - W) = 2W - N
    return 2 * w - n


t = int(input())
for _ in range(t):
    n = int(input())
    mat = [list(map(int, input().split())) for _ in range(n)]
    print(solve(n, mat))

这篇文章有帮助吗？

| GitHub 留言