NOIP 2025 游记
Synthesize · · 生活·游记
诡异的两道黑题击碎了我的 300 分梦。
本文采用 1-index，即 NOIP 当天为 Day 1.
本文内的 Remark 表示书写本游记时的评价或联想到的事件。
Day -4.
这是 NOIP 集训的第一天。我记得 1 件事情。但是我不希望将此事公开于此处。
Day -3.
这是 NOIP 集训的第二天。我记得 0 件事情。我在这里将选择性公开如下 0 件事情。
Day -2.
这一天的 NOIP 模拟赛中我获得了 0 分，原因是 T1 写了 6kb 代码后，在比赛开始后 3h 时仍未调出，遂破防，下班。特此纪念。
这天是 CMO 的 Day 1. 同机房有两名初二选手在下午参加了场外赛。其中一位选手 A 比另一位选手 B 多解决了 1 或 2 个得分点（即 3 或 6 分），满足 A 不等于 I，其中 I 为大写英文字母，应理解为单词。这样说话好诡异啊。
Day -1.
这一天的 NOIP 模拟赛中我获得了 [我不记得了] 分。其中 T2 在洛谷上拥有 149 的测试点，时限均为 3.5s。我在提交至洛谷时未删除 freopen 并不幸将评测机卡死数分钟。这对机房里部分同学的提交疑似也造成了影响。我需要向那些同学进行一次道歉。（可能同时还包括部分洛谷用户。）
这天是 CMO 的 Day2. 同机房有两名初二选手在下午参加了场外赛。其中一位选手 A' 比另一位选手 B' 少解决了 0 至 2 个得分点（即 0 或 3 或 6 分），满足 A 等于 A'，B 等于 B'。
假设上文的所有“或”均为均匀随机，则选手 A 比选手 B 期望高 1.5 分。
Remark. 上文中的选手 A 疑似达到了集训队分数线。
Day 0.
这天我执行了一个摆烂。
Day 1.
这天是 NOIP 的日子。这天我吃了三块巧克力。巧克力很好吃。
08:30 NOIP 开始了。负责公布压缩包解压密码的监考老师在记事本中写下了密码并将其放大，使得所有人应当能够看清楚密码。注意到密码的第一个字符是 !（英文字符）。监考老师输入了 ！（中文字符）并在调整字体及字号后发现无法将此字符与下一个字符之间的空白去除，进而反复向大家强调这里没有空格。我不记得我有没有笑。在若干秒后有选手提出密码在输入后无法解压。在此后若干秒后老师修改了此字符。我好像笑了。
08:35 我已完成电脑系统的切换，lemon 的配置和第一题题面的阅读。
08:40 我已获得第一题的思路。我开始写代码。
08:45 第一题的代码长度较短。我进行了约 0 秒的调试后在 lemon 的总分变成了 100。这样说话好诡异啊。读者似乎需要进行约 0.1 秒的一步思考。
08:50 我已完成第二题题面的阅读。
08:55 我开始使用草稿纸。监考老师称之为演草纸。同时我注意到部分同学开始出入机房，理由是上厕所。
??:?? 我并不记得这件事情发生的时间，但认为应当插入于此处，即使我认为此事件不在此时发生。有一位同学在上完厕所回到机房后由于正在思考导致其缓慢走回自己的座位。监考老师认为他可能在观看他人的电脑屏幕并制止之。我没有笑。
09:20 经思考，我好像得出了一关键性结论。小 X 的策略不优的等价条件是其最终在剩余 1 元钱时遇到一个 2 元钱的物件，价值为
09:25 我在代码注释中写到了 little X。它使我想到了 littlebug. @littlebug 是一位洛谷用户。
09:45 我一边写一边完善解法，于此时完成了代码。
09:50 我对着 sale2.in 调试代码，并于此时在 lemon 上获得了 200 分。注意我为 sale 暂时开了 10s 的时限。原因是我的代码时间复杂度是
09:55 我在 1s 时限下通过第二题。优化方式是双指针优化每次循环里的 lower_bound。
Remark. 我的做法和题解区里大部分做法相同。可是我不清楚为什么我没有用到 Vandermonde 卷积。这份代码通过了洛谷上的全部数据点。
10:00 我已完成第三题题面的阅读。与此同时，我感到疑惑。我不明白树高的用处是什么。
11:00 不知不觉间我已完成一个小时的罚坐。此时我已经尝试了各种假的贪心算法和一个假的树形 dp。我打算去阅读第四题的题面。
11:05 我已完成全部题面的阅读。我发现第四题暴力枚举区间长度后单调队列可以获得 40 分。我赞美了中国计算机协会。
11:15 我已将第四题的 40 分代码完成。
Remark. 值得注意的是，我在 CSP-S 赛前集训中的某一天模拟赛中 T1 获得了 20 分，原因是我不会写单调队列。我现在会写了，可喜可贺。
11:45 更进一步的对特殊性质的思考未果后，我返回了第三题。
12:05 我观察了 tree1.in 和 tree2.in 两组数据。我发现 tree1 的第一个数据和 tree2 的第一个数据都存在一个对最优结果的构造满足：每个子树都为一段连续区间且每个节点都为字树内最大值。并且每个子树为
12:15 我发现 tree1.in 的第二个数据不满足这个性质。我认为可以通过一个 dp 来决策每个点是为兄弟子树的区间“添砖加瓦”（即扩展区间，在其右端点后补充数字）还是“自立自强”（即自己成为一个
12:25 我发现这可以用一个类似贪心的思路解决。对每个节点观察是给其根链上的节点子树 mex 值都增加其子树大小更优还是对其子树做和整棵树一样的事情更优。我写了一下后发现可以通过 tree1.in 和 tree2.in。（好像是这样的）
12:45 我发现这好像是假的。hack 我也不记得了。我好像重新写了一个更暴力的 dp 并进行了暴力的子树合并。
Remark. 我现在写这份游记的时候似乎又认为这个解法是正确的了。
12:55 我好像发现这是假的，但可以通过一部分数据，我不再处理这道题并开始摆烂。
13:00 NOIP 结束了。我和同学交流后发现有并不少的同学都解决了第三题，但似乎基本都没有及时完成调试。我在后三个小时内获得了 40 分的总分。真是可悲。
Remark. 我最终的第三题代码在洛谷上可以获得 8 分。