NOIP2022游记

看到一句话。人事已尽，天命难违。

至少我战胜了自己？

前夜。

和 MC 互相鼓励了一下，早睡。

没有像去年一样做噩梦，但是早上五点半自然醒。

其实梦到了关于 NOIP 的事，但是比较模糊。

开场 5min 搞 vim 配置，这次是 64 位系统很友好。

开场看题，T1 第一眼感觉比较奇怪，不过既然放在 T1 那么肯定不会太难，一会回来推一下应该就出来了。T2 看上去是人类智慧，T3 图论感觉不太擅长，T4 感觉就是扫描线搞一搞。

然后发现 T1 所有东西都很好递推表示，就飞快地写完了，确认了一下多测清空直接走了。

T2 第一眼没什么思路，我决定直接去搞 T4。

扫描线下来拿两个单调栈维护 a_i 和 b_i 的最大值，然后相当于 a\times b 的历史和，但是发现区间对 a_i 或 b_i 加和历史和下传的标记冲突了，想了下还是不太会维护，去看 T2。

看了十来分钟才发现 k=2n-[1,2]。

对于 k=2n-2，显然留一个空栈，其他每两种颜色放一个栈就好了。

考虑多一种颜色，感觉就是分讨一下，大概是考虑每种颜色下一次被消掉的最早的那个颜色。然后前前后后搞了一个半小时啥都没搞出来，这时候还是 100+0+0+0，心态有点崩，调整一下去看 T3。

发现每次对方只会删一条边，说明一个强连通分量里的边怎么删都没事，那么有关系的边就是缩点后的树边。在这个树上直接 dp 就好。感觉有点难写，前前后后大概花了半个小时，写了 20min。

T2 将是个未知数，所以先把 T4 的 O(n^2) 的暴力给它打了。

回来理了一下 T2 思路，大概是如果已经放了 2n-2 种颜色，那么考虑是否有一个栈满足它栈底的比栈顶先删，如果有就放这个栈上面，否则就放空栈。

飞快地写完后写了个 checker，并过掉了不怎么强的大样例。

时间还有一个小时，去看看能不能在 T4 多捞点分。

发现有一种 A 和 B 都随机的数据，一共 52 分，于是猜了下每次暴力遍历栈的大小期望复杂度不会太大，然后用线段树搞了一下区间加。

算了一下复杂度，大概是 O(n\ln n \log n)。

回来拍 T2，拍出两个错都是 checker 和 gen 的问题。然后就没问题了，但是事实是我 n 造太大了，很水。

赛时估分 100+[15,100]+100+52=[267,352]。

那时候，我想，我赢了。

在 INFOJ 上自测，T1T3T4 一分没挂。

可惜 MC 挂没了，T3 因为注释的问题 CE 了，唉，以后的路要我自己走了。

然后听说 alpha 学校在测，问了下榜，于是说我 T2 爆零了。

看了一下代码，多测没清空 ans=0，赛时为了 checker 的方便我都是直接 T=1 了。

看了一下题目数据范围，没有 T=1 的点。意味着这题注定 0 分了。

水了下群，发现我的做法似乎是正解。加了下交到 INFOJ 发现只有 50pts，也不少了，唉。

有点好笑。在几个群和几个人那里发泄了一下。要靠省选翻盘了。

我对我自己的定义是一个暴力选手，只能蹭队线。翻盘对我来讲很难。

稍微发泄了一下，我想我能做到。

然后就一直找 alpha 问分问队线，发现没落后太多，还是有希望。

然后一直在找 MC 和 wxw 诉苦，以及一些小群。

在心态上也算战胜自己了，我会走到最后的。

尽人事，听天命。

这里借用最近很喜欢的一首歌《巡光》的歌词。

你未必 光芒万丈

但始终 温暖有光

愿多年 之后回想

仍不悔 少年模样

一路向阳。

出分了，注定的 100+0+100+52=252。

听说大部分人 T2 分都低了，看了下小图灵，rank 19。

然后拿官方数据测了下加了多测清空的 T2，发现是 55pts，如果 307 的话应该是 rk4 吧。