你需要在一个序列建模系统中，给长度为 n 的输入序列做“有限入度”的注意力连边选择，使得信息总量最大。具体约定如下： · 每个位置 j 携带一个 d 维实数特征向量 Xj（所有向量均非零），以及一个整数容量 cj，表示该位置最多可以接收来自它之前位置的连边条数。 · 先对每个向量做 RMSNorm 归一化：对向量的每个分量除以“各分量平方的平均值再开根号”。等价地，若向量为 x，则 rms = sqrt((x[0]^2 + ... + x[d-1]^2)/d)，归一化向量为 x/rms。此处归一化不使用偏置与缩放（gamma=1，epsilon=0）。 · 对任意一对位置 i<j，计算缩放点积 a(i,j) = (x̂(i) · x̂(j)) / sqrt(d)，再取平方 a(i,j)^2 作为该连边的“贡献值”。 · 对于每个 j，从所有 i<j 的候选连边里，最多挑 cj 条，使得全局目标 S = Σj Σi<j chosen a(i,j)^2 最大。 · 输出 round(100 * S) 的整数值。
· 第一行：n d（空格分隔） · 接下来 n 行：每行 d 个浮点数，表示第 j 个向量的 d 个分量 · 最后一行：n 个非负整数，表示 c0, c1, ..., c(n-1)
· 一个整数，即 round(100 * S)
4 2 2 2 3 0 0 4 1 1 0 1 1 2
500
考点：贪心
限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：贪心
本题切入点
每个位置 j 的连边只与 i<j 有关，各 j 相互独立：先 RMSNorm 归一化，再把所有 a(i,j)² 排序取前 c_j 个累加即可，无需全局搜索。
每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。
思路框架（贪心 通法 · 非本题专属）
实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。
复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)
该范式的通法易错点
样例 1：输入 4 2 / 2 2 / 3 0 / 0 4 / 1 1 / 0 1 1 2 → 输出 500
归一化后：x̂0=[1,1]，x̂1=[√2,0]，x̂2=[0,√2]，x̂3=[1,1]
贡献平方：a(0,1)^2=1，a(0,2)^2=1，a(0,3)^2=2，a(1,2)^2=0，a(1,3)^2=1，a(2,3)^2=1
每个 j 最多选 cj 条：j=1 取1；j=2 取1；j=3 取2，共 S=5，输出 round(100*5)=500
解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：2025年秋招-华为-10月15号AI岗。