NOI Online 2022 游记

考的似乎比较套路,没有去年的思维 / 数学。

以考试当天为 Day 0。

Day ?

很早就报名了,都快忘记这件事了(

Day 0

在学校考试。

校内又说什么要占机房考试,好不容易在 8:20 的时候才到机房安心坐下来。

8:30 开题,还好没咕,不像 NOI 线上,一个小时还没拿到题。

结果盯着 T1 发呆了许久,满脑子里都是二维数点 $O(n\log^2 n)$,根本做不了这题。半个小时过去了,没有任何收获。

意识到事情没对,马上开 T2,发现是一个输出一个方案即可的题,似乎哪年 NOI 考过这样的题,还是随机化过去的?

tg 应该不是这类题目,推了推性质,发现可以按 size 分类,相同 size 的只可能不交或是完全相同,否则一定合法。

胡了一个只用判 size 相邻的做法,发现没对,可以按 size 倒序插入,用桶维护哪个点被那个集合覆盖,如果新来的一个集合覆盖的颜色不止一种,一定合法。

赛时没想清楚,随便输出一个颜色,考后才发现要输出不同颜色中 size 最小的。

写完 T2,过样例,由于不会造数据,只好跳过。此时 10:10。

发现 T3 似乎是一个简单题,拆一拆贡献,记录每一个位置的数被统计为最大值 / 最小值了多少次,发现剩下的是一个三维偏序(才没想什么还可以转化为二维偏序的方法),可以 $O(n\log^2 n)$,做 8 次,感觉有点卡。

马上开始码,还算顺利,没调多久就过了所有样例,极限数据 1.79 s,感觉很稳。

回过头来看 T1,已是 10:50。大力猜一手结论,应该是直接找到后面第一个比自己大的,然后如果颜色相同一直向前跳,扫描线处理询问,可以做到 $O(n\log n)$(不算向前跳的假的复杂度)。

发现要码 2 个线段树,心态不好,看到自己只有 30 min 左右的时间了,结果写完死活过不了大样例,此时已经是 11:40 了。

发现中间有一步不应该将因颜色相同而跳过的点删去,改了过后,过了大样例,还只要 0.5 s,马上交上去,11:47。

跳了过程可以用并查集优化,快速码了一个,11:51,发现自己 AK 了交不上去了!

最后 10 min 中,在狂躁之中度过,发现一点转机都没有,守到 12 点,唉声叹气地走了。

出来议论,发现一些人做出来 T1 了,连低一个年级的同学都有人做出来。可惜我没交上去(悲

但是大家似乎没做出来 T3,似乎随便写写,得了个暴力 + 部分分。赶紧去食堂吃饭了。

下午还得考试,又回到机房,12:28,了转反,考试延期了半个小时!

确认一下是不是真的,马上将自己的 T1 交了上去。不知道自己怎么样了呢。

水了一会,又去看各大 OJ 有没有测的,发现 InfOJ 可以测,但是已经排了 24 页的提交记录了

13:30 左右,lg 可以测了,发现 T1,T2,T3 都过了,心态很不错。看到 T2 有人说要取 size 最小的,没在意。

等到看到 InfOJ 可以测 T2 时,发现只有 Subtask 2 没过,连 Subtask 6 都过了,80 pts。我相信 CCF 的数据应该不强(flag

lg 加强了几次 T2 数据,结果随便就过了,不知道该相信哪边(事后看显然是 InfOJ

等 CCF 数据。

Day 4

看到 CCF 出了一个“成绩公示”,结果什么都是访问异常,啥也看不到。

看到有人说用另外的网址可以看到成绩,开幕雷击,一车人直接 AK 了!

发现 CCF 数据实在是强,直接 10 个点卡了我四个点,T2 直接 60 pts,和随机化寻找一个分了(我可是写挂了正解呀

$100 + 60 + 100 = 260$。

结果 lg 上一车人说数据过水,痛苦面具。水一点该多好啊,难得接近 AK 一次

总结

对于这种偏结论或乱搞的题目,感觉自己很多细节没有想清楚,这种东西赛时很难检查到,赛后后悔也来不及了。还是多做这种结论题吧。

还有,怎么没考 DP?一考大概率裂开。

等联合省选。