大厂真题 / 华为

华为 2026-10-21 笔试真题 - 研发岗

本场考试概述

考试时间：2026年10月21日

考试岗位：研发岗

难度评级：中等

考点分析：

• 第一题：并查集、连通块最优代表（简单）。
• 第二题：多重集合划分、排列枚举、二分查找（中等）。
• 第三题：区间赋值、区间信息合并、懒标记线段树（中等偏难）。

建议策略：

• 第一题把“并查集的结构根”和“业务上的时标源”分开维护，便能同时使用按大小合并和路径压缩。
• 第二题先区分两数的位数是否相等，再决定是否枚举排列；相同数字必须去重。
• 第三题采用有最坏复杂度保证的区间数据结构，不把 Python 有序列表的插入、删除误当成对数操作。

第 1 题：时标同步

题目描述

系统有 $N$ 个芯片，编号为 $0$ 到 $N-1$。芯片 $i$ 的时标优先级为 $pri_i$。剩余通信链路是双向的，时标信息可以沿链路传递，因此每个连通分量构成一个时标域。

每个时标域选择一个芯片作为时标源：优先级最大的芯片优先；如果最大优先级对应多个芯片，则选编号最小的芯片。域内所有芯片同步这个时标源。

给定故障后仍然连通的链路，以及若干待查询芯片，输出每个查询芯片所属时标域的时标源编号。没有任何链路的芯片独自构成一个域。

输入格式与约束

• 第一行是 $N,M$：芯片数和链路数，$1\le N\le 10^5$，$0\le M\le 2\times 10^5$。
• 第二行是 $N$ 个优先级，$0\le pri_i\le 10^5$。
• 接下来 $M$ 行，每行两个编号 $X,Y$，表示二者之间有双向链路，$0\le X,Y<N$。
• 下一行是查询数 $Q$，$1\le Q\le 10^5$。
• 最后一行是 $Q$ 个查询编号 $Z$，$0\le Z<N$。

输出格式

输出一行 $Q$ 个整数，按查询顺序给出时标源编号，使用空格分隔。

样例 1

输入

4 2
1 3 2 2
0 1
3 2
3
1 2 0

输出

1 2 1

解释：域 ${0,1}$ 中芯片 $1$ 的优先级更大；域 ${2,3}$ 中两个芯片优先级相同，选择编号较小的 $2$。因此查询 $1,2,0$ 分别得到 $1,2,1$。

思路分析

第一步：连通关系只需要建立一次。

每个查询都从对应芯片重新搜索整个连通块，会重复遍历同一片网络。题目没有在线删除链路的操作，可以先处理全部链路，再回答查询。并查集正好用于维护这种连通分组。

第二步：把结构根与时标源分开。

若强制把优先级最高的芯片当根，就不能自由地按树大小合并。更稳妥的方式是维护三个数组：

• parent：并查集父节点。
• size：根对应的集合大小。
• best：根对应的集合中，优先级最大、并列时编号最小的芯片。

合并两个集合时，小树挂到大树下面；业务代表只需比较两个旧代表，无须扫描整个集合。结构根不一定是答案，查询应返回 best[find(z)]。

第三步：处理重复连接和边界。

自环、重边以及已经连通的两个芯片都不需要再次合并。查找使用迭代路径压缩，避免递归深度问题。每个芯片最初独立成域，代表就是自己，因此孤立点自然得到正确答案。

正确性证明

初始化时，每个集合只有一个芯片，best 显然正确。

假设合并前两个集合的 best 都正确。新集合中的最优芯片必然是两个旧集合最优芯片中的较优者：任何非代表芯片都不可能优于本集合的代表。按优先级、编号比较二者后，新的 best 仍然正确。按大小选择结构根不会改变集合成员，也不会改变这个结论。

处理完所有链路后，并查集集合恰好是图的连通分量。因此查询返回的 best[find(z)] 就是所在时标域按规则选择的时标源。

题解代码

import sys
input = sys.stdin.readline


