NOI2018

Day -1

之前在雅礼集训,所以就直接坐了公交车去了洋湖校区。差不多中午就到了,吃了吃饭啥的。之前听说开幕式要搞啥各省代表队入场,感觉雅礼那些管事的是不是石乐志。

剩下的时间就在阅览室写题,阅览室空调不大行,热的要死,感觉雅礼那些管事的确实石乐志。

晚上开幕式竟然还搞彩排,各省喊了喊口号,大屏幕还放了选手照片,感觉控制不住自己喷脏话的欲望了啊。怎么现在正常办个活动这么困难啊。

Day 0

dzd 飞机咕咕咕了,所以为了配合领导的行程就把笔试放到了上午。之前没事就去评测鸭上做笔试题,感觉已经非常熟练了,就没怎么被鄙视。

上午的时候试机,笔试和去年一样,满分,问了问几个同校的也都是满分,试机题没有提答非常开心,虽然之前用了一周左右的时间做了几个提答题,但是提答的水平还是不大行。

剩下的时间还是去阅览室写题,无聊的时候找 yjt 插了个旗,真是有毒…

FLAG

开幕式基本和彩排的时候一样,热的要死,雅礼竟然在周围放了几个冰块来降温???

dzd 也没搞啥大新闻,就是日常批判了一下贵国制度?

密码条的密码是 aahydt ,鸿运当头?感觉非常的慌张。

Day 1

一声哨响,没有看题,先去写了 vimrc template 以及一些乱七八糟的 alias 。「不慌,慢慢来」我对自己说。

写完后感觉没啥问题就去看题了。t1 好长,先跳了,t2 看到了要模,大体观察了一下是个计数题,自我感觉计数水平还是不错的,也许可以做出来。t3 是个子串有关的串串题,不错啊,感觉 SAM 跑不了了。

刚看完题旁边的小哥已经开始疯狂敲键盘了,怎么一副志在必得的样子啊,我好像还一个题都不会啊。心态有点崩,瞄了一眼他的考号是 HE-12,难道有水题?

本来想先莽一下 t3,冷静了一下就先去看 t1 了。艰难读完题面后还没反应过来,又瞎看了看数据范围,反复读了几次题后终于反应过来了,好像是个重构树傻逼题哦。求稳先写了个暴力,过了大样例后也很快写完了标算。大概在九点的时候拍上了。

思考了一下感觉这个套路应该不那么普及,去年我是在第四个小时的时候拿到了一百分,这次是在第一个小时,应该问题不大了,去上个厕所冷静一下。

回来后就是烤串还是数数的问题了,时间尚且充裕,就烤串吧。撕烤了半小时左右,没想到什么靠谱的做法,区间的限制不大会处理,但是出题人给了 62pts 不带区间限制的,那就努力拿这部分分吧。想来想去广义 SAM 的复杂度总是感觉有问题,期间想到一个做法,但是印象里 BZOJ 上有道相似题目的复杂度在别人的博客里被提到是带根号的,就去想别的做法了。

想到可以按照题意来维护线段树合并,每次实际上是打一个标记的问题。因为标记没有时间的先后关系,我可以标记永久化后统一下传,这样算下来复杂度就是一个 log 的了。

正准备写,突然发现这个做法空间上好像有点问题。要拿到完整的 68pts 我至少需要开到 2G 的空间,但是出题人只给了 1G,不过还好给的数据有梯度,在这个空间限制下我至少可以拿到 44pts。

时间不等人,这个时候已经过了半个小时了,我先写了一个暴力。然后开始实现这个做法,写完后发现我如果想统一下传标记,还需要把线段树的所有节点按照深度排序,这样的话我计数排序至少还要一个线段树节点大小的数组,能拿的分数又要向下压。冷静了一下决定先卡一卡空间,把一些地方的 int 改成了 short,所需的节点数压到了恰好上界的地方,这样的话我可以消耗 903MB 的静态空间,同时拿到 52pts,但是如果我开到了 957MB,就可以拿到 56pts。但是有没有可能程序运行时又会消耗一些额外的空间导致我 MLE 呢,程序占用空间的计算这一方面我不了解,也不知道有什么可以科学测量占用空间的方法。想了想还是求稳,把空间开到了 903MB。

这一圈折腾下来,和我的暴力拍上的时候就只剩一个半小时,赶紧回去做 T2。想来想去没想到什么靠谱做法,应该是个结论题,结论也可能是和逆序对有关的。就写了个暴力来配合猜结论,猜了十几分钟终于猜对一个结论,但是看起来异常僵硬,而且想来想去也只能帮我拿到指数级别暴力的分数,但是没有什么办法了,要留够充足的时间检查,就赶紧把这个部分分给写了。

写完后刚好剩下半个小时,算了算自己能拿的分大概就是 100pts + 44pts + 52pts = 196,不高不低吧,希望不要挂题,看其他人发挥了。走了几遍检查的程序,最后十分钟看第三题的代码时突然意识到有一部分的空间消耗是不必要的,我只要做一些微小的改动就可以省掉一半的空间,在不卡空间的前提下就可以稳稳的拿到 60pts!

正准备开始动键盘的时候,突然回想起了 WC 时候的 CE 惨案,还是忍痛 AFK 了。然后就坐到了考试结束。

出考场问了问认识的人,果然重构树这个套路不比我想象的普及,但是好像大家都会 t3 68pts 的做法,是不是我考场上傻逼了?吕老板中间来问候了一下,安慰我考得还行,但是我的感觉还是不大对,大众分 212,我可能玩砸了..

