NOI2021 游记

chen_03 · 2021-07-28 21:53:25 · 个人记录

基本算是写完了吧，一些细节以后慢慢补。

上接 FJOI2021 游记，我是 E 类选手。

中考垫底人要来 NOI 垫底了。

由粉兔负责的校内集训。

省队集训。

仍然是日常被同学们吊着锤 + sb 题想不出来。

每天都是上午模拟赛，下午听课。听课仍然是日常掉线。扫雷真好玩。

突然发现离 NOI 没剩几天了，这太可怕了。

其实几天前就有这几天冲一冲的想法了。于是每天从早到晚一直复习，从前几天讲课的 PPT 到学过的所有算法，再到最近做过的所有题，都要看一遍。笔试也简单地看了看。

然而我是不可能不划水的，于是刷完了《起风了》《天空之城》，并且感觉《天空之城》好好看 + 歌好好听，遂二刷 + 循环电影原声带。

由于台风的影响，提前一天出发去余姚。

和学长们一起坐上早上九点多的动车，下午一点多到了站。惊喜地发现有工作人员来接站。坐了十几分钟的大巴车，就到了余姚市梦麟中学。

先去报到，领了胸牌和一堆赠品。在报到处的签名墙上看到了 Karry5307。 由于学长们签名都签得极小，我也签得非常小。

我的宿舍在浩博楼 3 号 311 室。走向宿舍的路上有一个摄影师一直跟着我们拍，到宿舍后还给了我一个特写，于是我们在闭幕式上齐齐上镜。

到宿舍后发现我的两个舍友（hzt 和 jbc）都还没到。给每个人配的生活用品有一个盆子、一套刷牙用具（牙杯、牙刷、牙膏）、两条毛巾、两个衣架和一卷厕纸。枕头上有一条草席虽然被我拿来当了坐垫，浴室里有沐浴露和洗发水，还有扫把、畚斗、拖把、晾衣杆各一件，阳台可以晒衣服虽然台风天没人把衣服晒外面。2 号床和 4 号床旁边都有接线板，然而我是 6 号床。

先把所有生活用品拆封了。本来想把衣服全部拿出来的，但教练说可以直接把箱子放在柜子里，我就照做了。

三位跟去的父亲（包括我爸）给我们买了蚊帐，感谢两位教练帮我把蚊帐挂了起来。这就算安顿好了吧。

发现 Tony2 住在对面 310 室。

晚饭食堂给了所有人一个固定的配餐，感觉挺阴间的。

空余时间基本都在复习。

吃完早饭继续复习。然后听说下午笔试，吓得我又看了看题库。

午饭后教练正式通知下午笔试了。进场前做了 UOJ 上的模拟笔试，被坑到了 98 分（全国青少年信息学奥林匹克竞赛；不可以输入哪个命令），慌得一批。去考场时没带打印出来的题库，也没带手机，没法再复习了。就这样，不知我经历了什么，就到了下午 3 点，笔试开始了。

“完 全 出 自”

丢密码条扣几分？好像听学长还是室友说过是 5 分，选 C；开考前不允许做什么？似乎是可以动鼠标和键盘的，但按照 CCF 的尿性肯定是不行的，选 ABCD。

我好像 5 分钟就做完了，然后认真检查了 25 分钟，在 15:18 交了题。15:35 出了分：100 分。我顿时松了口气。

笔试后通知说 Day1 的比赛可能会推迟一天，看天气情况。

然后学长们都离场了，只有我留下来打练习赛。gedit 没有自动缩进而 Anjuta 有，果断选择 Anjuta。

题目是去年的 Day1。回忆了一波美食家怎么写，然后开始码，感觉这个键盘按 Ctrl+S 特别难受。写到一半，不知我按了什么键，Anjuta 突然自己关掉了，也没保存，我的代码没了好多。继续写，它又突然自己关掉了。如此重复了几次，搞得我好久才写完美食家。

我完全无法理解。看来要写一行就保存一下。

UPD：应该是因为 Anjuta 太 sb 了。我为什么不用 emacs……

调了一会儿过了所有样例，但大样例似乎跑得很慢。后来想了想，这是正常的速度，那没事了。

开始写命运。忘了怎么转移了，于是先写完了线段树合并。然后回忆了一波转移方程，写上去。运行一下，它输出 0。改了一个错误后，它输出 7。此时练习赛已经结束了，我还没调完，我自闭了。

晚上听说 CCF 组织我们明天看奥运会开幕式，大草。

