NOI2024 翻盘记

前排提示：这里的“翻盘”指的不是 Day1 寄了 Day2 翻盘（虽然也有一点？），而是 Day2 单场比赛的翻盘。

2024.7.12（UNR 笔试）

没看到与题库相比改了答案，喜提 \(99\)，正赛可不能这么粗心！

2024.7.13（UNR Day1）

唐完了。

上来 A 结论假了，浪费了一个小时。

B 式子推错了，改对后以为单次复杂度是 \(O(V^2\ln V)\) 的，想了好久怎么优化。

最后一个小时看 C，被榜诈骗了。以为是简单题，激进起来想正解，结果暴力分只拼了一点点。

喜提 \(100+100+14\)，rk74。

2024.7.14（UNR Day2）

应该能稍微翻下盘吧？

A 看完题就会做了，成功抢到了一血。

B 写了一个 \(O(n\log V)\)，样例过了 \(80\) 分。

C 先拼一点暴力，发现写了随机的分就可以过所有样例，预感又要有人被诈骗。

后来在 BC 之间反复横跳，但啥都没想出来。

\(100+40+40=180\)，单场是 rk27。

两天合起来只排在 rk47，成功 Ag。达成成就：UNR 排名是去年的五倍有余。

2024.7.16

报道日，发现宿舍是按学校顺序排的，舍友是 sky 和两个双十的 D 类。

拿到了徽章，但决定在考完 Day2 之前还是先不进行什么社交活动。

2024.7.17（笔试日）

开幕式 dzd 依旧稳定爆典，贡献了选手们为数不多的笑料。

其他部分也就中规中矩，除了后面这个表彰仪式简直又臭又长/qd。

下午笔试，做了两题之后发现帮我选好答案了？？？致敬传奇出题人 Zayin。

于是延时了 \(15\text{min}\) 后重新开始，我没存答案，不过还是顺利 AK 了。

出来听说下发的是去年同准考证选手的答案，有人被坑了。

晚上睡得很好。

2024.7.18（Day1）

开题先看了一圈样例，发现 B 是个交互，大感不妙。

从 A 开始开，第一眼不会，想了一下发现构成双射的数之间可以随意选择匹配，这样就会多项式复杂度做法了。

想了一下可以哈希优化，加上双指针从以做到线性，在大约 \(15\text{min}\) 的时候通过所有大样例。

打开 selfeval 一测，发现给我爆 ce，看了一下代码感觉没问题，于是举手向监考求助。

他过来一顿指点，又让我交了好几发 ce，然后去问技术人员怎么回事。随后通知说 selfeval 锅了，正在修。

于是先开 B，一开始没看清楚数据范围，以为直接分治就做完了，写了一下发现算上第一个包只有 \(26\) 分。

期间 selfeval 修好了，一测发现怎么 A 有 \(20\) 个点？pretest 赛制？好时代要来了？

想 B 的优化，感觉可以随着层数的变化从二叉变成多叉，写了一个贪心状物拿了 \(52\)，再加了一个剪枝获得了 \(69\)。

先丢掉开 C，很快就观察出了结论，写了个 \(O(n^2)\) 获得 \(56\) 分。发现只要每次快速找到只剩 \(1\) 的路径就做完了，感觉自己能做出来，于是继续想 C。

又想了好一会，发现自己不会低于 \(O(n^{1.5})\) 的做法，只会一个 \(O(n\sqrt n)\) 的 kdt，和 \(O(n\sqrt{n\log n})\) 的分块。

我并没有吸取 thupc 的教训，想着 kdt 怎么着都能过个 \(10^5\) 吧，于是开始莽。写了将近两个小时发现比 \(O(n^2)\) 可以多过 \(0\) 分！

感觉不能要了，先回去看 B，发现我其实可以把所有分叉的可能搜出来，状态数不会太多，获得了 \(t=9\) 的 \(78\) 分。

为什么我不能做 \(t=8\) 呢？我的多叉不像正常人一样是平均分，而是直接把余数丢到了下一层，于是将所有状态搜出来都过不去 \(t=8\)。

最后的时间想着写个 C 的分块，看看能不能冲过 \(10^5\)，但写到一半感觉写不完了，于是转拼菊花的分，但不知道为什么到最后都没调出来。

