NOI2021 游记

· · 个人记录

考完了，心情非常不错，来写一篇游记。

为什么呢？因为我考场上第一次写的东西全都写错啦，写部分分的时候把 if 注释掉啦，取模的时候没有考虑负数直接全 WA 啦。

相信同为 OIer 的我们一定会感同身受，相信你们也会感到十分高兴，于是我来写一篇纪念一下~

7.23 & 7.24

坐火车到了宁波余姚，当时天气真的热，一点都没有下雨的意思。

坐火车的时候第一次自己打了 FFT 和 FWT 的模板和 Dinic、预流推进的网络流，大概都打了两遍，最后一遍还都挺顺利的。后来有人告诉我 FFT 和 FWT 不考

好像还写了后缀数组，倒是练了很多东西。后来旁边同学跟我说火车上写题不好，就开始打游戏

到了宿舍，舍友都是外校的，不好联机打游戏。所以我就到了花花和 dyc 的那屋，正好 wzj 和 dyq（娄钰没有）也过来了，凑成了五个人，后来我们全都待在那屋里了。他们最近打麻将，就教了我一下，后来就一直在打雀魂了。

24 号晚上领了密码条，然后得知了台风的消息。本来的社会活动也取消了，下午匆忙地考了笔试。笔试出自 NOI 笔试题库，但不完全出自，反正是 98 分及以下了。问题不大。

小贴士：丢失密码条要扣 5 分，笔试要考哦

NOI 的场面真的非常宏大！整个篮球馆全都是电脑，而且上面还挂着大标幅，场地的前后方还有大型的钟表提示时间。总之是从未见过的大场面。笔试的时候托 dyc 拍了张照纪念一下。

7.25

休息一天。一直在打游戏。

7.26 Day1

最终分数：100+0+28=128。

因为昨天受台风影响，所以比赛时间调到从 9 点开始。进场之后，比赛开始还剩 20 分钟，结果我发现没带身份证！于是赶紧下去，正好碰见一些同学也没带身份证。等先拿的同学回来后，我就拿着他的伞跑回了宿舍拿到了身份证。回到赛场，因为没拿胸牌，保安竟然不让我进！幸亏有善良的工作人员让我进去了，不然可能就完了。

小贴士：考试记得带身份证哦

考前还发了纸质版试题，挺离谱的。

考试开始之后还是没有拿到，于是就看电脑上的 pdf 了。第一题的修改明显是一个 LCT 的操作，但是不好做 Makeroot，并且查询也比较难办。于是就果断抛弃了这个想法，后来就想到可以用树剖去维护每个结点的信息，重儿子和轻儿子分别维护。这样极其难写，写出来包含 6 种不同的 Change，差点把我写吐血。后来用大概 3 个小时调出来了，大样例运行 1.2s，卡卡常就行了。

第二题先想 k=2，仍然没什么思路...去上了个撤硕，还是女厕所，因为男生太多了。突然想到这题本质上就是行列式，就直接开写，写着写着就意识到 k>2 且 n_i 相同本质上就是行列式的乘积。但是行列式容易写挂，于是补了一个特殊性质 B。大样例过了。tmd 重点是大样例过了。什么出题人，啊？大样例不好好出？你让人怎么调？啊？！

然后我就没看过这题。

草。

第三题，一看就非常恶心，而且时间只剩半个小时了，我就对于 n\le 1000 搞了一个 Floyd，然后树的情况写了 k=0,1。k=1 还调了很长时间，到最后卡线调出来。

然后就超时了。

我就想问了，啊，1e6 次 LCA 从来没有超时过，现在开了 O2 就超时了？啊？LCA 这么慢出题人你家里人知道吗？

小贴士：LCA 尽量不要用倍增写哦。如果用倍增的话，在单个跳的时候，

if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];

尽量写成

if(st-(1<<i)>=goal) st-=(1<<i),x=fa[x][i];

这样可以减少寻址。对于 1e6 规模次查询，后面的写法时间减半哦。

Day1 赛后统计

7.27

