NOIp2024 游记

on$ $11.30

今年在山东理工大学考，离家的直线距离不到 2km

day -1

晚上在学校吃了考试前最后一顿晚饭，奖励自己吃了鸡肉卷。

晚上去试机，不太到 19：30 的时候信息楼里外人山人海，于是很聪明的和 bth 一起等了几分钟，发现人很少的时候开始上楼。（逆天的 1 考场在 3 楼）

进了考场先看到了 zmy，找到座位坐下后就看到两个队爷 cxm 和 chb 在交谈什么。然后发现左边是队爷 ysy。

调了一通 dev，打了缺省源，然后开了虚拟机试了试，除了很卡没啥毛病。鼠标线很短，依旧暴力硬扯解决问题。

19：57 监考说时间马上到了，虽然不是很理解，但是也没啥事儿干了，于是准备离场。在考场里转了一圈，找到了近 10 个队爷。（但是没看到 wmh？）

很顺畅的出了楼，心里高兴了很多。

day 0（contest day）

早上 7 点多起了床，感觉自己非常凌乱，但似乎状态挺不错的。目标仍然是开考 1h 后任意时刻满足：得分（pts）严格大于时间（min）。

到了信息楼底下，拿了学籍证明，才 7：45。

等到快到 7：50 时上了楼，大概是考场第 3 个到的。过了一会儿看到了 chb 和 wyd 大佬。

进了考场，开始试机，顺便打了对拍，大概到 8：20 左右翻了一下压缩包，然后发现竟然没有题目的 ans 文件是 1KB 的，很不爽，然后发现可能是好几个多测。

8：25 左右监考开始朗读密码，原来考场里没有大屏。两个密码都是一遍输对，非常爽！

8：28 开始读题。想了 2min T1，发现不会，意识到似乎题并不是那么简单。

8：30 监考说考试开始，然后就有几个队爷开始砸键盘。但是旁边的 ysy 好像在看后面的题，于是我以为 T1 不是签到，然后开始通读题目。

8：40 我读完了 4 个题。然后悲哀的发现 T1 是签到。于是只能开始用心思考 T1。

8：45 我对 T1 稍微有了一个想法，于是开始写。这个时候考场里大部分队爷都在砸键盘。

8：55 大样例有些不对，于是开始肉眼查错+手搓小数据。

9：15 仍然没有发现错误，于是非常慌张。然后随便滚了几下滚轮，看到了我把 a[j] 打成了 a[i]。改了。大样例过了。这个时候是 9：18。于是很快去上了厕所，吃了薄荷糖，喝了不少饮料。

于是我开始思考 T2。很显然这个数据范围直接表明了它就是一个通过 x_{c_j}=d_j 中的 c_j 来转移的 dp 或者直接计数。然后我意识到由于二元关系只有相等和不相等，因此 d_j 具体是多少不影响答案。所以不妨设所有的 d_j=1。

然后我开始疯狂推式子，枚举两个钦定的位置的距离，尝试打表找出规律。期间经历了很多，发现自己想不清楚，于是先去做了一下 T3，这个时候大概是 9：45。

T3 很快想出了 k=1 的做法，竟然有 24pts。开始尝试 k=2，式子也很快写出来了。尝试拓展到 k 更大的情况，发现应该是一个容斥，刚好与 k<=8 的 48pts 做法相吻合。开始疯狂推式子，然后推了个很奇怪的东西出来，然后开始写，只过了小样例。然后就意识到了不对，发现只能符合 k=1 的 24pts。

此时大概是 10：15。也就是说我在开考近 2h 时仍然只有 100pts。非常乱。好在我有薄荷糖。

于是开始沉下心来寻找 T2 的式子。意识到可以从反面来考察。又思考了一会儿得到了式子：v^{2(c+1)}-v^c。此时没有意识到这是 v=2 的式子。写了之后又过不了大样例。

然后不知道怎么想的就写了 v^{2(c+1)}-v^{c+1}+v^c 上去。然后所有大样例都过了。但是我还是没想清楚这个式子的含义。反正可以弃之了。这个时候是 10：47。

心情终于好一点了，然后发觉身上很热。于是脱了外套又上了个厕所吃了薄荷糖。

决定最后再回来做 T3。于是开冲 T4。

先写 O(qn) 的暴力。准确应该是 O(q*(r-l+1)) 的，能有 n,q<=5000 和性质 B 的 32pts。然后发现不想带 log 就需要写 O(1)lca，然后想了一会儿怎么做来着。我会！

然后又想了一会儿性质 A 的 32pts。链上的，我可以用 depth 排序，然后先预处理个主席树，然后维护区间内最长连续 1 的个数，然后套个二分，就行了。但是 2log 跑 5e5 有点悬。没关系，冲！

写了大概 25min，调了 5min，非常顺利的跑过了 query1.in 和 query2.in，然后 query3.in（链）RE 了。然后非常悲哀地发现应该是 dfs 爆栈了，而我也不会手动开栈，于是不得不写了个 data_maker 自己造 <=5000 的数据，两份代码一拍，嗯，没问题！

大概 11：45 左右整理了代码，遂弃之。

开始反攻 T3。

仔细思考。我不会容斥。尝试推出其他式子。考察 k=3 的式子是什么样的。发现必须容斥。我还是不会。甚至连 k=2 都不会。我不知道两条 key 左边的点怎么算。尝试写出一个 (c\cdot d+\dbinom{c}{2})*(deg_x-2)! 的式子。发现还是只能过小样例。于是我不会了。

12：20 左右，我发现还有链和菊花的没写，然后发现链的答案就是 1，菊花的情况，用我刚刚写的东西好像也刚好能算，然后发现链的情况也可以算，于是什么都没写就多了 16pts。

然后 12：30 高高兴兴地测了一下链的大样例，然后不幸地发现又爆栈了！我就造了几个链的小样例试了试，输出都是 1，没啥问题。然后发现菊花图我怎么测！开始手算菊花小样例，试了几个，也都没啥问题。大概 12：45 遂弃之。

重新测了四个题的所有能过的样例，都没啥问题。整理了一遍文件夹，12：50 装好了所有文件。等待离场。期间开了一下虚拟机，发现忘了用虚拟机测了。反正我也没写啥奇怪的代码，不管了。

监考提前了 30s 组织离场。

中午吃的理工大的食堂，非常好吃！

估测大概是 100+100+40+64=304，难度应该是绿绿蓝紫。要是不挂分，清北营应该能苟去了。

luogu 评的是蓝绿紫紫，还好。

听说 SD 只有 cxm AK 了（？）

upd on ???

官方出分：100+100+40+48=288，T4 终究 2log 还是跑不了 5e5

SD 高中生 rk18