NOIP 2024 游记：莫笑痴情太痴狂

Day -1

打信心赛，复习各种板子。用 FHQ 写【普通平衡树】，调了好久才过。

Day 0

上午复习了一些做过的 dp 题，写了篇博客 浅谈网格图优化 dp。又看到双序列拓展了，你猜今年会不会出一个单序列收缩。/kx

下午去霸树中学试机。通过了 A+B 和 expand。expand 喜提把 m 写成 n，调了 30min。希望明天不要出现这种事故。

Day 1

7:35 到达霸树中学。进行合照操作并面积了龙猫。

8:10 进入考场，发现 Linux 的机时晚了 8 个小时。我可以打到 21:00！

8:30 正式开题。读完第一题后直接想按照两侧是否固定讨论，并且想到能匹配就匹配的策略，很快确定了单侧固定能匹配就匹配的正确性（这里不匹配，留到后面匹配，不会增加匹配位置数量）；然后略画了一下就确定了两侧均不固定时能匹配就匹配的正确性。于是在 8:49 通过了所有样例。

8:50 开 T2。先认为只有两个固定位置相邻才会不合法；然后画了一下中间有一个空位的情况发现形成链也可以不合法，于是每个空位段之间独立，直接分别算每个段的不合法方案数送走。在 9:15 通过了所有样例。

9:15 开 T3，大约 5 分钟后发现一个点相邻的所有边形成一条链，且链头是来的方向。为了避免去重，首先考虑了哪些情况是合法的：至少有一个链头的方向有关键边。同时又意识到了链的结构之间互不影响，于是认为直接把每个点的合法链数目乘起来就可以得到答案。

事实上这样是错的，因为不能把不同来源的方案乘在一起，但我一直没有发现。9:45 写完上述解法，简单调试后通过了 1\sim 3 以及菊花和链的大样例，发现另外的样例错了。于是开始调试。

在长达 1h 的调试过程中，我多次考虑了链的结构之间互不影响的正确性，并多次认为它是对的，原因是链之间只有一个交点，一条链上两点是否连接显然不会由另一条链决定。但我仍然没有意识到一个链合法对起点边有要求这一事实。并由于菊花的测试点也可以通过，我更加相信了该做法的正确性。

10:40 决定放弃调试 T3，先看 T4。首先会了一个 O(nq) 的显然做法，然后将问题转化成了区间内 dfn 序最小和最大两个点的 LCA，尝试多种维度的扫描线无果。此后又考虑了 dsu on tree 的做法，用 set 维护子树内极长的标号区间，在合并城更大的极长区间时更新答案，剩的部分拆分后形如一个三维偏序。由于我认为合并极长区间的次数和启发式合并次数一致，均为 O(\log n)，因此我认为该算法复杂度是 O(n\log^3 n)，且讨论常数较大，很难通过 10^5 的数据点，于是考虑了各种扫描线减少 \log 的方式，仍然没有结果。

11:10 考虑到 \log ^3 的算法通过 10^5 较为困难，且代码难度相对较大，于是开始写 O(nq) 做法。期间多次将 ST 表和 O(1) LCA 写错。

11:45 通过前两个样例。回去调 T3。经过不断的尝试及思考，终于在 12:10 的时候意识到这个算法的离谱，尝试一些忽视起点的 dp 无果后，意识到必须对起点进行容斥。

12:20 开始考虑 k=2 的算法，并很快得到答案。

12:35 在原代码基础上进行补充修改，通过了 k\leq 2 的样例。此后尝试考虑容斥，先考虑了三个会被算重的点在一条链上的情况，且曾经短暂意识到这样的方案会被算 3 次，可以直接枚举相邻两个然后减去（这是正解）。很遗憾由于脑子里过于混乱，这个方案被我 pass 掉了，后来甚至画出来一个点周围连出去三个方向的合法起始边的图（这显然不成立），于是认为只能 O(2^k) 做容斥，太难写遂放弃。

13:10 在确认单上签字。最终得分定格在 100+100+56+32=288。很吉利的数字。

下午 DeepSkyCore 讲了 T3。发现在确认枚举相邻两个起点减去的做法正确后，我可以在 1min 之内会后面的 dp。很遗憾赛时太混乱没有想清楚。

Day 2

早上看群发现在讨论 T4 dsu on tree 的做法，突然意识到由于空隙只有 O(n) 个，所以合并只会有 O(n) 次，也就是说我赛时想的做法实际上是 \log^2 的。很遗憾赛时太混乱没有想清楚。

感觉整场比赛的失误很大程度上都来源于 T3 对着假算猛调没发现（注意到这个假算有 40 分），T4 没敢写看起来是 \log^3 的做法或许是另外一个失误？两个小时应该够我写出来这个做法的。

后记

接下来该省选翻盘了。兄弟们加油冲冲冲！

红尘自有痴情者 \ 莫笑痴情太痴狂 \ 若非一番寒彻骨 \ 哪得梅花扑鼻香

后后记

Day 7，12 月 6 日。提前十分钟打开申诉页面查分。288，没有挂分。万幸。

祝读到这里的朋友们，无论是已经退役还是仍在路上，都一切安好、万事如意。