NOI 2020 退役记

Day -1

早上来到了火车站,坐了六个小时的火车,车上玩cytus2玩到防沉迷后开始睡觉,终于来到了长沙

来到学校,领完东西到寝室,发现寝室没网,必须得去自习室,和前年的WC差不多

Day 0

今天要考笔试,早上起床又看了遍笔试题,就去参加开幕式了

开幕式

开幕式前选手们每个省排成一排在操场上站了十几分钟,然后进入会场

开始前放的视频是长沙一中的宣传视频和CCF的著名“3M原则”视频

然后就是领导们讲话和长沙一中学生们的才艺表演,最后那个揭幕仪式有点高级

开幕式结束后吃完饭回到寝室直接睡到下午两点

笔试开始

前面的题都非常简单,直到第47题:

在NOI机试正式开始前,下列哪些行为是禁止的?

然后有一个选项是不能触摸鼠标和键盘 这怎么可能嘛 交完后得知答案后才发现,这居然不行😒?! 明天我一定要在考试前摸键盘 笔试喜提99分

Night

看了看板子,还抄了份KM的板子现场背

Day 1

昨天晚上醒了好多次,早上醒来头晕乎乎的,吃了块🍫试图挽救 考前突然忘记“志愿者招募”是怎么构图的了,又看了一下 这是伏笔

Day 1考试开始

开考前先摸键盘,无事发生 花了15min看完了三道题的题面 感觉今天的部分分有点多 抱着保银冲金的策略,我打算先把部分分先打得完 T1显然的的dp,先写了一发,50pts,看一眼数据范围,有些玄机,感觉可做,先放着等会儿再来做 T2看完题,每条边选或不选,树上一条链中至少要有一边,突然就想到了网络流/费用流?然而用类似“志愿者招募”的线性规划的方法勾了半天图却还是构不出来。再看一眼题目。嗯?求方案数?我怎么做着做着就变成最优化问题了???😱推倒重来,比较小的部分似乎容斥后只需求树上链的并就行了,可我只会树链剖分啊,肯定没这么复杂,先去看看T3 T3我靠好麻烦啊啊,第一眼看上去就感觉要求好几维的偏序问题。

  1. ,似乎可以枚举后用BIT维护
  2. ,变成了一个求区间顺序对的问题,emmm实在不知道怎么用两个的复杂度的做法,只好写了个莫队,跑得还挺快
  3. 性质C,整个序列逆序对个数不超过50,我先用个set处理出了所有逆序对,然后只需二维数点了,用个主席树就行

至此,T3总共写了52pts 回到T2,又思考了两三分钟,突然发现不需要树链剖分,建一棵虚树后,链就打个标记扫一遍就完事了, 40pts22个点建虚树2333,感觉大材小用,不过最后题解里说这部分确实得这样写 最后还剩30min,突然发现因为一条链一定是的祖先,那么就可以直接dp一发,记表示结点往上的距离中至少要选一条边的情况的方案数,复杂度原本是的,发现转移用卷积优化一下就变成了。于是T2变成了56pts。这时只剩下15min,我估计也写不了什么分了,于是就开始检查。T1就搁在那儿了。

估分50+56+52=158

考试结束

考试结束后,听见好多别的学校的人说200+,感觉有点凉凉,但感觉应该还是在银牌线以上

发现T1其实发现之后裂个点就可以100了,感觉考试的时候也能想到,但写写也不知道要写多久,可能后面的分也会少一点

T2听说我那个算法容斥虚树和dp加起来总共能拿72分,然后我心底一凉,我那个for循环上界写的是而不是,改三四个字符本来能拿72,不过最后几分钟我能把这个dp写完也不错了,人都慌死了那个时候

最终得分45+56+52=153,T1好像有点写挂了,银牌分数线大概在120左右,金牌线在210左右。似乎我第一题写出来了就稳了

Night

恰完晚饭来到自习室,又背了会儿板子,看了几道前几年的题,就回寝室了。

晚上睡觉的时候感觉枕头好高啊,一直睡不着,一看手表3:30

Day 2

🍫🍫🍫🍫🍫🍫🍫

Day 2考试开始

T2题面很长,三道题一共看了20+min

看完题后我的内心是懵逼的,感觉只有T2可以有理有据地做

