NOI2024 游记

省选 2024 游记 敬请期待

SX-03

Day -??

每天模拟赛被各种吊打。

不会猜结论怎么办。

Day 998244350

UNR 也打爆了。
怎么这么喜欢猜结论。

Day 998244352（报到日）

打板子，知道不会有用，纯粹是平复心情。
看别人的游记也是一个缓解紧张的方法。
感觉心情足够平静的了。
打铁就打铁，还是学文化课好。

Day 0

打板子。

开幕式很好看。

人应该有血性，应该有原则，不能丧失自己的原则。
—— dzd

下午试机，NOIP 只写了两个题，然后笔试，我还卡着没进去的时候就听见有人笑，刚开始以为下发 std 了，延迟 15 min，题都比较正常，提交完看记录全是 0 还问了一下正不正常。检查到最后一分钟的时候一刷新突然发现多选答案全没了，就很怕提交上去的真的没有……笔试完上厕所还回来发现其实是有的，那没事了。

听说试机应该多适应一下键盘，打点板子。现场打了一下已经忘得差不多的 Splay（文艺平衡树），然后写全套的暴力、数据生成器、对拍，拍上了。出去以后遇到了和 WC 一样的迷路，不过这回试完机还是白天，没有随机游走太长时间。

回宿舍继续打板子。zhjxaoini 大佬说可以听一下《好运来》。感觉有效缓解紧张。我想如果这回比较顺利，可以考虑找同学在文艺汇演的时候一起上去唱《好运来》。
感觉 D1T1 应该还是各种数据结构，我应该不太会有问题，没有理由紧张。

晚上感觉又有点紧张了，半夜突然就醒了睡不着，不过应该不会影响第二天。

Day 1

进场前心情非常平静。
进来发现我那个座位前面的上面正对着窗户，可以看见拿外面拿手机拍照的围观人员。
一坐下手脚就开始麻，想起来省选那两天也是这样，就是太紧张导致的，但是好像没什么影响。我还把桌子上压在键盘下面装纸质题面的袋子当成“键盘垫”了……
到时间，开始看题，看三个题的名字 set、richest、tree，猜测 richest 是数据结构 T1（）。pdf 密码大概是 just#remember19 之类的。怎么 T2 是交互啊，不是说三年一次吗？我不会交互啊！
好好看 T1，看见“判断等价”基本就可以考虑哈希了，再看等价的条件，想起了之前看过但没有写的一个模拟赛题，现在就是后悔，非常后悔。 所以还是想对 prv 哈希之类的，想着记 prv[i][0/1/2] 表示上一个与 i 的交集为 0/1/2 的位置什么的，然后开始猜结论，猜 A_{[l,r]},B_{[l,r]} 等价当且仅当 \forall i,j\in [l,r], |A_i\cap A_j|=|B_i\cap B_j|，手动验证样例 1 好像是对的，然后写 O(qn^2) 暴力过了前三个样例，感觉猜对了，然后一边跑第四个样例一边想着怎么证明刚才的 prv 和这个等价以及怎么哈希……样例四跑完了，diff，\huge\color{red}\text{WA!} 只有一行！
看了一下这个询问的区间长度只有 3，感觉应该是写挂了或者 corner case，但是看了半天也不知道哪挂了，手动验证发现：确实是结论被 hack 了。
布什，戈门，前三个样例就这么弱吗？
此时大概过了 50 min 了，感觉要完，想着不能一直想什么原题和 prv，全推倒重来。题目中的排列相当于把一个数 i 安排到一个数 P_i 出现的所有位置，所以可以考虑比较所有数出现位置构成的多重集，如果多重集相等就等价，正确性比较“字面意思”，好像容易用和哈希之类的东西维护，好像可以？然后应该可以对每个 l 求出最右的 r 满足等价，然后 O(1) 回答询问。
虽然知道可以双指针，但是想先找个方法查询 [l,r] 的多重集的哈希，想了个比较麻烦的动态开点线段树做法，然后一边写一边想双指针……根本不用线段树啊！我在想什么！然后 O(1) 分钟打完了，过了样例，在 selfeval 上测，100。怎么 selfeval 有 20 个样例？经过反复确认和 assert 确定这是 THUSC 赛制的 NOI 了，好运来！
开 T2，Sub1 显然，Sub2 有一个暴力是建线段树，然后想了个底层分块发现并没有什么用，同时开始看 T3，大概会指数暴力和特殊性质，写完指数暴力和性质 A 发现 B 是 2-SAT 求字典序最小解，我不知道为什么确信这个是 NPC 问题所以没有写。回去 T2 改多叉树，每层的叉数不同，想到了 vEB 树，最后调到 \frac{1}{4}\sqrt{\text{len}} 叉过了 78，觉得已经很了不起了。测 selfeval 发现本地 3s 在 selfeval 7s+，问工作人员无果，感觉是 selfeval 的交互库自适应导致的，卡了下常数 5.3s。然后没什么能写的了，最后几分钟又测了一下 selfeval。

