写在前面

本次给大家带来2026年10月21日华为非AI方向笔试题的3道题，

涉及到的岗位是：通软，嵌软，测试，普通算法(岗位名中不包含AI)以及数据科学，考试内容和报考部门无关，只和岗位有关。

需要我整理的机考一周速成题单可访问文章底部左侧：阅读原文

每周2举行华为机考公开模拟赛，自主命题，贴合考点，欢迎各位参与。

第1题-故障域时标同步(150分)

题目内容

整套装置里安放了  块转发芯片，编号从  编到 。报文进出这些芯片时，时间戳必须对齐。对齐靠芯片互相传递时标信息完成，这一过程叫做时标同步。

对齐遵守下列约定。

• 每块芯片把自身的时标权重  写进时标信息，再沿着尚未断开的链路，把信息交给所有还能走到的芯片。
• 能够彼此走到的芯片组成一个时标域。域内挑出权重  最高的芯片当作时标源，其他芯片改用它的时标。若好几块芯片的权重同为最高，就改挑其中编号最小的那一块。走不到任何其他芯片的，自己单独组成一个时标域。

眼下大量链路已经损坏，不少芯片再也走不到对方，装置会裂成好几个时标域。排查并修复时，要查出指定芯片正跟随哪一个时标源，也就是它所在域里被挑中的那块芯片的编号。

输入描述

评测机经由标准输入送入全部数据。

• 第一行是两个整数  和 。 为芯片块数， 为仍然保留的链路条数。
• 第二行是  个整数，按编号  到  的顺序，给出每块芯片的时标权重 。
• 其后  行，每行两个整数  和 ，表示编号  与编号  之间有一条双向链路。同一对端点可以写多次，芯片也可以连到自己，这些写法都不增加新的可达关系。
• 下一行是一个整数 ，表示询问次数。
• 最后一行是  个整数 ，为被点名芯片的编号。点名从左到右各回答一次。

数据范围：

输出描述

只打印一行。这一行含有  个整数，彼此以单个空格相隔，开头和结尾都不留空格。从左往右，第  个整数就是第  次询问所对应的时标源编号。

样例1

输入

5 34 1 4 7 20 22 13 442 4 1 0

输出

0 3 0 0

说明

• 三条链路把五块芯片分成两块：编号 、、 互相走到，编号 、 互相走到。
• 前一块的权重是 、、。最高权重为 ，编号  与编号  并列，取更小的编号 。
• 后一块的权重是 、，被挑中的是编号 。
• 四次点名依次是 、、、，答案依次是 、、、。

题解

解题思路

还能互相走到的芯片，构成无向图上的一个连通块。芯片连向自己，或者同一对端点写了多次，都不会让连通块变大或变小。每个连通块里，时标权重最大的芯片是时标源；权重并列时，编号更小的芯片是时标源。一次询问只需要回答这块芯片所在连通块的时标源编号。

1. 用并查集维护连通关系。每一条双向链路都把两个端点合并到同一块。两端已经同块时直接跳过，自环和重复链路都落在这里。
2. 查找代表元时把路径压平，合并时按秩把矮的一块挂到高的一块下面，这样一条长链也不会把查找拖成线性。
3. 链路全部处理完以后，按编号从小到大扫描芯片。把当前芯片和它所在块已经记下的时标源比较：权重更大就换上它；权重相同则留下编号更小的。没有任何链路的芯片单独成块，时标源就是它自己。
4. 对每次询问，先找到该芯片的代表元，再读出代表元上保存的时标源编号。

复杂度分析

• 时间复杂度：。每条链路合并一次，每块芯片和每次询问各查找一次。按秩合并配合路径压缩之后，单次查找接近常数。
• 空间复杂度：。父节点、秩、权重，以及每个连通块的时标源，都只随芯片块数增长。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

deffind_root(parent, x):# 先走到代表元，再把沿途芯片直接挂上去，避免递归把长链撑爆    root = xwhile parent[root] != root:        root = parent[root]while parent[x] != root:        nxt = parent[x]        parent[x] = root        x = nxtreturn rootdefunite(parent, rank, a, b):# 两端已在同一块时直接返回，自环和重复链路都落在这里    a = find_root(parent, a)    b = find_root(parent, b)if a == b:returnif rank[a] < rank[b]:        a, b = b, a    parent[b] = aif rank[a] == rank[b]:        rank[a] += 1defchoose_source(chip_count, weight, links, queries):# 每块芯片起初自成一块    parent = list(range(chip_count))    rank = [0] * chip_countfor u, v in links:        unite(parent, rank, u, v)# -1 表示该连通块还没有时标源    source = [-1] * chip_countfor i in range(chip_count):        root = find_root(parent, i)        best = source[root]# 权重更高者优先；权重相同则编号更小者优先if best == -1or weight[i] > weight[best] or (weight[i] == weight[best] and i < best):            source[root] = ireturn [source[find_root(parent, g)] for g in queries]defmain():# 第一行：芯片块数、仍保留的链路条数    header = input().split()    chip_count = int(header[0])    link_count = int(header[1])# 第二行：按编号从 0 开始的时标权重    weight = list(map(int, input().split()))    links = []for _ in range(link_count):        parts = input().split()        links.append((int(parts[0]), int(parts[1])))# 询问次数，以及被点名的芯片编号    query_count = int(input())    queries = list(map(int, input().split()))if len(queries) != query_count:        queries = queries[:query_count]    answer = choose_source(chip_count, weight, links, queries)    print(" ".join(str(x) for x in answer))if __name__ == "__main__":    main()

