NOI2021 游记

· · 个人记录

进不了省队的 D 类彩笔初中生第一次参加 NOI。

Day -inf

去 ZROI 线下集训，8 场模拟赛，Rating 反复横跳，大起大落。我在这几场模拟赛中，逐渐形成了先花 1-3h 磕 T1，然后 T2 T3 暴力拿分的策略。效果还可以，有几场把 T1 A 掉了，甚至能排到前 20，这是出乎意料的，本来以为来 ZR 就是垫底底的。

收获颇丰，许多学过的东西加深了印象，没学过的也尽可能了解了一些，意识到线下集训比线上效果好太多了。（还和 AK IOI2021 的 dmy 合了影 /se/se/se。)

clb 每天都要调侃一下恺皇，说 lk 预定 NOI 冠军！！1

集训结束后回了老家，然后就被通知 NOI 提前报到，发现还有一吨板子没有打，很难受。

Day -2

下午到了余姚梦麟中学，别人都一个背包一个行李箱简简单单，就我一个人还大包小包（由于某些原因带了被子床单啥的）。

梦麟中学，大概是不久前建的，给人一种很新、环境很好的感觉，建筑风格有点度假区的意思，让人不太能意识到它是一所学校。

刘老师给我把健康卡啥的签了字，然后把各种证明上交后就进学校了。

进门直走体育馆就是报到处，领了衣服背包啥的，还有免费纪念品，旁边在卖付费纪念品，时间仓促没有买，结果后来再去就收摊了（悲）。随后在签名墙上写上我的名字和 id。

由于是下午到的，我进宿舍的时候两个 hsy 高一高二室友 dyh、hyk 已经在了。比较悲催的是空调是坏的，找了宿管好几次才派人来修。我在我的 6 号床把自己带的床单被子一弄，蚊帐一挂，直接把没有人的上铺当储物架。

随后许多人惊叹：你还自己带被子？你还带了蚊帐？

我：……

这是房间里进来一个人，直呼 dyh 「小杜」，差点被 dyh 拍死。他问我是不是 cyh，我说是，然后得知这位是 hsy 高一巨佬 zlt。

晚饭是和 cjf 及 zlt 去食堂吃的，打饭。难吃的一批，没吃几口。晚上和他俩去操场散步，风很大，很舒服，聊了聊 NOI Linux 2.0，我发现自己是个一无所知的大彩笔。之后去看了看「自习室」，其实就是普通教室贴了个牌子，插座都不够用，没什么兴趣于是走了。

回到寝室，发现只有 2,4 号床头有插座，于是报告老妈，晚一点她就买了个插座送过来，还送了点罐装粥啥的。

睡觉，床质量极差，稍微动一下嘎吱嘎吱响，而且很硬，而且不够长（对我而言）。

这一天体验感极差。

Day -1

