大厂真题 / 华为

华为 5.22 笔试真题 - AI岗

本场考试概述

考试时间：2026年5月22日 考试岗位：华为暑期实习 AI 岗（AI算法、AI应用开发、AI数据科学等） 难度评级：中等偏上

考点分析：

选择题（20道）：大模型工程（Adam 训练显存、gradient accumulation、MHA 多头注意力、BLIP-2 Q-Former）、数学（互斥独立、贝叶斯、张量收缩、Newton/Lagrange 插值、Weierstrass 逼近）、数值与线代（AllReduce 舍入误差、矩阵病态条件数）、机器学习评价（Precision/Recall、聚类指标）、参数估计（MLE）、过拟合/欠拟合
第一题：随机森林交易风控算法（中等，决策树遍历 + 多数表决）
第二题：KVCache 感知请求路由（困难，字典树）

建议策略：

AI 岗选择题分数权重大（单选 15x6 + 多选 5x12 = 150 分），先把选择题刷透再啃编程题；本场多选题 4 道集中在数学/数值（条件数、聚类指标、MLE 适用、Weierstrass），需要稳基础
第一题就是把决策树读进数组、顺着 idx/val 跳左右、最后多数表决，没思路陷阱；Python 用 sys.stdin.buffer.read().split() 一次读完，否则会卡 IO
第二题朴素扫所有缓存序列必超时，必须想到字典树：把同节点里的所有缓存序列合并成共享前缀树，LCP 查询从根沿请求一步步走

选择题（20道）

第1题

设模型参数量 $P$，训练数据量 $D$ token，采用 FP16 混合精度训练（Adam 优化器）。以下关于显存占用的估算，说法正确的是：

A. 使用梯度检查点（Gradient Checkpointing）会增加显存占用 B. 训练时需保存 FP32 主权重、FP16 参数、FP16 梯度，以及 Adam 的一阶和二阶矩（FP32），总显存约 $16P$ 字节 C. 仅模型参数占用显存 $2P$（FP16），训练总显存约等于 $2P$ D. 训练显存仅取决于参数量，与 batch size 和序列长度无关

答案：B

考点：大模型——训练显存

Adam 混合精度训练单参数显存：FP32 主权重 4B + FP16 参数 2B + FP16 梯度 2B + FP32 一阶矩 4B + FP32 二阶矩 4B = 16B。A 错，梯度检查点用算力换显存，显存反降；C 错，只统计参数忽略了梯度和优化器状态；D 错，激活显存随 batch 和序列长度线性增长。

第2题

已知事件 $A$ 与 $B$ 互斥且独立，则下列一定成立的是：

A. $P(A) = P(B) = 0.5$ B. $P(A \cup B) = 1$ C. $P(A) + P(B) = 1$ D. $P(A) = 0$ 或 $P(B) = 0$

答案：D

考点：数学——概率论

互斥推出 $P(A \cap B) = 0$，独立推出 $P(A \cap B) = P(A)P(B)$，联立得 $P(A)P(B) = 0$，故必有一个为 $0$。A、B、C 都需要额外条件。

第3题

训练脚本支持 gradient accumulation，你把 micro_batch 由 $b$ 调到 $2b$，并把 accumulation 相应减小，global batch 保持不变。通常最可能出现的变化是：

A. 一定吞吐下降 B. 参数量减少 C. 显存占用上升 D. 一定收敛更好

答案：C

考点：大模型——训练优化

micro_batch 变大，单次前向/反向需要保存的激活与中间梯度变多，显存随 micro_batch 大致线性上升。吞吐通常上升（更好利用 GPU 并行）但不绝对；参数量与 micro_batch 无关；global batch 不变时收敛轨迹基本一致。

第4题

Transformer 模型最初被提出来主要是用于什么任务？

A. 文本生成 B. 图像分类 C. 语音识别 D. 机器翻译

答案：D

考点：深度学习——Transformer

2017 年 “Attention is All You Need” 论文以 WMT 英德/英法机器翻译为基准提出 Transformer，编码器-解码器结构正是为序列到序列翻译设计。

第5题

BLIP-2 中 Q-Former 的核心设计原理是”可查询的 Transformer”。关于其工作机制和训练策略，以下哪项描述最准确？

