NOI2022 游记

feecle6418 · 2022-08-26 10:02:22 · 个人记录

看别人的游记，总觉得事件丰满，语言生动，读起来非常流畅；反观自己的，似乎总是干瘪死板，而且分段过多，读起来不顺畅。这是为什么？可能是我之前没有“细心观察”的缘故，也可能是写时没有注重细节，仅仅勾勒了整场考试的大体框架。希望这次游记比以前写得稍微好一点。

Day -inf ~ Day -3

省选考了 CQ 队长，很离谱，不过原因应该是另外几个强者都在摆烂。D2T2 交错代码 100->84，不挂可能全国 rk2 了。

之后 PKUSC 全面爆炸，Day1 两位数，Day2 没 AK，认清自己菜的本质。

后来在多头指引下开始写闲话。

主办方要求 8 月 13 日到达参赛地点，在那边几次模拟赛都出现了令人惊讶的伞兵挂分方式，状态非常不好。感觉银定了！！！见识了卷王政委是有多么卷。最后两场模拟赛懒得补题了，考前一直在摆。

Day -2

进学校。很高级，感受到了什么叫做“经济发达地区的国际学校”。饭很好吃，寝室住宿条件感觉不输于酒店，所有生活用品都有提供。

去参观学校，和多头一行玩转圈圈的设施。多头好像参与度过高，导致当场吐了 /fad

晚上黑箱教室里民间活动。节目好评！多头演讲好评！但是懒得去解密了。当了一场观众。原创歌曲超好评！

和 crn 去面了 ix35，但是他俩交流蒙日乘，我全程自闭 /ll

Day -1

报道日，领徽章。要了 17 个，一共给了 20 个。一上午只换出去 8 个，感觉需要主动一点，就开始到处宣传。晚上抓住机会把剩下几个全换出去了。

最后一共换到了 21 个徽章（白嫖了一些，赠送了一些）。

Day 0

忘了干什么，大概就是在寝室看模板，玩 generals，玩 semantle，看 B 站。

Day 1

考试日！其实没有特别紧张。考前总结了一下思维技巧，这是两天考试的大框架。后面可以看到考试时的确是认真实践这个框架的。

有思路也不能做很久。

如果思考时间已经很长，而且算法不简单，应当先写一个不太优，但不太难写的做法（除非完全没有暴力分。）

不要扣死细节。特别是“建图”：图应当表示二元关系，关系是边，关系的作用元素是点。

NOI 不是 AGC！

如果某个方法很麻烦，一定不是正解，标算一定简洁优美。注意是否人为破坏了题目中各种对象的统一性

没思路时，按顺序执行：

直观化思考（特别有用，先直观，然后用直觉，观察”结构“）！如果题目本身过于形式化，可以从简单情况入手。

在不改变答案的前提下尽量简化问题，方法有：拆开无关变量；分类讨论；转化思考顺序（说起来容易，做起来难。倒着做；考虑交换两个操作的顺序答案是否变化），或是弱化条件、增加决策量（绝对值拆开，\max(x,y) 改成主动决定选 x 还是选 y），或是主动加强条件减少决策量。注意，不改变答案不意味着不改变问题本身。

写暴力找规律，或者验证结论。这步不要花太长时间。

“方法论”

对于任意（子集），都有……

寻找二元运算的性质（关系是竞赛图？是树？具有结合律/可合并？……）

答案只会是……

进考场。

8:00：T1 一看就会了。开始写。
9:00：过了大样例，出于不信任大样例的强度，开始写对拍。
9:30：对拍过程中拍出来两个错，都是链表写错了。这时大概改完了，开 T2。
10:00：突然发现 T2 看错题了（区间长度 >2，我看成了 \ge）！之前还以为特别简单的。上个厕所冷静一下。
10:10~10:30：打了个暴力找规律（什么样的序列合法），没找出来。
10:30：上了个厕所冷静一下，发现可以 dp。dp 需要记录前面 4 个位置的值，理性分析发现共有 35 个状态。直接写可以过 40 分，改成 dp 套 dp 可能会有 (k+1)^{35} 个状态，但总感觉状态数不大。但是如果这就是标算，就违背了 标算一定简洁优美 的大前提，所以我主动摒弃这个想法，尝试找到更好的判断方式。
11:00：找不到，开写暴力。
12:00：写完了前 40 分。中途应该浪费了一些时间读 T3。这 40 没拍。
12:20：写了一个 T3 暴力，发现假了，进而发现我甚至不会前两个测试点。
12:40：写完了 T3 的测试点 3,4。继续思考前两个测试点无果，考后发现不难，应该是过于紧张了。
12:45：写完了把 T2 40 和 15 对拍的程序，拍出错了？？？
12:50：找到错了，是全 0 和 1 1 1 两种情况要特判，好恶心啊。赶紧加特判。
13:00：考试结束了。

