NOI 2024 游记

Day -1

报道日。室友是 zqc,wyc,yjh。

晚上狼人杀，经典场面《狼人空刀》《ly 第一天裸点三狼》。

Day 0

开幕式。dzd 讲话仍然是贡献了最多乐子的环节。一分钟爆出两个沙东笑话。

下午笔试。打开一看笑嘻了，笔试答案已经有人帮忙填好了。Zayin 重出江湖。然后宣布 3:15 重新开始，笔试一遍写完之后和下发的答案对了一遍没有问题，然后 AK 了笔试。

出场后知道下发的不是 std，而是多测没有清空，留下了上一届选手的答案。感谢 SD-06 给我留下了正确答案。ysy 得到了一份错误答案并相信了错误答案喜提 98 分和大家的嘲讽。

晚上被制裁了不能狼人杀，和几个室友和 ly 出包魔法师。魔怔。

Day 1

睡得不是很好，五点四十就醒了。进场开题前特别紧张，不断深呼吸试图调整情绪但是用处并没有多大。开题先看了一遍，T1 像是往年常见的 T1 数据结构。T36 神秘交互。T3 感觉是不可做的图论。决定顺序开题。

第一个小时给 T1 胡了一些 Hall 定理相关做法均在大样例 WA 了 \(O(1)\) 行。在 1h 的时候心态开始急急急。我怎么能连 Day1T1 都不会的。急急急。在 1.5h 的时候被迫承认 Hall 定理和这题基本无关。心态非常炸裂，白白浪费了 1.5h。接着就猜了出现集合的集合相同是充要条件，并且可以双指针维护。写了个异或哈希+umap 通过了 pretest。发现 pretest 有 20 个之后询问是否是最终数据，回答是无可奉告。这时候大概已经过去了 2h。

认为自己已经比大家落后了 1h+，心态还是有些炸裂的。于是以一种急急急的心态去看 T2。这我哪会啊？想了 10min 之后发现我把求最大值读错题成了排序。接着就会了 \(t=20,s=n-1\) 的做法和 \(t=1,s=\frac{n(n-1)}{2}\) 的做法。感受到正解就是两个结合起来。每次可以用后一种暴力来减小问题 \(n\) 的规模，如果是把规模由 \(x\) 减小到 \(y\)，那么尽可能平均分是最优的。也就是每一部分的大小都是 \(\lfloor \frac{x}{y} \rfloor\) 或 \(\lceil \frac{x}{y} \rceil\)。于是就可以 \(O(tn^2)\) dp 出来最优策略。接着发现了转移具有决策单调性，所以可以 \(O(tn\log n)\) dp。写了一下很快跑出来了 \(t=8,s=1099944\) 的策略。实现了这个策略并一遍通过了 selfeval。这时候大概过去了 2h50min。

用 T2 抢回来了一些时间之后心态好了很多。2h+ 我能搞不定一个 T3 高分暴力？还真搞不定。想到 3h30min 发现自己真的不会 \(O(\text{poly}(n))\) 的做法。尝试树形 dp，容斥，网络流，2-SAT 均无果。只剩 1.5h 的时候决定先把会的暴力拼出来，暴搜和 A 性质都是简单的，B 性质贪心一下就可以了，结果一开始还以为需要 bitset 维护，调了很久调到 4h40min 才通过 selfeval。用了 50min，在最后 20min 才拿到这 16 分。最后 selfeval 100+100+36=236 离场。

出门遇到了 jsy，他也是 236，他说感觉是大众分。并且看到群里云浅说队线 300 分，感觉自己没救了，非常难受。接着队线就从 300 掉到 264，并一路掉到了 ~240，才发现自己实际上并没有差太多。下午查分之前急急急，但好在最后没有挂分。cxm 236，zyz 247，dwt 225 都在队线附近，希望大家后天都能进队线。

讲题的时候超超发现 T2 出题人是 liuzhangfeiabc，并且他被这题创了，就一直在瑞平 qdez 的出题人一旦出手就是 shit。我听了 T3 发现其实 \(O(n^3)\) 很简单，痛失 \(28\) 分。但是被 \(O(2^n)\) 草了那么多分是什么情况啊。

晚上跑到了 HA 宿舍狼人杀。因为在 SD 宿舍被制裁了。我作为悍跳做出了给对跳发第二晚查杀的神秘操作被推出去。另外还有 zqc 第二天悍跳点一个查杀且不给警徽流的神秘操作。感觉很乐。

Day 1.5

上午参观博物馆，腿要废了。cxm 向我预告明天会有 IMO Au 出题，也就是会有数学题。有数学题我不是就完蛋了？寄。

下午在宿舍开摆，一直在想明天怎么打才能进队。我推测明天会很难且最终队线会在 ~500(flag)，所以决定切了 T1 并尝试切 T2，如果失败就打满暴力的策略(flag2)。

Day 2

开考前一直在安慰自己就算拿了 Ag 也有 whk 兜底，并没有使心态好多少。因为我还是渴望 Au 啊，渴望保送，更渴望和那些我以前可望不可即的选手们站在 OI 比赛的最高领奖台上，笑着接受别人的祝贺。OI 生涯的最后 5h，我希望能不留遗憾。