A. Q-Former 包含双向自注意力（queries 之间）和交叉注意力（queries 与视觉特征），冻结视觉编码器，queries 通过交叉注意力从冻结的视觉特征中抽取压缩信息 B. Q-Former 是视觉编码器的替代品，输入原始像素，输出固定 $N$ 个 token，通过 ITG 损失训练文本生成能力 C. Q-Former 的 queries 通过自注意力直接与文本交互，无需交叉注意力即可压缩视觉信息，训练时解冻视觉编码器以学习更好的视觉表示 D. Q-Former 使用共享的自注意力层同时处理可学习 queries 和文本 tokens，通过 ITC/ITM/ITG 三个损失训练，所有损失都更新视觉编码器参数

答案：A

考点：大模型——多模态

BLIP-2 第一阶段冻结视觉编码器，Q-Former 用一组可学习 queries 通过自注意力相互交互、再通过交叉注意力从视觉特征中”查询”压缩信息。B 错，Q-Former 不输入原始像素而是 ViT 输出；C 错，没有交叉注意力无法压缩视觉信息；D 错，视觉编码器始终冻结。

第6题

在计算机渲染 3D 模型时通常会使用双线性插值处理纹理映射，与最近邻插值相比，双线性插值主要可以减少？

A. 数据存储 B. 精度损失 C. 计算时间 D. 视觉锯齿

答案：D

考点：数学——插值

双线性插值用 $2 \times 2$ 邻域像素加权平均得到目标颜色，过渡平滑，消除最近邻在边缘和斜线处的”阶梯状锯齿”。A 与存储无关；B 精度概念不严谨；C 计算时间反而增加。

第7题

在分布式训练时，AllReduce 的浮点累加顺序不同会导致最终模型参数有微小差异。这种差异属于哪类误差？

A. 舍入误差 B. 模型结构误差 C. 采样误差 D. 截断误差

答案：A

考点：数学——数值计算

浮点加法不满足结合律，$(a+b)+c$ 与 $a+(b+c)$ 因尾数对齐时丢弃低位而产生微小差异，属于舍入误差。截断误差来自级数/积分截断，与累加顺序无关。

第8题

在广义相对论或高阶连续介质力学中，张量的”收缩（Contraction）”是一项核心运算。假设有一个 $3$ 阶张量 $T$，其分量表示为 $T_{ijk}$。若我们对该张量的第 $1$ 个指标和第 $3$ 个指标进行收缩，得到一个新的数学对象 $V$。关于 $V$ 的数学性质，下列说法中最准确的一项是：

A. $V$ 的分量可以表示为 $V_j = \sum_k T_{kjk}$，它是一个 $2$ 阶张量（矩阵） B. 收缩操作仅对方阵形式的 $2$ 阶张量（即求迹 Trace）有定义，对于 $3$ 阶及以上张量，必须先通过张量积将其降维 C. 收缩操作等价于对张量在特定平面上进行”投影”操作，因此 $V$ 的阶数保持不变，仍为 $3$ 阶 D. $V$ 的分量可以表示为 $V_j = \sum_i T_{iji}$，它是一个 $1$ 阶张量（向量）

答案：D

考点：数学——张量

对一对指标做收缩等价于把这两个下标置成同一个哑指标并求和，每收缩一对阶数下降 $2$。第 $1$ 与第 $3$ 指标收缩得 $V_j = \sum_i T_{iji}$，结果阶数为 $3 - 2 = 1$。A 错，那是对第 $1$ 个指标求和不是收缩；B 错，收缩定义对任意阶张量都成立；C 错，收缩必然降阶。

第9题

在欺诈检测中，若漏检（把真实欺诈样本错判为非欺诈）成本远高于误报成本，模型评估时应优先关注哪个指标？

A. 准确率 B. 均方误差 MSE C. 召回率 D. 特异度

答案：C

考点：机器学习——评价指标

漏检即假阴性 FN，召回率 $\text{Recall} = \text{TP}/(\text{TP}+\text{FN})$ 越高 FN 越少。准确率在类别极不平衡时失效；MSE 用于回归；特异度衡量真阴性率，与漏检率不直接对应。

第10题

在机器学习模型评估中，如果任务中误报正样本的代价较高，应优先关注以下哪个指标？

A. Precision B. Accuracy C. Recall D. 样本总数

答案：A

考点：机器学习——评价指标