def time_sources(n, priority, edges, queries):
    parent = list(range(n))
    size = [1] * n
    best = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for x, y in edges:
        rx, ry = find(x), find(y)
        if rx == ry:
            continue
        if size[rx] < size[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        size[rx] += size[ry]
        a, b = best[rx], best[ry]
        if priority[b] > priority[a] or (priority[b] == priority[a] and b < a):
            best[rx] = b
    return [best[find(z)] for z in queries]


def solve():
    n, m = map(int, input().split())
    priority = list(map(int, input().split()))
    edges = (tuple(map(int, input().split())) for _ in range(m))
    # 先消费链路迭代器，查询在连通关系建立之后才读入。
    answers = time_sources(n, priority, edges, range(n))
    q = int(input())
    queries = list(map(int, sys.stdin.read().split()))
    print(' '.join(str(answers[z]) for z in queries[:q]))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O((N+M+Q)\alpha(N))$，其中 $\alpha$ 是反阿克曼函数。代码先求出全部芯片的代表，再直接回答查询；按大小合并和路径压缩保证并查集操作的均摊界。

空间复杂度：$O(N+Q)$。链路逐行读取，不保留全部边；并查集、全部芯片答案占 $O(N)$，查询及输出缓冲占 $O(Q)$。

第 2 题：最小整数差值

题目描述

给定 $M$ 个取值在 $1$ 到 $9$ 之间的数字，允许重复。将所有数字分成两个非空部分，每个部分内部可以任意排列，再依次拼接成一个整数。每个数字必须且只能使用一次。

把两个整数记为 $A,B$，要求 $A\ge B$。求最小差值 $C=A-B$，并输出所有达到这个最小差值的不同数值组合。

相同数字的不同下标分配不算不同结果；交换两个相等的整数也不产生新结果。输出按 $A$ 从小到大排列。

输入格式与约束

• 第一行是 $M$，$2\le M\le 10$。
• 第二行是 $M$ 个数字 $a_i$，$1\le a_i\le 9$。
• 两部分均非空；输入不含数字 $0$，不存在前导零问题。

输出格式

第一行输出最优组合数 $N$。接下来 $N$ 行，每行输出 A B C，其中 $A-B=C$，所有行使用同一个全局最小差值 $C$。

样例 1

输入

2
4 5

输出

1
5 4 1

解释：只能分别取 $5$ 和 $4$，差值为 $1$。

样例 2

输入

3
5 4 1

输出

1
14 5 9

解释：把 $1,4$ 拼成 $14$，另一部分为 $5$，得到最小差值 $9$。

样例 3

输入

4
1 2 2 1

输出

2
12 12 0
21 21 0

解释：两部分各使用一个 $1$ 和一个 $2$，既可以都拼成 $12$，也可以都拼成 $21$。两组数值结果都必须输出。

思路分析

第一步：按数字的使用次数划分，而不是按下标划分。

记 total[d] 为数字 $d$ 的出现次数。依次枚举左半部分使用该数字的次数 left[d]，取值为 $0$ 到 total[d]；右半部分的次数随之确定。

这样天然消除了相同数字的下标差异。只处理左边位数不少于右边且两边非空的划分。

第二步：位数不同，直接取两端极值。

不含前导零时，位数多的整数一定更大。固定这个划分后，左侧升序拼接得到最小的 $A$，右侧降序拼接得到最大的 $B$，二者组合就是该划分的最小差值。

不能把“左右尽量等长”当作未经证明的剪枝。这里保留所有合法长度划分，只是不等长时不枚举排列。

第三步：位数相同，枚举一侧并二分另一侧。

只有 $M$ 为偶数时才会出现等长划分。两边都至多五位，可以分别生成不同排列对应的整数，得到有序集合 left_values、right_values。

固定左侧整数 $A$ 后，在右侧找不超过 $A$ 的最大值 $B$，即可使这个 $A$ 对应的非负差值最小。用 bisect_right 找到第一个大于 $A$ 的位置，前一项就是候选；若不存在则跳过。

等长划分的左右互换也会被枚举，因此把较大数限制在左边不会漏掉答案。

第四步：保留全部并列最优解。

维护最小差值 best 和答案集合。发现更小差值时清空旧答案，相同差值时加入新组合，最后按 $A$ 升序输出。差值固定后，$B=A-best$，所以按三元组排序与要求一致。

正确性证明

次数枚举覆盖每种数字多重集合划分，且没有遗漏任何合法分配。

对不等长划分，任意其他排列都满足 $A\ge A_{\min}$、$B\le B_{\max}$，因此 $A-B\ge A_{\min}-B_{\max}$，取两端极值最优。

对等长划分，枚举覆盖所有可能的左侧整数。固定 $A$ 后，不超过它的最大右侧整数使差值最小；若其他右侧整数也能形成全局最优差值，它必须与该候选具有相同数值。因此二分只保留一个候选不会遗漏不同最优组合。

全局最优解必然也是所属划分、所属 $A$ 下的最优解。算法检查了这些候选，并用集合去重，故输出恰好是全部不同的最优数值组合。

题解代码

import sys
from bisect import bisect_right
from itertools import permutations, product
input = sys.stdin.readline


def minimum_pairs(digits):
    m = len(digits)
    total = [digits.count(d) for d in range(1, 10)]
    best = None
    answers = set()

    def consider(a, b):
        nonlocal best
        delta = a - b
        if best is None or delta < best:
            best = delta
            answers.clear()
        if delta == best:
            answers.add((a, b, delta))

    def numbers(chars):
        return sorted({int(''.join(p)) for p in permutations(chars)})

    for counts in product(*(range(c + 1) for c in total)):
        k = sum(counts)
        if k < m - k or k == m:
            continue
        left = [str(d) for d in range(1, 10) for _ in range(counts[d - 1])]
        right = [str(d) for d in range(1, 10)
                 for _ in range(total[d - 1] - counts[d - 1])]
        if k > m - k:
            consider(int(''.join(left)), int(''.join(reversed(right))))
            continue
        left_values, right_values = numbers(left), numbers(right)
        for a in left_values:
            pos = bisect_right(right_values, a)
            if pos:
                consider(a, right_values[pos - 1])
    return sorted(answers)


def solve():
    m = int(input())
    digits = list(map(int, input().split()))
    answers = minimum_pairs(digits[:m])
    print(len(answers))
    for row in answers:
        print(*row)


if __name__ == '__main__':
    solve()

复杂度分析

设 $D$ 为次数划分数，$E$ 为等长划分数，$R$ 为输出组合数。$D=\prod_{d=1}^{9}(total_d+1)\le 2^M$。当 $M$ 为偶数时，令 $k=M/2$，有 $E\le\binom{M}{k}$；奇数时 $E=0$。

时间复杂度：$O(DM+E\cdot k!\cdot(k+\log(k!))+R\log R)$。等长划分中生成排列、转整数、排序和二分占主要开销，且 $k\le 5$。奇数长度时只需划分与拼接，不需要排列枚举。

空间复杂度：$O(M+k!+R)$，包括当前划分、当前两组排列值和答案集合；没有等长划分时可去掉 $k!$ 项。

第 3 题：区间染色后的最长稳定段

题目描述

有一条包含 $n$ 个位置的带子，位置从 $1$ 编号到 $n$，初始位置 $i$ 的颜色就是整数 $i$。

依次执行 $m$ 次染色。每次给出 $l,r,c$，将闭区间 $[l,r]$ 内的所有位置改成颜色 $c$。

一个连续区间内所有位置的颜色相同时，称它为稳定段。每次染色后，输出整条带子上最长稳定段的长度。相同颜色可以跨越本次染色边界，与原有位置连成更长的段。

输入格式与约束

• 第一行是 $n,m$，$1\le n,m\le 10^5$。
• 接下来 $m$ 行，每行是 $l,r,c$，$1\le l\le r\le n$，$1\le c\le 10^9$。

输出格式

输出 $m$ 行，每行是对应操作结束后的最长稳定段长度。

样例 1

输入

10 5
2 5 7
6 8 7
3 7 4
1 10 1
4 4 9

输出

4
7
5
10
6

解释：

• 第一次操作后，位置 $2$ 到 $5$ 连续为颜色 $7$，长度为 $4$。
• 第二次操作后，位置 $2$ 到 $8$ 合并成颜色 $7$ 的稳定段，长度为 $7$。
• 第三次操作把位置 $3$ 到 $7$ 变成颜色 $4$，最长长度为 $5$。
• 第四次操作把整条带子变成颜色 $1$，最长长度为 $10$。
• 最后只改位置 $4$，右侧位置 $5$ 到 $10$ 仍为颜色 $1$，长度为 $6$。

思路分析

第一步：为什么只维护最长长度不够？

如果把一个区间分成左右两半，合并后的最长同色段可能完全在左边、完全在右边，也可能跨越中点。跨中点的答案取决于左半的同色后缀、右半的同色前缀，以及二者边界颜色是否相同。

因此每个线段树节点维护：

• left_color、right_color：左右端点颜色。
• prefix：从左端点开始的最长同色前缀长度。
• suffix：到右端点结束的最长同色后缀长度。
• best：整个区间的最长同色段长度。

区间长度由节点边界确定。

第二步：合并左右儿子。

先令父节点答案为两个儿子的 best 最大值。如果左儿子右端颜色等于右儿子左端颜色，则跨中点候选长度为：

父节点前缀通常等于左儿子的前缀；只有左儿子整段同色、且中点两侧同色，才可再拼上右儿子的前缀。后缀的处理完全对称。

第三步：区间赋值使用懒标记。

若一次染色完全覆盖节点区间，就不必继续逐格修改：该节点两端颜色都变成 $c$，前缀、后缀、最优长度都等于区间长度，同时记录赋值标记。

以后需要访问它的部分子区间时，再把标记下传给左右儿子。更新结束后向上合并，根节点的 best 就是全局答案。颜色均为正数，可以用 $0$ 表示“没有待下传的赋值标记”。

实现提醒：初始叶子的颜色必须设为位置编号，不能用永远不会与新颜色相同的占位值。按段维护的思路也可行，但 Python 的 list.insert 和中间删除是线性操作，不能据此声称每次操作都是 $O(\log n)$。

正确性证明

叶子只包含一个位置，各项长度为 $1$，颜色等于该位置当前颜色，信息正确。

假设两个儿子的信息正确。任意父区间内的连续同色段要么完全位于一侧，要么跨中点。前两类由两个 best 覆盖；第三类存在的必要条件是中点两侧同色，其最大长度恰为左后缀加右前缀。因此合并得到的 best 正确。前缀、后缀的延伸条件同样精确。

整段赋值后节点内所有位置同色，直接把三个长度置为区间长度正确；标记下传只是把同一赋值作用于两个儿子，不改变实际颜色。由更新路径上的归纳，根节点始终正确描述整条带子，所以每次输出正确。

题解代码

import sys
input = sys.stdin.readline


def longest_segments(n, operations):
    capacity = 4 * n + 5
    left_color = [0] * capacity
    right_color = [0] * capacity
    prefix = [0] * capacity
    suffix = [0] * capacity
    best = [0] * capacity
    lazy = [0] * capacity

    def pull(node, left_len, right_len):
        a, b = node * 2, node * 2 + 1
        left_color[node] = left_color[a]
        right_color[node] = right_color[b]
        prefix[node], suffix[node] = prefix[a], suffix[b]
        best[node] = max(best[a], best[b])
        if right_color[a] == left_color[b]:
            best[node] = max(best[node], suffix[a] + prefix[b])
            if prefix[a] == left_len:
                prefix[node] += prefix[b]
            if suffix[b] == right_len:
                suffix[node] += suffix[a]

    def build(node, lo, hi):
        if lo == hi:
            left_color[node] = right_color[node] = lo
            prefix[node] = suffix[node] = best[node] = 1
            return
        mid = (lo + hi) // 2
        build(node * 2, lo, mid)
        build(node * 2 + 1, mid + 1, hi)
        pull(node, mid - lo + 1, hi - mid)

    def apply(node, length, color):
        left_color[node] = right_color[node] = color
        prefix[node] = suffix[node] = best[node] = length
        lazy[node] = color

    def update(node, lo, hi, ql, qr, color):
        if ql <= lo and hi <= qr:
            apply(node, hi - lo + 1, color)
            return
        mid = (lo + hi) // 2
        if lazy[node]:
            apply(node * 2, mid - lo + 1, lazy[node])
            apply(node * 2 + 1, hi - mid, lazy[node])
            lazy[node] = 0
        if ql <= mid:
            update(node * 2, lo, mid, ql, qr, color)
        if qr > mid:
            update(node * 2 + 1, mid + 1, hi, ql, qr, color)
        pull(node, mid - lo + 1, hi - mid)

    build(1, 1, n)
    answers = []
    for l, r, c in operations:
        update(1, 1, n, l, r, c)
        answers.append(best[1])
    return answers


def solve():
    n, m = map(int, input().split())
    operations = (tuple(map(int, input().split())) for _ in range(m))
    print('\n'.join(map(str, longest_segments(n, operations))))


if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：$O(n+m\log n)$。建树为 $O(n)$，每次区间赋值为 $O(\log n)$，读取根节点答案为 $O(1)$。

空间复杂度：$O(n+m)$。线段树占 $O(n)$，递归栈深度为 $O(\log n)$，代码保留 $m$ 个答案统一输出。若流式输出，则除输出缓冲外只需 $O(n)$。

小结

• 时标同步：数据结构代表与业务代表可以分离，避免为了业务排序牺牲并查集的平衡策略。
• 最小整数差值：先用位数关系消除大部分排列，再对等长情况做精确枚举，最后统一去重。
• 区间染色：最长同色段属于可合并区间信息，关键是同时维护边界颜色、前后缀和整体最优值。