大厂真题 / 华为

华为 5.22 笔试真题 - 研发岗

本场考试概述

考试时间：2026年5月22日 考试岗位：研发岗（国内） 难度评级：中等偏难

考点分析：

1. 第一题：RLE 块匹配 + 计数原理（难度中等）
2. 第二题：单调栈（难度中等）
3. 第三题：状态机 DP + 位掩码（难度困难）

建议策略：

1. 第一题先把 RLE 等价条件想清楚，再用乘法原理计数，避免直接暴力枚举子串
2. 第二题是单调栈模板套用，重点理解”严格递减”和”从右往左扫描”两个细节
3. 第三题观察到 \(\text{win\_size}\) 不超过 3 是关键，立刻能想到用 3 位掩码作为 DP 状态

第一题：好看的子串数

题目描述

有一个好看的串 $A$。

对于一个串 $T$，每次可以选择其中任意两个相邻且相同的字符，然后删除其中一个。例如 aab 可以在一次操作中变成 ab 或 ab 或 ab。

如果串 $T$ 可以通过若干次删除操作得到串 $A$，则串 $T$ 也是好看的串。

现在得到了一个串 $S$，需要计算 $S$ 中有多少个子串是好看的串。

两个相等但在字符串 $S$ 中出现位置不同的子串被认为是不同的子串。

输入描述

第一行包含两个整数 $n, m$，表示字符串 $A$ 和 $S$ 的长度。第二行一个长度为 $n$ 的字符串 $A$。第三行一个长度为 $m$ 的字符串 $S$。保证字符串仅包含英文小写字母。

输出描述

输出一行一个数字，表示答案。

样例

输入

1 1
a
b

输出

0

仅有一个子串 b，与 a 的字符不一致，无法通过删除操作得到 $A$。

输入

3 6
aab
aaabbb

输出

6

满足条件的 6 个子串依次为 aab、aaab、aabb、aaabb、aabbb、aaabbb。

思路分析

第一步：理解”删除相邻相同字符”的本质

“删除相邻相同字符之一”这个操作只能缩短某一个字符块的长度（例如 aaa 变成 aa），既不能跨块也不能把整块删空。因此串 $T$ 能化简成串 $A$ 等价于两个条件同时满足：

1. 两者的 RLE（Run-Length Encoding）块字符序列完全相同
2. $T$ 每个块的计数都 $\geq$ $A$ 对应块的计数

第二步：RLE 压缩

把 $A$ 和 $S$ 分别压缩成块序列。设 $A$ 共 $p$ 个块，字符 \(\text{aCh}[j]\)，计数 \(\text{aCnt}[j]\)；$S$ 共 $q$ 个块，字符 \(\text{sCh}[i]\)，计数 \(\text{sCnt}[i]\)。

第三步：枚举对齐窗口

在 $S$ 的块序列上枚举长度为 $p$ 的连续窗口。窗口内字符序列必须与 $A$ 完全一致，否则跳过。

第四步：中间块约束

窗口内的中间块（窗口首末块之外的块）会被合法子串完整包含，必须满足 \(\text{sCnt}[i+j] \geq \text{aCnt}[j]\)，任一中间块不满足即跳过该窗口。

第五步：首末块乘法计数

合法子串的左端点可以在窗口首块内滑动，右端点可以在窗口末块内滑动，左右独立可乘：

• 左端方案数 = \(\text{sCnt}[\text{left}] - \text{aCnt}[0] + 1\)
• 右端方案数 = \(\text{sCnt}[\text{right}] - \text{aCnt}[p-1] + 1\)

两数同时为正时窗口贡献为两者之积。

第六步：单块特例

当 $p = 1$ 时左右端点落在同一块内，子串长度从 \(\text{aCnt}[0]\) 到 \(\text{sCnt}[i]\) 均合法。长度为 $L$ 的子串个数为 \(\text{sCnt}[i] - L + 1\)，对 $L$ 求和得等差数列：

题解代码

