NOI2020 游记

写这篇游记的时候，感觉自己语文水平完全不行。写了又删删了又写，寥寥的几个字硬是磨了好多个小时。得赶紧退役回去学文化课了。 AFO。 ### Day -2 Day -2 是 APIO 比赛日，就兼着 APIO 游记一并写了。 开场懵了，三题都一点思路没有。 快速浏览题意和部分分后，发现 T2 为一条链无解，为一个环是最大值，马上敲完拿了 6 分。抢到一个 ID 两位数的有分程序，开心（ 又瞎猜了 T1 Sub1 的一个结论，只有每个位置都满足 $a_i + 1 \equiv a_{i +1} \pmod{M}$（$a_i$ 是粉刷第 $i$ 面墙的承包商）才有解，竟然直接拿了这 12 分。不久我就发现这很明显是错的，$0, 1, \ldots, M - 1, 1, \ldots, M - 1, 0$ 这个数据就可以直接卡掉。 接下来一眼秒了 T3 的 26 分，还原出树后找直径然后不断找最远点，10 分钟 rush 完求直径和树剖 LCA 的实现一遍交上去过了两个 Sub。才过去半个小时，感觉开场挺顺的。 然后开 T2 的树部分分，感觉很可做，要维护什么最接近的度数为 3 的点，还有这个度数为 3 的点相邻的边权第 3 小的边，还有特殊情况是两条链全部伸在这个度数为 3 的点的一个子树内，然后要求最小的边和次小的边下去的最小的边……（说的有点混乱，但我坚信是有人和我想偏到同一个地方去的）写了好久写出来了，样例也都过了，交上去就是死活过不了，连着 WA 了十几发，暂时放弃了。 半场过去了，分数还是好低，只好试着实现了一下 T1 的 Sub2, 3，又连着 WA 了十多发，到三个半小时的时候才过了前三个 Sub。 又花了一个小时优化了做法，才过了 T1 Sub4。这时候只剩半个小时结束，才 102 分。突然想到了 T3 完全二叉树的做法，赶紧去写。 离比赛结束只差 1 分钟的时候写完了，本机小数据测试都过了，交上去。本来满心期待着能拿 21 分，等了半分钟后，比赛结束了，评测结果才出来：CE，std::sort 未定义。 发现自己忘记开 algorithm 库了，过编译是因为交互器帮我开了…… 最后只有 102 分，丢人了。希望能拿一个铜牌。 NOI 前一天的考试打得烂成这样，瞬间变得非常慌。 ### Day -1 从福州坐高铁去长沙。我们买了一班最便宜但是最慢的，在福建和江西境内都憋屈地只能跑 200，入了湖南才加到 300。我在车上读前几个月罗翔老师推荐的书《房思琪的初恋乐园》，花了五个半小时看完了，目的地也刚好到了。 学校意外的离高铁站很近，摆渡车不久就到了。接着就是报到登记，一系列手续挺是繁琐，队伍也排的顶长。终于登记好后，我们领了胸牌和与式的衣服，还有一个赠送的大包包，由志愿者领到宿舍了。志愿者的友善我给五星好评，在我们手忙脚乱拿不下所有物品的时候，志愿者主动过来帮我们拿，并一路送到宿舍里，真的感谢他们的帮助。 晚上去食堂，本还担心着会不会被辣呛，结果发现是刚刚好的辣度，不仅可以接受，吃起来还特香，简直是我吃的最好吃的食堂。我敢肯定这不是我旅途劳累后觉得饭菜好吃的原因，因为接下来的几天我的味蕾都是被这样的满足。 宿舍有晾衣绳、衣架、脸盆、水桶和洗衣液，可以洗衣服了，好评。 这天晚上宿管阿姨好像忘了熄灯，我们通宵到了快两点。 ### Day 0 早上七点半迷迷糊糊睁开眼睛，想到八点早餐就结束食堂就要关了，赶紧把其他人叫起床。火速洗漱后吃了早饭，到操场上集合前往开幕式会场。 开幕式最有趣的部分就是杜主席讲话。和其他老师不同，杜主席讲的非常中肯，非常贴近实际生活。从他的描述中，我也体会到了这次办赛的不易以及领导们的勇气与付出。值得一提的是，杜主席 “定” 了一项新规矩：出现一次剩饭就扣 1 分（没错，粉兔就是因为这个没有金牌的，就是的就是的（大雾））。 下午笔试和试机。笔试没有悬念的满分了，试机的三题是去年的斗主地、序列和 I 君的探险。看到交互题了，说明今年有交互题了，更慌了。 晚上 10 点半，宿管老师在粉兔洗澡的时候熄灯了。夜空几乎透不出光芒，浴室里漆黑一片。我和同宿舍的 lh 觉得粉兔好惨，但除了调侃宿管老师外，也做不了什么。 ### Day 1 上一天熄灯很早，也睡的很早。早上 7 点起来也蛮有精神。在食堂吃早餐的时候就十分的紧张，拿托盘的手一直不停地抖着抖着，从脖子到脚全身都在发凉。我和 lh 说，我感觉好紧张啊。lh 也用发抖的声音说，他也很紧张，去年也没有这样子。我感觉我说错话了，在一个把这当做最后一战，不成功便成仁的高二学长面前提起这样的事，只会让他心态变差。我低过头，便不再说话了。 前面老师让大家稍作整理，8 点 1 分正式开赛了。我看到第一页的试题摘要：传统、传统、传统。看来交互在明天吗，那运气还不错，今晚可以再学学交互。 看到第一题。图论，$n \le 50$，$T \le 10 ^ 9$。好像是矩阵快速幂裸题？看了看 $w \le 5$，直接拆点，$\mathcal{O}((nw)^3 \log T)$。觉得好难写，先写了个 $\mathcal{O}((n + m)T)$ 的拓扑排序，就放一边先看 T2, T3 的部分分了。 T2 似乎有个明显的容斥，记 $f(S)$ 表示不经过 $S$ 内边的方案，答案大概是类似 $\sum (-1) ^ {\lvert S \rvert} f(S)$ 的一个式子（$-1$ 的指数记不清楚有没有 $+1$ 了）。$f(S)$ 与 $S$ 交集大小有关。$S$ 的交集可以用 FMT 来求，就是对每条边贡献到所有经过它的子集上，这是一个超集加可以取补集之后变成子集加操作用 FMT 来快速维护，复杂度是 $\mathcal{O}(nm + 2 ^ m m)$，拿了 40 分。稍微想了一想能不能优化这个容斥式子，没有任何思路，就放一旁去看 T3。 T3 看到是个矩形逆序对，又看见我们区有位长头发的监考老师走来走去，又注意到题面里有个小 L，瞬间知道是怎么回事了。想都不想直接奔着部分分打。24 分平方暴力树状数组直接做，特殊性质 A 区间逆序对莫队 + 树状数组硬上，虽然我也会二次离线但是完全不想打，测了极限数据似乎都挺快，特殊性质 C 二维数点直接离线树状数组做。特殊性质 B 见过类似的套路，所以一眼看出来是扫描线建树 + 启发式合并求答案。但只有 12 分而且好难写，就回到 T1 去写正解了。这时候是四个小时，$65 + 40 + 52 = 157$ 分。 T1 正解意外地好写，半个小时写完一遍过编译过样例过对拍了。然后去 rush 特殊性质 B，写了 20 分钟后还遥遥无期，离结束只剩 10 分钟了。于是扔掉去检查文件名、数组大小之类的问题。 下午出成绩了，没挂分，$100 + 40 + 52 = 192$。同校同学的 T2 都比我高，他们说这个 $\mathcal{O}(n ^ 2)$ 做法可以一眼秒，线段树合并的优化也很显然，我自闭了。事实证明网上同步赛上初三的学弟也把这题 A 了，我自闭得更严重了。 讲评的时候说 100 名线在 203，排名在自己预期之上，还挺激动的。 晚上夏哥直播了糖豆人，B 站转播鸽了好久，学校信号又好差连不上 404，崩溃了好久。十点半左右开始转播了，我用大会员返还的金瓜子买了一些礼物送，终于把粉丝牌子刷到了 10 级，可以送泡泡枪啦！无比激动。直播到十一点，夏哥下播了，我也去睡觉了，~~我和直播贴贴。~~ 宿舍里就剩粉兔没洗澡了。粉兔准备去洗澡的时候，宿管老师又把灯熄了。粉兔又摸黑洗了一天。 ### Day 2 还是很紧张，一点也没有放松。教练说的什么第二天心态会好一点，都是骗人的。 早上准时开题，看到三道传统，我人懵了。 翻到第一题，构造一个方案，我人懵了。 翻到第二题，题面这么长，我人懵了。 翻到第三题，弦图，我人懵了。 我考前还认为 NOI 不会考构造题的。构造题这种题目，部分分就极其难出，放在模拟赛里训练思维可以理解，放在正式比赛势必会造成巨大的且奇怪的区分度，而这是应当避免的。 就我个人所看到的，福建省的情况：这道题是否做出来就对应了是否进集训队 —— 没做出来，其他题做成什么样都无济于事。 我考场第一个结论都没猜出来，完全不会构造。出题人讲评的时候说随便暴搜一下就可以搜出 $n, m \le 4; k \le 50$ 的方案，我是完全想不出来怎么搜。狂码了 200+ 行的暴力枚举 + 最大流 check 还原方案，$\mathcal{O}(\binom{n}{2} ^ m \cdot \operatorname{maxflow}(n + m, n + m))$，一个多小时后拿了 15 分。最终也是 15 分。其他题排名都进了前 150，只有这题在前 300。 T2 题面虽然长，还是非常易懂的。正如讲评时有位大佬所吐槽的那样：我希望这样子的题面在 OI 中再次出现。我也有这样的愿望。 样例有 12 分好评，直接写了。 链的 4 分是送的，除了 $\exists n = 1$ 都无解，直接写了。 性质 4 的 16 分从链拓展一下，写个树形 DP 就有了。这题短时间内就拿了 32 分，比 T1 憋屈的 15 分网络流爽多了。 接着我想性质 4 的树形 DP 可以拓展，只要非空左子树合法且非空右子树合法且空左子树合法且空右子树合法，则这个子树合法。实现了发现过不了样例 4 和 5，有一两个 `No` 的被我判成了 `Almost Complete`。赛后得知这个做法是出题人点名卡的 “三缩一” 做法，不过好像有人在这个做法的基础上加个 “忽略左右子树都不是叶子的树” 这样的特判 A 了。现在我不知道这个加了特判的做法是不是对的，听起来是很靠谱的。因为如果一边不是叶子，那么会存在一个这个位置上是叶子节点，然后另一边子树是可以无限扩张的，这个树就是没有用的。 T3 感觉特殊性质 B 很可做，就是拉完链后不能走回头路，感觉很 DP 的样子。想了两个多小时，写了好多个假 DP 都过不了样例。最后搞了个很麻烦的 DP：维护一下当前在奇链 / 偶链上，另一端的链头是否被隔开，上一步走 1 边是在前一步还是更之前，`dp[n][2][2][2]` 这样的超麻烦的东西，写了好长好长的转移，成功把程序答案和标准答案的位数做到相同了，但都是过不了。最后 `puts("-1")` 走人。 出考场我自闭了，但听到输出 `-1` 的人意外的多，我心中一喜。又听到 A 掉 T1 的人也非常多，我心直接凉了。 下午出成绩，没有挂分，`-1` 竟然有 $5$ 分的成绩。$15 + 32 + 5 = 52$，两天加起来连笔试 $344$。银牌应该是有了，但估计只能排在中部吧。 晚上听讲评的时候，待在宿舍的 lh 打电话过来，说线出了。我 125 名银牌，他 45 名进队了，粉兔 51 名恰好被线卡了一分。然后被教练催去面试，北大老师问了我几个问题，就建议我报考北大的强基计划，我也提交了报考北大强基的申请书。 挺开心的，感觉高一的课没有白停，取得了满意的成绩，也收获了自己努力所向的东西。 回到宿舍，lh 进队，粉兔大概率进队，氛围是轻松愉悦的。大家在一起划水、聊天，就这样到了很晚很晚。 11 点多的时候，还是只有粉兔还没洗澡。我问粉兔要不要赶紧去洗，他说都考完了应该不会熄灯了吧。话语刚落，宿管老师就把灯熄了。 最后一晚的住宿，粉兔还是没能逃过厄运。 ### Day 3 早上本来想听国家队答辩，到了会议室发现人坐满了，就到隔壁的自习室写游记。本来写了很长很长的心路历程，想把我这半年来所有的压力宣泄在游记里面，但又想到现在不应该是传播负能量的时候，就把写了的 1000 多字皆数删了。 颁奖典礼上，看着胸口挂着的沉重的银牌，心里有一种所有付出的努力全部凝成了实体，变成了这枚奖牌的感觉。我不知道如何描述这样一种心情，好奇怪呵，明明挂着那么重的东西，却感觉是卸下了更重的东西。 下午做高铁回了福州。没书看了，取而代之，我把夏色皆守的前三天看完了。好感动啊，我发现原来友情可以是这么美好的东西。朋友可以成为那种你在最寂寞最茫然的时候唯一的依靠，真真切切打动了我的心灵。至于为什么不看完第四天？因为流量没了。 晚上 11 点多回到家，NOI 2020 之旅就结束了。 ### 8 月 21 日 写游记的今天，应该是 Day 4，但我不想用这个作为今天的标识了。我的竞赛旅途已经过去，最后一站留在了坎坷的 NOI 2020，火辣的长沙。这段和同学们在机房里一起奋斗的时光，让我收获了许多，不仅有学科知识，也有社会经验和为人的道理。我相信着，多年以后当我回想起青春生活时，这段竞赛生涯一定是其中最优美的华章。 --- Tweetuzki 2020 年 8 月 21 日