5月31日华为OD机考 | 二星题真题解析
题目大意
n 个魔法石围成环形,能量可正可负。选一段连续石子(可跨首尾),要求总和能被 k 整除,求最大总和,无满足条件则输出 0。
数据范围:\(n\le 2\times 10^5,k\le 1000\)。
核心考点
环形数组 + 前缀和 + 同余定理 + 哈希表 + 滑动窗口
解题难点
- 环形可跨首尾,普通线性解法不行
- 有负数,模运算容易出错
- 数据量大,暴力必超时,需线性复杂度
解题思路
- 环形转线性:数组拼接自身变 2n 长度,只取长度不超过 n 的子数组,避免重复选元素。
- 同余原理:\(pre[j]-pre[i]\) 能被 k 整除 \(\iff pre[j]\%k = pre[i]\%k\)。
- 负数取模修正:
mod = (pre % k + k) % k,保证余数在 0~k-1。 - 哈希表优化:记录每个余数最早最小前缀和,同余数用当前前缀和减最小值,更新最大答案。
易错点
- 没控制子数组长度≤n
- 负数未做模修正
- 哈希表存最大前缀和而非最小,得不到最优解
- 无合法情况未返回 0
备考小结
经典模板题:环形数组翻倍拼接、整除问题用前缀和同余匹配、负数固定模修正公式,记住套路可直接套用考场同类题。
查看7道真题和解析
华为HUAWEI工作强度 1383人发布