复习了一整天，没有划水。

早上听说 dzd 在巡视学生宿舍，十分慌张。然而他好像没来我这栋楼。

看这个天气情况，明天应该就是 Day1 了。

果然，晚上收到通知说明天 8:30 在主赛场待命。看来还是有所推迟。

晚上八点多发了个空间，九点多就去睡了。

睡到了 7:30。

早饭后，我们全副武装地走向主赛场——穿好雨衣，撑好雨伞，我还穿上了谢队给的鞋套。事实证明这个鞋套太管用了，我的鞋一点也没湿。

快九点时，我第一次听说有纸质题面这种东西。不一会儿纸质题面就发下来了。一看，三题都是 1 秒、1\text{ GB}，我惊了。T1 叫“轻重边”，应该是树剖或者 LCT 之类的东西。透过封面，我看到了 T2 的图和输入格式，感觉很可怕的样子。

九点整，比赛正式开始了。看 T1，感觉它非常 LCT。瞄了一眼 T2 和 T3，感觉题面太长了，于是开始想 T1。

先想了想 LCT 怎么做。回忆了一波 LCT 的各种操作，发现 LCT 似乎不可做（？？？）。又想了个树剖 + 树套树的 \mathcal{O}(n\log^3 n) 做法（？？？），一算复杂度直接爆炸，后来又发现我假了（菜！！！）。

然后就是各种尝试，但都以失败告终。我啥题都想不出来实锤了 qwq。于是先写了 \mathcal{O}(nm) 的暴力，链的部分分写到一半不想写了，就去看 T2 和 T3。

看 T2，发现当所有 n_i 都相等时，记相邻两层的奇数方案数分别为 a_1,a_2，偶数方案数分别为 b_1,b_2，由于 (a_1 a_2+b_1 b_2)-(a_1 b_2+b_1 a_2)=(b_1-a_1)(b_2-a_2)，所以可以分别计算每层的答案，再全部乘起来。于是写了个 \mathcal{O}(Tkn!\log n) 的暴力，去看 T3。

T3 的题意不太清楚，按我的理解，如果从 s 可以到 u 但从 u 不能到 t，那么 u 不合法。乍一看似乎完全不可做（菜！！！），想了好久才发现可以从 s 跑一遍 dfs，再在反图上从 t 跑一遍 dfs，然后取交集，这样做是 \mathcal{O}(mq) 的，于是就写了。直到写这篇游记的时候我才发现 m 可以大到 6\times 10^5，但出题人没有去卡它。

回过头来看 T2，发现它很行列式，但不是每个排列都合法。想起了粉兔讲过的某道行列式题，开始想怎么构造矩阵。然后发现令 a_{u,v}=1 就行了，我直呼我是 sb。

对每一层都求一遍行列式，这样做是 \mathcal{O}(Tkn^3) 的，似乎有点大。想到把所有矩阵乘起来再求行列式答案不变，但这样复杂度是一样的，就弃了（我在干嘛？？？）。注意到题面中说 n_1>10 的数据只有一组，由于题面是改过的，我怀疑这句话有没有错，还特意问了工作人员。那没事了，写完直接过了所有“所有 n_i 都相等”的样例。

补完了 T1 链的部分分，此时 T1 的代码已经很长了。发现特殊性质 B 巨大难写，就去写了 T3 树 + k=0 的部分分。

此时我已经快自闭了，还有一个巨大难写的特殊性质 B/px。但是再怎么自闭也不能放弃。写！！！

然后我写了一个树剖 + 两棵线段树 + 一个修改 + 一个查询/px，全部放到一个 namespace 里，使代码长度增加了接近一倍/px。调过了编译后很快就过了大样例。

讲个笑话，我 T1 写了 258 行的暴力/ll

此时已经是 13:40 了，离结束还有 25\text{ min}，我赢得了与自己的战争，我热爱老大哥！ 认真检查了三题的代码（虽然没有检查出错误），测了样例，加上 freopen，比赛就结束了。

如果不挂分的话就是 70+75+36=181。出考场后和学长们交流了一下，发现他们的分数几乎都和我差不多，虽然比我高一点。学长说 T1 可以树剖，我完全无法理解，我还是太菜了。另外学长们几乎都 A 题了，就我没有，我还是太菜了。

又和 FJ 省队的其他人交流了一下，发现我的分数似乎还不错（？）。吃完饭回到宿舍，和打同步赛的同学们交流了一下，发现他们几乎都很惨。

