NOI 2022 游记

· · 个人记录

前言

今年是第二次参加 NOI，初中时期的最后机会。去年已经拿了个银牌（虽然是卡线），今年没进 E，但还是买了个 D，不知道我在想啥。

回顾去年 NOI2021 我写的游记，感觉心态是非常不错吧，今年可能很难再维持那样无所谓的心态了。果然还是难以避免这样的趋势。

去年同校的高二学长得到了金牌，无憾退役。然而今年一位实力稳进队的高二同学却因为低级失误与金牌无缘。整个 rdfz 几乎都发挥很差，几乎都被 Day1 搞了心态。

但这届 NOI 就这样不尽人意吗？

我想也不是。以分数为唯一评判标准，也许会多多少少失去一些美好回忆吧。所以我想写一篇比较长的游记，目的是回忆那些好玩的瞬间。

8.13~8.20

12 号之前一直在 MO，后来通知说因为疫情防控要提前七天到昆山。而且本来是华二是主办方，突然跑到什么华二国际学校去了，很玄妙。

路上和初二同学坐在一起，本来我们都是各自玩自己的游戏，他玩篮球我引诱。然后我下载了一个双人游戏，就玩了很久。

到达昆山火车站，看到了一个牌子，上面写着“昆山有温度，四海皆家人”。实在是有温度。体感温度 50 度，简直是地狱。然后同学找到一处有空调的地方，大家就全站在那儿，简直是天堂。

到酒店之后，同学给我看了张图片，图片里有半个牌子，上面写着“昆山有玉玉在 大美昆曲大”。最后发现这个图片是动图，整张牌子写的是“昆山有玉 玉在其人 大美昆曲 大好昆山”。其实还可以断成“昆山有玉玉在 其人大美”，当时我们全都绷不住了。

这几天基本上都是上午北京队集训测试，下午不听讲题打 ACM。本来酒店是提供早饭的，结果教练因为40块钱太贵就换成去街边的粥铺吃。但其实还挺好吃的。因为测试的原因午饭只能在一点半之后解决，所以就统一点了外卖。晚饭则是在街边随便找一家野鸡饭店。虽然是在江苏，但好像没有江苏菜，其它各地的菜应有尽有。

我知道了我是常数怪的事实，主席树、杜教筛都被卡常。我还知道了求区间第 k 大问题竟然要用主席树解决。相信普通人都不会想到区间中位数用离线+KDT，我有光明的未来！

和 wzj，dyq 打了两场牛客，两场都被虐了，深感自己的菜。不过有一场封榜后题数翻倍，wzj 最后 10 分钟绝杀 FWT

8.20~8.22 Before Day1

学校装修和设施简直难以置信！！！！！！！！！！！！有这条件，谁tm上 rdfz 啊

20 号下午又打了一场牛客。（xtq：没法要了） wzj 用 bitset 优化费用流，简直神了。

晚上竟然直接就睡着了，可能是因为条件太好了吧。

21 号学会了新技能：双升，直接和舍友打了一整天。晚上背了背笔试。文艺汇演吹爆！还有 xtq 献唱《十年》！还有我玩谁是卧底一轮游！（ps：真的没有人看过 UOJ 的帖子知道 gcc 有 bug 吗 QAQ

22 号笔试，上午舍友给了我一个背笔试的程序，凹了好几次终于 full combo 了。笔试的时候据说两分钟之后就有人交卷了。我还得知了有超多隐藏引诱人！原来 dengyaotriangle 也是音游人（只不过玩节奏光剑）晚上总结了去年的失误，明天 Day1 过了 T1 之后就当个暴力老哥就好。

8.23 Day1 最终得分 125

去年是一人一人发纸质题面，这回是直接压在键盘底下。又体会到了看着大屏幕上的倒计时那种紧张的感觉。

翻开题，A 题感觉就是一个线段树合并维护摩尔投票法的板子。不过还要维护队尾的元素，实属阴间。感觉不到一个小时应该能写完，就先看 B,C 了。

看完 B，理解成差分形式的话，就是对于 l<r，可以让 a_l 减 k，a_r 加 k，但是当 k=1 时必须满足 r-l\ge 3。一看部分分，n=5 之后就是 n=1000，实在是难绷。不会做，直接看 C。

然后就懵 B 了。C 题题面就看了半个小时，让人难以理解。我就不知道定义什么不合法信息还有什么信息之类的概念有什么鬼用，不就是一个子树合并吗... 不过是一眼 zx 题。

