大厂真题 / 拼多多
拼多多 5.17 暑期实习笔试真题
本场考试概述
考试时间：2026年5月17日 考试岗位：暑期实习 难度评级：困难
考点分析：
- 第一题：枚举 / 模拟（难度简单）
- 第二题：哈希计数 + 枚举中点（难度中等）
- 第三题：双优先队列 + 动态规划（难度困难）
- 第四题：轮廓线 DP + 矩阵快速幂（难度困难）
建议策略：
- 前两题尽量稳拿，实现简洁不易出错
- 第三题要识别”DP 转移含 $i$、$j$ 耦合项时分离变量”的技巧，再用堆加速
- 第四题对状态压缩 DP 和矩阵快速幂的熟悉度要求高，没把握时可以先骗 80% 的小数据分
第一题：Boss挑战
题目描述
AK 机正在挑战强大的 Boss，他有 $n$ 个技能，每个技能具有伤害值（释放一次造成的伤害）和冷却时间（释放后必须等待的时间，从释放开始计算）。
具体规则如下：
- 战斗从时刻 $0$ 开始，持续 $T$ 秒
- 你只能选择一个技能，在时间范围内周期性释放
- 每次释放耗时 $1$ 秒，期间不能释放其他技能
- 释放后必须等待冷却时间 $c_i$ 秒才能再次释放；如果 $c_i < 1$ 秒，两次释放之间的有效间隔仍为 $1$ 秒
- 一旦选择某个技能，就必须周期性持续释放，不能中途切换
目标：选择一个技能和起始时刻（取 $0$ 最优），使得在 $T$ 秒内造成的总伤害最大。
$1 \leq n \leq 10^5$，$1 \leq T \leq 10^9$。
样例
输入
10
50
3
输出
200
技能 $1$ 个，伤害 $50$，冷却时间 $3$。从时刻 $0$ 开始释放，在 $[0, 3, 6, 9]$ 时刻各释放一次，共 $4$ 次，总伤害 $50 \times 4 = 200$。
思路分析
第一步：理解释放周期
每次释放占用 $1$ 秒，冷却时间为 $c_i$，因此两次释放的间隔为 $\max(c_i, 1)$ 秒。这是因为释放本身至少需要 $1$ 秒，当 $c_i < 1$ 时有效周期仍是 $1$。
第二步：计算释放次数
起始时刻取 $t = 0$（越早越好），在 $[0, T-1]$ 的范围内，每隔 $\text{period} = \max(c_i, 1)$ 秒释放一次，释放次数为：
\[\text{count}_i = \lfloor (T - 1) / \text{period} \rfloor + 1\]第三步：枚举取最大值
对每个技能计算 $d_i \times \text{count}_i$，取最大值即为答案。单次遍历即可完成。
题解代码
import sys
input = sys.stdin.readline
T = int(input())
damages = list(map(int, input().split()))
cooldowns = list(map(int, input().split()))
n = len(damages)
best = 0
for i in range(n):
# 冷却 < 1 秒时仍需 1 秒释放间隔，有效周期取 max(c, 1)
period = max(cooldowns[i], 1)
# 起始时间 t=0 最优，[0, T-1] 内可释放 (T-1)//period + 1 次
count = (T - 1) // period + 1
gain = damages[i] * count
if gain > best:
best = gain
print(best)
复杂度分析
- 时间复杂度：$O(n)$，遍历每个技能做一次常数运算
- 空间复杂度：$O(n)$，存储伤害和冷却数组
第二题：特殊三元组
题目描述
给定一个整数数组 $\text{nums}$，找出所有满足条件的特殊三元组 $(i, j, k)$，其中 $i < j < k$，满足：
\[2 \times (\text{nums}[i] - \text{nums}[j]) = \text{nums}[k]\]由于答案可能非常大，请返回结果对 $10^9 + 7$ 取模后的值。
$1 \leq n \leq 3000$，$-10^9 \leq \text{nums}[i] \leq 10^9$。
样例
输入
1
5
8 4 2 8 4
输出
2
满足条件的三元组：$(0, 1, 3)$ 对应 $2 \times (8 - 4) = 8$；$(0, 1, 4)$ 对应… 实际验证 $2 \times (8 - 4) = 8$ 与 $\text{nums}[k]$ 匹配即可，共 $2$ 个。
思路分析
第一步：变形等式，选择枚举维度
原式 $2 \times (\text{nums}[i] - \text{nums}[j]) = \text{nums}[k]$ 等价于 $2 \times \text{nums}[i] = 2 \times \text{nums}[j] + \text{nums}[k]$，即：
\[\text{nums}[i] = \text{nums}[j] + \frac{\text{nums}[k]}{2}\]如果暴力枚举三个下标是 $O(n^3)$，超时。降维的关键是枚举中间点 $j$，将”左侧找 $i$”和”右侧找 $k$”拆成两个独立子问题。
第二步：前缀哈希计数
固定 $j$ 后，对每个 $k > j$ 计算 $\text{target} = \text{nums}[j] + \text{nums}[k] / 2$。如果 $\text{nums}[k]$ 是奇数，$\text{target}$ 不是整数，等式无整数解，跳过。否则查询前缀哈希表中 $\text{target}$ 出现了多少次，即为有效的 $i$ 的个数。
第三步：维护哈希表的时序
从左到右扫描 $j$。对当前 $j$，先枚举所有 $k > j$ 完成查询，然后再将 $\text{nums}[j]$ 加入哈希表。这保证查询时哈希表中只包含下标严格小于 $j$ 的元素，$i < j$ 的约束自动满足。
总时间 $O(n^2)$，足以处理 $n \leq 3000$。
题解代码
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def solve_case(n, nums):
"""统计满足 2*(nums[i]-nums[j])=nums[k] 的三元组数量"""
if n < 3:
return 0
# cnt[v]：当前已扫过的下标中值为 v 的个数（对应 nums[0..j-1]）
cnt = {}
ans = 0
# 外层枚举中点 j
for j in range(n):
nj = nums[j]
# 内层枚举右端点 k，查询左侧有多少 i 满足条件
for k in range(j + 1, n):
nk = nums[k]
# nums[k] 为奇数时 target 非整数，无解
if nk % 2 == 0:
target = nj + nk // 2
if target in cnt:
ans += cnt[target]
# 处理完 j 的所有查询后才加入前缀，保证 i < j
cnt[nj] = cnt.get(nj, 0) + 1
return ans % MOD
T = int(input())
out = []
for _ in range(T):
n = int(input())
nums = list(map(int, input().split())) if n > 0 else []
out.append(str(solve_case(n, nums)))
print("\n".join(out))
复杂度分析
- 时间复杂度：$O(n^2)$，外层枚举 $j$，内层枚举 $k$，哈希查询 $O(1)$
- 空间复杂度：$O(n)$，哈希表最多存 $n$ 个不同值
第三题：自习室学习
题目描述
AK 机是个爱学习的人，最近家里在装修，他只能去附近的自习室学习。自习室有 $n$ 个房间，每个房间只有一段时间是空的。AK 机必须在空闲开始时就到达，也不必等到空闲结束就能离开。AK 机从不同的房间转移，至少需要 $2$ 分钟时间。求最长能学习多长时间。
每个房间的空闲窗口为 $[x_i, x_i + y_i)$，即从第 $x_i$ 分钟起空闲，持续 $y_i$ 分钟。
$1 \leq n \leq 10^5$，$0 \leq x_i \leq 10^9$，$1 \leq y_i \leq 10^9$。
样例
输入
2
0 50
100 50
输出
100
AK 机在第一个房间学习 $50$ 分钟，转移到第二个房间学习 $50$ 分钟，一共 $100$ 分钟。
思路分析
第一步：定义 DP 状态
按空闲开始时刻 $x_i$ 升序排序。定义 $dp[i]$ = 到达房间 $i$ 开始时（$x_i$ 时刻）已累计的最长学习时间。最终答案为 $\max_i(dp[i] + y_i)$，即选 $i$ 作为最后一段并学满。
第二步：分析状态转移
考虑 $j$ 作为 $i$ 之前最后一段会话所在的房间，转场至少需要 $2$ 分钟：
- 情况 A（$j$ 学满）：若 $x_j + y_j + 2 \leq x_i$，则 $j$ 有足够时间学满 $y_j$，转移为 $dp[i] = dp[j] + y_j$
- 情况 B（$j$ 提前离开）：若 $x_j + 2 \leq x_i$ 但 $x_j + y_j + 2 > x_i$，则 $j$ 必须在 $x_i - 2$ 时刻离开，实际在 $j$ 学了 $x_i - x_j - 2$ 分钟，转移为 $dp[i] = dp[j] + (x_i - x_j - 2)$
第三步：分离变量加速
直接枚举所有 $j$ 是 $O(n^2)$，需要用数据结构加速。
- 情况 A 的贡献为 $dp[j] + y_j$，只与 $j$ 有关，取前缀最大值即可
- 情况 B 的贡献为 $(dp[j] - x_j - 2) + x_i$，其中 $x_i$ 对固定的 $i$ 是常数，只需在合法 $j$ 中求 $dp[j] - x_j - 2$ 的最大值
第四步：双堆维护
- 堆 B：存所有满足 $x_j + 2 \leq x_i$ 的前驱，按 $dp[j] - x_j - 2$ 排序（大顶堆）
- 堆 A：当堆 B 中的 $j$ 进一步满足 $x_j + y_j + 2 \leq x_i$ 时，升级到堆 A，按 $dp[j] + y_j$ 排序
每个 $j$ 最多入堆 B 一次、弹出后入堆 A 一次，总均摊 $O(n \log n)$。
题解代码
import sys
import heapq
input = sys.stdin.readline
N = int(input())
rooms = []
for _ in range(N):
x, y = map(int, input().split())
rooms.append((x, y))
# 按空闲开始时刻 x 升序排序
rooms.sort()
# dp[i]：到达房间 i 开始时已累计的最长学习时间
dp = [0] * N
# heap_A：维护"已学满前驱"的 dp[j] + y[j]（负数实现大顶堆）
heap_A = []
# heap_B：维护"必须提前离开前驱"的 (dp[j] - x[j] - 2, j)
heap_B = []
j_ptr = 0 # 单调指针：跟踪哪些 j 已加入 heap_B
for i in range(N):
x_i, y_i = rooms[i]
# 步骤 1：把所有 x[j] + 2 <= x[i] 的 j 加入 heap_B
while j_ptr < i and rooms[j_ptr][0] + 2 <= x_i:
x_j, _ = rooms[j_ptr]
heapq.heappush(heap_B, (-(dp[j_ptr] - x_j - 2), j_ptr))
j_ptr += 1
# 步骤 2：堆 B 堆顶若已可学满（x[j]+y[j]+2 <= x[i]），升级转入 heap_A
while heap_B:
_, j_idx = heap_B[0]
x_j, y_j = rooms[j_idx]
if x_j + y_j + 2 <= x_i:
heapq.heappop(heap_B)
heapq.heappush(heap_A, -(dp[j_idx] + y_j))
else:
break
# 步骤 3：查询两个堆取最大转移值，0 对应"i 是第一段，无前驱"
best = 0
if heap_A:
best = max(best, -heap_A[0])
if heap_B:
best = max(best, -heap_B[0][0] + x_i)
dp[i] = best
# 最终答案：枚举 i 作为最后一段，学满 y[i]
answer = 0
for i in range(N):
answer = max(answer, dp[i] + rooms[i][1])
print(answer)
复杂度分析
- 时间复杂度：$O(n \log n)$，排序 $O(n \log n)$，每个房间至多入堆、出堆各一次
- 空间复杂度：$O(n)$，DP 数组和堆的空间
第四题：道路修建II
题目描述
道路可以看作是一个 $M \times N$ 的网格，每个单元格需要被铺满。可以使用 $1 \times 1$ 的石砖和 $2 \times 2$ 的石砖。石块不能拆分，石块之间不可重叠，且必须完全覆盖整个网格。请计算用这两种石砖完全铺满 $M \times N$ 网格的不同修建方案数。
由于答案可能会很大，只需输出答案对 $10^9 + 7$ 取模后的值。
$1 \leq N \leq 10^{18}$，$1 \leq M \leq 5$。
样例
输入
4 2
输出
5
$4 \times 2$ 网格的合法方案共 $5$ 种：全用 $1 \times 1$、$2 \times 2$ 放最左、放中间、放最右、两个 $2 \times 2$ 并列。
思路分析
第一步：识别问题结构
$N$ 极大（可达 $10^{18}$）但 $M$ 很小（$\leq 5$），自然想到按列推进。每一列只有 $2^M$ 种可能的状态（$M = 5$ 时仅 $32$ 种），把列间递推关系写成矩阵乘法，再用矩阵快速幂把 $N$ 次递推压成 $O(\log N)$ 次矩阵乘。
第二步：定义列状态
用 $M$ 位二进制串表示当前列每行的”被占用”情况。第 $r$ 位为 $1$ 表示该行已被上一列延伸过来的 $2 \times 2$ 砖占据，本列不能再放东西。
第三步：列内转移（构造转移矩阵）
固定当前列的输入状态 \(\text{mask}\)（哪些行被上列占了），从上到下逐行决策：
- 若第 $r$ 行已被占用（\(\text{mask}\) 第 $r$ 位为 $1$）：跳过，处理下一行
- 若第 $r$ 行空闲，有两个选择：
- 放 $1 \times 1$ 砖：不影响下一列
- 起 $2 \times 2$ 砖：要求第 $r+1$ 行也空闲且在界内，同时向右延伸到下一列（在 \(\text{new\_mask}\) 中将第 $r$ 和第 $r+1$ 位置 $1$）
遍历所有 \(\text{mask}\) 和所有合法的放置方案，构建转移矩阵 $T$，其中 \(T[\text{new\_mask}][\text{mask}]\) 表示从状态 \(\text{mask}\) 转移到 \(\text{new\_mask}\) 的方案数。
第四步：矩阵快速幂求解
初始状态为 $\text{mask} = 0$（第 $1$ 列前面没有砖伸过来），经过 $N$ 列后终态也为 $0$（第 $N+1$ 列不存在，不能有砖伸过去）。答案为 $T^N[0][0]$。
矩阵规模为 $2^M \times 2^M$（$M = 5$ 时为 $32 \times 32$），每次矩阵乘法 $O(2^{3M})$，快速幂执行 $O(\log N)$ 次，总复杂度可接受。
题解代码
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
def matmul(A, B, sz):
"""矩阵乘法 C = A * B，跳零项加速稀疏转移"""
C = [[0] * sz for _ in range(sz)]
for i in range(sz):
Ai = A[i]
Ci = C[i]
for k in range(sz):
a = Ai[k]
if a == 0:
continue
Bk = B[k]
for j in range(sz):
Ci[j] = (Ci[j] + a * Bk[j]) % MOD
return C
def matpow(A, p, sz):
"""矩阵快速幂 A^p：倍增法把 p 次乘法压成 O(log p) 次"""
# 单位矩阵作为乘法初值
R = [[1 if i == j else 0 for j in range(sz)] for i in range(sz)]
while p > 0:
if p & 1:
R = matmul(R, A, sz)
A = matmul(A, A, sz)
p >>= 1
return R
def build_trans(M):
"""构造列间转移矩阵 T[new_mask][mask] = 方案数"""
sz = 1 << M
T = [[0] * sz for _ in range(sz)]
for mask in range(sz):
# DFS 枚举本列从上到下的所有放置方案
stack = [(0, 0)] # (当前行 row, 已确定的 new_mask)
while stack:
row, new_mask = stack.pop()
if row == M:
T[new_mask][mask] += 1
continue
if mask & (1 << row):
# 第 row 行已被上一列 2x2 占据，跳过
stack.append((row + 1, new_mask))
continue
# 选项 1：放 1x1，下一列该行仍空闲
stack.append((row + 1, new_mask))
# 选项 2：起 2x2，要求 row+1 在界内且未被占用
if row + 1 < M and not (mask & (1 << (row + 1))):
stack.append((row + 2, new_mask | (1 << row) | (1 << (row + 1))))
return T, sz
N, M = map(int, input().split())
T, sz = build_trans(M)
R = matpow(T, N, sz)
# 初态 mask=0，终态 mask=0
print(R[0][0] % MOD)
复杂度分析
- 时间复杂度：$O(2^{3M} \cdot \log N)$，矩阵规模 $2^M$，快速幂 $\log N$ 次矩阵乘法。$M = 5$ 时约 $32^3 \times 60 \approx 2 \times 10^6$ 次运算
- 空间复杂度：$O(2^{2M})$，存储转移矩阵
小结
本场拼多多笔试延续了其高难度风格，四题考点覆盖广：
| 题号 | 考点 | 核心技巧 |
|---|---|---|
| T1 | 枚举模拟 | 计算有效周期，直接公式求解 |
| T2 | 哈希 + 枚举 | 枚举中点降维，前缀计数避免重复遍历 |
| T3 | DP + 堆优化 | 分离变量将 $O(n^2)$ 转移优化为 $O(n \log n)$ |
| T4 | 轮廓线 DP + 矩阵快速幂 | 状态压缩列状态，矩阵幂处理超大 $N$ |
关键收获：
- T2 的”枚举中点 + 前缀哈希”是三元组计数的经典降维模式，遇到 $i < j < k$ 且等式含三变量时优先考虑
- T3 的双堆结构体现了”转移式中分离 $i$、$j$ 相关项”的思想，本质上是用堆代替线段树来维护前缀极值
- T4 结合了轮廓线 DP 的状态定义方式和矩阵快速幂处理大规模线性递推的能力，是竞赛中处理”一维极大、另一维极小”网格问题的标准武器