Linshey 说 T2 把所有矩阵乘起来再求行列式就是正解了，我顿时震惊，然后在群里说了一堆 four-letter words。 我都想到这个了怎么就没想到把它拓展到一般情况呢？/ll/ll/ll 然后发现 18Michael 把 T2 给切了，吊打我好几十分，这也太强了吧！看来我不配来 NOI 实锤了。

开始担心挂分。跟学长 lzy 说我怕挂分，得到的答复是“挂就挂呗”。就这样，我在紧张的情绪中，不知不觉地等到了 16:15，可以查分了。

本来以为 CCF 会咕咕咕，但到主赛场后我发现已经有很多人查到分了。原来是把分数发到选手的比赛用机上啊，并且看不到其他人的分数。我一看，一分不挂，70+75+36=181。

本来我以为这就是胜利了，但在回宿舍时，我听到了这样一段对话：

教练：你多少？
大佬 A：300 了。
教练：那他呢？
大佬 B：也 300 了。
大佬 A：其实很简单！

我一万个问号/jk/jk/jk

回到宿舍，发现室友 hzt 和 jbc 都很惨。hzt T1 没调出来，从 100 挂到了 25。然后他从今天调到了第二天，还不知道调出来了没有。

看了看群，发现可能有 30 个 AK 的/jk/jk/jk，队线在 250 左右。谢队从 240 挂到了 214，感觉他可能 Au 不保/jk/jk/jk。

晚上听讲评，T1 211 人 AC 我自闭了，T2 64 人 \ge 85 分我自闭了，T3 133 人 \ge 44 分我自闭了。看来真的要垫底了。

听完讲评后不想卷了，开始划水。

不用去看河姆渡人了，好耶。

一觉睡到八点多，不想去食堂了，就吃了昨天考场上发的面包，喝了前天拿的牛奶。

从昨晚开始就一直划水，方式包括但不限于玩游戏、看《天空之城》、学唱《天空之城》主题曲、研究《你的名字。》。

下午有嘉年华活动，我去看了但没去玩，因为怕掉 rp。学长 yc 和 ysh 投壶投了四五次，yc 一箭没进，ysh 至少还进了一箭。然后发现飞镖才是真正好玩的东西，我就在旁边的练习靶上玩了好几次。

晚上还是九点多就睡了。

睡到了七点多。

去主赛场时，学长们在毒奶会有几道交互、几道提答。我还是坚信有 0 道交互、0 道提答。

比赛开始前约 10 分钟拿到了纸质题面，果然是 0 道交互、0 道提答。三题都是 2 秒（T3 后来改成了 3 秒），T2T3 都是 1\text{ GB}，T1 这个 384\text{ MB} 是什么鬼。

八点整，比赛准时开始了。T1 什么鬼，T2 什么鬼，T3 什么鬼/yun。

T1 完全没有想法（菜死了！！！）。用 bitset 可以做到小常数的 \mathcal{O}(nm)，直接写了，并且认为这能通过前 5 个点。然后看 k=1 的部分分，觉得可以用 trie 树，但想了各种写法后，不是太慢了就是空间不够用。看来只能用哈希大法了。不太想写，就去看 T2。

T2 仍然是完全没有想法。题目竟然要输出分子和分母而不是对分数取模，我直接一个问号。想着怎么约分，手玩了一会儿 f 函数的计算过程，完全找不到方法。

然后发现它其实是每次给分子、分母中的一个加上另一个的整数倍，由于一开始分子、分母是互质的，所以它们一直都是互质的。那没事了，暴力写上去。又发现特殊性质 A 的答案是斐波那契数列，也写掉了。

回过头来把 T1 的 k=1 写了，用的是 unordered_map（这东西竟然可以 hash bitset）。没有 k=1 的样例，我就假装我写的是对的，去看 T3。

T3 的这个样例解释太有用了（我一开始还觉得它臭长臭长的，没人会去看）。发现若干 01* 操作的拼接可以用真值表转化为 0-*1 四种操作（- 表示不操作）。我们处理出每个操作序列进行 0-*1 操作分别在（p 之后的）哪些位置。对于一个 p 的集合，我们处理出每个位置进行了 0-*1 操作中的哪些操作。然后手算出 16 种操作集合的贡献，为 [3,3,3,2,3,2,1,1,3,1,2,1,2,1,1,1]。然后用样例解释里的方法容斥一下就行了。

