大厂真题 / 华为

华为 9.2 笔试真题 - 研发岗

本场考试概述

考试时间：2026 年 9 月 2 日

考试岗位：研发岗

题型构成：3 道编程题。

证据边界：前两题的题意、范围与样例能够完整恢复，并给出可验证的 Python ACM 解法。第 3 题材料在“可不升级”和“升级恰好 $k$ 条边”之间存在口径冲突；常见的分层最宽路写法还会把绕行、重复经过同一条边算作合法路径，与“一条链路只能升级一次”不符。因此本文保留可确认的题面、样例与歧义分析，不发布无法证明正确的代码。

第 1 题：被城墙包围的村庄

题目描述

给定一张 $m\times n$ 的地图。X 表示城墙，O 表示村庄；村庄只沿上、下、左、右连通。若一个村庄能经由若干村庄到达地图边界，它不会被改变；否则它所在的封闭区域会全部变成城墙。求最终被改建的村庄格子数。

输入描述

第一行输入两个整数 $m,n$，满足 $1\le m,n\le 500$。

接下来 $m$ 行，每行是长度为 $n$、仅含 X 和 O 的字符串。

输出描述

输出无法通过村庄道路到达边界的 O 的数量。

样例

输入

4 4
XXXX
XOOX
XXOX
XOXX

输出

算法

一个村庄能到达边界，当且仅当它与某个边界上的 O 连通。把四条边上的所有 O 同时放入队列，执行多源 BFS，标记所有可从边界到达的村庄；最后统计未被标记的 O。

正确性证明

引理 1：BFS 标记的每个格子都能到达边界。初始格子就在边界；之后每个新标记格子都与一个已标记村庄相邻。沿父链最终可到达某个初始边界格，故引理成立。

引理 2：每个能到达边界的村庄都会被 BFS 标记。设该村庄到某个边界村庄存在全由 O 构成的路径。边界端点是 BFS 起点，BFS 会沿路径逐格扩展，因而最终标记该村庄。

由两条引理，未标记的 O 恰好是不能到达边界、需要改建的村庄，算法统计结果正确。

Python ACM 题解

import sys
from collections import deque


def solve():
    input = sys.stdin.buffer.readline
    m, n = map(int, input().split())
    board = [input().strip() for _ in range(m)]

    free = [[False] * n for _ in range(m)]
    queue = deque()

    for i in range(m):
        for j in (0, n - 1):
            if board[i][j] == ord("O") and not free[i][j]:
                free[i][j] = True
                queue.append((i, j))
    for j in range(n):
        for i in (0, m - 1):
            if board[i][j] == ord("O") and not free[i][j]:
                free[i][j] = True
                queue.append((i, j))

    for_x = ((1, 0), (-1, 0), (0, 1), (0, -1))
    while queue:
        x, y = queue.popleft()
        for dx, dy in for_x:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                if board[nx][ny] == ord("O") and not free[nx][ny]:
                    free[nx][ny] = True
                    queue.append((nx, ny))

    answer = sum(
        board[i][j] == ord("O") and not free[i][j]
        for i in range(m)
        for j in range(n)
    )
    print(answer)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(mn)$。每个格子至多入队一次，并进行一次最终统计。

空间复杂度：$O(mn)$，用于标记数组与 BFS 队列。

易错点

应从所有边界村庄同时搜索，而不是只处理四个角。
入队时立即标记，避免同一格被重复入队。
$m=1$ 或 $n=1$ 时所有村庄都位于边界，答案为 0。
最大连通块可有 $2.5\times10^5$ 个格子，不宜使用递归 DFS。

第 2 题：B 进制定长回文数

题目描述

给定进制 $B$、长度 $L$ 和序号 $K$，求从小到大排列的、第 $K$ 个长度恰为 $L$ 且不含前导零的 $B$ 进制回文数，并输出它的十进制值。序号从 1 开始。

输入描述

一行输入三个整数 $B,L,K$：

\[2\le B\le16,\qquad 1\le L\le60,\qquad 1\le K\le9\times10^6.\]

保证第 $K$ 个回文数存在，且答案不超过 $10^{18}$。

输出描述

输出该回文数的十进制值。

样例

输入

3 4 5

输出

三进制的对应回文数是 $21123=68{10}$。

算法

令 $h=\lceil L/2\rceil$。一个 $L$ 位回文数由前 $h$ 位唯一确定，其合法前缀从 $B^{h-1}$ 开始连续排列。由于高位优先的大小关系与前缀顺序一致，第 $K$ 个前缀为

\[half=B^{h-1}+K-1.\]

