NOI 2020

记忆的终点?

Posted by Ghastlcon on August 20, 2020
CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可,转载请注明:“转自 NOI 2020

无人能预测的命运之舞台
我就是想看这个

因为实在没心情,所以随便写了,图片也不放了。

$\mathrm{Day -1}$

不是很懂为什么教练买了 $8$ 点的高铁票,搞得 $5$ 点半就起床。

和 $\text{yyc}$ 匆忙赶到火车站上车,毫无波澜地来到了长沙。养老院群里,似乎再也没有可以见面的人。

怎么还有接站服务的,过于高级。

宿舍环境不错,感觉比去年好多了,去年啥都没提供,不过咋又是住女宿啊。

往牌子里塞了个头像,感觉良好。

今年似乎还是有纪念品卖,真是够贵的。

吃饭的时候发现菜里面全是辣椒,还有很多长得很像豆角的青辣椒,不愧是你。

晚上去自习室,发现根本没有电,网速还奇慢无比,于是随便写了个 $\text{LCT}$ 就跑路了。

过了半年多终于又见到了 $\text{Rose}$,感觉他进队稳了。

$\text{pb}$ 大师怎么这么赢啊。

$\text{Day 0}$

$7$ 点的时候昨晚因断电熄灭的灯亮了……

队长不见了,广东队失去了精神支柱。开幕式挺无聊,今年似乎不用喊口号。上去拍照发现得蹲在女队旁边,然后照片里根本就没有我。

$\text{dzd}$ 说什么吃饭有剩饭扣 $1$ 分,吃饭大赛?

