华为 · 模拟 · 算法编程题
华为 模拟 n ≤ 50 时限 1 秒 / 256 MB

题目描述

小红需要实现 Expert Choice Routing。给定 n 个 d 维 Token、门控矩阵和 e 个专家变换矩阵：
1. 对每个 Token 计算 X_iW_g ，并在专家维度上使用数值稳定 Softmax 得到门控权重；
2. 每个专家独立选择门控权重最高的 s 个 Token，权重相同时选择编号较小者；
3. 对被专家选中的 Token 计算行向量 X_iW_e ，乘对应门控权重并累加到输出。未被任何专家选中的 Token 输出零向量。
若第一行维度不满足约束，输出一行 `0`。

输入输出

输入描述
第一行输入 n,d,e,s 。
接着输入 n 行 Token 矩阵 X ，每行 d 个数；再输入 d 行门控矩阵 W_g ，每行 e 个数；最后依次输入 e 个专家矩阵，每个矩阵为 d 行、每行 d 个数。
合法输入满足 1 ≤ n,d,e ≤ 50 、 1 ≤ s ≤ n ，所有浮点数绝对值不超过 100 。
输出描述
合法输入输出 n 行，每行 d 个浮点数，保留两位小数；维度非法则输出 `0`。

样例共 2 组

样例 1 · 每个专家按归一化门控权重独立选择三个 Token，再对专家输出加权求和。
输入
4 3 2 3
1.0 0.5 0.2
0.8 0.3 0.9
0.2 0.7 0.4
0.5 0.1 0.6
0.3 0.7
0.5 0.2
0.2 0.1
1.0 0.0 0.0
0.0 1.0 0.0
0.0 0.0 1.0
0.5 0.0 0.0
0.0 0.5 0.0
0.0 0.0 0.5
输出
0.28 0.14 0.06
0.59 0.22 0.66
0.11 0.38 0.22
0.37 0.07 0.44
样例 2 · s=0 不满足合法维度约束。
输入
3 2 2 0
1.0 0.5
0.5 1.0
0.2 0.3
0.1 0.2
0.8 0.6
0.2 0.4
0.9 0.1
0.1 0.8
0.0 0.1
输出
0

算法解析依据充分

考点：模拟

数据规模 n ≤ 50 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：n ≤ 50
  • 元素值域：d ≤ 50，e ≤ 50（注意整数类型选择，避免溢出）
  • 复杂度门槛：允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：模拟

本题切入点

按 Expert Choice Routing 流程实现：先对每个 Token 在专家维度做数值稳定 softmax 得门控权重，再让每个专家独立挑权重最高的 s 个 Token（同分取编号小者），最后加权累加各专家输出。

不涉及复杂算法，把题目描述的流程原样翻译成代码逐步执行即可。

思路框架（模拟 通法 · 非本题专属）

  1. 用变量记录题目要求的「状态」（当前值、剩余数量、当前位置等）。
  2. 按题面给出的顺序，把每一步操作写成一段代码，逐条执行。
  3. 每一步执行后更新状态，并在题目要求的位置输出或累计答案。
  4. 注意循环的边界：执行多少次、何时终止、是否能终止。

实现要点：结构上通常是一个外层循环包住若干 if/else 分支；只要状态定义清楚，正确率很高。

复杂度：时间 O(操作次数) ｜ 空间 O(状态数)

该范式的通法易错点

  • 终止条件写错导致死循环或漏做最后一次操作。
  • 状态更新顺序颠倒（先改了下标又用旧下标）。
  • 题目里「最多 / 恰好 / 至少」的语义差别没区分。

对照本题

  • 数据规模 n ≤ 50，允许 O(n³) ~ O(n⁴) 的多重循环，可以放心枚举。
  • 元素值域最大到 50 —— 求和 / 相乘时记得开 64 位整数。

样例解读

样例 1：输入 4 3 2 3 / 1.0 0.5 0.2 / 0.8 0.3 0.9 / 0.2 0.7 0.4 / 0.5 0.1 0.6 / 0.3 0.7 / 0.5 0.2 / 0.2 0.1 / 1.0 → 输出 0.28 0.14 0.06 / 0.59 0.22 0.66 / 0.11 0.38 0.22 / 0.37 0.07 0.44

每个专家按归一化门控权重独立选择三个 Token，再对专家输出加权求和。

样例 2：输入 3 2 2 0 / 1.0 0.5 / 0.5 1.0 / 0.2 0.3 / 0.1 0.2 / 0.8 0.6 / 0.2 0.4 / 0.9 0.1 / 0.1 0.8 / 0.0 0.1 → 输出 0

s=0 不满足合法维度约束。

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：2026年-华为-06月12号AI岗。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解