出来就发现多头过了 T2，但是没过 T1，但是 T1 暴力分特别多，所以多头分应该特别高。多头好像就是用一个“状态数不大”的 dp 套 dp 过掉了 T2！又听说 crn gyh 都写了 dp 套 dp，但是 gyh WA 了大样例，crn 状态数太多了，好像都只有 40。

如果标算就是“猜想状态数不多，搜一下发现真的不多”就离谱了，至少我绝不会在正式考试干出这种事（一定不写正确性没有保证的代码）。

不过他们的 dp，状态数好像本身就比我少一些，不清楚。

然后就一直摆了，玩 semantle，睡觉。然后去查分，一分没挂，100+40+10=150。但是 gyh,crn 好像 T1 都挂了。多头 175，真的强！听说 SD 队长 220，Kubic 210。

好像集训队线很低，140 左右。其实不太理解，150 不是暴力打满就完了吗（甚至没有打 T3 换根 dp）？

晚上忘记干啥了。

Day 1.5

玩了整整一天 minecraft，好耶。找到了四个 ruined portal，其中有两把金镐，附魔得非常高级（三种特性，等级分别 III,III,I）。遗憾的是掉进坑里导致物品全没了。

Day 2

今天比 Day1 紧张很多。不过还是以上面所述为基本策略。

8:00：看 T1,T2,T3，一眼都不会。
8:15：会 T1 了，开始写。复杂度不清楚是什么，但上界是 120\times n。（考后 upd：我考场上的程序偷懒用了 map 导致多带了 log，所以理论上是可以被卡 TLE 的，但是出题人没有卡，感谢不杀之恩）
9:30：T1 写完拍完，没有拍出错。开 T2。
10:00：想了一会，只会 A 的 O(n^3) 和 B。其实 A,C 都隐约有想法，但是正确性非常不明朗，就弃了。
10:30：没有发现什么好方法，而且时间不多，必须开始写暴力了。
11:30：写完了 T2 暴力，没有时间拍，只能用大样例测正确性。预计有 52。开 T3。
11:50：T3 k=3,4 都 trivial。k=5 可以写一种奇奇怪怪的爆搜，不知道能拿多少分。
12:25：写完了 T3 前 20，感觉通解比较难写，先看特殊性质。m=0 好像可以用二次函数凸性，固定 3 的个数，2 的个数要么最小要么最多，dp 即可。
12:40：写完了 A。接着发现加一个爆搜每个边的连通块，就可以过 B。开冲。
12:55：写完了 B。过了 B 的大样例，但是在 n=50 那个样例 WA 了（时间上能跑过）
12:57:30：调出来了，要特判 0 边。特别慌，没有做更多测试了。
13:00：结束了。

T3 预估分数是 52，估的总分是 100+52+52=204。出来发现多头和 gyh 和 crn 都会 T2。

然后又回寝室打了很久 minecraft。2:30 可以查分了。教练说是 198，我想是不是 T3 挂了一个 6 分点。

打开分数的时候很震惊，100+36+62。T3 3^n 暴力冲过了 n=50，多了 10 分。但是 T2，n\le 7 的点挂了？？？？

测了一下，发现我没判 -1，草。

最终总分 150+198=348（不算笔试），最开始听说队线 330 左右，后来又说 300，后来又说 310，后来 yyl 好像看错成绩了，就不知道队线多少了。

如果这样就进队了，那我觉得很离谱啊，就写了一堆暴力，还挂了分，考场上没整出任何有意思的东西，就能进队？我是不是被反向区分上来了啊。

不管了，昆山那边有疫情，所以提前回重庆了。在机场和飞机上一直在玩 minecraft。

但是回不了家，因为沙坪坝是高风险地区。

晚上暂住在我爸一个朋友家里。NOI 就突兀地结束了。

Day 3

出分了，448，莫名其妙排名很高（rk12）。gyh 和 dottle 排名都很高，祝贺机器人们！！

无论如何一个阶段的学习结束了，新阶段开始了。这不是 the end，这是 the new beginning。