两点四十的时候我从阅览室里跑了出来,正午的长沙,太阳焦灼。考场的大门还是紧闭,看到了外语一行人,好像都考得不错,突然门开了,赶紧跑了进去。

顺着一溜的 Right Outputs! 滑下去,100 + 44 + 52,还好,至少没有挂题,瞄了一眼旁边的那个之前疯狂敲键盘的小哥好像是 115,嘿嘿嘿。找周围认识的人问了问,果然挂题的居多,听说 xwb 几乎切了 t3,总分 240,牛逼,手机上给几个人报了消息就去报告厅听讲题了。t1 175AC,比想象中的多,出题人放过了两个 $\log $ 的可持久化并查集的做法。t2 出题人给出的结论和我观察出来的不大一样,而且我也没有发现那玩意是个卡特兰数,也就无法和括号序列对应上去,不过也没多少人拿高分,不算太亏。t3 看起来是全场 68pts,有不少 90+。

中间 wh 来说,平均分 115,算上 D 类 200 分以上有 70+,也就是说我现在的分数是在集训队线下一点的位置。下一场要努力一些了。晚上回阅览室写题。

Day 2

听说不参加社会活动 day2 翻车,就跑来晒太阳了。发生了一些不大愉快的事情,干死雅礼的负责人。

下午回到阅览室,补了补之前没写完的一个题,然后想写另一个题怎么都写不进,突然收到了之前某封奇怪邮件的回复,心态不太稳就回去睡觉了。

今天发的密码条没有那些奇怪的缩写。

Day 3

吹了哨后就开始休闲写 vimrc template 和 alias。写完后开始看题,也许是 day1 还不错心态放松了吧。

t1 看完就会了,不就是个无脑 exgcd 吗,先打了个暴力就放到那里了。看了看 t2 好像可以做,t3 第一眼看到题目名多边形,第二眼看到主人公九莲,好的基佬史努比,打扰了告辞。

先写了会式子,然后就去打代码了,非常庆幸之前花过一段时间来处理自己关于 exgcd 一些细节的疑问,实现的时候一些不确定的地方都是之前想的非常清楚的了。大概一个半小时的时候过了大样例,感觉大样例看起来还是非常厉害的,数据也不好造,就没有拍放在那里了。

接着开始莽 t2,想了大概有一个多小时,一个高分做法都想不到,一些地方的处理越往深处想就越不可写。然后放弃自我开始看 t3,又想了一个多小时还是只会指数级别的做法。没办法就写了 20pts 的暴力。然后接着回去做 t2,补了 15pts 的暴力后想了半天终于会了链上的做法,但是还是只有 15pts,赶紧写了写,和暴力拼一拼就是 30pts,剩四十分钟了,这场 100pts + 30pts + 20pts,可能要 AFO 了。

因为 pb 坐我旁边,结束了之后和他讨论了一下,他提出了 t1 一个神奇的问题,考场上我似乎没有想到,但是好像确实可能会出现这种问题,问了问另外几个人好像也没有说这个问题怎么处理,不敢细想赶紧回了阅览室。

中途又听到了各种选手的各种自爆,但是感觉自己 t1 可能要挂了非常的慌张。在阅览室外面来回踱步,心是真的跳到了嗓子眼。

很快到了查分的时候,飞快的跑到了电脑前,点开 pdf,100pts + 30pts + 20pts,依旧没挂题!算上 A 类加分,总分是 451,看起来是个还不错的分数。

然后就是等线了,xwb d2 自爆,总分比我低了 20pts,mjl 和 wg 也没有考的比我高,往年 HA 都是一到两个人进队,我也许可以进队?

其实这个时候轻松许多,吕老板猜队线 440 左右,各路神仙的估计也相差不大,进队不一定,但是 Au 肯定是有了。听了听讲题,t1 是个 ruc 小哥出的,没啥喷点就不说了,算是不那么僵硬的数论题吧。t2 是吕老板提供的 idea,猫坤出的题,全场最高分 45,t3 防 AK,基佬史出的,全场最高分 50。

见了见父母,一顿吹逼之后回去等队线。

队线不一会就出了,是 452………

一下子似乎反应不过来,但是还是从报告厅出来了,去了 THU 那里等老师过来。因为之前 THUSC 的时候自爆了只拿了前一百降 60 的协议,停课时间太长文化课已经废了,能不能换成降一本的其实心里也不大有谱。清华的老师过来的时候好像还挺顺利的,金牌就直接给换成降一本了。

剩下的时间里就是各大高校选人的时间了,去年体验过的那种刻骨的绝望,今年可以只作为一个旁观者了。在阅览室划了一会水,到十点左右回到了宿舍,左等右等室友都还没回来,突然发现宿舍对面就是高校面试的地方,已经十一点多了,还是明亮的房间和忙碌的人群。

面试

最后大家结果都还不错啦,HA 省内的正式队员大概是两个 THU 一本,一个 THU 60,一个 SJTU 一本,一个 ZJU 一本,两个 WHU 一本,一个 BUPT 一本。

晚上和室友瞎扯到了两三点。

Day 4

一觉睡到中午,下午闭幕式领了奖,拍了照,又感受了一次雅礼的弱智组织。明年广东的,看起来不错啊,至少从宣传片上来说,可惜也没有机会再去了。