import sys
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    A = input().strip()
    S = input().strip()

    # RLE 压缩
    def rle(s):
        chars = []
        counts = []
        for c in s:
            if counts and chars[-1] == c:
                counts[-1] += 1
            else:
                chars.append(c)
                counts.append(1)
        return chars, counts

    aCh, aCnt = rle(A)
    sCh, sCnt = rle(S)
    p = len(aCh)
    q = len(sCh)

    if p > q:
        print(0)
        return

    ans = 0

    if p == 1:
        # 单块：每个匹配字符块贡献 k*(k+1)/2 个长度合规的子串
        target = aCh[0]
        need = aCnt[0]
        for i in range(q):
            if sCh[i] == target and sCnt[i] >= need:
                k = sCnt[i] - need + 1
                ans += k * (k + 1) // 2
    else:
        # 多块：枚举 S 中长度为 p 的块窗口与 A 对齐
        for i in range(q - p + 1):
            # 检查字符序列是否匹配
            ok = True
            for j in range(p):
                if sCh[i + j] != aCh[j]:
                    ok = False
                    break
            if not ok:
                continue
            # 检查中间块计数是否满足
            for j in range(1, p - 1):
                if sCnt[i + j] < aCnt[j]:
                    ok = False
                    break
            if not ok:
                continue
            # 首末块可滑动边界，方案数为各自余量乘积
            left = sCnt[i] - aCnt[0] + 1
            right = sCnt[i + p - 1] - aCnt[p - 1] + 1
            if left > 0 and right > 0:
                ans += left * right

    print(ans)

solve()

复杂度分析

时间复杂度：RLE 压缩 $O(n + m)$；枚举窗口共 $O(q)$ 次，每次 $O(p)$ 检查字符与中间块，总计 $O(q \cdot p)$。

空间复杂度：$O(n + m)$，存储两段 RLE 序列。

第二题：建筑物的安全视野

题目描述

在城市规划中，建筑师需要分析建筑物之间的视野关系。给出一条街道上的一排建筑物，每个建筑物有一定的高度。对于每个建筑物，定义一个安全视野距离：从该建筑物向右看，能看到的建筑物的数量。

一个建筑物 $i$ 能够看到另一个建筑物 $j$ 的条件是：$j$ 在 $i$ 的右侧；$i$ 和 $j$ 中间没有比 $i$ 更高的建筑物遮挡（相同高度的建筑物不遮挡）；视线必须是连续的，一旦被某个更高的建筑物遮挡，就无法看到更远的建筑物（即使更远的建筑物比遮挡物更高）。

输入描述

第一行包含一个整数 $n$，表示建筑物的数量。第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$，表示每个建筑物的高度。

输出描述

输出 $n$ 个整数，用空格分隔，表示每个建筑物的安全视野距离。

样例

输入

5
3 1 4 2 5

输出

2 1 2 1 0

• 建筑物 1（高度 3）：看到建筑物 2（高度 1），看到建筑物 3（高度 4），被遮挡，视野距离 2
• 建筑物 2（高度 1）：看到建筑物 3（高度 4），被遮挡，视野距离 1
• 建筑物 3（高度 4）：看到建筑物 4（高度 2），看到建筑物 5（高度 5），被遮挡，视野距离 2
• 建筑物 4（高度 2）：看到建筑物 5（高度 5），被遮挡，视野距离 1
• 建筑物 5（高度 5）：右边没有建筑物，视野距离 0

输入

6
6 5 4 3 2 1

输出

5 4 3 2 1 0

序列严格递减，每个建筑物右侧所有建筑物都比自己矮，没有遮挡，能看到全部右侧建筑物。

思路分析

第一步：明确问题本质

求每个建筑物右侧第一个严格更高建筑的下标，再减去自身下标即为答案。暴力做法 $O(n^2)$，数据量可达 $5 \times 10^6$，必须 $O(n)$ 解决——正好是单调栈的经典场景。

第二步：从右往左扫描，维护单调栈

从右往左遍历，维护一个”待遮挡候选”栈。栈中元素是已处理过、可能成为更靠左建筑物遮挡者的下标。

第三步：保持栈的单调性——从底到顶严格递减

若栈中存在两个高度满足 $h[a] \leq h[b]$ 且 $a$ 更靠右，那 $b$ 永远轮不到去遮挡左侧建筑（$a$ 离左侧更近且高度不低于 $b$），可以淘汰。同高度不构成遮挡，保留更靠左的同高建筑没有意义，故连等号一起淘汰，栈保持严格递减。

第四步：弹栈与计算

处理位置 $i$ 时，弹出所有满足 $h[\text{top}] \leq h[i]$ 的栈顶——它们既挡不住 $i$，也挡不住未来更靠左的建筑。弹栈后：

• 栈空：右侧无更高建筑，所有右侧建筑都能看到，视野距离 = $n - 1 - i$
• 栈非空：栈顶为右侧首个严格更高建筑，视野距离 = \(\text{stk}[\text{top}] - i\)

第五步：入栈

把当前位置 $i$ 压入栈，作为后续更靠左建筑的候选遮挡者。

以 [3, 1, 4, 2, 5] 为例从右往左扫描：