早上在寝室自习，很严重的问题是没有桌椅，床上看电脑太累了，于是万能妈妈又买来带小桌板的椅子，除了搬上楼（我们寝室在顶楼）有点累，用起来还是蛮舒服的，好评。 吃中饭前有消息说下午考笔试，但是没有收到正式通知，所以就大概看了看题库。吃饭的时候教练通知 $2:30$ 笔试。然后中间一个多小时一直在看笔试。 笔试。好像不是很正式的样子，也很快，$30min$。一道题问密码条丢了扣多少分，隐约记起刘老师半小时前给密码条的时候嘱咐丢了要扣 $5pts$，于是果断选对；还有一道题问比赛开始前不能干啥，我寻思登录系统和碰键盘大概是可以的，于是果断选错。 好！白送的 $100pts$ 只拿 $99pts$！！1 自闭了。 傍晚听说 hsy 高二巨佬 Yukikaze_ 过生日，他们还买了蛋糕以及……女装？大概是给 Cirno_9 准备的（（（ 去食堂打饭的时候，他们恰好唱完歌在鼓掌？我也过去蹭了蹭热闹，接着整个食堂的选手都鼓起掌来，后来在洛谷群看到有人问是不是谁过生日，就在群里和大家一起祝 Yukikaze_ 生快。 后来 PYY 叫我和 cjf 过去，给我们也分了块蛋糕。赞赞赞。 回寝室后他们在省队群里开了视频通话，直播 C9 nz 打音游。哈哈哈哈哈哈哈哈哈哈哈奥哈奥哈哈奥奥奥或或或或或或或或或或或或或或或或或或或或或或或哈或哈哈哈！！！！！1 之后一直在寝室打板子。晚上我机智地把发的被子当垫被铺在床上，就没那么硬了，并且采用侧卧的方式，也不会睡不下了（（（ # Day 0 大雨，大概是台风登陆造成的。 早上穿拖鞋去吃的早饭，然后回寝室打了打可持久化平衡树、线段树合并啥的。中午 cjf 妈妈（观摩团）送来了面包和泡面，于是干脆寝室里干饭，下午又继续打板子，期间还听 dyh 大佬讲了几道题，以及做了一下 NOI2018 Day1 T1，发现用以前做过的一道 APIO 题的套路，Kruskal 重构树一下就可以了。晚上就打了一牙杯的热水热前天的罐装粥，因为懒得出去吃了。 可能是因为一天宅在寝室没出去活动，再加上大概是第一次集体生活，以及马上 Day 1 多少有点紧张，头有点晕，心情比较低落，和妈妈打了很久电话，几近哭出来。回寝室时室友都一脸诧异问我去哪了。我打了杯热水，并立刻洗了热水澡，出来时已经好很多了。手机有个北京的未接来电，然后打开 QQ 发现 ZR 毛晖老师给我发信息问咋不接电话，紧接着又打过来了，告诉我不要有太大压力，也不要因为是 D 类就怎么怎么样，许多大神都是从 D 类开始的。之后徐教练也打了个电话问我比赛策略是什么，告诉我放轻松应对。大概也能猜到为啥他们突然打电话来鼓励我。爸爸发微信来嘱咐我吃维 B。晚上两个 hsy 大佬和我聊天，挺放松的。 睡得很好。 # Day 1 由于台风等不确定因素影响，原定 $8$ 点的第一试推迟，$8:30$ 在体育馆外集合，随时准备入场。 来到对应的电脑前坐下，大概 $8:45$。$9:00$ 开考。登入系统，首先打开 gedit 进行配置，熟练地把考前背下来的编译运行脚本输入进去，然后写了个 `a+b`，感觉编译没问题，就去开题了。压缩包密码 `noi2021@yuyao`。 开 `O2` 和 `c++11` 好评，但看到时限全部 $1s$ 就意识到很可能卡常。 开 T1。出乎意料的是，题面居然非常简短，直接告诉你要干啥，而不是往年编个小故事套进去的风格，瞬间感觉到出题人可能不用心。首先暴力就是模拟，然后一条链的情况可以简单用线段树维护。认真思考一下，发现如果把边权转化成儿子节点的点权，那么修改操作就变成了链赋值和链上所有点的儿子赋值，瞬间联想到树链剖分，但咋搞儿子的赋值咧？以及意识到一个恐怖的事情：考前唯一没有打的数据结构模板就是树链剖分。考场上写真的没问题吗？此外 T1 是多测，考前正好做了个多测题，忘记清空 LCA 的 `anc` 数组，所以现在很敏锐地注意到这个点。 根据要先看一遍所有题的原则，把 T2 T3 都看了看，完全没思路，T2 甚至不太会暴力，T3 手玩了一下发现只会 bfs 暴力，于是回到 T1。 感觉 T1 应该是可做的，于是决定采用在 ZR 模拟赛的策略，先干一段时间 T1 再说。想了想如果重链上儿子的编号连续，这个就比较好搞。于是想到一种方案，就是把重链先都剖出来，然后把第一条重链进行编号，再把这条重链上的儿子进行编号，再把这些儿子所引出的重链拿出来进行上述过程。好像可行，此刻十分欣喜，因为有可能可以切掉 T1。但还是强迫自己冷静下来，先把暴力模拟写了一下，过了样例。于是开始写魔改的树剖，期间一直祈祷千万别写错，并写的很仔细，每个地方都强制思考了一下正确性。把节点编号的部分写完，差不多 $2h$ 了，打算先停下来检验一下对不对，于是手出了几组数据，突然发现有的重链编号不连续，手模拟了一下，发现确实就是方案的锅而非程序的锅，倒吸一口冷气，以为方法假掉了，但很快发现其实只有重链的 $top$ 与重链上其它的点编号不连续，这个只需要在往上跳的过程中单独处理一下即可，于是继续写。 差不多 $2h50min$ 的时候写完了，手抖着测了一下小样例，过了，于是稍微放松了一些，测大样例，看到 `diff` 指令后面没有反馈，意味着没有不同，意味着过了大样例，大松一口气。我切了 NOI 题了，而且是一遍过？！但突然意识到还应该测一下运行速度，于是用随机数造了一组满数据。 `user 1.06s`。 草？ 要哭了，好不容易写了个正确性有保证、理论时间复杂度有保证的 NOI Day1T1 算法，结果卡常了？于是开始卡常，把在线段树中判不合法的区间修改挪到树链网上跳的地方判，减少函数调用次数。 `user 0.98s` 好，有效果！ 其实我非常清楚常数大的原因，我的魔改树剖，在修改操作时，要分赋值为 $0,1$ 两种操作，而每个操作每处理一条重链大概要 $4$ 次线段树赋值操作，所以常数是传统树剖的 $8$ 倍左右。但询问操作其实没有很大常数。于是我又意识到一个严重的问题，要是有更多修改操作，会不会 T 飞？立刻改了数据生成器再跑一次。 `user 1.2s` 草？ 更要哭了。抬头一看，已经 $3h10min$ 左右了，再不看后面的题就来不及了，可是我这个大常数 T1 程序甚至可能只能得个暴力分。随后我又采用了单独写一个线段树单点修改的函数，但并没有太大作用。此时已经 $3h20min

