NOI2022游记

· · 个人记录

Day -inf

买了个 D

Day -?

突然要求提前七天到，感觉很离谱

Day -7

高铁票有幸买到了教练旁边

昆山真热

热死了

地狱

Day -6

膜你赛 140\to10，赛后发现 A 题搜的时候没加 vis 导致重复入队，B 题没 memset

Day -5

膜你赛 140\to200，原因是 SPJ 炸了，C 题 std 20 分而我 20\to100，B 题我下标从 0 开始但后面忘了，导致 20\to0

昆山真是没什么本地特色（除了热）一整条街全是湖南和安徽菜

Day -4

摸。众所周知，题目分享有且只有两种情况：不听也会与听了也不会

晚饭辣死了

Day -3

膜你赛惊现有机化学，谴责只有 C 给了 >1 个样例

Day -2

膜你赛只有我不会杜教筛，于是现学，学完发现还要用我不会的拉格朗日插值，于是摆了

Day -1

终于在这地方熬过去快一半了，感觉每家饭馆都差不多，没什么好吃的，菜也差不多一样，天气还热的不行。明天去学校

Day 0

这是学校？？？有亿点过于豪华

Day 1

宿舍设计真人才，光线真是太好了，迫使我在宿舍外面打板子（

领物资，居然给个大电脑包，内附一堆 NOI 口罩，一个吉祥物，三支 NOI 笔和俩衣服，太良心了（不知道还有没有漏的）

Day 2

摆，顺带复习笔试。下午笔试考完为什么不能立刻看分啊？

明天 Day 1，祝我 ++rp，早点睡了。

Day 3 (考试Day1)

T1 感觉比较可做，但是询问并不知道该怎么扫一遍求，只会 O(\sum{(m^2)}\log n) 的做法，也就是对于 m 个序列各自的绝对众数都判一遍，不过理论复杂度好像很炸。

想了想之后还是不会复杂度对的做法，于是只好写这个，同时用了一个我觉得很精妙的优化：维护最大值和次大值，对于每个值计算其出现次数的理论上限，询问时按照理论上限降序排序扫，如果理论上限不超过一半就直接返回。到这里已经过去不少时间了，我也相信自己想不出正解，所以我只能赌一手这题是诈骗题，或者出题人人美心善数据水。

然后看 T2，15 分的暴搜比较显然，后面想了很久也没有思路，我确定比赛时间内想不出来正解了，于是把暴力打了去开 T3。因为有 WC 的经验，我怀疑 T3 这么长的题面背后可能有不少很可做的暴力分，一定不能放弃掉。

花了半个多小时看完 T3 的题面后……你一个可做的暴力都不给的？连个 M=N 的理解题意辛苦分都不给吗？唯一感觉比较可做的是链和所有询问 u=1，因为后者分多所以先想，但是发现 u=1 的点我只会从下向上合并信息，这样的话对于每个 d 都不一样，没有思路。

看链，链的子任务想到了倍增，但你出题人 M=5 是几个意思？连个倍增都不放？又想了很久，发现能分块，算了算又发现初始化的复杂度炸了，再研究发现块长 =\sqrt[3]n 才能过，毒瘤。

写完过了样例，最后再检查的时候发现下标完全越界了……这样例咋过的？？？惊心动魄改完了，再交上去，期望得分 (100-)+15+10=125-。

顺便说一下，这个鼠标真阴间，特别容易不知道怎么着就把一段代码拖到别的地方，导致我第一题如果不是最后看了一眼差点 CE。

考完吃饭，听到了许多 long long 的声音，起初我以为是 T2，结果发现他们说的是 T1。觉得自己寄了。问大佬，会了第一题 O(n\log n) 的做法，原来这不是诈骗题，感觉自己真危了。

去查分，在门口听见有人大喊出题人我爱你，重有了几分希望。惊心动魄打开成绩文档，T1 居然最慢的点只有 0.3s，错了三个应该是爆 int 了，后面的分都拿到，一共 85+15+10=110 分，感觉非常可以接受。果然出题人人美心善。