误报即把负类错判为正类（假阳性 FP），$\text{Precision} = \text{TP}/(\text{TP}+\text{FP})$ 越高 FP 越少。本题与第 9 题构成精确率/召回率取舍的对照。

第11题

某工厂有甲、乙两条生产线，甲生产线次品率为 $3\%$，乙生产线次品率为 $5\%$，甲生产线产量占总产量的 $60\%$，随机抽取一件产品为次品，则该次品来自甲生产线的概率为：

A. $3\%$ B. $60\%$ C. $47.4\%$ D. $52.6\%$

答案：C

考点：数学——贝叶斯

由贝叶斯公式 $P(\text{甲}\mid\text{次}) = \frac{P(\text{次}\mid\text{甲}) \cdot P(\text{甲})}{P(\text{次})} = \frac{0.03 \times 0.6}{0.03 \times 0.6 + 0.05 \times 0.4} = \frac{0.018}{0.038} \approx 47.4\%$。

第12题

相比于单头注意力，多头注意力（Multi-Head Attention, MHA）的核心优势在于？

A. 减少推理阶段的 KV Cache 显存占用 B. 允许模型在不同的表示子空间中并行关注来自不同位置的信息 C. 能够显著降低模型的总体参数量 D. 能够彻底消除序列处理中的位置依赖问题

答案：B

考点：深度学习——Transformer

MHA 把 $d$ 维 QKV 拆成 $h$ 个低维子空间各自做 attention，不同头能学到不同的关注模式（如句法、语义等）。A 是 MQA/GQA 的优化目标；C 错，参数量不变；D 错，位置依赖靠位置编码而非头数。

第13题

线性回归模型中，通常采用哪种损失函数进行参数估计？

A. 均方误差（MSE） B. 交叉熵损失 C. Hinge 损失 D. $0$-$1$ 损失

答案：A

考点：机器学习——损失函数

线性回归在高斯噪声假设下最大似然估计等价于最小化 MSE，且 MSE 连续可导便于解析或梯度求解。交叉熵用于分类，Hinge 用于 SVM，$0$-$1$ 损失不可导。

第14题

Newton 插值多项式与 Lagrange 插值多项式的关系正确的是：

A. Lagrange 只适用于等距节点，Newton 适用于任意节点 B. 二者相同，都是同一个插值多项式的不同表示 C. Newton 只适用于等距节点，Lagrange 适用于任意节点 D. 二者一般不相同，Newton 只能近似而 Lagrange 是精确

答案：B

考点：数学——数值/插值

$n+1$ 个互异节点的插值多项式由唯一性定理决定为同一个 $n$ 次多项式，Newton 与 Lagrange 只是不同的构造写法。Newton 形式便于增量添加节点，Lagrange 形式系数清晰，二者代数等价。

第15题

在图像处理中，将一张 $224 \times 224$ 的 RGB 图像展平为一维向量，其维度是？

A. $224$ B. $150528$ C. $50176$ D. $672$

答案：B

考点：深度学习——CNN

RGB 有 $3$ 个通道，向量维度 $224 \times 224 \times 3 = 150528$。C 漏算了通道维度。

第16题（多选）

以下哪些因素使得线性方程组 $Ax = b$ 更容易受到扰动影响（即更病态）？

A. 矩阵 $A$ 的维数很大 B. 矩阵有接近相等的特征值 C. 矩阵的条件数很大 D. 矩阵 $A$ 的行列式接近零

答案：C, D

考点：数学——线性代数/数值

A 错误：维数大本身并不直接决定病态，单位阵即使很大也良态。B 错误：恰恰相反，特征值彼此接近意味着条件数接近 $1$，反而良态；让条件数变大的是特征值绝对值差距悬殊。C 正确：条件数是病态性的标准度量，相对扰动放大上界正比于条件数。D 正确：行列式趋近 $0$ 说明 $A$ 趋近奇异，最小奇异值/特征值很小，条件数发散。

第17题（多选）

在没有真实标签的情况下（无监督），下列哪些指标可以用于评估聚类效果的好坏？

A. 轮廓系数（Silhouette Coefficient） B. 戴维森-堡丁指数（Davies-Bouldin Index） C. 准确率（Accuracy） D. 卡林斯基-Harabasz 指数（CH Index）

答案：A, B, D

考点：机器学习——聚类评估