• $i=4$, $h=5$：栈空，\(\text{ans}[4]=0\)，入栈 [4]
• $i=3$, $h=2$：栈顶 $h[4]=5>2$，不弹，\(\text{ans}[3]=4-3=1\)，入栈 [4,3]
• $i=2$, $h=4$：弹 3（$h[3]=2 \leq 4$），栈顶 4（$h[4]=5>4$），\(\text{ans}[2]=4-2=2\)，入栈 [4,2]
• $i=1$, $h=1$：栈顶 $h[2]=4>1$，不弹，\(\text{ans}[1]=2-1=1\)，入栈 [4,2,1]
• $i=0$, $h=3$：弹 1（$h[1]=1 \leq 3$），栈顶 2（$h[2]=4>3$），\(\text{ans}[0]=2-0=2\)，入栈 [4,2,0]

最终输出 2 1 2 1 0。

题解代码

import sys
input = sys.stdin.readline

def solve():
    n = int(input())
    h = list(map(int, input().split()))

    ans = [0] * n
    stk = []  # 存下标，栈底到栈顶高度严格递减

    # 从右往左扫描
    for i in range(n - 1, -1, -1):
        # 弹出所有不高于 h[i] 的栈顶
        while stk and h[stk[-1]] <= h[i]:
            stk.pop()
        if not stk:
            # 右侧无更高建筑，所有右侧建筑均可见
            ans[i] = n - 1 - i
        else:
            # 栈顶为右侧首个严格更高建筑
            ans[i] = stk[-1] - i
        stk.append(i)

    print(' '.join(map(str, ans)))

solve()

复杂度分析

时间复杂度：$O(n)$，每个元素至多入栈出栈各一次。

空间复杂度：$O(n)$，存储栈与答案数组。

第三题：数据传输网络调优

题目描述

有一个由 $n$ 个数据交换节点（编号为 $0$ 到 $n-1$）组成的新型数据传输网络。数据包从头节点发送，按照编号顺序依次经过每个节点的处理，最终到达尾节点。在每个节点处理时，会产生 \(\text{delay}[i]\) 单位的处理时延。

每个数据交换节点 $i$ 支持配置优先转发模式，它将会在数据包中添加特殊的标记，使数据包在本节点和后续 \(\text{win}[i]\) 个节点处理时走优先转发通道，降低处理时延（不包含本节点时 \(\text{win}[i]=0\)，则只有节点 $i$ 自身受影响）。受该标记影响的节点所产生的处理时延将不再是 \(\text{delay}[j]\)，而是 \(\text{delay}[j] - \text{opt}[i]\)（为时延优化值，若结果为负则该节点产生的处理时延为 0）。如果某个节点被前面多个节点的优先转发模式影响，它的处理时延会被减少多次。

目标是在整个网络中最多选择 $K$ 个节点配置优先转发模式，使数据包到达尾节点时产生的总处理时延最小，输出最小的总处理时延。

输入描述

第一行包含两个整数 $n, K$，分别表示网络中节点总数和最多可配置优先转发模式的节点数。第二行包含 $n$ 个整数 \(\text{delay}[i]\)，表示每个节点默认情况下产生的处理时延。第三行包含 $n$ 个整数 \(\text{win}[i]\)，表示在第 $i$ 个节点配置优先转发模式时影响的后续节点数。第四行包含 $n$ 个整数 \(\text{opt}[i]\)，表示在第 $i$ 个节点配置优先转发模式时的时延优化值。

输出描述

输出一个整数，表示通过配置后所能得到的最小的总处理时延。

样例

输入

3 1
50 40 30
3 0 1
0 50 10

输出

80

若在节点 1 配置，其作用范围为自身节点 1，节点 1 的处理时延从 40 变为 0（因为 $40 - 50 < 0$），总处理时延为 $50 + 0 + 30 = 80$，此选择最优。

输入

5 2
10 20 30 40 50
1 0 1 3 2
15 20 0 30 35

输出

65

在节点 0 和节点 3 配置优先转发模式时：节点 0 处理时延从 10 变为 0，节点 1 处理时延从 20 变为 5，节点 3 处理时延从 40 变为 10，节点 4 处理时延从 50 变为 15。总处理时延为 $0 + 5 + 30 + 10 + 15 + 5 = 65$。

思路分析

第一步：关键观察——win 值不超过 3

\(\text{win}[i] \leq 3\)，这意味着任一标记最多影响后续 3 个节点。要计算当前节点受到多少优化，只需回溯最近 3 个位置的标记状态——由此引出滑动比特掩码状态机 DP。

第二步：状态定义

设 $f[i][k][\text{mask}]$ 表示处理完前 $i$ 个节点、已用 $k$ 个标记、最近 3 个位置的”是否被标记”组成的位掩码为 \(\text{mask}\) 时，前 $i$ 个节点的最小累计处理时延。掩码第 $b$ 位表示位置 $i - 3 + b$ 是否被标记。

