do_while_true's blog

晚风中闪过 几帧从前啊

0%

NOI 2022 游记

南偏西传来的强烈光线,我一直在追逐着它,

在无论明后天又或是以后都会改变的天空下。

前言

一直不是很想动笔写东西。其一本身文化水平不高,而又总想写出点什么东西,才总是这样踌躇不定,最后也只好作罢;其二是我总是在事后才感觉到以前的诸多想法是在拘泥于一些没有意义的事物,但是仔细一想这是我一段时间内思考的东西,用些文字来记录下来也何妨不可?这次的契机是考前最后一次从机房出校门口时,同学说等好我的游记,才下定决心用文字记录下这一段发生在我身上的事。

NOI 前

从八月初开始,进行了大量的 NOI 模拟训练。省选第二试告诉我确实有触及省队的实力水平,而在 NOI 赛前训练要做的是避免如省选第一试和 NOIP,没有写完,或者写完没拿到,那些应该拿到的暴力分。于是在校内的 NOI 模拟训练中,除了有一天有个码力题没有写出来,在其余的所有模拟赛中基本上失分不超过 20~30 分,也算是训出了效果。

Day -1 ~ Day 0

提前了两三天打板子,但是效率仍然不是很高。因为感觉除了几个真的需要复习的板子,其余的也没有打的必要,只是在考前给自己减少一些压力罢了。话虽如此,也的确认真复习了一下平衡树怎么写。

志愿者组织的 NOI 欢迎晚会非常的有趣,似乎想要和疫情以前的 WC 文艺汇演一样。虽然我参加过两届 WC,但是由于疫情这两届 WC 都是线上举办。节目似乎就是唱歌和玩游戏。

谁是卧底。第一轮被热心老哥胁迫举手,被迫上台,第一轮因为大家都没爆一些有用的信息,于是把最后一个发言的我给票出去了。第三轮的时候又被热心老哥胁迫举手,被热心主持人再一次叫上台。这一次第一轮多少也暴露出了些有用的信息,但是台下的投票的时候台下的沙东老哥们一致起哄把我票出去,于是我又被第一轮票出去了。获得了速通谁是卧底的小丑称号。

笔试题库背了很多遍了,考笔试进考场前,看了两眼错题,背了背配置文件就进去了。笔试只有一个选项没有见过,想了想既然考前不让碰外设,自然也不能登录操作系统,于是笔试就轻松满分了。

直到笔试结束依然没有什么考试的紧张感觉,但是坐下来又觉得非常浮躁打不下板子。就和 kdw 在洛谷上口胡题目,也不求能积累什么套路,权当给大脑热热身。

Day 1

Day 1 进考场前,比赛的紧张感终于涌进了我的血管,擦掌欲试。发现座位旁边就是湖南队长,十分震撼。开考后发现键盘下面就是纸质题面,这应该是我第一次机试的时候拿到纸质题面。直接在纸质题面上写写画画比干巴巴读 pdf 好到不知道哪里去了!

大致浏览了一下题,T1 像是个数据结构题,T2 像是个打表观察 SG 函数题,T3 看到题目名是个树上领域数点,一开题面看到整整一页都是在对抽象的信息进行定义,就没仔细读是个啥,决定先写前两个题。

读完第二遍第一题,摩尔投票法、线段树合并、启发式合并这几个词就已经浮现在了我脑中,花了 30 min 才写完暴力,然后开始写正解。题面中很多限制都是 $n+q$,于是毅然把所有数组都按 $n+q$ 开。写着写着发现怎么还有删除末尾的操作,于是加了一个 deque 的启发式合并。加上暴力和对拍,第一题大概两个小时就写完了。

第二题大概花了一两个小时想怎么判定胜负,试了好几种都不行,写了个 dfs,发现把题面中的两个操作都读错了。还剩一个小时,决定先把第三题写了。又花了将近半个小时读题,大致理解了它要我干什么,看了一眼部分分,除了暴力还有一个比较显然的猫树。觉得猫树写不完,就一直在调暴力,到最后都没发现暴力是假的。

考完后估分是 $100+15+0$,毕竟 T1 过拍了还是比较十拿九稳的。出考场问了一下周围人的分数发现还不错。和 Futari 一起走的时候遇到了 dottle,他说要开 long long,才发现 T1 忘开 long long 了。问了一圈好像只有两个人开了,暂时安心了一下。