心态不是很好，有点慌乱，赶紧开 T2。T2 题有点长，题目读了好几遍没有读清楚，大概是因为比较慌。于是去上厕所冷静一下。厕所居然要排队？而且是在女厕所被征用为通用厕所的情况下？哦，每次只能进一个人啊，难怪。发现 ustze 大佬排我后面。

回来，在纸上画了画，发现好像能做很多分，于是准备写，但刚写到读入就发现题没读对，怎么还输入边啊？

哦，边是给定了的。那我白做了半天。又想了想，发现时间已经越来越少了，就莽了个傻逼状压 DP，期望得分 20pts。

草，没有给这个部分分的样例？那我就手造，发现好像比较对，但数据太小，完全不能保证程序正确性。

算了，开 T3。想了想，没有很好的思路，就把开始想的暴力 bfs 写了，过了小样例，期望得分 28pts。

此时通知比赛延长 5 min，现在还剩 20min。

然后就在 T2 T3 之间反复横跳。最后又出了几个 T2 的小数据，发现程序结果匪夷所思。

哦，题读错了（第几次了？）。第一层的每个点都要选。于是去掉一个转移方程，ok 了。

然后去想 T3 树的部分，并没有发觉到什么性质。考后 cjf 告诉我利用给定的图的性质可以推出这是个外向树。

差不多还剩 10min 的样子了，一切思考停止了。把文件夹中无关的文件都删掉了，打开终端删去隐藏的无关文件（gedit 生成的备份文件）。

大概，Day1 就这样结束了吧。

到点，考试结束，选手离场。

此时，我的最低得分大概是 30pts+0pts+28pts=58pts。

心情很低落，和 cjf 一起走去食堂吃饭。其实没啥胃口，随便扒拉了两口。打电话跟妈妈聊了一下，说自己打得不太理想。后来妈妈送了点泡面什么的到门口要我去拿。