看看部分分,哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

感觉今天要爆零了

T2先想了个做法,就是对于一棵树

假如输入的那么可以推出

然后发现这个做法不具有普遍性,只有在具有性质4的时候成立,但我还是开始写了

不过这个好像有点难写,感谢开了c++11,我可以直接用unordered_map存hash值,写了两个半小时之后,发现前四个样例都过了。又加了些东西后,我的代码理论上能过小的点和有性质4的点和全是链的点,但根本没有办法写对拍,于是此时我的分数处于区间之间,我还是很有可能爆零的。

此时剩下T1和T3,感觉两道都是结论题,我一向习惯做有理有据的推理题而不是猜结论题,最后rand(2)去做了T3。

刚开始看到T3的时候我有点冒冷汗,考试前看到过弦图但是感觉很远古的东西了应该不会考所以就没记结论。看到第一个最小的部分分就不会做,我的心拔凉拔凉的。看到性质A,每条边权都相等。然后发现因为有弦图的那个性质,随便口胡证了一下。只要缩点之后在同一个双连通分量里时,那么答案就是两点之间最短路,否则输出。然后性质B,画了个图,发现情况有点多,dp一下可能会好一点。尝试写了一下,发现有一堆乱七八糟的情况,于是又弃疗了。

最后看看T1,没有看见。。。于是写了一个乱七八糟的贪心,然后总感觉的时候我这种构造方法似乎是肯定有解的但也没有多少时间留给我证明了,我也不敢保证能对,于是为了防止爆零,又写了个的暴力,于是,考试就结束了

坐在我左边的选手似乎从开考时就弃疗了,接下来五个小时里,他的动作在擦手,擦脸,吃东西,抖腿等动作之间连续变换,尽管我尽力不去理他,但吵得我真的很烦

估分:之间随机

考试结束后

终于知道昨天王宏老师为什么让那些Day1低于60分的人今天要多拿分了,因为今天真的没有什么暴力分,感觉今天的题是最不像NOI题的NOI题了,可能是因为这次考试结合了NOI和CTSC的目的吧。

T1听出题人讲了一大串证明后似乎我考试想的结论是对的,然后从推到就比较方便了

T2似乎将每棵树的主链搞一搞,把三合一变成四合一,然后用线段树维护一下就是一个的复杂度,用unordered_set就是线性的了

最终得分:35+16+20=71

T2居然才这么点分😭,难以置信,不管了,反正也拿不了Au,也差不了多少

今天听讲题的时候突然发现,考试前我自认为会考的字符串、数论、多项式/生成函数、网络流/费用流居然一个都没考,怕了怕了

Night

既然一切都结束了,那今天必然是要通宵的

Day 3

通宵颓废后感觉并没有想象中的累想知道我这四天总共睡了几个小时

吃完早饭后又打了一会儿游戏就去参加闭幕式了

闭幕式

闭幕式又是和以往一样:领导们总结这次举办的成功之处,然后就是宣布获奖名单。但因为这次是noi,所以每一位获奖的人不仅仅能有奖状,还能有一块奖牌。

这似乎是我oi生涯中第一次拿真的奖牌吧,也是最后一次了。看看获奖名单,许多实力非常强的人却没有得到金牌,相信他们也一定是非常遗憾。

在才艺表演之后,是两届举办学校的交接仪式,这次非常特殊,因为明年——2021年,noi将会在我们学校举办。

看着我们学校的宣传片,不时还能看见自己的身影,我心中最强大的竟不是羞耻感,反而确确实实有一种自豪的感觉。宣传片拍得确实非常好,而且这是noi第一次在一个县级市举办,不得不说是我们的光荣。可惜的是,明年我已经不再可能登上这个赛场了。我们学校已经两届没有Au了,希望我们下一届的神仙们能给我们学校维持排面

The End

有史以来打得最憋屈的一场比赛,这次是我真的唯一一次分数至上的比赛,也是我一次完全没有享受到比赛乐趣的比赛。没办法,我也不是没有过比赛太浪而爆炸的时候,这次要是太浪爆炸,就真的真的没有play again这个选项了

没关系,一切都结束了,七年oi,青春中永远的彩虹,感谢相遇。

这次,OIER PhoenixGS 正式退役了

再见