大厂真题 / 华为
华为研发岗 2026-09-16
本场考试概述
考试时间：2026-09-16
考试岗位：研发岗
难度评级：中等偏难
考点分析：
- 第一题 雷达站等距探测统计：平方距离分组与哈希计数（难度中等）。
- 第二题 设备组合优化：集合覆盖与状态压缩 DP（难度中等）。
- 第三题 聚餐时间规划：Dijkstra、反图与旅行商型状压 DP（难度困难）。
建议策略：
- 第一题固定中心点后再分组，避免三重枚举；平方距离最大为 $8\times10^{10}$。
- 第二题的关键约束是 $k\le20$，应压缩需求特性，而不是枚举最多 30 台设备的子集。
- 第三题先把路网压缩成起点、朋友和餐厅之间的最短路，再枚举接人集合与顺序。
第 1 题：雷达站等距探测统计
题目描述
平面上有 $N$ 个互不相同的雷达站。定义有序三元组 $(i,j,k)$ 为等距探测三元组，当且仅当 $j\ne k$，并且点 $i$ 到点 $j$ 与点 $k$ 的欧氏距离相等。
顺序有意义：$(i,j,k)$ 与 $(i,k,j)$ 是两个不同三元组。求全部等距探测三元组的数量。
输入描述
第一行是点数 $N$，$3\le N\le2000$。
接下来 $N$ 行每行两个整数 $x_i,y_i$，满足 $-100000\le x_i,y_i\le100000$。所有点互不相同。
输出描述
输出等距探测三元组总数。
样例 1
输入
3
0 0
1 0
2 0
输出
2
样例 2
输入
3
0 0
1 0
3 0
输出
0
样例 3
输入
4
0 0
1 0
0 1
-1 0
输出
8
思路分析
第一步：固定中心点。 直接枚举 $(i,j,k)$ 是 $O(N^3)$。固定 $i$ 后，只需知道其余点到 $i$ 的距离是否相等。
第二步：按平方距离分组。 对每个 $j\ne i$，计算 $d=(x_i-x_j)^2+(y_i-y_j)^2$ 并计数。无需开平方，既避免浮点误差，也不改变相等关系。
第三步：计算有序对。 若某个距离组有 $c$ 个点，先选 $j$ 再选不同的 $k$，共有 $c(c-1)$ 种。对所有中心和距离组累加即可。
正确性说明
固定中心 $i$ 后，同一距离组中的任意两个不同点都与 $i$ 等距，因此产生 $c(c-1)$ 个合法有序三元组；不同距离组不能互相配对。所有三元组都有唯一中心和唯一距离组，所以算法既不会遗漏，也不会重复计数。
题解代码
import sys
from collections import defaultdict
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
points = [tuple(data[i:i + 2]) for i in range(1, 1 + 2 * n, 2)]
answer = 0
for center_x, center_y in points:
count = defaultdict(int)
for x, y in points:
dx = x - center_x
dy = y - center_y
distance = dx * dx + dy * dy
if distance != 0:
count[distance] += 1
answer += sum(value * (value - 1) for value in count.values())
print(answer)
solve()
复杂度分析
时间复杂度：$O(N^2)$，每个中心都扫描全部点。
空间复杂度：$O(N)$，单轮哈希表最多记录 $N-1$ 个距离。
易错点
- 题目统计的是有序三元组，贡献是 $c(c-1)$，不是组合数 $c(c-1)/2$。
- 不能用浮点开方后的结果作为哈希键。
- 固定宽度语言需要用 64 位整数保存平方距离和答案。
第 2 题：设备组合优化
题目描述
有 $n$ 台设备，每台设备带有 $m$ 个功能特性。某项业务需要 $k$ 个互不相同的特性。选择尽可能少的设备，使业务所需的每个特性都至少被一台所选设备覆盖。
如果无论怎样选择都不能覆盖全部需求，输出 0。
输入描述
第一行是 $n,m,k$，满足 $n\le30$、$m\le10$、$k\le20$，三者均为正整数。
接下来 $n$ 行，每行 $m$ 个整数，表示一台设备拥有的特性编号。
最后一行包含 $k$ 个互不相同的整数，表示业务需要的特性编号。
输出描述
输出覆盖全部需求所需的最少设备数；无法满足时输出 0。
样例 1
输入
3 3 3
1 2 3
4 5 6
7 8 9
1 4 7
输出
3
样例 2
输入
3 2 5
1 2
3 4
5 6
7 8 9 10 11
输出
0
样例 3
输入
1 1 1
1
1
输出
1
思路分析
第一步：压缩需求集合。 给 $k$ 个需求特性编号 $0$ 到 $k-1$。每台设备只保留与需求相交的部分，并压成一个 $k$ 位整数。无关特性不会影响答案。
第二步：定义状态。 dp[mask] 表示恰好处理完当前若干台设备后，覆盖集合 mask 所需的最少设备数。初始只有 dp[0]=0。
第三步：逐台做 0-1 转移。 对一台掩码为 cur 的设备，从上一轮的每个可达状态转移到 mask | cur，代价加一；同时保留不选该设备的状态。使用上一轮副本可保证每台设备最多选一次。
覆盖面被另一台设备完全包含的设备不会优于后者，可以提前去掉；相同掩码也只需保留一台。
正确性说明
归纳考虑设备处理顺序。处理第 $i$ 台设备后，任一最优方案要么不选它，此时由上一轮相同状态覆盖；要么选它，此时从上一轮某个状态与当前设备掩码取并集得到。转移枚举了这两种且仅有的情况，因此 dp 始终记录对应覆盖集合的最少设备数。最终全集状态就是所求答案。
题解代码
import sys
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
iterator = iter(data)
n = next(iterator)
m = next(iterator)
k = next(iterator)
devices = [[next(iterator) for _ in range(m)] for _ in range(n)]
required = [next(iterator) for _ in range(k)]
position = {feature: index for index, feature in enumerate(required)}
masks = []
for device in devices:
mask = 0
for feature in device:
if feature in position:
mask |= 1 << position[feature]
if mask:
masks.append(mask)
full = (1 << k) - 1
if not masks or any_feature_missing(masks, full):
print(0)
return
unique_masks = set(masks)
masks = [
mask for mask in unique_masks
if not any(mask != other and (mask | other) == other for other in unique_masks)
]
unreachable = 255
dp = bytearray([unreachable]) * (1 << k)
dp[0] = 0
for current in masks:
next_dp = dp[:]
for covered, count in enumerate(dp):
if count == unreachable:
continue
merged = covered | current
if count + 1 < next_dp[merged]:
next_dp[merged] = count + 1
dp = next_dp
print(dp[full] if dp[full] != unreachable else 0)
def any_feature_missing(masks, full):
covered = 0
for mask in masks:
covered |= mask
return covered != full
solve()
复杂度分析
时间复杂度：$O(nm+r2^k)$，其中 $r\le n$ 是去重和去除被包含设备后的掩码数。
空间复杂度：$O(nm+2^k)$，分别用于暂存设备特性和 DP 数组。
易错点
- 状态位对应的是业务需求特性，不是所有出现过的特性。
- 一台设备内的重复特性只能覆盖一次，按位或会自然去重。
- 输出 0 表示不可覆盖，不能与“选择零台即可满足”混淆；本题 $k$ 为正数。
第 3 题：聚餐时间规划
题目描述
城市道路有单向和双向两种。你从路口 $s$ 开车前往路口 $t$ 的餐厅，并可绕路接上 $k$ 位朋友中的任意一部分。未被接的朋友自行步行去餐厅。
开车每公里需要 2 分钟，步行每公里需要 10 分钟。每位朋友要么全程步行，要么在自己的起点被接上车；道路和路口允许重复经过，车辆没有承载上限。求所有人都到达餐厅的最短时间，即最后一人到达的时刻。
输入描述
第一行是 $n,m,s,t$，满足 $1\le n,m\le1000$，路口编号为 1 到 $n$。
接下来 $m$ 行每行是 $u,v,w,d$。道路长度 $1\le w\le100$；$d=0$ 表示只能从 $u$ 到 $v$，$d=1$ 表示双向。
随后一行是朋友数 $k$，$0\le k\le15$。
当 $k>0$ 时，下一行给出 $k$ 位朋友所在的路口。题目保证所有人都能到达餐厅。
输出描述
输出所有人到达餐厅的最短时间，单位为分钟。
样例 1
输入
6 7 1 6
1 2 2 1
1 3 3 1
2 4 1 0
3 4 1 0
3 5 2 0
4 6 3 1
5 6 2 1
3
2 3 5
输出
22
样例 2
输入
6 7 1 6
1 2 2 1
1 3 3 1
2 4 2 0
3 4 1 0
3 5 2 0
4 6 3 1
5 6 2 1
3
2 4 5
输出
20
思路分析
第一步：把路网压成关键点距离。 车在接人点之间一定走最短路。从 $s$ 和每位朋友的位置分别在正图跑 Dijkstra，得到起点到朋友、朋友之间的距离。为了求所有位置到餐厅的距离，从 $t$ 在反图跑一次 Dijkstra；单向边不能把正图中从 $t$ 出发的距离反过来使用。
第二步：枚举接人集合和顺序。 定义 dp[mask][i] 为已经接上集合 mask，且最后停在朋友 $i$ 处时的最短行车距离。第一个接 $i$ 的代价是 $dist(s,p_i)$；之后从最后一位朋友转移到未接的朋友。
第三步：合并车程和步行时间。 对每个 mask，车接完这些朋友后再到餐厅。没有被接的朋友各自走最短路，取其中最大步行时间。该方案的完成时间是车到达时间与最慢步行时间的较大值，对全部集合取最小。
不能漏掉 mask=0：此时车直接去餐厅，但仍要等待所有朋友步行到达。
正确性说明
Dijkstra 给出了任意相邻接人决策之间的最短合法路程。dp[mask][i] 枚举了集合 mask 的所有接人顺序，并按最后一人分类取最小，因此得到接完该集合且停在 $i$ 的最短距离。再加上 $i$ 到餐厅的最短路，就得到该接人集合的最短车程。未接朋友互不影响，其最晚到达时间是各自步行时间最大值。枚举全部接人集合并取最小，覆盖所有合法策略。
题解代码
import sys
import heapq
INF = 10 ** 30
def dijkstra(graph, start):
distance = [INF] * len(graph)
distance[start] = 0
heap = [(0, start)]
while heap:
current, node = heapq.heappop(heap)
if current != distance[node]:
continue
for neighbor, weight in graph[node]:
candidate = current + weight
if candidate < distance[neighbor]:
distance[neighbor] = candidate
heapq.heappush(heap, (candidate, neighbor))
return distance
def solve():
data = list(map(int, sys.stdin.buffer.read().split()))
iterator = iter(data)
n = next(iterator)
m = next(iterator)
start = next(iterator)
target = next(iterator)
graph = [[] for _ in range(n + 1)]
reverse_graph = [[] for _ in range(n + 1)]
for _ in range(m):
u = next(iterator)
v = next(iterator)
weight = next(iterator)
direction = next(iterator)
graph[u].append((v, weight))
reverse_graph[v].append((u, weight))
if direction == 1:
graph[v].append((u, weight))
reverse_graph[u].append((v, weight))
friend_count = next(iterator)
friends = [next(iterator) for _ in range(friend_count)]
from_start = dijkstra(graph, start)
to_target = dijkstra(reverse_graph, target)
if friend_count == 0:
print(2 * from_start[target])
return
between = [[0] * friend_count for _ in range(friend_count)]
for i, position in enumerate(friends):
distance = dijkstra(graph, position)
for j, other in enumerate(friends):
between[i][j] = distance[other]
state_count = 1 << friend_count
dp = [[INF] * friend_count for _ in range(state_count)]
for i, position in enumerate(friends):
dp[1 << i][i] = from_start[position]
for mask in range(1, state_count):
remaining = (state_count - 1) ^ mask
for last in range(friend_count):
current = dp[mask][last]
if current == INF:
continue
bits = remaining
while bits:
bit = bits & -bits
nxt = bit.bit_length() - 1
new_mask = mask | bit
candidate = current + between[last][nxt]
if candidate < dp[new_mask][nxt]:
dp[new_mask][nxt] = candidate
bits -= bit
walk_time = [10 * to_target[position] for position in friends]
subset_max = [0] * state_count
for mask in range(1, state_count):
bit = mask & -mask
index = bit.bit_length() - 1
subset_max[mask] = max(subset_max[mask ^ bit], walk_time[index])
all_friends = state_count - 1
answer = max(2 * from_start[target], subset_max[all_friends])
for mask in range(1, state_count):
drive = min(
dp[mask][last] + to_target[friends[last]]
for last in range(friend_count)
)
if drive == INF:
continue
walk = subset_max[all_friends ^ mask]
answer = min(answer, max(2 * drive, walk))
print(answer)
solve()
复杂度分析
时间复杂度：$O((k+2)(n+m)\log n+2^k k^2)$。共执行 $k+2$ 次 Dijkstra，状压转移枚举状态、终点和下一位朋友。
空间复杂度：$O(n+m+k^2+2^k k)$，包括正反图、关键点距离和 DP 表。
易错点
- 到餐厅的距离必须在反图上从餐厅出发求得。
- 一个朋友都不接时，答案仍需与所有朋友的步行时间取最大值。
- 道路和路口可以重复经过，因此关键点之间可以直接使用最短路拼接。
小结
- 第一题把等距关系转成平方距离分组，每组用有序对计数。
- 第二题利用需求数不超过 20，把集合覆盖压成 $2^k$ 个状态。
- 第三题先做最短路降维，再用旅行商型状压 DP 处理接人集合与顺序。