大厂真题 / 华为

华为 4.8 笔试真题 - 研发岗

本场考试概述

考试时间：2026年4月8日 考试岗位：研发岗 难度评级：困难

考点分析：

第一题：混合进制编码 + 中心扩展法求最长回文子串（难度中等）
第二题：贪心 + 大顶堆（难度中等）
第三题：状态压缩 DP + 子集枚举（难度困难）

建议策略：

第一题优先拿下，模拟过程梳理清楚，回文部分用中心扩展即可
第二题贪心思路明确，注意维护堆时正确更新当前耗时
第三题 N≤15 是状压 DP 的明显信号，子集枚举模板要熟记

第一题：包裹的编码

题目描述

给定一个十进制整数 N（可为负数）和一组进制序列 bases，进行混合进制编码后映射为字母串。若字母串是回文串，在后面添加 (palindrome)；否则输出最长回文子串（多个同长取字典序最小）。

样例

输入

-21
5 7 3

输出

bb

输入

0
5 7 3

输出

aaaa (palindrome)

题解：模拟 + 中心扩展法

编码构造：把

当作初始商，依次除以各个 base，每次余数就是当前位的编码数字，商进入下一轮。在最前面加上符号位（负数为 1，非负为 0），再把每个数字映射成字母。

回文检测：用中心扩展法，枚举每个位置作为奇数/偶数长度回文的中心，左右扩展，维护最长且字典序最小的结果。

时间复杂度：O(n^2)，n 为字符串长度。 空间复杂度：O(n)。

import sys
input = sys.stdin.readline

def encode(N, bases):
    sign = 1 if N < 0 else 0
    x = abs(N)
    digits = [sign]
    for b in bases:
        digits.append(x % b)
        x //= b
    return "".join(chr(ord('a') + d) for d in digits)

def expand(s, l, r, best):
    n = len(s)
    while l >= 0 and r < n and s[l] == s[r]:
        cand = s[l:r + 1]
        if len(cand) > len(best) or (len(cand) == len(best) and cand < best):
            best = cand
        l -= 1
        r += 1
    return best

def longest_palindrome(s):
    best = s[0]
    for i in range(len(s)):
        best = expand(s, i, i, best)
        best = expand(s, i, i + 1, best)
    return best

N = int(input())
bases = list(map(int, input().split()))
s = encode(N, bases)
if s == s[::-1]:
    print(s + " (palindrome)")
else:
    print(longest_palindrome(s))

第二题：大模型性能优化

题目描述

n 个模块串行执行，每次优化可将某模块耗时减半（向上取整），但不低于下限 b_i。给 m 天时间，每天优化一个模块，求最小总耗时。

样例

输入

3
80
10

输出

题解：贪心 + 大顶堆

每次挑”当前能减最多的模块”优化。收益 = c - max(ceil(c/2), b_i)，用大顶堆维护，循环 m 次取堆顶操作。

时间复杂度：O(m log n)。 空间复杂度：O(n)。

import sys
import heapq
input = sys.stdin.readline

def solve():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    cur = a[:]
    heap = []
    for i in range(n):
        nxt = max((a[i] + 1) // 2, b[i])
        gain = a[i] - nxt
        if gain > 0:
            heapq.heappush(heap, (-gain, i))

    for _ in range(m):
        if not heap:
            break
        neg_gain, i = heapq.heappop(heap)
        if -neg_gain <= 0:
            break
        c = cur[i]
        nxt = max((c + 1) // 2, b[i])
        cur[i] = nxt
        new_nxt = max((nxt + 1) // 2, b[i])
        new_gain = nxt - new_nxt
        if new_gain > 0:
            heapq.heappush(heap, (-new_gain, i))

    print(sum(cur))

solve()

第三题：分布式任务调度

题目描述

N 个任务（N≤15），每个有 CPU 需求、内存需求、价值。服务器 CPU 规格 C、内存规格 M。对服务器数量 1 到 N，分别输出最大总价值。

样例

输入

输出

5
7
7

题解：状态压缩 DP + 子集枚举

N≤15，用 N 位二进制数表示任务子集。预处理每个子集的 CPU、内存、价值之和以及是否能放进一台服务器。

状态方程：f[S] = 把 S 里任务全部跑完的最少服务器数。对 S 的每个非空子集 T（能放进一台服务器），f[S] = min(f[S], f[S^T] + 1)。

子集枚举用模板 T = (T-1) & S。最后汇总：对每个 S，用 f[S] 台服务器可获价值 sumv[S]，做前缀最大值得到最终答案。

时间复杂度：O(3^N)，约 1.4×10^7。 空间复杂度：O(2^N)。

import sys
input = sys.stdin.readline

def solve():
    N, C, M = map(int, input().split())
    cs = [0] * N
    ms = [0] * N
    vs = [0] * N
    for i in range(N):
        cs[i], ms[i], vs[i] = map(int, input().split())

    full = 1 << N
    sumc = [0] * full
    summ = [0] * full
    sumv = [0] * full
    for S in range(1, full):
        lb = S & -S
        i = lb.bit_length() - 1
        prev = S ^ lb
        sumc[S] = sumc[prev] + cs[i]
        summ[S] = summ[prev] + ms[i]
        sumv[S] = sumv[prev] + vs[i]

    feasible = [sumc[S] <= C and summ[S] <= M for S in range(full)]

    INF = N + 5
    f = [INF] * full
    f[0] = 0
    for S in range(1, full):
        T = S
        while T > 0:
            if feasible[T] and f[S ^ T] + 1 < f[S]:
                f[S] = f[S ^ T] + 1
            T = (T - 1) & S

    ans = [0] * (N + 2)
    for S in range(full):
        k = f[S]
        if k <= N and sumv[S] > ans[k]:
            ans[k] = sumv[S]
    for k in range(1, N + 1):
        ans[k] = max(ans[k], ans[k - 1])

    out = []
    for k in range(1, N + 1):
        out.append(str(ans[k]))
    print("\n".join(out))

solve()

小结

第一题混合进制编码 + 中心扩展法，编码部分是模拟取余过程，回文部分 O(n^2) 即可
第二题贪心 + 大顶堆，每次选减少量最大的模块优化，堆维护 O(log n)
第三题状态压缩 DP + 子集枚举是经典组合，N≤15 就是状压信号，子集枚举模板 T = (T-1) & S 务必熟记

这篇文章有帮助吗？

| GitHub 留言