考完 D1 觉得自己很了不起，结果问别人大概都差不多，金线非常高，但是好像还在银线上。

还可以，就是怕 T1 数组开小，查分之前先看了一眼 T1 代码才敢看分。

听讲题，我们至今仍未知道 T1 出题人是谁，据 dayux 说是加拿大人？不是新加坡就行。

Day 499122178

感觉考完 Day1 以后已经非常悠闲了。
社会活动，三峡博物馆，很好。

晚上打板子。

Day 2

pdf 密码 the#life#you#want24。

开 T1 看见“互质”之类的害怕是数论，然后先写暴搜，发现很多限制其实直接搜就是满足的，相当于一个数对 (x,y) 可以到达 (x+2y,y) 和 (y,x)，不能连续两步翻转，这就可以不重不漏，也不会出现不互质的，就可以写出 O(\text{ans}) 的 bfs，有 85（注意到剩下的不是 TLE 而是 MLE，埋下伏笔）。
没过 T1 有点慌了，然后看了一下 T2 感觉 O(n^2) 能做，写完觉得链应该随便线段树做，正解可能是长链剖分之类的，但是等写完线段树发现并不好优化：暴力相当于要正着 dp 一次反着 dp 一次不好优化（其实应该只要考虑前面对后面的贡献就可以）。
看 T3，感觉很像去年 D1T3 那种题，在 dfs 树上各种分类讨论，会了 B 性质 O(n^2) 和所有 A 性质，没时间写第一档暴力，写了个能过小样例的可能不好 hack 的乱搞。
T1 其实可以发现所有答案形如一些“等差数列链”，对于链上不能再翻转的部分可以 O(1) 算，不知道能优化多少，但是测出来还是 MLE 85，后来知道如果用 dfs 实现（减小空间）可以做到 90\sim 95。
最后 5 分钟感觉没什么希望写了 T2 5 分特殊性质，还挂了几次，因为函数名冲突。
走的时候问了一下工作人员能不能把四个牌子拿走，工作人员告诉我不能拿走，后来才知道如果不问就可以拿走。
往出走的时候听见别人讨论“T2 会不会”“T1 是类欧”更慌了。但是出来和同学讨论好像又都差不多。

查分基本毫无悬念。可能 Ag 稳了？查分现场还遇见了“Bingxiu2”。

打乒乓球，毫无悬念每次被吊打。
听讲题，T1 正式选手没人过，T2是签到，线段树分裂。

希望大家都能过上各自想要的生活！

Ag 线大概就是 409 了。
问了一下 SX 省有谁愿意和我一起唱歌，得到了 zhjxaoini 和 wYYSZLwSSY 的支持，但是 wYYSZLwSSY 说 好运来是抽象的歌，我不够抽象，应该换一个，于是就换成了《夜空中最亮的星》。

Day 3

上午，文艺汇演/演(ぴ)讲(?)大会，感觉大家都好会唱歌。我们的节目在最后一个，文艺汇演结束的时候放的是同一个背景音乐，那么如果报的是好运来会怎么样。

下午颁奖。

std::exit(EXIT_SUCCESS);

whk，启动！

去年省选被卡的时候，我想到一个非常“春秋笔法”的说法：
如果我今年有 >=Ag，就说“OI 是充满奇迹的学科”，否则就说“OI 是彩票竞赛”，现在 OI 是充满奇迹的学科了。