大厂真题 / 华为
华为 2026-10-10 笔试真题 - 研发岗
本场考试概述
考试时间：2026年10月10日
考试岗位：研发岗
难度评级：中等
考点分析：子集枚举与优惠券搜索、多源 BFS、区间覆盖动态规划。
建议策略：先完成多源 BFS，再处理规模较小的优惠券搜索，最后把数轴覆盖转化为前缀状态。优惠券的使用顺序、空凑单列表和覆盖边界都需要单独检查。
第 1 题：凑单与优惠券最优组合
题目描述
需要购买 $n$ 件必买商品，另有 $m$ 件可选商品，每件最多购买一次。给定 $k$ 张优惠券，任选其中若干张并决定使用顺序，求最少实际支付金额。
每张券最多使用一次；使用前的当前价格必须不小于该券门槛 threshold。类型 0 为满减券，将当前价格减去 value；类型 1 为折扣券，将当前价格变为 $\lfloor p\cdot value/100\rfloor$。更新后的价格用于判断下一张券的门槛。最终金额若为负数，输出 0。
输入格式：第一行是 $n,m,k$，其中 $1\le n\le10$、$0\le m\le10$、$0\le k\le5$。第二行给出 $n$ 个必买商品价格，随后给出 $m$ 个可选商品价格；$m=0$ 时没有这一行。商品价格不超过 $1000$。接下来 $k$ 行为 type threshold value，门槛和数值均为正整数，折扣值 90 表示九折。
输出格式：输出一个整数，表示最少支付金额。
样例 1
输入
1 2 2
190
10 20
0 200 30
1 200 90
输出
170
解释：四种购物车总价为 $190,200,210,220$。选择 $10$ 元的凑单商品，总价达到 $200$，使用满减券后支付 $170$。此后价格低于另一张券的门槛，不能继续用券。
样例 2
输入
2 2 2
50 50
30 70
0 100 20
1 150 50
输出
75
解释：只加入 $70$ 元的可选商品，总价为 $170$；先满减得到 $150$，再打五折得到 $75$。若先打折，则得到 $85$，不再满足满减券的 $100$ 元门槛。
思路分析
第一步：枚举购物车。 额外购买商品可能触发更优惠的门槛，不能只比较不凑单的情况。用子集扩展生成全部可选商品总价，再加上必买商品总价。
第二步：枚举券的所有使用前缀。 以当前价格和已用券集合为搜索状态。每到一个状态，都可以立刻停止用券，因此先更新答案；然后尝试每张未使用且满足门槛的券。位掩码只用于记录是否使用，不能仅按掩码保留一个最小价格：更小的当前价格可能失去后续高门槛券的资格。
第三步：检查顺序和结束条件。 样例二购买总价为 170 的商品，先减 20，再打五折，得到 75。反过来使用会改变下一张券是否可用。若价格已经不大于零，最终支付不可能优于零；因为门槛为正，也无法继续使用任何券，可以直接返回。
正确性说明：每个购物子集都会被枚举。对于固定购物车，任意合法优惠券序列均对应搜索树中的一条路径，其每个前缀都包含在停止候选中；搜索只排除不满足门槛或重复使用的券。故所有合法方案的最小支付都被比较。
题解代码
import sys
def minimum_payment(required, optional, coupons):
totals = [sum(required)]
for price in optional:
totals += [total + price for total in totals]
best = min(totals)
def search(price, used):
nonlocal best
best = min(best, max(0, price))
if price <= 0:
return
for j, (kind, threshold, value) in enumerate(coupons):
if used >> j & 1 or price < threshold:
continue
nxt = price - value if kind == 0 else price * value // 100
search(nxt, used | (1 << j))
for total in totals:
search(total, 0)
return best
def solve():
values = list(map(int, sys.stdin.read().split()))
n, m, k = values[:3]
pos = 3
required = values[pos:pos + n]
pos += n
optional = values[pos:pos + m]
pos += m
coupons = [tuple(values[pos + 3*j:pos + 3*j + 3]) for j in range(k)]
print(minimum_payment(required, optional, coupons))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(n+2^m\cdot k\cdot k!)$（$k\ge1$），每个子集枚举所有排列前缀，每个节点检查至多 $k$ 张券；$k=0$ 时为 $O(n+2^m)$。
空间复杂度：$O(2^m+n+m+k)$，用于子集和、输入数据及深度不超过 $k$ 的递归栈。
第 2 题：病毒扩散模拟
题目描述
一个 $m\times n$ 房间由网格表示：0 为健康人员，1 为已感染人员，x 为障碍。病毒每小时向上下左右相邻的健康格传播一次，障碍不可穿过。
求所有健康人员都被感染需要的最少小时数。若仍有健康人员无法到达，输出 -1；开始时没有健康人员则输出 0。
输入格式：第一行 $m,n$，均在 $[1,100]$ 内；接下来 $m$ 行，每行 $n$ 个以空格分隔的网格标记。
输出格式：输出最少小时数，或 -1。
样例 1
输入
3 4
0 0 0 0
1 x 0 0
0 0 x 1
输出
3
解释：两个感染源同时出发，各格的最早感染时刻如下。第一行第三列最晚感染，因此答案为 $3$。
1 2 3 2
0 x 2 1
1 2 x 0
样例 2
输入
3 3
0 x 0
x x 0
1 0 0
输出
-1
解释：左上角健康人员的两个相邻格均为障碍，永远无法被感染。即使其余健康人员都可被感染，仍应输出 $-1$。
思路分析
第一步：把所有感染源同时入队。 分别从每个感染源搜索会重复遍历房间。所有初始感染格的感染时刻都是零，将它们一起放入 FIFO 队列，就能按时间层次统一扩散。
第二步：首次入队就标记感染。 从时刻 $t$ 的格子走向健康邻格，该邻格的感染时刻为 $t+1$。入队时立即把它从健康改为感染，避免同一格被多个感染源重复加入。队列按时刻非递减弹出，第一次到达就是最短传播时间。
第三步：维护剩余健康人数。 每感染一人，计数减一。遍历结束后仍有剩余，说明存在被障碍隔开的区域或没有感染源，输出 -1；否则返回最大的感染时刻。无健康人员时答案初值零即可覆盖。
正确性说明：把非障碍格连成无权图，多源 BFS 得到每个格子到任意感染源的最短距离。所有健康格的这些距离的最大值，就是完成传播的最早时刻；无法访问的健康格对应无法完成的情况。
题解代码
import sys
from collections import deque
def infection_time(grid):
m, n = len(grid), len(grid[0])
queue = deque()
healthy = 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
queue.append((i, j, 0))
elif grid[i][j] == "0":
healthy += 1
answer = 0
while queue:
i, j, hour = queue.popleft()
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == "0":
grid[ni][nj] = "1"
healthy -= 1
answer = hour + 1
queue.append((ni, nj, hour + 1))
return answer if healthy == 0 else -1
def solve():
input = sys.stdin.readline
m, n = map(int, input().split())
grid = [input().split() for _ in range(m)]
print(infection_time(grid))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(mn)$，每个格子最多入队一次，每次只检查四个方向。
空间复杂度：$O(mn)$，用于网格和队列。
第 3 题：多规格炸弹覆盖
题目描述
数轴上有 $N$ 栋建筑，位置互不相同。炸弹只能部署在建筑处，有 $M$ 种规格，每种规格可使用任意多颗。规格为 $r$ 的炸弹消耗 $r$ 单位资源，覆盖与部署点距离不超过 $r$ 的所有建筑。
求覆盖所有建筑的最小资源消耗。
输入格式：第一行是 $N,M$，满足 $1\le N\le100$、$1\le M\le10$。第二行给出 $N$ 个不同的整数位置，范围为 $[0,10^9]$；第三行给出 $M$ 个不同的整数规格，范围为 $[1,10^9]$。
输出格式：输出最小总消耗。
样例 1
输入
3 3
0 20 80
15 20 40
输出
35
解释：在位置 $0$ 部署规格 $20$ 的炸弹，覆盖位置 $0,20$；在位置 $80$ 部署规格 $15$ 的炸弹，总费用为 $20+15=35$。距离等于规格也算覆盖。
样例 2
输入
9 3
4 2 0 100 110 105 200 250 300
50 2 5
输出
13
解释：在位置 $2,200,250,300$ 各部署一颗规格 $2$ 的炸弹，其中位置 $2$ 的炸弹覆盖 $0,2,4$；在位置 $105$ 部署规格 $5$ 的炸弹，覆盖 $100,105,110$。总费用为 $4\times2+5=13$。
思路分析
第一步：枚举一颗炸弹能覆盖的区间。 建筑排序后，每颗炸弹覆盖一个连续下标区间 $[L,R)$。枚举每个部署点和每种规格，二分求出该区间；端点距离等于规格也被覆盖，因此右边界使用 bisect_right。
第二步：定义已覆盖前缀。 令 $dp[i]$ 为覆盖前 $i$ 栋建筑的最小代价，初始 $dp[0]=0$。当一颗炸弹满足 $L\le i<R$ 时，它覆盖了第一栋尚未覆盖的建筑 $i$，且能把连续覆盖前缀推进到 $R$，于是有：
\[dp[R]=\min(dp[R],dp[i]+r).\]按 $i$ 从小到大处理。每次转移都会严格增加前缀长度，不存在循环依赖。
第三步：证明不会漏掉允许重叠的方案。 任意全覆盖方案都包含一颗覆盖当前第一栋未覆盖建筑的炸弹；加入它后，已有前缀与该区间没有空隙，可以推进到它的右端。重复这一过程即可从该方案中取出一条到达 $N$ 的转移链。被取出的炸弹是原方案的子集，费用不会增加。反过来，每条转移链都给出真实可部署且覆盖全部建筑的方案，故 DP 的最小值正是最优值。
这一状态不要求各颗炸弹的覆盖范围互不相交，也不要求部署点是第一个未覆盖的建筑。样例二可以在位置 2 使用规格 2，同时覆盖 0,2,4。
题解代码
import sys
from bisect import bisect_left, bisect_right
def minimum_resource(positions, radii):
positions = sorted(positions)
n = len(positions)
intervals = []
for center in positions:
for radius in radii:
left = bisect_left(positions, center - radius)
right = bisect_right(positions, center + radius)
intervals.append((left, right, radius))
dp = [float("inf")] * (n + 1)
dp[0] = 0
for i in range(n):
for left, right, cost in intervals:
if left <= i < right:
dp[right] = min(dp[right], dp[i] + cost)
return dp[n]
def solve():
data = list(map(int, sys.stdin.read().split()))
n, m = data[:2]
print(minimum_resource(data[2:2 + n], data[2 + n:2 + n + m]))
if __name__ == "__main__":
solve()
复杂度分析
时间复杂度：$O(N^2M+NM\log N)$，预处理 $NM$ 个区间，随后每个前缀遍历全部区间。
空间复杂度：$O(NM+N+M)$，保存区间、输入与前缀状态。
小结
- 凑单题的规模允许全枚举，用券门槛依赖当前价格，因此顺序必须进入搜索。
- 病毒扩散用多源 BFS 同时模拟所有起点，入队时标记避免重复。
- 数轴覆盖可以按第一处未覆盖位置推进前缀，不必枚举所有炸弹组合。