把 half 拆成恰好 $h$ 个 $B$ 进制数位。先写入全部前缀，再倒序写入最前面的 $L-h$ 位，即得到完整回文数；在拼接时用 value = value * B + digit 同步转成十进制。

正确性证明

引理 1：合法 $L$ 位回文数与首位非零的 $h$ 位前缀一一对应。给定前缀后，后 $L-h$ 位必须是相应前缀数位的逆序，故唯一；反之任一合法回文数显然给出唯一前缀。

引理 2：两个合法回文数的大小顺序与其前缀的大小顺序相同。若前缀不同，完整数第一次不同的数位必在前 $h$ 位；该位的大小已经决定两个等长 $B$ 进制数的大小。

合法前缀从 $B^{h-1}$ 起连续递增。由两条引理，第 $K$ 个回文数对应前缀 $B^{h-1}+K-1$；算法按回文定义镜像该前缀，因此输出正确。

Python ACM 题解

import sys


def solve():
    B, L, K = map(int, sys.stdin.buffer.readline().split())
    h = (L + 1) // 2
    half = B ** (h - 1) + K - 1

    digits = [0] * h
    value = half
    for i in range(h - 1, -1, -1):
        digits[i] = value % B
        value //= B

    answer = 0
    for digit in digits:
        answer = answer * B + digit
    for i in range(L - h - 1, -1, -1):
        answer = answer * B + digits[i]

    print(answer)


if __name__ == "__main__":
    solve()

复杂度分析

时间复杂度：$O(L)$。

空间复杂度：$O(L)$，用于保存前缀数位。

易错点

奇数长度时中心位不能镜像两次，镜像数位数应为 $L-h$。
K 从 1 开始，因此前缀增量是 $K-1$。
不能枚举十进制整数逐个判断回文；$L$ 可达 60。
固定宽度语言需使用 64 位整数，并避免额外计算可能溢出的巨大幂。

补充题：智慧城市网络调优（题意边界说明）

可恢复题面

有 $n$ 个城市（编号 $0$ 到 $n-1$）和 $m$ 条带正整数带宽的双向链路。选择一条从 0 到 $n-1$ 的路径；被升级的链路带宽变为原来的 2 倍，每条链路最多升级一次。目标是最大化路径升级后的瓶颈带宽，即路径上最小链路带宽。

输入第一行为 $n,m,k$，满足

\[2\le n\le100,\quad 1\le m\le1000,\quad 0\le k\le\min(10,m).\]

随后 $m$ 行为 $u,v,w$，其中 $0\le u,v<n$、$u\ne v$、$0<w<1000$。若终点不可达，输出 -1。

材料一处要求“升级恰好 $k$ 条链路”，另一处又允许“一条路径完全不升级”；样例 3 也把不升级的直连路径作为候选。因此可确认的候选口径更接近：要么不升级，要么恰好升级 $k$ 条互不相同的路径边。

示例

示例输入

示例输出

可选择路径 $0\to2\to4$，升级两条边后带宽分别为 40 和 30，瓶颈为 30。

为什么不发布分层最宽路代码

常见方案把状态写成“当前城市 + 已使用升级次数”，然后在分层图上做最大瓶颈路。它对允许重复顶点、重复边的游走是正确的，但不能保证原图中的路径是简单路径，也没有记录某条无向边是否已经升级过。

例如 $n=3,m=2,k=2$，链路为 (0,1,7) 与 (0,2,1)。分层状态可以走 $0\to1\to0\to2$，并在往返时把同一条 (0,1) 链路重复计入升级，违反“每条链路只能升级一次”；若不重复升级，它仍借绕行边凑足次数，而通常“路径”语义不允许重复顶点。

若明确允许游走且升级次数只按“经过动作”计，分层算法可以成立，但这与“每条链路最多升级一次”冲突。若采用通常的简单路径 + 恰好升级 $k$ 条不同边语义，就需要同时约束不重复顶点/边；一般图上的这类带资源简单路径优化不能由上述多项式状态压缩直接解决，现有材料也不足以证明一个标准多项式解法。

因此，本题只保留题面证据和可复核样例，不把不可靠程序包装成标准答案。若正式题面进一步明确“允许不升级”“路径是否可重复顶点/边”及升级对象的唯一性，才能据此选择正确模型。

易错点

不能用分层状态把同一条边升级多次。
“至多 $k$”“恰好 $k$”和“0 次或恰好 $k$ 次”是三个不同问题。
图论中的 walk 与通常竞赛题所称的简单路径不能混用。
样例只能验证少数输入，不能消除题面语义冲突。

这篇文章有帮助吗？

| GitHub 留言