NOI 2020 退役记

这个家伙很菜，什么也没有留下

ZJ 老年高二卑微弱校 D 类选手

ZJOI 2020 各种暴毙

虽然说我从来没有期望过进省队，但是 rk89 也是远低于预期

当时连退役记都没心情写，教练问我 WC 和 APIO 要不要去，我全拒了，报了暑假各种文化课培训班

万万没想到被续了 D 类

¶ Day -inf

文化课补习班ing

学会了杜教筛

补了前几年的题，学习了模拟费用流，学习了后缀数组

¶ Day -1

在高铁上学习了二次剩余，学习了 CRT

和镇海神仙队同车厢，瞥了一眼全在打游戏，瑟瑟发抖.jpg

接站时，“效实中学 2 个人是吧。绍兴中学 1 个人是吧。”“是 10 个”

志愿者好评，提供了各种帮助，发了狗牌和两本书还有几件衣服和一个书包（书包比较神奇，不难发现表面有一个 USB 口，其内部又有一根 USB 线，具体用途不明（

食堂是自助餐，供应果汁+豆浆，好评

感谢 ouuan 的 Despised

¶ Day 0

上午开幕式

忽然明白 3M 原则是什么梗

dzd：“我要强调几条纪律:1：…2：…3：在食堂剩饭总分扣一分。” 掌声雷动（雾

下午笔试+试机 坐在风口下面，冻成冰沙雕（考场能不能带小被子

恭喜 UOJ 猜到笔试题

打了几个板子发现啥都不会，KDT 不会，Splay 忘了，DP 全推不出，自闭ing

¶ Day 1

忽然发现男生和女生是在同一层楼隔着屏风（滑稽.jpg

寝室空调开太冷了，小被子无法温暖我，睡得很晚，睡眠质量也差

没分在风口位置，万幸，温度舒适

目标分数 150pts

看了一下 T1，暴力和 UNR#4 D1T3 的暴力差不多，设 $f_{i, j}$，表示 $1$ 走到 $i$ 走了 $j$ 的长度的最大收益，$O(mT)$，只有40pts 感觉没法优化。

冷静一下看 T2 感觉会 $O(n\cdot2^m)$ DP，不是很好写，没多少分。

看 T3 感觉是数据结构，并不是很会。

先打了 T1 暴力，忽然看到 $w \le 5$ 感觉可以矩阵，先考虑一下 $5\times n$ 的矩阵发现不行，用了 $1\times 5n$ 的矩阵，$250^3\log 10^9$ 感觉很虚，但还是写了。存了矩阵 2 的幂次，写乘法用了几个 register，忽然发现 $1\times 5n$ 矩阵乘 $5n\times 5n$ 矩阵是 $n^2$，非常感动。复杂度大概是 $O(n^3\log T + n^2 k \log T)$。

随了几组，可以跑过。忽然忘记对拍脚本写法，用 Python os.system() 瞎搞。2.5h A 了 T1。

上个厕所平复一下激动之情，写了一下 T2 $O(n*2^n)$。看了一下 T3，当时觉得 T3 A性质可以用树套树水过 40pts 美滋滋（然而并不能

忽然忘记树套树怎么写，乱搞了一通，单点修改和区间查询正常了，过了 $O(mn\log n)$（但实际上只要扫描线即可）。发现区间修改不会做，然后乱搞了一下 tag，并没有写过去。

比赛结束

T2 T3 全写了普及组暴力 估分 $140$

同寝神仙 252，听他怒斥傻逼题，深深感到了自己的弱小

感觉 T2 顺着想是不难发现 $n^2$ $DP$ 的可惜去搞 T3

复测的时候发现 T3 $O(nm\log n)$ 的暴力没删调试，GG 140->128

旁边有个兄弟文件夹建错了，默哀（考完 Day 2 回看，只考 Day 1 Ag->Ag，只考 Day 2 Au->Ag

听说 zx 和 zyy 阿克了 %%%

晚上讲题，从来没听说过所谓区间逆序的说法，分块只做过模板（也处于我对分块的偏见，认为它是不优美的数据结构），我才是时代的眼泪。

感觉别人 T2+T3 都 70pts 以上，非常难受

讲题以后就各种颓废，完全没心思，看了看 2016 年集训队论文第二篇网络流相关。

¶ Day 2

没睡好，有点晕

开考前去操场上小声唱歌（「不可道」真的好听，安利

心情平静

翻了一下题，感觉 T1 是网络流，T2 题面暗示是一个智商题，T3 是个看不懂的图论。

想了想 T1 的网络流，建了一个 naive 的图，想起我校大佬教育了我的 ZJOI 2020 D1T3 序列的 naive 网络流做法是错的，感觉不可以做。

然后不难观察如果你要使用两个原材料（一个 $\le k$，一个 $\ge k$），肯定会把小的用完。