下午笔试顺利 $100$,$47$ 是个坑题,本来还不确定能不能碰鼠标键盘,结果 $\text{dzd}$ 说了句“笔试还有个目的就是让选手们重新熟悉一下竞赛规则”,于是就全选上了(

看了下试机题,是机器人,序列和 $\text I$ 君的探险,那是不是今年又有交互?

编译选项里甚至还有 $\texttt{-std=c++11}$!$\text{wh}$ 说到这里的时候全场鼓掌。

对着这个序列冲了个费用流就跑路了,还调了会。

晚上啥都没做,看了一堆板子搞到 $11$ 点多。

$\text{Day 1}$

今年居然在考前发吃的,看起来还挺高级。

开场看完题发现没一个会做,对着这个 $\text A$ 搞了搞感觉复杂度和 $w$ 有关,一看发现 $w\leq 5$ 直接笑死。

结果还是不会,不知道为啥只会 $\mathrm O(n^3w^3k\log t)$ 。一个小时过去了,我还没签成签到。

看了下这个 $\text B$ 发现直接容斥有 $40$ 分于是就写了,因为比较懒所以写了个剖,跑的出奇的快。感觉后面的分都不太能做。

这个 $\text C$ 强于区间逆序对,感觉是个 $\text{lxl}$ 题。然而除了 $\text B$ 部分分都挺蠢的,随便写写搞了个 $52\%$ 就跑了。

回来看 $\text A$,试图用线性递推的那套理论优化,用 $\text{Cayley-Hamilton}$ 定理冲了下然后发现我成功将复杂度优化掉个 $w=5$ 。

然后算了下 $n^3k\log t$ 发现是 $7.5\cdot 10^8$,这怎么看都不对,只要 $n^3$ 和这个 $k$ 靠着就必死。

再想了想发现维护短向量就行了,然后半小时写完。这个时候 $12$ 点。

发现得分已经 $192$ 了,按照队线不上 $200$ 的猜测于是开始求稳。检查了好多遍然而啥都没检查出来。

最后为了做个有梦想选手,把 $\text C$ 的剩余分数改成了用暴力跑。


好像这个 $\text B$ 是弱智题,打扰了。

那我没了啊,这队线肯定 $200+$ 了。$\text{Rose}$ 和 $\text{pb}$ 都 $250+$ 了,感觉他们都稳了。

$100+24+64=188$,这个 $\text B$ 真的败笔了。$\text C$ 莫名其妙多了 $12$ 分我是想不到的,看起来还是要有些梦想。

听说正式队线 $220$ 左右,问题不大。

$\text{Day 2}$

没有社会活动,不用担心 $-50$ 了。

看完题又发现没一个会做,行吧。居然没有交互,烟雾弹?

这个 $\text A$ 浓厚网络流气息,搞了会感觉不太行。

为什么 $n-1\leq m$ 只有这么点分,很简单吗?整个图是个连通块?

猜了个每次最小连最大,不敢写。然后我点开 $\texttt{dish2.ans}$,看了几眼之后——

大师,我悟了!

写完之后测了下 $\texttt{dish3.in}$,发现输出和 $\texttt{dish3.ans}$ 完全一致,甚至都不需要 $\text{spj}$,笑飞了。出题人甚至没有把答案 $\texttt{random\_shuffle}$ 。

然后 $m=n-2$ 感觉完全不会,怎么分成 $2$ 个连通块才能保证各自有解?不太明白。

跑去看 $\text B$ 发现题都不能轻易看懂,并且只能在叶子上长这个限制有点麻烦。感觉不太能做。

$\text C$ 的弦图性质有啥用啊,最短路这种东西和完美消除序列应该是无关的啊?想了想感觉完全不会做,输了个 $-1$ 跑路了。

这个时候都 $11$ 点了,我的总分高达 $25$ 分。回来看这个 $\text A$ 直接猜测和是 $k\cdot (n-1)$ 就肯定有解。随了几组数据发现好像确实是这样。

那我直接背包出个子集就好了?这复杂度 $\mathrm O(\frac{nmk}{w})$ 看起来很假啊?感觉跑不过去。

想了很久也不知道咋优化,最后用 $\texttt{vector}$ 写了个背包。

这个 $\text B$ 好像有些分很送啊,我来看看。好像送了高达 $16$ 分,不错啊,走了。

忽然发现 $\text A$ 有几个点 $n\leq 25$,为了保险起见还是多写个折半吧。

最后结束前想了想 $\text A$ 的复杂度,等等……好像背包的复杂度是 $\mathrm O(\frac{n^2k}{w})$?!

我怎么还在用 $m$ 算这个复杂度啊,真是有够蠢的,要是因为这个送自己出队就搞笑了。抬头看了眼时间发现 $12:58$,已经没有希望了。

就靠在座位上,看着时间从 $12:58$ 到 $12:59$ 到 $12:59:30$ 又到 $12:59:59$,想着自己过去的所有经历。

这个分也就 $100$ 出头,无论怎样都不可能翻盘了的……

比赛结束,请所有选手尽快离开座位……


怎么 $\text{GD}$ 这么拉跨啊,集体翻车了?感觉是 $\text{GDOI}$ 打多了。

$\text{Rose}$ 也翻车了,$\text{pb}$ 还是好稳啊。

$\text{CCF}$ 传统艺能咕咕咕,下午 $4$ 点多才看到分数。

$85+16+5=106$,给了 $85$ 我满足了,就这样吧。

已经知道自己进不了了,在校园里游荡,发现这个分能排到 $\text{GD rank 7}$,咋回事。

晚上坐着听讲题的时候出榜了,果然没进,随便了……这些东西都与我无关了,我再也不需要听这些题的解法了。

去找 $\text{PKU}$ 换了个强基约,上面甚至都没盖章,感觉啥用都没有,不换也无所谓。

晚上就和退役老哥们庆祝退役,试图开心但是根本开心不起来。

$\text{Day 3}$

早上圆交体验还行,问题比以前的正常多了。

$\text Q$:你现在是第 $6$ 名,$\text{lyx}$ 也是镇海中学的,如果把他踢下去把你换上去,你觉得如何?
$\text A$:我觉得我没那个水平

闭幕式并没有什么心情听,就上去拿了块再普通不过的银牌。建议 $\text{CCF}$ 以后发 $100$ 个金牌,反正没保送都走强基,多发点大家都开心。

我曾经幻想过无数次……

幻想着“我曾经幻想过无数次……如今它终于到来了。”。

但是它最终也没有来到。

坐在座位上反复把玩银牌,忽然意识到,我的单色 $\text{OI}$ 生涯真的就从此结束了,可能再也不需要去担心其他东西了。

收拾好这 $5$ 天内的所有东西,离开了这个我曾经希望爱过的地方。只是现在确实什么都没有了。

高考之后,有缘再见。