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 的暴力差不多,设 fi,jf_{i, j},表示 11 走到 ii 走了 jj 的长度的最大收益,O(mT)O(mT),只有40pts 感觉没法优化。

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

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

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

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

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

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

比赛结束

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

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

感觉 T2 顺着想是不难发现 n2n^2 DPDP 的可惜去搞 T3

复测的时候发现 T3 O(nmlogn)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 网络流做法是错的,感觉不可以做。

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

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

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

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

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

GG

Day 2 翻盘->翻车

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

45+8+2045+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 算法少,但是省选缺少纸质教材,如果没有同学交流学习效率是难以上升的,不在于个人颓废之类的原因,而在于省选算法确实更加困难,有同学可以互相教育提升水平。(虽然感觉我这段话是在为自己找借口

也许夹杂了一些暴论(