UPD：我用二进制数记录位置集合，合并时或起来即可。由于机器人爆炸的情况特判掉了，所以我的写法是跑不满的 \mathcal{O}(2^n nm)。

写完调了一会儿过了前三个样例，第四个样例过不去，危。然后发现我的 sb 写法会把操作序列中 R 的数量统计错，改完就过了所有样例。

此时大概是 12:20，还剩 40 分钟。手玩了 T1 的 k=1，感觉我没写错。然后就和 Day1 一样，检查代码、测样例、加上 freopen。发现 T3 的第四个样例要跑 2.7 秒，非常危险。于是用了前天讲评时说的卡常方法——减少 long long 取模次数，卡到了 1.7 秒。不久，比赛就结束了。

估分是 28+35+28=91，感觉自己输得透彻/ll/ll/ll。出考场后，马上问学长谢队多少分。学长说谢队 A 掉了两题，那他不是稳进队了吗！太强了，谢队竟然 Day2 翻盘了，而前两年他 Day2 都爆炸了来着。

lzy 和 ysh 分数和我差不多，而 yc 几乎切掉了 T1（被卡常了），吊打我好几十分。

学长说 T1 询问串随机全输出 0 就行了/px，我又是差一点想到/ll，白丢了 12 分/ll/ll/ll。然后学长说 T1 用抽屉原理乱搞就行了，这个做法好有道理啊！可我为什么想不到呢？/ll/ll/ll 这次得分情况这么好，我 Ag 可能没了/ll/ll/ll。

和同步赛的同学们交流了一下，果然是人均吊打我。Linshey 想到了 T1 正解（虽然常数比较大），18Michael T3 会 32 分，总分估计要比我还高。这都是什么强神啊，我只能被吊着锤。

今天提早了十几分钟去查分，在主赛场门口站了十分钟。那时我的心情说不清的复杂，就不详细描述了。终于可以查分了，我打开 PDF 一看，24+35+28=87，T1 挂了 4 分/ll。不过这印证了我上不了 100 的事实，因为加上 T1 那 12 分我也只有 99/doge。

所以我的总分是 100+181+87=368。

回到宿舍一想，诶我 T1 过的是前 6 个点啊？那就是我的暴力艹过了 n=m=10^4 的数据，而 k=1 的部分被卡常了。

听讲评，T1 173 人 \ge 40 分、348 人 \ge 20 分我傻了。看来我急需一个脑子。不过 T3 28 分还算挺高的？这更说明 18Michael 太强了 Orz。

由于后面要高校宣讲，时间不够，T2 直接不讲了可还行。

吃晚饭时粉兔说队线是 498。谢队进队了！！！！！%%%%%%%

又有人在群里发了排行榜的第一页，看来是出榜了。yc 吃完去看了榜，说 ysh 有 Ag，那我不是也 Ag 了/cy/cy/cy，因为我比 ysh 高几分。

晚上大家到对面 310 室划水，6 个人打了好久的 generals 2v2v2，气氛十分活跃。

jbc 坑了我 381\text{ MB} 流量。

成功录下了熄灯音乐。

开幕式咕了，闭幕式总算是没有咕。

所有 FJ 人上台领奖时我都拍了张照片（除了学长 lzy 没拍到）。我继续膜拜谢队%%%%%%%。

给最佳女选手颁奖时，dzd 摸了一下她的脸蛋/jk。

印象最深的还是 dzd 的讲话。

dzd（一脸严肃）：有两个人发挥了非常重要的作用，一个是 zhq（校长），另一个，是，dzd。

dzd：教育部实施了“枪击”计划。

被明年 NOI 的宣传视频深深吸引了。那时候的我又会在何方？

UPD：为什么 NOI 官网 9 月 2 号才发布这个视频……

不久后，我拿到了自己的成绩证明。手写的名字、分数、奖牌颜色，dzd 和 wh 的签名也是手写的。成绩为 368 分，银牌分数线为 310 分。这意味着什么？这是个好的结果吗？抑或它意味着我付出的远远不够？

我和学长们吃完午饭后就要走。闭幕式结束后的这一期间，教练给我们各种拍照。在报到处前面合影时，教练随便找了个人帮忙拍，没想到竟叫到了学军的徐先友老师。

我们往校门口走去。再见了，NOI！再见了，余姚市梦麟中学！再见了，余姚！

不久后，我们就登上了归程的动车。

同步赛成绩出来了，18Michael 吊打我整整 19 分，Linshey 由于 CE 而不屑于吊打我。看来我还是太菜了，是我不配了。