A 正确：轮廓系数仅依赖样本到同簇/异簇的距离，无需标签。B 正确：DB 指数比较簇内分散度与簇间距离，无需标签。C 错误：Accuracy 需要预测类别与真实标签对齐，属于监督指标。D 正确：CH 指数基于簇间/簇内方差比，无需标签。

第18题（多选）

下列场景中，MLE 更适用的有：

A. 需快速得到点估计 B. 参数为离散型且取值较少 C. 无明确先验信息 D. 样本量较大

答案：A, B, C, D

考点：机器学习——参数估计

A 正确：MLE 给出单点最大化解，无需采样后验。B 正确：离散参数取值少时可直接枚举每个取值的似然，MLE 实现极其简单。C 正确：MLE 不依赖先验，正是频率派与贝叶斯派的分水岭。D 正确：样本量大时 MLE 渐近正态、相合、有效，是大样本下的首选估计量。

第19题（多选）

以下哪些方法可以同时很好地缓解过拟合和欠拟合？

A. 调整模型复杂度 B. 特征选择 C. 增加训练数据 D. 集成学习 Bagging

答案：A, B

考点：机器学习——正则化

A 正确：复杂度可升可降，欠拟合时增大模型、过拟合时减小模型，能同时治。B 正确：特征过少导致欠拟合、特征过多/含噪导致过拟合，选对子集两端都能缓解。C 错误：增数据主要降方差缓解过拟合，对偏差（欠拟合）几乎无帮助。D 错误：Bagging 通过聚合多个高方差模型降方差，主要缓解过拟合，对欠拟合无能为力。

第20题（多选）

关于 Weierstrass 逼近定理（闭区间上的连续函数可以用多项式一致逼近到任意精度）及其数值实现，以下正确的有：

A. 逼近多项式的次数可以任意低 B. 实际计算中通常使用 Chebyshev 展开而非 Bernstein 多项式 C. 任何闭区间上的连续函数都可以用多项式一致逼近 D. Bernstein 多项式收敛速度很快适合实际计算

答案：B, C

考点：数学——数值/逼近

A 错误：达到任意精度可能需要任意高的次数，定理只保证”存在某个次数”。B 正确：Chebyshev 展开收敛指数级，且节点等振荡分布抑制 Runge 现象，是数值实践首选。C 正确：这就是 Weierstrass 定理本身的结论。D 错误：Bernstein 多项式收敛为 $O(1/\sqrt{n})$ 级别，仅用于存在性证明，实际计算极慢。

第一题：随机森林交易风控算法

题目描述

某电商平台利用机器学习进行交易反欺诈。算法团队已经离线训练好了一个随机森林模型，现在需要实现该模型在线上的预测引擎。

随机森林由多棵独立的决策树（Decision Tree）组成。每笔交易包含 $M$ 个特征属性。预测时，每棵决策树都会从根节点开始独立对交易进行评估：如果遇到内部节点，会判断交易的第 $\text{idx}$ 个特征值是否小于等于阈值 $\text{val}$，若是则走向左子节点，否则走向右子节点；如果走到叶子节点，该树会输出一个预测类别，$0$ 代表正常交易，$1$ 代表欺诈交易。

最终，整个森林的预测结果采用”多数表决”（Majority Voting）原则，即统计所有树输出的类别，得票数最多的类别作为最终结果。注意：如果 $0$ 和 $1$ 的票数相同，出于用户体验考虑，一律判定为正常交易（输出 $0$）。

请你编写程序，根据给定的随机森林结构和 $N$ 笔交易数据，输出每笔交易的最终预测结果。

输入描述

第一行包含三个用空格分隔的整数 $T, M, N$，$T$ 为树的数量，$M$ 为特征维度数，$N$ 为待预测的交易笔数。

接下来是 $T$ 棵树的结构定义。对于每棵树：第一行包含一个整数 $K$，表示该树共有 $K$ 个节点，节点编号为 $1$ 到 $K$，根节点编号固定为 $1$；接下来 $K$ 行，按节点编号 $1$ 到 $K$ 的顺序依次描述每个节点，每行以一个整数开头。若为 $1$ 代表内部节点，后接 $4$ 个整数 $\text{idx}, \text{val}, \text{lc}, \text{rc}$，表示如果特征序列中第 $\text{idx}$ 个特征值 $\leq$ $\text{val}$，则跳至编号为 $\text{lc}$ 的节点，否则跳至编号为 $\text{rc}$ 的节点（特征索引从 $1$ 开始）；若为 $0$ 代表叶子节点，后接 $1$ 个整数，值为 $0$ 或 $1$，表示该节点的分类结果。

