某智慧城市运营平台持续监测全市供水管网在连续 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 为对应供水量。 使用二阶多项式岭回归拟合模型： 回归系数通过以下矩阵公式求解： 各符号含义如下： 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

输入

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

说明

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

备注:
本题由牛友@Charles 整理上传
加载中...