又是休息了一天。但不完全休息。上午倒也没什么，反正就是打游戏。我还跟 wzj 他们学了一个叫“政变”的桌游，玩的挺开心。下午是 NOI 嘉年华，但是和信息学一点关系都没有。就是搞一些小游戏，像保龄球、乒乓球颠球、掷骰子之类的。人特别多，看了一下就走了，没玩。

听说玩了还会有纪念品？拿到的跟我描述一下？

7.28 Day2

最终分数：36+35+20=91。

崩掉了。比 Day1 还要崩。

赛前我一直在提示自己：当一个暴力哥就行了，所以策略就是：前两个小时把暴力分尽量提高，后三个小时不想了直接写。

然后开了第一题，感觉没什么思路。后来才发现这道题 16 位分一块就做完了，但是没做过像这样随机数据的题。考场上也想过 k_i=1 的类似做法，即分成两段至少有一段相等，但是不知道咋回事赛场上一直觉得复杂度错误，唉，就只能打暴力了。最后拼了一个随机询问，期望 20+12=32。

后来还多过了一个点，嘿嘿

前两个小时主要在想第二题，很快就想到了特殊条件 A 是斐波那契数列相邻两项之比，然后对于只有 APPEND 操作可以用矩阵来处理。到现在就 50 分了，感觉实现起来《非常容易》，就直接过了。

第三题，直接一个最暴力的容斥能搞到 O(2^n\times n^2\times m)，再加上无 R 操作的部分可以拿到 32 分。也感觉实现起来《比较容易》，也《不太可能出现问题》，就直接开始写。

给自己留了约三个小时的时间。先做看起来写着《比较容易》的第二题。然后就因为输入被卡了半个小时。

更恶心的是！我写矩阵乘法的那个部分分，写了，测了大样例过了，我就以为没有问题。但实际上挂了。你可能以为是大样例很水，但并不是。

我大样例测错了。也就是说，我测的是之前保证正确的部分分。

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈！！！！！

第二题无了，第三题也发挥良好呢。为什么后面的 12 分没有拿到呢？因为我取模后的数是负数！

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈！！！！！

总之 Day2 就是这样的欢乐，最后拿到了 91 分的高分，感到十分满意呢。

Day2 赛后统计

7.29

上午是闭幕式。大概是昨天晚上，我得知了我的分数在银牌分数线上，算是一个不小的惊喜吧。今天一上午就去了“梦剧场”参加闭幕式，坐下之后，想起 NOI 两次考试多多少少都有些失误，感到一丝遗憾。

开幕式由于台风原因不能如期举行，所以闭幕式也增加了一些内容。开场就放出了一张大中国地图，然后主持人把每个省份都说了一遍，随后那个省的代表团就起立，大家一起鼓掌。我看到了整个会场的人——都是和我一样，怀揣着梦想，也许是进国集，也许是像我一样玩得开心，参加了这场 NOI。到了颁奖环节，获奖选手一一上台，正好在分数线上的选手面露笑容，正好在分数线下的选手面色苍白。

我瞬间感受到，我们是一个大团体。

谁会喜欢考试的时候因为低级错误而被扣分呢？再想起来，我的那些错误不算最惨，还有同学因为文件错误而整题爆零，还有同学想出了正解但没有时间......

而这次 NOI 最令人难忘的，是赛前一起做题的过程，是赛后一起讨论互相膜拜的过程，这才是我们 OIer 最喜欢的事情啊！杜子德主席的讲话非常有道理，不能因为一次失败而自暴自弃产生抑郁啊。

回想这一年，我经历了许多——感谢 CSP2020，这是我第一次在考场上通过非简单题，给予我勇气；感谢 NOIP2020，这是我的一次较差的发挥，它让我懂得了考试策略的重要性；感谢 APIO2021，让我见识到了真正的难题，教会了我在 OI 赛制下对拍的重要性；感谢全国省选，这是我在 NOIP 后的一次翻盘，既有成功也有侥幸，使我在面对接下来的考验有了更多信心；感谢北京集训，让我见识到了好多好多的大佬，在做题的时候锻炼了思考能力；感谢 NOI2021，让我第一次体验了全国级别的大赛，使我看到了差距，激励我不断前进......

感谢 OI，感谢 2021 带给我的所有。

2022，继续加油。