也就是一瞬间的事情，我已经不太记得，也不太能够描述当时具体的心理状态如何了。 T1—— $100pts$ ！？ 我，我，我 A 了 T1 ？ T2—— $20pts$ ！！ T2 暴力 DP 没挂！ T3 意料之中 $28pts$。 那么，我 Day1 总分就是 $100pt+20pts+28pts=148pts$ ？！ 这完全超出了我的预期，欣喜若狂。回去看了看 T1 小分，最后一个点 $0.8s$。我爱死 CCF 超快的评测机啦！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！ 这时刘老师过来了，老妈电话也打过来了，于是汇报了一下情况。 cjf 那边 T1 暴力+乱搞也获得了不俗的分数。但此外 HB 选手大都有不同程度的挂分，据说 EA T2 行列式写挂了，但由于样例过水没查出来。（悲） 随后去吃饭，然后去「梦剧场」听讲题，T1 是 LCT 或者树剖，但我的做法与 std 不同。T2 就是把每层的邻接矩阵乘起来然后算行列式，据说是 LGV 引理板子，也有不少人写部分分做法然后过掉了整道题。 T3 缩点+虚树，不太会。 总共 $30$ 多个 AK 的，据说比往年 Day1 加起来都多，并且洛谷上三题均被评为紫。 看了看得分分布，估摸着我大概卡在 Ag 线。 晚上写了 T1 题解就睡了。 # Day 1.5 社会活动日，然而因为台风+疫情，社会活动鸽掉了。 直觉告诉我要考字符串，并且 zlt 说肯定要考构造，就打了 SA （我唯一会的后缀算法）模板，听 dyh 讲了几道字符串题，并找了一些 CF 交互做了一下，看了看一些构造题。 下午嘉年华，说是去了就有纪念品。于是去了。 大概是保龄球投壶投飞镖等项目，只玩了 $4/6$ 的项目，由于人太多就兑奖走了。兑到了去了就有的纪念品。本以为是帽子或者 U 盘什么的，结果是——榨菜？一大盒榨菜？ 让选手 Day2 吃面包配榨菜？ # Day 2 天气好转，$8:00$ 正常开始比赛。 时限均为 $2s$，看样子不卡常。压缩包密码 `300+300=600`。 先把三题都看了一下，感觉难度明显提升，不太可以采用那种硬干一题的策略，于是就打算拿满暴力分。 T1，只会暴力比较，后来想到了 $k$ 较小的时候 hash 一下，但感觉空间会炸。 T2，暴力模拟。 T3，暴力枚举。 T1 写完暴力，过了样例，又思考了一下，发现只把字典 hash 存一下，$k$ 较小的时候暴力枚举询问串的哪个位置不同，就不会爆空间，于是写了。 之后去厕所，command_block 排我前面。 T2 发现分子分母是永远互质的，根本不用管，只需要分别取模即可。于是暴力模拟。 T3 写完搜索加了一些优化，压根没仔细看样例解释的容斥，可能是太慌乱了。 后来感觉 T2 性质 A 可以搞，只关心开头、结尾以及长度，结果似乎可以表示成斐波那契数？于是写。 总而言之，Day2 就是打了三个暴力，而且没有得到很多分。 虽然都是打的暴力，但 $5h$ 依旧过得很快。 结束后 cjf 跑过来说他有 $90$ 多，说 T2 是矩阵乘法，后来他大概讲了讲我发现确实，操作可以看作矩阵乘，那么就可以用结合律。 下午查分，$24pts+25pts+12pts=61pts$，垫底。大概全场人均 $100+$。cjf T1 CE 了，据说可能按快了没保存。 算了算总分 $99pts+148pts+61pts=308pts$，怀疑会卡 Ag 线。 听讲题，突然意识到 T1 `map` 改成 `unordered_map` 可以多 $4pts$，但大概也无所谓了。 高校宣讲的时候我懒得听，跑了，在校园里溜达，拍了好多很不错的照片。 晚上出分了，Ag 线 $310$，我 $308$ D 类 Cu。果然卡 Ag 线且在线以下。这么一想那个 `unordered_map` 值一个 $Ag$ ！！？算了，反正是 D 类，记住教训即可。 今年 HB 发挥很差，最高的 Aly 也只有 $448+5$，未能 Au。其次是 ustze。EA 好像砸了。同寝室 dyh hyk 都没有上 Ag。 看成绩的时候，发现有人坐在花坛边缘抱头痛哭。 两位神仙 zjk、zhr AK，lk 好像失误错失了冠军，但依旧 Au。cmd 神 Au。 许多熟知的选手，就，退役了。他们将要在高考战场上所向披靡。 我深刻感受到，发挥是多么重要。C9、dyh 等人实力绝对是远超于我的，但由于各种各样的原因，没能取得理想的成绩。将来，我以正式选手身份参加时，一定要抱有平常心，并吸取此次的教训。前者的基础是 whk 成绩的稳定，后者则需要大量练习。 晚上 tp 等在酒店让家长教练签。 寝室 dyh，hyk 邀请我打王者，便下了一个，结果下载到 $10:30$ 都没下完，就先睡了。 # Day 3 早上闭幕式，把没有办成的开幕式强行加进去了，还有一些舞蹈节目。 各省代表队不上台亮相，差评。 wh 对本次题目特点总结：「题意简单、模型经典、考察选手基本功」。全场掌声如雷。 夏令营选手颁奖不登台，差评。 印象最深的是 dzd 的讲话。「这次 NOI 能成功举办，主要靠两个人，一个是 zhq，一个是 dzd。」 下午 $1$ 点动车，在车上玩了前一天晚上下好的王者荣耀。 NOI2021，就这样结束了吧。 我对自己的成绩还是比较满意的。这次 $20$ 多天的出行，收获颇丰。事实证明这次买 D 参加时非常有必要的，不来一次，真的不知道 NOI 到底是怎样的，真的不知道自己和大佬们还有怎样的差距，真的不知道考试时的感受以及如何稳定心态。 新的赛季即将到来，我想，应当在保证 whk 成绩较稳定的情况下，投入尽可能多的时间到 OI，大量做题，学习新知识，争取获得巨大提升。 See you next year at Shanghai!