AT_intro_heuristics_c Incremental Scoring

给定 $ D $ 天的比赛日程以及 $ M $ 个日程更改的查询。在第 $ i $ 个查询中，你会获得两个整数 $ d_i $ 和 $ q_i $，需要将第 $ d_i $ 天的比赛类型更改为 $ q_i $，并输出修改后的日程中最终的满意度。请注意：每次修改是持续的，意味着第 $ i $ 个查询是基于已完成的第 $(i-1)$ 个查询的结果。

输入包含了问题 A 的输入信息，紧接着是问题 A 的输出和查询数据。 > $ D $ $ c_1 $ $ c_2 $ $\cdots$ $ c_{26} $ $ s_{1,1} $ $ s_{1,2} $ $\cdots$ $ s_{1,26} $ $\vdots$ $ s_{D,1} $ $ s_{D,2} $ $\cdots$ $ s_{D,26} $ $ t_1 $ $ t_2 $ $\vdots$ $ t_D $ $ M $ $ d_1 $ $ q_1 $ $ d_2 $ $ q_2 $ $\vdots$ $ d_M $ $ q_M $ - 对应于问题 A 的输入部分的约束和生成方法与问题 A 是一致的。 - 对应于问题 A 的输出部分，每个 $ d $ 满足 $ 1 \leq t_d \leq 26 $，且从范围内均匀随机生成。 - 查询数量 $ M $ 满足 $ 1 \leq M \leq 10^5 $。 - 每个 $ d_i $ 满足 $ 1 \leq d_i \leq D $，并均匀随机生成。 - 每个 $ q_i $ 满足 $ 1 \leq q_i \leq 26 $，并从当前日程中第 $ d_i $ 天比赛类型不同的 25 个值中随机生成。

在每次处理完第 $ i $ 个查询后，输出最终的满意度 $ v_i $，格式如下： > $ v_1 $ $ v_2 $ $\vdots$ $ v_M $

### 指导 解决此类问题的一种有效策略是使用「局部搜索法」。这种方法不是从头开始寻找解决方案，而是对已有的解决方案进行小幅调整以期找到更好的解。如果调整后的解较优，则保留，否则恢复原解。通过多次迭代，可以逐步提高解决质量。以下是这种策略的伪代码： ``` solution = 初始解（可以随机生成或采用贪心算法等） while 有时间: 轻微修改 solution if 修改后的解变差: 恢复到修改前 ``` 在这个问题中，可以随机选择一天 $ d $ 和一个比赛类型 $ q $，然后将第 $ d $ 天的比赛类型更改为 $ q $。其伪代码为： ``` t[1..D] = 初始解（使用随机生成或贪婪法） while 有时间: 随机选择 d 和 q 记录原类型 old = t[d] 将比赛类型设为 t[d] = q if 变差: 恢复原类型 t[d] = old ``` 使用局部搜索法的关键在于设计变更操作。变更太小容易陷入局部最优，变更太大则近似于盲目搜索难以改善；同时，还需保证变更得分的快速计算。对于问题 C，重点在于第二点，可以通过差分计算来得到变更后得分的变化。有效的差分计算可以加速得出结果；反之，如果无法为差分计算加速，可能需要重新考虑变更策略，或考虑问题是否适合局部搜索法。 由于这类问题接受次优解，因此对于存在 bug 的程序不会被判定为错误，这就导致 bug 的发现时间延后。为了及早发现问题，可以对复杂操作的代码进行单元测试。例如，计算得分差分时，可以检测差分计算结果是否与从头计算一致。 ### 下一步 回到问题 A，尝试实现基于局部搜索法的解决方案。对于本问题，“随机选择日期 $ d $ 和比赛类型 $ q $，并将第 $ d $ 天的比赛类型改为 $ q $”这种变更操作并不理想。你可以思考如何改善此操作，同时引入模拟退火法等改良策略，该方法允许一定程度上的变差以期望获得更优解。更多的操作示例和方法请参考比赛后的题解。 ### 示例解释 注意：这个输入输出例子仅用于小规模验证，不符合 $ D=365 $ 的约束，不会作为实际测试用例使用。 **本翻译由 AI 自动生成**