第2题-数字分列最小差(150分)

题目内容

这里有一列正整数，长度记为 。列中每个数只取  到 ，并且同一个数可以反复出现。

需要把这些数拆进两个部分，每一边至少放一个数，每个数正好被用一次。两边各自占据的位置不必连在一起。同一边内部可以打乱先后，再顺着书写顺序连成一个整数。希望得到的两个整数尽量靠近。比较时只保留不小于零的差：较大的那个整数叫做 ，较小的叫做 ，二者的差记作 。

把所有能使  达到最小的整数对都列出来。每一行写一组 、、。若不同的拆法拼出了同一对整数，这一对只保留一次。多组结果里  一样小时，按  由小到大逐行给出。

输入描述

评测机经由标准输入送入全部数据。

• 第一行是一个整数 ，表示这一列有多长。
• 第二行是  个整数 ，相邻两项之间用空格隔开。

数据范围：

输出描述

• 先输出一行整数 ，表示达到最小差的整数对有多少组。
• 再输出  行，每一行写出三个整数 。它们满足 ，并且 ，其中  就是那个最小差。行与行之间按  由小到大排列。

样例1

输入

27 2

输出

17 2 5

说明

• 只有两个数，只能一边放一个。
• 较大的是 ，较小的是 ，差为 。不存在更小的差。

题解

解题思路

每个数字恰好进入两个部分中的一个，两边都不能是空的。同一边里的数字可以任意排列，再连成一个整数。把较大的整数记为 ，较小的记为 ，差是 。需要列出所有使  最小的整数对。不同拆法如果拼出同一对整数，只保留一次，并按  从小到大输出。

1. 长度不超过 ，用二进制掩码枚举每个数字分到哪一边。掩码为  或全  时有一边为空，直接跳过。左右对调还是同一个划分，因此只处理掩码较小的那一次。数字相同的时候，不同掩码可能对应同一组数字，这种划分只计算一次。
2. 每一边先排序，再按字典序生成下一个排列，并把排列拼成整数。重复数字不会走出新的排列，因此相同整数只会出现一次。
3. 两边的整数两两配对。比较时使用临时变量，把较大值放在前面再计算差值，避免改写循环变量后影响下一次配对。差值变小就清空已保存的整数对；差值等于当前最小值就把这一对放进集合。
4. 集合按较大整数升序输出。第一行是对数，后面每一行依次写出较大整数、较小整数和差值。

复杂度分析

• 时间复杂度：。各个划分两侧的不重复排列两两组合，总次数与  同阶。数字大量重复时，实际排列数会远小于这个上界。
• 空间复杂度：。要保存一侧能拼出的整数，以及达到最小差的那些整数对。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

defform_numbers(digits):# 先排序，再按字典序取下一个排列。重复数字不会产生新的整数    digs = sorted(digits)    numbers = []whileTrue:        value = 0for digit in digs:            value = value * 10 + digit        numbers.append(value)        index = len(digs) - 2while index >= 0and digs[index] >= digs[index + 1]:            index -= 1if index < 0:break        swap_index = len(digs) - 1while digs[swap_index] <= digs[index]:            swap_index -= 1        digs[index], digs[swap_index] = digs[swap_index], digs[index]        digs[index + 1 :] = reversed(digs[index + 1 :])return numbersdefmin_pairs(digits):    count = len(digits)    full = (1 << count) - 1    best = None    pairs = set()    visited = set()for mask in range(1, full):        other = full ^ mask# 交换两边会得到同一个划分，只处理掩码较小的那一次if mask > other:continue        left = tuple(sorted(digits[i] for i in range(count) if (mask >> i) & 1))        right = tuple(sorted(digits[i] for i in range(count) if (other >> i) & 1))# 相同数字换位置会得到同一组数字，这种划分只算一次        key = (left, right) if left <= right else (right, left)if key in visited:continue        visited.add(key)for left_value in form_numbers(left):for right_value in form_numbers(right):# 用临时变量比较，避免把循环变量改掉后串到下一次if left_value >= right_value:                    large, small = left_value, right_valueelse:                    large, small = right_value, left_value                diff = large - smallif best isNoneor diff < best:                    best = diff                    pairs = {(large, small)}elif diff == best:                    pairs.add((large, small))return sorted(pairs)defmain():# 第一行是数字个数    length = int(input())# 第二行是每个数字，取值在 1 到 9    digits = list(map(int, input().split()))if len(digits) != length:        digits = digits[:length]    answer = min_pairs(digits)# 第一行输出方案数，后面每行是较大数、较小数和差    print(len(answer))for large, small in answer:        print(large, small, large - small)if __name__ == "__main__":    main()