最后是 $N$ 行交易数据，每行包含 $M$ 个用空格分隔的整数，代表一笔交易的 $M$ 个特征值。

输出描述

输出共 $N$ 行，每行一个整数（$0$ 或 $1$），代表模型对该笔交易的最终预测结果。

样例

输入

输出

两棵树各只有 $1$ 个叶子节点：第 $1$ 棵树根节点是叶子输出 $1$，第 $2$ 棵树根节点是叶子输出 $0$，票数相同。根据规则平票一律判定为正常交易，故输出 $0$。

输入

输出

0
1

共有 $3$ 棵树、$2$ 个特征、$2$ 笔交易。对于第一笔交易 $(8, 8)$：第 $1$ 棵树根节点判断特征 $1$（值为 $8$）$\leq 10$ 成立，走向左节点（编号 $2$），节点 $2$ 是叶子输出 $0$；第 $2$ 棵树根节点判断特征 $2$（值为 $8$）$\leq 5$ 不成立，走向右节点（编号 $3$），节点 $3$ 是叶子输出 $0$；第 $3$ 棵树根节点即为叶子，直接输出 $1$。三棵树输出 $0, 0, 1$，多数为 $0$，最终输出 $0$。

思路分析

第一步：节点存储

每棵树用一个长度 $K+1$ 的数组承载，下标 $1$ 到 $K$ 对应原题节点编号，下标 $0$ 留空。每个节点存两种形式：

叶子节点（类型 $0$）：只需记分类结果 $\text{label}$
内部节点（类型 $1$）：需要分裂特征下标 $\text{idx}$、阈值 $\text{val}$、左右孩子编号 $\text{lc}$, $\text{rc}$

第二步：单棵树预测

从根节点 $1$ 出发循环判断当前节点。如果是叶子，记录 label 退出；如果是内部节点，读出该交易的第 $\text{idx}$ 个特征值，按规则跳转左或右子节点。题目保证每个内部节点有两个有效子节点且无环，循环必然在有限步内终止。

第三步：多数表决

用 $\text{zero}$ 和 $\text{one}$ 两个计数器累加 $T$ 棵树的输出。最终按”$\text{zero} \geq \text{one}$ 输出 $0$，否则输出 $1$”决策，把”平票输出 $0$”这条业务规则合并进 $\geq$ 里。

IO 优化：Python 用 sys.stdin.buffer.read().split() 一次性读入所有数据到列表，通过指针逐个解析，避免逐行 input() 导致超时。

题解代码

import sys


def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    T = int(data[p]); p += 1
    M = int(data[p]); p += 1
    N = int(data[p]); p += 1

    # 每棵树存为列表 tree[1..K]，节点元组：
    # (0, label) 表示叶子；(1, idx, val, lc, rc) 表示内部节点
    trees = []
    for _ in range(T):
        K = int(data[p]); p += 1
        tree = [None] * (K + 1)
        for i in range(1, K + 1):
            t = int(data[p]); p += 1
            if t == 0:
                tree[i] = (0, int(data[p])); p += 1
            else:
                idx = int(data[p]); p += 1
                val = int(data[p]); p += 1
                lc = int(data[p]); p += 1
                rc = int(data[p]); p += 1
                tree[i] = (1, idx, val, lc, rc)
        trees.append(tree)

    out = []
    for _ in range(N):
        feats = [int(data[p + j]) for j in range(M)]
        p += M
        zero = one = 0
        for tree in trees:
            cur = 1
            while True:
                node = tree[cur]
                if node[0] == 0:
                    if node[1] == 0:
                        zero += 1
                    else:
                        one += 1
                    break
                # 内部节点：按特征值与阈值比较走左/右
                cur = node[3] if feats[node[1] - 1] <= node[2] else node[4]
        # 平票按业务要求输出 0
        out.append('0' if zero >= one else '1')

    sys.stdout.write("\n".join(out))


if __name__ == '__main__':
    main()

复杂度分析

时间复杂度：$O(N \cdot T \cdot D)$，其中 $D$ 为树的平均深度，最坏 $D = K$，但满二叉树深度约 $\log K$

