华为 · 前缀和 · 算法编程题
华为 前缀和 时限 1 秒 / 256 MB

题目描述

为提升长序列推理效率,现定义一套“分块压缩 + 打分 + 二段划分”的流程。给定长度为 n、维度为 d 的向量序列 X0..X(n-1)(均非零)与块大小 b,将序列按顺序切成相邻的 m=ceil(n/b) 个连续块,每块至多 b 个向量(最后一块可不足 b 个)。
对第 k 个块(1≤k≤m):
·
先做按维度的“块内均值”得到向量 h_k(每一维为该块该维的平均值)。
·
设常数 b1=2、b2=1,并给定长度为 d 的向量 W1、W2。定义
s_k = W1 · h_k + b1,z_k = max(0, s_k),c_k = W2 * z_k + b2
其中 “W2 * z_k” 表示用标量 z_k 逐分量缩放 W2,c_k 与 W2 同为 d 维。
·
定义 q 为全 1 的 d 维向量,得到标量打分
a_k = (q · c_k) / sqrt(d) = (c_k 各分量之和) / sqrt(d)。
得到序列 A = (a_1, a_2, ..., a_m) 后,把 A 恰好切成 2 段且两段都非空、彼此连续,记两段元素和分别为 S1、S2,目标最大化 min(S1, S2)。记最优值为 S,输出 round(100*S) 的整数(四舍五入到最近整数)。

输入输出

输入描述
· 第一行:n d b
· 接下来 n 行:每行 d 个实数,依次为 X0..X(n-1)
· 倒数第 2 行:d 个实数,表示 W1
· 最后一行:d 个实数,表示 W2
输出描述
一行一个整数:round(100*S)

样例共 1 组

样例 1 · · 分块:B1=[1,3],B2=[2,5]。h1=2.0,h2=3.5。 · b1=2,b2=1,W1=1.5,W2=2。· s1=1.52+2=5 → z1=5 → c1=25+1=11 → a1=11/√1=11 · s2=1.53.5+2=7.25 → z2=7.25 → c2=27.25+1=15.5 → a2=15.5 · A=[11,15.5],唯一切分 [11]|[15.5],min=11,输出 round(1100)=1100。
输入
4 1 2
1
3
2
5
1.5
2
输出
1100

算法解析依据充分

考点:前缀和

限制 1 秒 / 256MB | 标准输入输出

题目画像

  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

推荐方向:前缀和

本题切入点

先分块求均值向量得到 m 个标量打分 a_k,问题转成「在数组上切一刀使两段和的最小值最大」:预处理前缀和,枚举切分点 O(m) 取最优。

预处理前缀和数组,把「区间求和」从 O(n) 降到 O(1)。

思路框架(前缀和 通法 · 非本题专属)

  1. 预处理 pre[i] = a[1]+...+a[i]。
  2. 区间 [l, r] 的和 = pre[r] - pre[l-1]。
  3. 若题目是「多次区间修改 + 最后统一查询」,改用差分数组:d[l]+=v, d[r+1]-=v,最后做一遍前缀和还原。
  4. 二维情况用二维前缀和(容斥原理)。

实现要点:开 long long,避免 n 较大时求和溢出。

复杂度:时间 预处理 O(n),每次查询 O(1) | 空间 O(n)

该范式的通法易错点

  • pre 数组下标没留出 0 号位导致 l-1 越界。
  • 求和结果超出 int 范围(1e5 个 1e9 相加会溢出 32 位整数)。

样例解读

样例 1:输入 4 1 2 / 1 / 3 / 2 / 5 / 1.5 / 2 → 输出 1100

· 分块:B1=[1,3],B2=[2,5]。h1=2.0,h2=3.5。

· b1=2,b2=1,W1=1.5,W2=2。· s1=1.52+2=5 → z1=5 → c1=25+1=11 → a1=11/√1=11

· s2=1.53.5+2=7.25 → z2=7.25 → c2=27.25+1=15.5 → a2=15.5

· A=[11,15.5],唯一切分 [11]|[15.5],min=11,输出 round(1100)=1100。

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

本题来源:2025年秋招-华为-10月22号AI岗。

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