NOIP2024 游记

坐标：SC CD。

CSP 游记忘写了，也懒得补了考的太差导致的。

Day -1

一周的联考都打的稀烂，当天甚至获得了 80 分的好成绩，T1 sb 构造放 n = 0 的 corner 爆炸，后面直接爆炸一分没有。

就当为正赛攒 RP 吧。

Day 0

摆了一天。

随便敲了点板子，发现边双 / 点双的板子忘完了，爆。

第一次周五不上晚自习，回家继续摆。

睡觉前看了一眼 NOIP2022 T1，感觉是比较好写的计数，飞快写完过了就睡了。

晚上睡得不太好。

Day 1

说好的 7:50 在校门口集合，结果一车人七点半左右就直接进去了。/fn

考场不是前几天在高新试机时的机房。还好机子不是 Win10。

开始后扫了一圈，T1 应该是贪心或者 DP，T2 大概是 DP，T3 没怎么看懂，T4 看上去很可做。

回去看 T1 立马冒了个思路，想了一会发现题目读错了：我以为 s_1 和 s_2 的 t 串是相同的。重新思考过后发现似乎可以双指针直接贪心匹配，不过细节貌似很多。

开写！中间写错了一车细节，导致调到了将近 1h 才过掉小样例，但大样例直接爆炸。

想先丢掉看后面的题。但转念一想我 T1 不过我打锤子呢？于是继续冲 T1。此时隐约感觉到结论应该没假，想写拍子。

突然发现 B 性质错了，直接对着 B 性质调，发现 ans 越加越少。在 1.5h 的时候意识到少打了一个括号导致运算优先级出现问题（加法优先于 ==，我是唐氏儿），改正后立马过了大样例。O(n) 跑飞快。

写了 2k+，有可能是 T1 最长代码？

为什么我感觉 T1 难度不小？还是我唐完了？

先去看 T4。发现 O(n^2 \log n + nq) 的 20 分是好拿的，预处理出 f_{l, r} 表示 [l, r] 内的点的 LCA 即可。然后对着数据范围干瞪了 \infty 年，想冲链但是没冲出来，爆。

赛后发现 k = r - l + 1 是简单的，O(n \log^2 n) 也好想，但是为什么我啥都不会呢？

此时已经只剩 1.5h，我还只有 120 分，有点红温。要拿一等必须 200+，此时去拼 T3 的暴力是无意义的，于是果断开 T2。

先吃两块士力架冷静下来。一眼观察出我们只需关心相邻的已知位置，这样就可以 DP 了。设 f_i 表示目前决策到第 i 个已知位置的合法方案数，转移的话大概是 m^? 搞一下即可。

感觉比较好写，大约 12:00 调过了小样例，发现大样例 RE 了，原因是快速幂指数为负数。才意识到输入的已知位置是乱序的，sort + 去重过后过掉了大样例。

复杂度 O(m \log n)，一车取模，大样例 0.2s 问题不大？

切了 T2 感觉如释重负，一等有了？

还剩一个小时，开 T3。原来就是求把原树上的边连成图后从关键边开始遍历能得到的生成树个数。发现 A、B 性质的 16 分是简单的，写完大约 12:30。最后半小时冲 k = 1 的分，但没有冲出来。

估分：100 + 100 + 16 + 20 = 236。出来问了一圈同机房的一众大佬貌似都 260 左右，感觉考的不算差。

中午聚一起吃了火锅，舒服。

下午有神秘 cw 老哥问我们 cdqz 考得如何，边聊边摆。

Day 2

luogu 民间数据 T1、T2 过了，应该问题不大。

Day 7

查分，没有挂分，舒服。

Day 9 + 10

补了 NOIP T3 T4，思路都还是比较简单的。T4 写 2h 喜提 6.2k 代码，会不会是最长的呢？