行吧，B,C 都是神题，先把 A 给写了。比较幸运的是没调多长时间，9:30 的时候就过了所有大样例。但又感觉没法对拍，干脆不对拍了，测了一组极限数据之后就开始疯狂想 B 了。

我赛时认为既然从 5 直接跳到 1000，说明有一个显然结论能够直接优化到 O(n^3) 及以下。然后我找了两个小时啥也没找到，只拿了 25 分。还有一个小时看看 C。

C 我要吐槽，首先是题面，但这还不够，checker 拿哈希判还不输出中间结果，一直给我这儿输出 illegal MR/MC operation，整的我人破防了。最后只写了个链的情形 10 分滚粗了。属于是最高得分 135 了。最后十五分钟不知道干什么，很迷茫。

出考场的时候捂着耳朵。吃完饭之后才知道 B,C 大家都不会做，根本就不应该是 Day1 的题。

最后一看分 125，可能是 C 题写挂了吧，根本没看小分就慌忙关上了

大家都说 Day1 区分度不大，不过 qlr 220，估计要捧杯了。xtq 105，足以说明这个 Day1 有多不合理。所有人都很失落，但是在 xtq 说要联机糖豆人之后大家都很开心地玩起来了。晚上和北京队的众多同学打了一局三国杀。

8.24 Between Day1 & Day2

解谜游戏很好玩，不过一个小时不会的题被 xtq 秒杀了。这下是 Div2.A 都不会了。

打双升和三国杀，真的是太卷啦。

今天是开幕式，是不是意味着 Day1 的成绩可以不要了？（误

感觉 Day1 125 还不算差，Day2 稳定发挥就能银牌上位。（如果还是和 Day1 一样的话甚至能冲冲金？）

ps：无人机表演太厉害了。

pps：开幕式金句：CCF 一直在想如何让会员掏钱。 \ 从小就这么戾气，长大后怎么办？——杜子德

8.25 Day2 最终得分 129

开题之后，A 一眼树哈希，不过 k>=2 想了二十分钟还不会。提示还说了没有定向卡哈希算法，又难绷。特殊性质都在 k=0 而且测试点一大堆，更难绷了。理由很简单，Day1 出成这样铜牌可能就送不出去了。感觉可以写 k=0 和 O(n^3) 的 dp 做法，直接 80 分滚粗得了。

B 感觉很趣味，不过冒泡排序就是逆序对套一层皮。部分分仍然非常舒服，A 性质一眼贪心，本来是 O(n^2)，贪心过后可以优化到线性。B 想了一会，突然发现没有限制的位置一定连续段相同并且局部最优就是全局最优，就可以线段树维护做到 O(n\log n)。C 本来想延续 B 的思路，突然发现最小值限制导致了局部最优可能不合法，就寄了，没往下想。

C 属实是看完一遍不想再看了。先写个 A 吧，这回的 A 没有 Day1 这么好写了。大概在 10:30 写完了。调了好久的 k=0！！！！！简直没法要了！！！

再看 B，发现要凑的部分分太多了，可能写不完。所以写完 A 就不想题直接干 B 了。写着写着又感觉和保序回归啥的有点关系，就整体二分之后转化为 A 性质处理，但是没过大样例。最后只写了个 n,m\le 7 暴搜和 A,B 性质，加起来 64 分。

再看 C 的时候只剩 45 分钟了。推了推式子暴搜 13 分滚了。

出场的时候感觉 Day2 打的很憋屈，主要是没有开始就想出正解所以拼了一大堆东西导致没时间。最高分 80+64+13=157，听说金牌 D2T2 必须 A 掉，看来金牌无望了。bdfz 的一个初三舍友 100+100+0=200，加上 Day1 的 100 分，感觉要出金牌爷啦！

出分的时候想都没想到 A 题特殊性质的链全寄了，B 暴搜挂了，最终成绩 68+48+13=129。错啦。令人极其震惊的是 xtq 树哈希全挂分了，写了这个的全部变成 80 分以下。不过我没写正解，还没到那一步。听 xtq 说是 dmy 教他的，还过了 UOJ 的一道题，用了三年都没挂分。属实是太惨了。

赛后突然通知有病例，再不回北京来不及了，于是就匆忙逃离。NOI 就这样戛然而止。

返程的火车上继续打牌打游戏

后记

MoRan_Sky 退役，或许已经成为最大的遗憾。

如果我也会遭遇这样的经历，那我会怎样呢？

“前途很远，也很暗，然而不要怕。不怕的人面前才有路。”