最后是 \(100+78+56=234\)，出来一问，发现 B 是简单题，也有一些人过 C。感觉寄飞了，要比大众分低个 \(30\) 分。

福建 E 队一个 \(264\)，一个 \(252\)，而我们 A 队无人通过 B 题，感觉团体总分又烂掉了！

下午讲评，深刻地意识到了自己场上有多蠢。

小道消息说队线含 DE 是 \(240\)，那我吃个 A 队的 \(5\) 分只低了一分，还有救。

2024.7.19

社会活动，三峡博物馆，我不评价。

晚上睡得不好。

2024.7.20（Day2）

进场发现 A 是神秘数论，B 是看起来很可做的 ds 优化 dp，C 没搞懂。

先看了 A \(30\text{min}\)，发现自己除了知道可以辗转相除判无解以外一无所获。

我 D2T1 不过我打锤子呢？至少得过一个题吧？

于是先写了个 \(O(nm)\) 的 \(50\) 分，去看 B。

首先的想法是对 \(h_i\) 按顺序 dp，通过启发式分裂来维护一些东西，然后用 ds 维护树形结构的一些和。

先写除了启发式分裂，剩下都用 ds 维护的版本，写了好久都过不去样例，在 \(2.5h\) 的时候，我忽然意识到，我的转移系数假完了！顿时冷汗直流。

先改了改暴力 dp，在 \(3h\) 多一点的时候终于拿到了 \(O(n^2)\) 的 \(25\) 分。

此时我有两种选择：

1. 放弃这题的正解，选择拼看起来不少的部分分，但不一定够时间写其他两题的分了。

2. 继续冲正解，但冲不出来的话分数就会烂掉。

上了个厕所冷静思考了一下，如果选择第一种，那么我必然达不到 Au 线，而我此时应该已经上了 Ag 线，低位 Ag 和高位 Ag 没有区别！

于是我毅然地采取了第二种决策。

首先仍是对 \(h_i\) 按顺序 dp，有两种贡献方式，每个点有一些存活时间，在存在的时刻，他们的贡献是对到根路径的一个前缀。

先把转移方式改成上述的，并用倍增+树剖加速维护，调过样例的时间大约是 \(4h\)。

还剩最后一个算系数的部分，似乎还要用一个类启发式分裂的状物来做。我没写过启发式分裂，这个也不很板子，没把握在极短的时间内写对。

只剩 \(1h\) 了，我还只有 \(75\) 分，有点红温，要倒闭了。

但很快，我就意识到系数可以在一开始预处理，这样可以倒过来维护，用并查集+线段树合并就可以做了。

开写！一遍就过了所有样例，在 \(4h10\text{min}\) 的时候终于在这题拿到了 \(100\) 分。

回去看 A，观察到答案很小，于是直接记忆化搜索一下拿到了 \(70\) 分。

进而我发现由于辗转相除过程的唯一性，所遍历到的状态必然不重不漏，不用记忆化就可以直接搜到 \(85\) 分。

在 \(4.5h\) 开 C，发现暴力、性质 A、性质 B 的 \(O(n^2)\) 都是简单的，飞速地拿了 \(25\) 分。写完后还剩 \(5\text{min}\)，也写不了其他分了。

\(5+100+100+78+56+85+100+25=549\)。

出来问了一圈大家的成绩，固然比这个成绩高的很多，但我知道自己真的翻盘了。

预估的金牌线一路走高，从一开始的 \(529\)，到了 \(534、536\)，最终定格在了 \(538\)。现在的选手真是卷得离谱，也许未来有一天，金牌线会达到 \(600\) 甚至更高。

福建今年进了四个集训队，分别是我,ljr,hjx 和 wzh。其实早该有四个了，但是前几年的选手总是在 noi 莫名的失常。

2024.7.21

闭幕式。

最后是并列 \(\text{rk}38\)，苟到了金牌的第二批。

福建的四个集训队全在后 \(20\)，不是很牛。不过也没关系，毕竟 noi 成绩也不带入之后的比赛是不是？

站在台上，看着胸口挂着的沉甸甸的金牌，我却没有产生什么高兴的成绩。也许是因为发挥与成绩不尽如人意？又或者是我认为自己一定可以拿到这块金牌？

接下来我需要考虑下自己的下一个目标是什么。是进入候选队？还是 cf 上 LGM？。但无论如何，至少我有资格思考自己未来该干什么了。