下午查分,点开成绩单发现 T1 全部 Wrong Answer,还是不慌,过拍了怎么可能全 WA,拿数据跑了跑发现都过了。于是想申诉,这个时候学长问是不是爆空间了,帮我限制内存跑了一下程序,连样例都挂了。我才知道可以限制空间来跑程序。发现我 deque 开了 $10^6$ 个,但是后 $5\times 10^5$ 个是没有用到的。deque 少开一半空间,所有数据都过了。这时监考广播说评测系统会把 MLE 报成 WA,我终于意识到我 T1 的确是爆零了,因为多开的那一半的 deque,或是因为我不会限制内存来跑程序。

签到题因为一处小地方 MLE 成 0 分,这样 Day 1 只剩下 15 分,通常情况下 Day 2 比 Day 1 难,铜牌至少要 100 分的机试分……本来以银牌为目标的我似乎连铜牌都变得触不可及。

我的心情是木然,无奈,委屈,还是绝望?好像有谁在我身体中打了一百针镇定剂,我并没有感受到任何的情绪。

就当我 T1 过了,Day 2 认真打,看看算上那 100 分能不能到银牌线。

Day 1.5

社会活动日,但是由于可恶的疫情,嘉年华改为了校内活动。说是校内活动,实际上也没有组织什么活动,无非就是在宿舍里颓废或者学习。我和省里的老哥们玩你画我猜,还不忘发明我 T1 MLE 爆零的“地狱笑话”。

本来想着再多打一下板子,最后也只是沉沦在低级趣味之中。

Day 2

迅速进入了考试状态。

先大略扫了一眼题目,第一题是个判定删点树同构,第二题是个 CF 风格的找性质题,第三题给了一堆定义果断先放弃理解。打算打得保守一点。

仔细想了想第一题,发现不弱于判定树同构,打开数据范围一看,判定树同构拼个暴力竟然有七十多分,还提示数据中没有对任何哈希算法进行针对性构造。那二话不说先编个树哈希再说。

我很确信我没学过树哈希,但是不编出来暴力都没法打,于是就编了一两个小时。然后开始写暴力,写着写着想到了遇到子树哈希值不同就枚举映射的做法,复杂度关于 $n$ 是个多项式,具体多少不会算。就算过不了那先冲一个。算上各种暴力 T1 写了将近三个小时。

然后对 T2 和 T3 进行刮痧。T2 想不出什么性质,写了个爆搜和性质 $A$ 的 $\mathcal{O}(n^3)$,T3 想不出什么性质,写了个爆搜,但是不知道有多少分。有好几个小地方可以优化,但是跑过了三个样例,还剩十几分钟,保守起见就回去检查 T1 了。

出考场听汪神说我 T1 写的是正解,那还挺牛的啊!但是树哈希不知道真不真啊!万一树哈希假了岂不是爆零了!

估了估分,那 T1 过了岂不是有 150+,有点懵,但是还是做好了树哈希随机数据都冲突的可能性。

听昆山出了一例无症状感染病例,下午不查分就要跑路。收拾好东西后听说查分提前了一个小时,立马飞奔去考场,正好碰上学长在帮我查分,84+40+13=137。T1 最后几个点 WA 了,同样数据范围的两个点只过了一个,那就是树哈希不是很优秀产生碰撞了。T1 因为树哈希没到位没拿 16 分觉得挺理所应当的,T3 一问周围都 21 分,估计就是爆搜少加了那几处小优化。这么一想,Day 2 其实也算是一分未挂。仔细算了算几天得分,恐怕是戏剧性地翻盘铜牌了。如果 D1T1 没挂银牌也是稳的了。

直到走出考场,走出学校,在学校门口的桥上向远处望时,我才意识到,至此,这个赛季是结束了,最好的结果也只不过是以一个 D 类铜牌遗憾收尾。曾几何时跃跃欲试,想拿一块银牌证明自己的实力,现在看来确实有银牌实力,但是连铜牌能不能拿到都说不准。

银牌还是铜牌,又或是椰树牌,空气牌,都已经无所谓了。无非是外界给我绑住的一个评价而已。这次 NOI 之行于我最好的奖品,就是让我体验了一次,在第一试白丢 100 分的情况下第二试依然正常发挥的经历。

但是谁又甘心拿到一个和自己真正实力并不相符的奖项呢?

我不甘心。但是又能怎么办呢?学还是要学的,训还是要训的,不如多把眼光放在下一个,真正决定我命运的一年。

事已至此,只能选择相信自己了。