NOIP 2024 游记

出分了再写，别急。

好像打赢了，难得牛了一回，只是我运气好而已。

Before Contest

模拟赛随机倒闭，不会做人均题，各种挂分，什么道理呢。

好在最后一场信心赛 AK 了，总算找回一点自信。

Day 0

在家开摆，tetr 真的很好玩。

下午写了点板子，发现自己居然会写 tarjan 和 primal-dual 费用流，信心与期望倍增。

晚上出去采购了点零食和巧克力，买了两瓶茶，本来想参考某同学建议带两罐红牛，不过考虑到我从来没喝过所以后来也是买了放家里闲置着了。

看了一点经典题，看了两个模拟费用流题，看了一个 DS　题，复习了一下线段树历史和，发现自己能编对了，真的有进步了。回顾了一下去年 NOIP T3 T4，感觉现在没有不会做的道理。但是去年就确确实实是，水平太低了，倒闭了。很害怕这种冰冷的无力感啊，希望今年能顺利一点。

晚上稍微有点睡不着，毕竟是高中第一场比较重要的考试了。好在听了一会儿歌之后睡着了。

Day 1

早上起来给自己冲了一杯咖啡，喝了一口发现苦得逆天，不知道自己搞了什么神秘操作，于是兑了点牛奶带上路了。

抵达 efz，进场的时候发现好多人都到了。左右的哥们都不认识，再右边是鲮鱼大神。

发题。一上来没抄对解压密码，人品有点坏。还是按照既定策略，OI 赛制不抢首杀，先认真读 15min 题，把每个题都做初步的理解和思考。efz 就是出手大气，草稿纸都发 A3 的，羡慕了。

T1 看起来可能是个 dp，但是看了数据范围之后，感觉还是得贪心，想了一下发现贪心有道理的，调整可以证明每次两种决策可以任意选。

T2 读起来就感觉是个签到题，仔细一想确实，因为每段是独立的。每段内部是好算的，反过来算不合法的方案数，一定是从第一个开始一直推到最后一个，然后最后一个不符合条件，那排序算一遍就行了。

T3 直觉是一些弦图相关的东西，因为画出来之后相当于原树的每个点是一个团，团与团之间有连边，对这个东西计数 dfs 树。但是 k 条边的限制没什么好的处理方法，先跳过了。

T4 是个 DS 题。初看感觉不太可做，但是结合数据范围应该是 polylog 的。感觉是支配对相关算法，想了一下有个明显的 DSU on tree + 三维偏序的 3log 做法，感觉应该能优化，但是先不管了。

这时候听周围的键盘声，感觉声音明显不如去年开场 15min，估计签到并不容易。写了一下 T1，没过大样例，咋回事呢。调了一下发现是自己把 cnt 数组开成了 char，成功把自己整绷不住了。

再写了一下 T2，很顺利一遍过了。这时候大概 9:15，感觉签到还算顺利，毕竟这两个题还是比 CSP 前两题难了不少的。

重新回到 T3 T4 二择。考虑到我可能还是更会计数题一点，而且我的 T4 做法一点不靠谱，再开一下 T3。

首先考虑一下 k=1，感觉就是所有团都得满足一条链的起点是某个点，那不就是 \prod(siz_i-1)! 吗，写了一下，用对应样例验证了正确性。继续思考 k>1，如果起点在一个团里那就相当于要算起点至少是一个点的链，但是如果出现 k=3，然后 1,2 一个团 2,3 一个团的形态就炸了，怎么办呢。

对着这种奇怪计算方法算了大半天都没有任何进展，写了两个神秘 DP 状物，都只能通过菊花这种很蠢的样例。此时已经过了两小时，有点红温。

还好这时候想起来还可以上厕所，于是出去洗了把脸回来。这时候意识到得把前面的错误想法全都抛开重来了，再次 dfs 做法的时候清醒多了，一下就意识到容斥了。容斥完了之后，一个团如果钦定 \le 2 个方向就是 (sz-c)! 种方案，如果钦定三个及以上方向就无解了。所以可以直接 DP，赶快花 15min 写了，但是过不了小样例，细节挺多的，又红温了。

还好这时候想起来还可以再上厕所，于是出去洗了把脸回来，感觉冷静下来了。调了一下发现一个地方漏了一个系数，一调就过了小样例，测了一下 12 个大样例，都过了，放心多了。

这时候还剩 2h 做 T4，这怎么输？重新思考了一下，发现区间 LCA 就是相邻点 LCA 深度最小的那个，所以转成了链上问题，那么支配区间就只有从大到小合并的 \mathcal O(n) 个，这样三维偏序就是 2log 的了。

由于之前模拟赛有过三维偏序 2s 过 2e6 的经验，合理估计了一下感觉常数极小，应该能过，于是花半小时多小时写 + 调，测了一下大样例只要 700ms，赢了。

结束了？结束了。

3h20min，结束了。

激动的心、颤抖的手...

刚刚从紧张的情绪中淡定下来，突然有些缺氧和头晕（感觉可能是一下子从大口喘气的状态回到正常呼吸的状态），喝了点茶冷静一下，休息了五分钟之后还是决定检查一下。听起来周围的选手都还在敲键盘，感觉自己优势很大不能打丢了。

给 T1 写了暴力写了拍，给 T2 T3 测了边角数据，给 T4 写了拍，拍到大概 4h15min 觉得差不多了。监考老师提醒 linux 选手准备把文件拷回 windows 了，最后再开大栈按照 pdf 上的命令测了一遍所有大样例，全部通过了。

清理了一下文件，时间到，下班。

结果我的电脑网络还爆了，交不上代码，不让我下班是吧。最后请监考老师手动交了。

总共好像恰好写了 10640B 代码，零食和巧克力激动得忘了吃了，见笑了。

出来之后听下来感觉比去年略难一点？还有一些神秘 corner case 把一些 T2 T3 写法不同的卡了。出来想了一下发现那个区间交的三维偏序很容易变成二维偏序，那就是 1log 了。不过大样例 700ms 稳得不行，因为做法和树形态几乎无关。

似乎是第一次正式赛时做出点不止普及组小朋友水平的题，终于没有那种空有一身绝技的遗憾了。

没啥心思交流分数，回家打摆了。

Day 2

睡觉。

Day 3~5

韵律源点，双星了。

Day 6

tetr.io，S+ 段了。

Day 7

出分了，100+100+100+100=400，取之。

SH 省队最后一名记得请我吃饭（不是）。