为什么只看最近 3 位？因为 \(\text{win}[i] \leq 3\)，能影响位置 $i$ 的标记只能来自 $i-3, i-2, i-1, i$ 四个位置——前三个由 \(\text{mask}\) 编码，最后一个是本次决策。

第三步：状态转移

枚举本节点是否标记（$b \in {0, 1}$），需要计算：

1. 累加优化值：所有仍能覆盖到节点 $i$ 的标记的 \(\text{opt}\) 值之和。检查 \(\text{mask}\) 中每一位对应的位置 \(\text{pos}\)，若 \(\text{pos} + \text{win}[\text{pos}] \geq i\) 则该标记仍有效；若本节点标记 ($b=1$) 则 \(\text{opt}[i]\) 也作用于自身。

2. 计算实际时延：\(\text{cur} = \max(0,\ \text{delay}[i] - \text{reduction})\)

3. 更新掩码：丢弃位置 $i-3$ 的标记位（已不再影响后续节点），把本次决策 $b$ 放到新掩码最高位：\(\text{newMask} = ((\text{mask} >> 1)\ \&\ 0b11)\ \|\ (b << 2)\)

第四步：转移方程

第五步：最终答案

以样例 2 选节点 0 和节点 3 配置为例验证：

• 节点 0（标记，\(\text{win}=1, \text{opt}=15\)）：自身优化 15，$\max(0, 10-15)=0$
• 节点 1（不标记）：节点 0 的标记仍覆盖（$0+1 \geq 1$），优化 15，$\max(0, 20-15)=5$
• 节点 2（不标记）：节点 0 已失效（$0+1 < 2$），无优化，$30$
• 节点 3（标记，\(\text{win}=3, \text{opt}=30\)）：自身优化 30，$\max(0, 40-30)=10$
• 节点 4（不标记）：节点 3 仍覆盖（$3+3 \geq 4$），优化 30，$\max(0, 50-30)=20$

累加 $0 + 5 + 30 + 10 + 20 = 65$。

题解代码

import sys
input = sys.stdin.readline

def solve():
    line1 = input().split()
    N, K = int(line1[0]), int(line1[1])
    delay = list(map(int, input().split()))
    win = list(map(int, input().split()))
    opt = list(map(int, input().split()))

    INF = float('inf')
    # f[k][mask]: 已用 k 个标记，最近 3 个位置标记状态为 mask 时的最小累计时延
    # 滚动数组优化：只保留当前层和下一层
    f = [[INF] * 8 for _ in range(K + 1)]
    f[0][0] = 0

    for i in range(N):
        nf = [[INF] * 8 for _ in range(K + 1)]
        for k in range(K + 1):
            for mask in range(8):
                base = f[k][mask]
                if base == INF:
                    continue
                for b in range(2):
                    if k + b > K:
                        continue
                    # 累加所有仍影响节点 i 的过去标记的 opt 值
                    reduction = 0
                    for off in range(3):
                        pos = i - 3 + off
                        if pos >= 0 and ((mask >> off) & 1) == 1:
                            if pos + win[pos] >= i:
                                reduction += opt[pos]
                    # 当前节点若被标记，opt[i] 同样作用于自身
                    if b == 1:
                        reduction += opt[i]
                    cur = delay[i] - reduction
                    if cur < 0:
                        cur = 0
                    # 状态向前推：丢弃位置 i-3 的标记位，加入位置 i 的标记位
                    new_mask = ((mask >> 1) & 0b11) | (b << 2)
                    cost = base + cur
                    if cost < nf[k + b][new_mask]:
                        nf[k + b][new_mask] = cost
        f = nf

    ans = INF
    for k in range(K + 1):
        for mask in range(8):
            if f[k][mask] < ans:
                ans = f[k][mask]

    print(ans)

solve()

复杂度分析

时间复杂度：$O(N \times K \times 8 \times 2)$，状态数 $N \times K \times 8$，每个状态 2 个决策且常数判断。当 $N = 10^5, K = 100$ 时仅约 $1.6 \times 10^7$ 次基本操作。

空间复杂度：$O(K \times 8)$，使用滚动数组优化后只需存储两层 DP 表。

小结

• 第一题是 RLE 块匹配 + 乘法原理，关键转化是”删除相邻相同字符”等价于”每个块长度可缩短但不能删空”，从而用块序列窗口枚举取代暴力子串枚举
• 第二题是单调栈经典应用——求右侧第一个严格更大元素的位置。从右往左维护严格递减栈，每个元素至多入栈出栈各一次，$O(n)$ 解决
• 第三题的突破口在于 $\text{win}[i] \leq 3$，这使得影响当前节点的标记只来自最近 3 个位置，自然引出 3 位掩码作为 DP 状态，滚动数组优化后空间极小