Day 4

上午颓废，睡大觉

下午开幕式，无人机表演很好看，但记忆最深刻的还是€€£宣传片里怎么让人愿意掏钱时的掌声雷动

Day 5 (考试Day2，突如其来的返程)

早上吃饭的时候收到了昆山防疫办的全员核酸短信，没有预料到接下来会发生这么多的事情。当时脑子里全是考试，也没有多想。

考试，第一题树同构是北京队集训的时候刚好练过的，练习赛有机化学题 yyds。由于当时我们学校的住在同一个酒店，所以一起学习了 xtq 的 Hash 方法，觉得非常好。可惜我不知道 k>0 的时候除了枚举删点还能怎么做，于是理论得分 76，觉得可以了，看下一题。

第二题的 A 性质明显十分可做，于是我立马设计了一个 O(n^2) dp，结合第一档暴力期望得分 48，写一半发现时间复杂度假了，实际是 O(n^3)，理论得分变成 36 还是 40，反正依然可以接受。写完之后测样例，发现 dp 正确性也假了，觉得节奏有点崩。

重新设计了一个 O(n^3) dp，结果写一半发现又假了。为了保底决定赶快先把 O(2^n\cdot m) 的暴力和第一档暴力写，把这 28 分拿到手，然后看看下一题。

第三题题目很冗长，但相比 Day1T3 来说已经是十分简洁了。读完题发现暴力非常好写，于是写了个大概 O(k^nq) 的暴力（时间复杂度我也没算明白），但是看到这题很多部分分数据范围接近，于是加了个剪枝希望能多过几个点，期望得分 8。

重看第二题，发现貌似可以贪：1 的区间肯定全填 1，0 的区间按左端点从大到小排序之后，每一次尽量往左填 0，感觉非常的正确。但我没有注意到一个非常重要的性质——如果一个区间包含另一个区间，那么大区间是废的可以不用管，而去重后所有区间左右端点分别单调。这就导致我当时想的是写个线段树维护可以插 0 的点，但这样写的话时间不够了，于是只好去检查。理论上限 112，虽然第二题很不满意但是也还行。

考完发现身边同学都把第二题 A 性质切了，导致我比他们都少 20 分左右，有点慌。出考场之后突然被领队叫住让所有北京队选手都不要走，更慌了。等人差不多了，领队说昆山这边出了本土病例，而北京的一些防疫政策导致我们如果不今天回去就回不去了，必须在两点做核酸，三点查分，之后立刻赶下午四点半的一趟高铁回去。

于是我们饭也没吃就先去收拾东西，收拾完了还差 20 分钟两点，于是简单盛了点饭吃，然后做核酸，吃完回宿舍把行李拿出去放校门口。好在查分提前了半个小时，两点半就进去了，进去之后发现大家的 xtq Hash 全挂分了，我挂成了 64。不过或许是那几行优化的功劳，第三题居然得了 21 分，这导致我的分数反而超出了原本的理论上限 1 分，拿到了 64+28+21=113，两天加起来 223，Ag 应该比较稳了。

虽然第一题我们学校的都挂分了，但我们以每人 12\sim20 分的代价，换到了赛后讨论出的一个非常美妙的几乎可以被认为是真随机的树 Hash 方法，这个方法美妙到我甚至觉得拿这 12 分换不亏。

无论如何，还是这么慌里慌张的走了，坐上了返程的高铁，后面的活动也全改线上了。虽然正好少耽误几天上学（北京要求提前七天返京），但依然挺可惜的。

十点半终于到了北京，这气温简直是天堂。

Day 6

出榜了，不意外地拿了Ag，而北京成功包揽银牌前三（算上DE），感觉很离谱。

好在无论是第一题MLE，还是第二题没特判 100\to25，这些诡异的事情没有发生在我或是身边。但依然为他们祝好，希望明年能阳间一点。虽然，我也不清楚自己还有没有明年。