空间复杂度：$O(\sum K_i)$，存储所有树节点

第二题：KVCache 感知请求路由

题目描述

实现一个多节点 LLM 推理集群的请求路由器。每个节点维护一个 KV Cache，缓存已处理请求的完整 token 序列（模拟 prefill 完成后 KV 被缓存）。新请求到来时，选择能复用最多 KV Cache 的节点以减少 prefill 计算量；命中长度相同时，选负载最轻的节点。

路由规则按优先级为：

选与当前请求拥有最长公共前缀（LCP）的节点
若多个节点 LCP 长度相同（含均为 $0$），选当前队列中待处理 token 总量最少的节点
若负载也相同，选编号更小的节点

状态更新（每条请求路由后立即执行，模拟 prefill 完成）：将请求的完整 token 序列加入所选节点的缓存；将请求的 token 数累加到所选节点的负载上。

某节点与请求的匹配长度定义为：该节点缓存中所有序列与请求的最长公共前缀的最大值。若节点缓存为空则匹配长度为 $0$。

输入描述

第一行包含两个整数 $N, M$，分别表示节点数和请求数。

第二行包含 $N$ 个整数，表示每个节点初始待处理 token 数。

接下来 $N$ 行，第 $i$ 行描述节点 $i$ 的初始缓存，行首一个整数 $K$ 表示缓存中的序列条数，后接 $K$ 个序列，每个序列内 token 用英文逗号分隔，序列之间用空格分隔。若 $K = 0$ 则该行仅有 $0$。

最后 $M$ 行，每行一个请求的 token 序列，token 之间用空格分隔。每个 token 是 $[0, 100000]$ 范围内的非负整数。所有初始缓存序列长度之和不超过 $10^5$，所有请求序列长度之和也不超过 $10^5$，单个序列长度 $\leq 10^4$。

输出描述

输出一行 $M$ 个整数（用空格分隔），第 $i$ 个整数为第 $i$ 条请求被分配到的节点编号（$0$-indexed）。

样例

输入

3 4
100 50 200
0
0
0
10 20 30 40 50
10 20 30 40 60
10 20 30 40 50 70
5 6 7 8

输出

1 1 1 1

三个节点初始 load 为 $100, 50, 200$，缓存均为空。第 $1$ 条请求，三个节点 LCP 均为 $0$，按负载最轻选节点 $1$（load $50$）；路由后节点 $1$ 缓存追加该序列，load 变为 $55$。第 $2$ 条请求，节点 $1$ LCP 为 $4$（匹配前缀 $[10,20,30,40]$），其余为 $0$，路由到节点 $1$。第 $3$ 条请求，节点 $1$ LCP 为 $5$（命中第 $1$ 条），其余为 $0$，路由到节点 $1$。第 $4$ 条请求，三节点 LCP 均为 $0$，节点 $1$ 负载 $50+5+5+6=66$ < 节点 $0$ 的 $100$ < 节点 $2$ 的 $200$，路由到节点 $1$。

输入

4
0
1,2,3,4,5
0
2 3 4 5 6 7
9 10 11
2 3 4 5 100 200
88 77

输出

0 1 0 1

两个节点初始 load 均为 $0$，节点 $0$ 缓存有 $1$ 条序列 $[1,2,3,4,5]$，节点 $1$ 缓存为空。第 $1$ 条请求 $[1,2,3,4,5,6,7]$，节点 $0$ LCP 为 $5$，节点 $1$ LCP 为 $0$，路由到节点 $0$。第 $2$ 条请求 $[8,9,10,11]$，两节点 LCP 均为 $0$，节点 $1$ 负载 $0$ < 节点 $0$ 的 $7$，路由到节点 $1$。第 $3$ 条请求 $[1,2,3,4,5,100,200]$，节点 $0$ LCP 为 $5$，节点 $1$ LCP 为 $0$，路由到节点 $0$。第 $4$ 条请求 $[99,88,77]$，两节点 LCP 均为 $0$，节点 $1$ 负载 $4$ < 节点 $0$ 的 $14$，路由到节点 $1$。

思路分析

第一步：为什么暴力超时

暴力做法是把每个节点的每条缓存序列都跟请求逐位比一遍。一个节点里有多条缓存时，共享前缀被重复比较，浪费大量时间。