T1 神秘数论，看着像线性筛。T2 数据结构优化 dp。T3 tarjan 类图论。数学题真来了。但是我还是觉得要顺序开题，T2 不像好做的题的样子。想了一会 T1 推出来了一个神秘做法，在 gcd 的过程中 \(\lfloor\frac{a}{b}\rfloor\) 是偶数是合法充要条件。但是并没有什么用。1h 啥都不会感觉很破防。点开大样例突然发现答案很小，于是开始尝试 \(O(ans)\) 的搜索，很快发现每个数只会被唯一方式拓展到。写了一下获得了 \(85\) 分，卡了卡常获得了 \(90\) 分。于是做出决定弃掉这题，去做 T2。

T2 \(O(n^2)\) 的 dp 是显然的，开始考虑如何优化。首先观察到每次冲刺之后深度更小，去转移这个东西。用线段树下标表示深度，维护从根到当前节点的链每个位置转移过来，还需要维护转移系数。也就是需要进行 \(x\) 单点修改，\(y\) 区间加，查询区间 \(xy\) 和的线段树。所以要去思考如何找到 \(y\) 的修改，并描述为 \(O(n)\) 或 \(O(n\log n)\) 个区间修改的形式。

\(l_i=r_i\) 和 \(h_i=0\) 的特殊性质都过于唐了。决定去想链的特殊性质，每个点势能转移到一段区间的，从上到下区间会扩展，倒着做先预处理出来每次区间往里缩的过程。每次操作把右端点在 \(x\) 以后得缩到 \(x\)，左端点在 \(x\) 以后的删掉。后者直接用 set 维护，前者用一个线段树维护每个右端点上有多少，每次操作找到所有 \(x\) 后面的放到 \(x\) 身上。这样每次缩掉的都合并成一个，所以总的势能是 \(O(n)\) 的。

会了链之后想没有特殊性质，发现只需要把 set 启发式合并，线段树换成线段树合并之后是完全一样的，所以需要想从上到下转移的过程。很快发现需要类似启发式分裂的维护每一条重链，每次把轻儿子全部删掉，最后在对于每个轻子树递归考虑，这样这一部分操作次数是 \(O(n\log n)\) 的。上一部分向外扩展的操作次数是 \(O(n)\) 的。所以总复杂度是 \(O(n\log^2 n)\)。会了的时候大概是 2h30min，还有两个半小时但是不好写。

这时候需要做出决策去冲正解还是拼暴力。因为我感觉这个难度就是集训队题的难度，我在 Day1 分数不高的情况下做不出就没有集训队。而低位 Ag 和高位 Ag 没有区别，所以毅然决定开冲！这是我两年 OI 中做的最正确，最热血的一个决定。现在看来，虽然上百次模拟赛已经逐渐磨平了我的热血，让我变的逐渐保守。但我在最后一场比赛，仍然做出了激进的决定，去为自己拼搏一次。

写到 11:30 写完了。调到 12:00 过了样例，一测 selfeval 45 分。我的心脏一瞬间停止了跳动，难道我的两年 OI 就要这么结束吗？我不甘心。我依然决定接着冲正解，很快发现预处理的线段树部分复杂度写假了，修了一下发现又 WA 了！修到 12:30 过了大样例。在 selfeval 显示 Right Output! 100pts 的时候，我的双手都感到麻木，仿佛血液被抽走了一般。我知道，我真的做到了。最后一场比赛，最后一次为自己拼搏，我没有留下遗憾。

接着在 22min 里拼了 T3 B 性质 \(O(n^2)\) 和 A 性质，来不及写暴搜了。这一段时间我的手指一直发麻，似乎是在为刚才的劫后余生感到庆幸。最后看着 selfeval 的 90+100+20，结束了比赛。

宣布离场时候看见对面 dwt 哭了，他 T2 没调完。很替他感到很伤心和可惜，我相信他是有做出并调出这道题的实力的。安慰了他几句就出场了。

查分前十分钟我就在楼梯口焦急地等着，我想了很多，如果我挂了分会怎么样，如果我不挂分且能进集训队又会怎么样，思绪处在一个非常纷乱的状态。时间指向 15:00:00 的时候，我和很多人一起冲进了会场，用颤抖的手输入密码，打开文件，拉到底看到最后的 90+100+20=210，悬着的心终于放了下来。

接下来就是去问了问别人的分数并等待集训队线。集训队线由 534 变为 536，最后定格在 538。最终，我实现了两年来的梦想。

问了问别人的成绩，zyz 577 开了，云浅，jsy,zhk 也进了，非常替他们感到开心。省内 wyc,zqc 也都如愿拿到 Ag，也发自内心的为他们感到高兴。cxm day2 发挥不太好，希望他明年能进队。我相信，大家都会有光明的前途。

晚上继续狼人杀。

Day 2.5~

闭幕式，我在金牌第一批登上了领奖台，站在领奖台上接受别人的掌声。终于有一天，我和那些我一直认为遥不可及，只能仰慕的人站上了同一个领奖台，得到了 OI 生涯的最高荣誉。那一刻，我有些分不清究竟是现实还是我的幻想，似真似幻，也许就是这种感觉吧。

晚上 SD 省队互唱。最后我们唱了句号。也许这就是句号了吧，两年 OI 中的朋友，将会在很长一段时间里没有机会再见了，我不由得感到有些伤感。但这又不是句号，因为我相信，我们注定会在北京重逢的，这又会是新的开始。也许在某一个平行时空，我没有冲出 T2，拿到了银牌，但我们最终一定会在北大重逢的，平行时空终究会汇于一点。我们虽然殊途，但我们注定同归。

时针滴滴答 你还记得吗

说说心里话 你还怀念吗