第3题-染后最长同色段(300分)

题目内容

现有一条带子，长度记作 。开始的时候，带子上每个格子的颜色都不一样。

随后要按给定顺序做  次覆写。每一次指定一个闭区间 ，把其中每个格子都改成颜色 。

如果从第  格到第  格这一段里，格子的颜色完全一致，就把  叫做一条同色段。

每当一次覆写做完，都要汇报此刻整条带子上同色段的最大长度。

开始时，第  格的颜色等于它自己的编号 ， 从  取到 。

每次覆写给出三个整数 、、，含义是把闭区间  里的颜色统一写成 。

输入描述

• 第一行给出两个整数  和 。 是带子的长度， 是覆写的次数。
• 后面还有  行。每一行三个整数 ，按先后对应一次覆写。

数据范围：

输出描述

共写出  行。第  行一个整数，表示第  次覆写完成之后，同色段的最大长度。

样例1

输入

7 43 5 26 7 21 1 24 4 8

输出

4673

说明

开始时颜色依次是 。

• 第一次把  改成 ，得到 。第  格到第  格都是 ，长度 。
• 第二次把  改成 ，得到 。从第  格一直到末尾都是 ，长度 。
• 第三次把第  格改成 ，七格全是 ，长度 。
• 第四次把第  格改成 ，得到 。左右两段  都是长度 ，答案是 。

题解

解题思路

采用线段树 + 懒标记算法。

线段树每个节点维护：

• ：区间最左端的颜色。
• ：区间最右端的颜色。
• ：从左端开始的最长同色段长度。
• ：从右端开始的最长同色段长度。
• ：区间内最长同色段长度。
• ：区间统一覆写的懒标记。

初始时第  格颜色为 。每次将区间  覆写为 ：若线段树节点被完全覆盖，就直接更新其颜色、长度及懒标记；否则下传懒标记，递归修改子节点，再合并信息。

合并时，先取左右子节点的最大同色段长度。如果左子节点的右端颜色与右子节点的左端颜色相同，还要考虑跨越中点的同色段，其长度为左子节点的  加上右子节点的 。

每次操作结束后，根节点的  即为答案。

复杂度分析

• 时间复杂度：。建树需要 ，每次区间修改需要 。
• 空间复杂度：。线段树及懒标记数组占用  空间。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

defsolve(a, ops):    n = a * 4 + 5    lc = [0] * n    rc = [0] * n    pre = [0] * n    suf = [0] * n    mx = [0] * n    tag = [0] * n# 合并左右子节点defpush_up(p, l, r):        m = (l + r) // 2        x, y = p * 2, p * 2 + 1        lc[p], rc[p] = lc[x], rc[y]        pre[p], suf[p] = pre[x], suf[y]        mx[p] = max(mx[x], mx[y])if rc[x] == lc[y]:            mx[p] = max(mx[p], suf[x] + pre[y])if pre[x] == m - l + 1:                pre[p] += pre[y]if suf[y] == r - m:                suf[p] += suf[x]# 整段统一染色defapply(p, length, w):        lc[p] = rc[p] = tag[p] = w        pre[p] = suf[p] = mx[p] = length# 建树defbuild(p, l, r):if l == r:            lc[p] = rc[p] = l            pre[p] = suf[p] = mx[p] = 1return        m = (l + r) // 2        build(p * 2, l, m)        build(p * 2 + 1, m + 1, r)        push_up(p, l, r)# 下传懒标记defpush_down(p, l, r):if tag[p]:            m = (l + r) // 2            apply(p * 2, m - l + 1, tag[p])            apply(p * 2 + 1, r - m, tag[p])            tag[p] = 0# 区间覆写defupdate(p, l, r, ql, qr, w):if ql <= l and r <= qr:            apply(p, r - l + 1, w)return        push_down(p, l, r)        m = (l + r) // 2if ql <= m:            update(p * 2, l, m, ql, qr, w)if qr > m:            update(p * 2 + 1, m + 1, r, ql, qr, w)        push_up(p, l, r)    build(1, 1, a)    ans = []for l, r, w in ops:        update(1, 1, a, l, r, w)        ans.append(str(mx[1]))return ansif __name__ == "__main__":import sys    input = sys.stdin.buffer.readline    A, B = map(int, input().split())    ops = [tuple(map(int, input().split())) for _ in range(B)]    print("\n".join(solve(A, ops)))