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

题目描述

某智慧城市运营平台持续监测全市供水管网在连续 N=200 天内各区域的日总供水量(单位万吨,数值通常分布在 100.00 至 500.00 之间),数据已按日期先后排列。
因传感器故障,共有 M 处(M 的范围是 20 到 30)记录丢失,依次编号为 Gap_1, Gap_2, ..., Gap_M。
已知首日和末日的监测数据一定完整(即第 1 天和第 N 天不会出现丢失)。 你的目标是:对每一处丢失记录,利用其前后最近的连续真实数据段,构建二阶多项式岭回归模型来估算缺失值。
区间确定规则
假设某个丢失记录位于全局第 pos 天:
前方区间 [left_start, pos-1]:从 pos-1 向前(朝第 1 天方向)逐天检查,碰到的第一个丢失记录(Gap_1 到 Gap_M 中任何一个)所在天数的下一天即为 left_start。若一路到第 1 天都没有碰到其他丢失记录,则 left_start 为第 1 天。
后方区间 [pos+1, right_end]:从 pos+1 向后(朝第 N 天方向)逐天检查,碰到的第一个丢失记录所在天数的前一天即为 right_end。若一路到第 N 天都没有碰到其他丢失记录,则 right_end 为第 N 天。
模型构建
将上述前方区间与后方区间中所有真实记录汇总作为训练样本 (x, y),其中 x 为天序号(1, 2, ..., N),y 为对应供水量。
使用二阶多项式岭回归拟合模型: y = _2 x^2 + _1 x + _0
回归系数通过以下矩阵公式求解: = (X^T X + I)^-1 X^T y
各符号含义如下:
beta 是 3*1 列向量,包含待求系数 [beta_2, beta_1, beta_0]。
X 是 n*3 的设计矩阵(n 为训练样本数)。
对训练集中每个天序号 x_i,矩阵 X 的对应行为 [x_i^2, x_i, 1]。
y 是 n*1 列向量,存储训练集中各样本点的供水量。
X^T 为 X 的转置。
lambda 为正则化系数,本题统一取 lambda=0.1。
I 为 3*3 单位矩阵。
(.)^{-1} 表示矩阵求逆运算。

输入输出

输入描述
第 1 行:两个整数 M 和 N,以空格分隔。M 表示丢失记录总数(范围 20 到 30),N 表示后续数据行数(固定为 200)。
第 2 行到第 N+1 行:每行一个值,可能是:
一个浮点数,代表当天实际供水量。
一个字符串 Gap_i(i 从 1 到 M),表示该天数据丢失。
输出描述
共 M 行,严格按 Gap_1, Gap_2, ..., Gap_M 的顺序输出。
每行格式为 Gap_i: xxx.xx,即标签、冒号、空格、预测值(保留两位小数)。

样例共 1 组

样例 1 · 以 Gap_1 为例:Gap_1 位于第 2 天。前方区间为 [1, 1],即只有第 1 天的数据。后方区间为 [3, 16] 之前,由于第 17 天是 Gap_2,所以后方区间为 [3, 16],共 14 天数据。将这些点作为训练集,构建二阶多项式岭回归模型,代入 x=2 得到预测值 194.99。
输入
22 200
205.58
Gap_1
195.99
196.40
219.39
219.44
230.46
200.62
216.35
202.94
212.72
226.35
209.29
218.21
238.21
235.88
Gap_2
241.13
251.54
220.93
254.31
251.30
238.17
231.86
Gap_3
240.91
231.89
232.65
263.17
253.78
262.16
259.18
251.43
268.77
244.72
251.28
261.87
252.80
261.78
249.54
253.65
226.20
232.28
Gap_4
223.62
228.22
221.33
226.69
239.20
226.48
224.73
216.26
216.45
241.07
227.29
Gap_5
203.59
223.54
198.50
204.70
226.64
Gap_6
204.36
206.96
210.80
205.63
181.27
170.94
Gap_7
175.53
170.90
197.86
192.93
168.25
Gap_8
167.25
185.99
165.82
156.21
153.71
164.61
151.08
162.47
173.61
152.40
144.02
174.09
153.63
136.06
133.60
135.51
155.76
162.00
146.98
132.54
145.30
170.04
151.64
Gap_9
165.84
Gap_10
161.65
160.98
Gap_11
146.50
Gap_12
142.85
157.21
159.51
Gap_13
179.76
157.07
168.46
157.56
188.97
189.41
168.71
Gap_14
185.66
169.76
196.53
190.02
202.04
194.57
Gap_15
Gap_16
181.62
220.50
220.98
221.57
203.06
195.50
230.70
235.81
203.67
221.94
207.47
237.27
239.56
216.06
231.86
236.68
227.05
Gap_17
236.61
229.63
244.09
252.98
232.98
238.44
266.71
253.70
245.92
249.67
234.25
238.72
243.45
253.53
239.15
238.58
232.31
254.29
237.65
264.04
261.42
228.96
234.63
250.73
231.30
226.67
Gap_18
241.21
235.63
246.36
245.45
218.85
213.12
224.42
221.99
Gap_19
229.77
225.24
235.32
197.50
207.25
202.27
220.69
193.68
188.85
196.68
193.12
184.90
181.28
Gap_20
184.14
Gap_21
183.69
Gap_22
197.09
188.37
输出
Gap_1: 194.99
Gap_2: 235.41
Gap_3: 249.49
Gap_4: 246.24
Gap_5: 220.04
Gap_6: 206.00
Gap_7: 189.12
Gap_8: 171.16
Gap_9: 146.06
Gap_10: 163.92
Gap_11: 153.00
Gap_12: 146.94
Gap_13: 160.31
Gap_14: 181.80
Gap_15: 203.39
Gap_16: 203.64
Gap_17: 230.94
Gap_18: 235.83
Gap_19: 222.33
Gap_20: 179.61
Gap_21: 183.92
Gap_22: 188.19

算法解析依据充分

考点:模拟

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

题目画像

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

解题思路

推荐方向:模拟

本题切入点

对每处缺失按其前后最近连续真实段做二阶多项式岭回归:构造 x 的 1/2 次幂特征并带正则项,预测该天补值后按 Gap 顺序两位小数输出。

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

思路框架(模拟 通法 · 非本题专属)

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

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

复杂度:时间 O(操作次数) | 空间 O(状态数)

该范式的通法易错点

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

样例解读

样例 1:输入 22 200 / 205.58 / Gap_1 / 195.99 / 196.40 / 219.39 / 219.44 / 230.46 / 200.62 / 216.35 / 202.94 / 21 → 输出 Gap_1: 194.99 / Gap_2: 235.41 / Gap_3: 249.49 / Gap_4: 246.24 / Gap_5: 220.04 / Gap_6: 206.00 / Gap_

以 Gap_1 为例:Gap_1 位于第 2 天。前方区间为 [1, 1],即只有第 1 天的数据。后方区间为 [3, 16] 之前,由于第 17 天是 Gap_2,所以后方区间为 [3, 16],共 14 天数据。将这些点作为训练集,构建二阶多项式岭回归模型,代入 x=2 得到预测值 194.99。

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

本题来源:2026年-华为-3月4号AI岗。

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