然后就 dfs，眼睛看了一下小样例过了，大样例跑得飞快，试图手写 checker ，发现好像困难，随便调了点参数造了几组，又跑得飞快，不知道正确性怎么样。

去看 T2 T3，T2 反复在会了和假了之间横跳，想了一个三缩一立刻被自己 hack。 T3 题面看了好久才懂那个环是在限制原图，先打了一个 Tarjan 割边，想不到 $n^2$ 做法，画了一下，感觉性质 A 就是最短路，写了，过了 A 的样例。

还剩 2h 看 T3，把发的东西（士力架x2+菠萝包）全吃了，乱想了一个 $n2^m$ 被自己批判了，看了一下关于树高的限制，感觉可以枚举所有树判一下。

忽然发现不会如何枚举所有高度 $\le h$ 的二叉树，自己乱搞了一个，总复杂度是 $O(2^h\times 2^{2^h})$ 理应 h 越大越正确，但是只有 $h=4$ 能跑样例，没时间了。

GG

Day 2 翻盘->翻车

成绩咕了 1h 多，不知道什么原因

$45+8+20$ 非常感动， T2 好像后面一个点是用脚造的，T1 能把 dfs 卡成 45，我那个 Tarjan 判无解不如不写。

听说 PKU 要 480， 深深感到自己的弱小。

讲题全程掉线，感觉全是 observation， 出题人说 T2 输出样例有 12pts，我是傻逼。

由于对自己智商的不自信（实际也应该不自信 qwq），没有去思考 T2 正解，几乎时间全投入打暴力。

如果我是正式选手的话是 rk175，勉强 Ag

对于这次 NOI 2020 的题目，非常感动，因为颓废+学习文化课的原因，我多项式（指 FFT、NTT、以及所有多项式算法）和高级数据结构（LCT）还有高端字符串科技（例如 SAM、后缀树、ZJOI 2020 的 runs），是完全不会，这次考察的知识点并没有涉及。此次还是重在思维的考察（虽然我思维没有，但其他人也没有（暴论

¶ Day 3

高铁站茶颜悦色，因为各种原因并没有点 k 站长强烈推荐的幽兰拿铁

高铁上感慨了一下没做过的暑假作业，23 号开学。

短暂逃避文化课，拿了一张废纸

¶ 退役感想

写这篇文章时，看了看 working 文件夹许多没写完的题，看了看 _post 文件夹许多没补的题解，决定全删了

从上面这篇游记不难看出这名选手很菜，他很菜的原因是他很颓废。

长期处在退役/续命的叠加态，没有认真学习 OI（文化课还是认真学了

时间最长的停课也许是 CSP 前的两周停课。对于 ZJOI 2020 也只有一周的停课颓废。

但是显然，一周时间是无法补完所有知识点的。

于是他理所当然的炸了，并没有什么可抱怨的。

NOI 2020 D 类也完全是机缘巧合。

在一个并不怎么大力支持竞赛的学校，也许命运就是这样（其实主因还是自己颓废，网课的时候明明可以却没有学 OI

感谢我小学时的启蒙老师。

感谢我高中时的教练。

感谢我文化课老师的理解和支持。

感谢我的学长。

感谢我的同学们。

我给 OI 只贡献了 OI-wiki 的矩阵页面的一小部分 + 自己的一些 naive 课件 + 一些题解和题目翻译

我的 OI 生涯全程矩阵相关，我的最满意课件是「矩阵初步」，ZJOI 和 NOI 全靠矩阵 A 题，这就是缘分吧 233

¶ 人生经验

事实证明，学习完递归，单靠互联网资源学习，完全可以达到 NOIP 400+，加上必要的省选级别算法、数据结构 + NOI 原题训练，完全可以 NOI Ag 的（因为 Ag 多了）。

比如我初中基本上是自己一个人（颓废），高中做题方面基本没有别人帮助（但教练会安排比赛，后期有学长教育），刷的是洛谷试炼场（历史的眼泪）提升水平，考前打了几场牛客模拟赛熟悉节奏，就 400+ 了，我做题数可以说是非常少，我 OI-Code 基本上是我全部的练习代码（533 题，其中很多是我在混普及组的时候写的），加上 35 场 NOIP 模拟赛和 39 场 Codeforces，这就是我的 OI 生涯全部代码（当然还有一些摸鱼项目代码和杂七杂八的练习代码没有统计

对于所谓弱校没有资源的情况，我认为在 NOIP 阶段是不合适的，这一阶段已经有很好的纸质教材（安利 lyd 的「算法竞赛进阶指南」） + 丰富的模拟赛资源。

OI 的资源主要在于其有优秀同学 + 学长指导 + 学校支持，但我认为这在省选及以上更明显，因为 NOIP 算法少，但是省选缺少纸质教材，如果没有同学交流学习效率是难以上升的，不在于个人颓废之类的原因，而在于省选算法确实更加困难，有同学可以互相教育提升水平。（虽然感觉我这段话是在为自己找借口

也许夹杂了一些暴论（