第二步：字典树优化

把同节点里所有缓存序列拼成一棵公共前缀树（Trie）。例如序列 $[1,2,3]$ 和 $[1,2,4]$ 拼起来后，前缀 $[1,2]$ 这段路径只占一份。

第三步：LCP 查询

请求从 Trie 根节点开始走。每一位看当前节点有没有标着该 token 的孩子，有就走过去，没有就停。停下时已经走过的步数就是 LCP。

第四步：插入请求

路由完后把请求写进选中节点的 Trie。还是从根走，有路就复用，没路就新建一个节点接上。

第五步：节点存储

token 值最大到 $10^5$，不能像普通字母 Trie 那样用定长数组。每个 Trie 节点配一个哈希表（Python dict），键是 token、值是子节点编号，按需加键。

所有 Trie 节点扔进一个全局池子 children[]，节点之间用下标互相指。集群节点 $i$ 只记自己 Trie 的根编号 root[i]。

第六步：选哪个节点

维护 $\text{best\_node}$ / $\text{best\_lcp}$ / $\text{best\_load}$，$\text{best\_lcp}$ 初始设 $-1$，这样第一个节点的 LCP 必然能取代它。从 $0$ 到 $N-1$ 顺序扫，满足 lcp > best_lcp 或 lcp == best_lcp and load < best_load 就替换。题面第三优先级”编号小优先”自动满足：从小到大扫、相等不替换。

题解代码

import sys


def main():
    data = sys.stdin.buffer.read().split(b'\n')
    idx = 0
    N, M = map(int, data[idx].split()); idx += 1
    load = list(map(int, data[idx].split())); idx += 1

    # 节点池：children[i] 是 Trie 节点 i 的孩子表 {token -> 子节点编号}
    # 一开始为每个集群节点建一个空 root，编号就是 0..N-1
    children = [dict() for _ in range(N)]
    root = list(range(N))

    def lcp_query(rt, req):
        cur = rt
        for i, t in enumerate(req):
            nx = children[cur].get(t)
            if nx is None:
                return i
            cur = nx
        return len(req)

    def trie_insert(rt, seq):
        cur = rt
        for t in seq:
            nx = children[cur].get(t)
            if nx is None:
                nx = len(children)
                children.append(dict())
                children[cur][t] = nx
            cur = nx

    # 读 N 行初始缓存
    for i in range(N):
        toks = data[idx].split(); idx += 1
        K = int(toks[0])
        for j in range(1, K + 1):
            seq = list(map(int, toks[j].split(b',')))
            trie_insert(root[i], seq)

    # 处理 M 条请求
    out_parts = []
    for _ in range(M):
        req = list(map(int, data[idx].split())); idx += 1
        rlen = len(req)

        best_node = 0
        best_lcp = -1
        best_load = 0

        for u in range(N):
            lcp = lcp_query(root[u], req)
            if lcp > best_lcp or (lcp == best_lcp and load[u] < best_load):
                best_node = u
                best_lcp = lcp
                best_load = load[u]

        trie_insert(root[best_node], req)
        load[best_node] += rlen
        out_parts.append(str(best_node))

    sys.stdout.write(" ".join(out_parts))


if __name__ == '__main__':
    main()

复杂度分析

时间复杂度：$O(N \cdot \sum L_i + M \cdot N \cdot \bar{L})$，初始建树扫一遍所有缓存 token，每条请求在 $N$ 棵树上各走一次查询，命中节点再插一次。代入约 $10^5$ 次哈希操作。

空间复杂度：$O(\text{total_tokens})$，节点池大小受总 token 数约束

小结

选择题覆盖了大模型工程（Adam 显存估算、gradient accumulation、MHA、BLIP-2 Q-Former）、经典数学（互斥独立、贝叶斯、张量收缩、Weierstrass 逼近）和机器学习基础（Precision/Recall、聚类指标、MLE）三大方向
第一题是决策树遍历 + 多数表决，核心是把每棵树的节点读进数组、按 idx/val 跳左右孩子，最后统计票数。Python 注意用 buffer.read().split() 避免 IO 超时
第二题是字典树（Trie），朴素暴力逐条比对会超时，关键优化是把同节点的所有缓存序列合并为共享前缀树，LCP 查询变成从根节点沿请求逐步向下走

这篇文章有帮助吗？

| GitHub 留言