SCOI 2025

· · 生活·游记

苟进前十二就算胜利。

Day 1 / 2025.03.01

开考。打开 T1，好像是弱智题，离散化下暴力做就好了。先写个平方，怎么过不了样例。原来是 a 和 b 看反了，swap 一下就好了。改成 O(n \log n)，通过样例，现在 8:52，优势在我。

开 T2，怎么一脸不可做。冷静一下，原来不弱于 DAG 可达性，还真不可做。开始想 \frac{1}{w} 做法。编了半天取得一个 O(\frac{nm}{w}+\frac{nq \log w}{w}) 做法，直接开写。怎么跑的这么慢。卡会常，最后一个样例跑进六秒了，实际评测机应该比考场优秀吧，现在十点多，优势在我。

开 T3，看起来比虫洞可做多了，直接开做，感受了一下 K_4 无解啊，那是不是广义串并联图题。思考一下，完全不知道咋用广义串并联做。流泪了。过了会开始看部分分，树好像是弱智，写了一发成功通过大样例。然后继续回去做连通图，做了一万年完全不会。12:00 的时候又看了眼部分分，这个森林是不是弱智啊？写了个平方试试，怎么过大样例了。冷静了一下改成了 O(n \log n) 的。然后继续瞪连通图，完全不会。

出考场，原来实际评测机比考场机子慢？？？？？是不是完蛋了。

期望得分：100+[44,100]+52=[196,252]。

回到酒店，糊了个新 11.5 983，不推了。

Day 2 / 2025.03.02

开考前拿到下发包，后面两个题怎么样例都这么小，尤其是这个 years，不会又是 n \le 15 状压题吧。

打开题，怎么还真是。看了下 T1，瞎编了个贪心，发现直接 set 维护连续段就可以 O(n\log n)，但是这也太难写了，我选择写更好写的线段树 O(n \log V) 做法。直接自信开写，写完测大样例，怎么一组就要跑 0.5s。开始紧急卡常，根本卡不过去，一看已经开考两小时了，弃掉开 T2。

不懂啊，怎么感觉这个看着很 DAG 容斥。但是去年考过了，今年应该不会再考了吧，还是想点别的有道理做法。然后我怎么啥都想不到，火大了，写个 24 分暴力开 T3。

这是啥东西，完全不会，先写个爆搜，然后随便编一下单调递增的情况，可以拿 28，还不错，比最长待机良心多了。

还是再看看 T2 吧，看看特殊性质，感觉还是得 DAG 容斥啊！先跑个主旋律，然后缩完点之后就是要统计一个 SCC 能到达剩下所有点的方案数，这咋统计啊？想了一万年不会。

回去接着卡 T1，怎么完全卡不过去？遂红温，最后半小时一直在盯着电脑屏幕火大。

出考场，原来全世界都把 T1 过了。原来 T2 那个限制等价于存在恰好一个零入度 SCC 所以直接容斥就做完了。原来 T1 的样例超级弱。唉不是哥们，啊？这是啥？

期望得分：80+24+28=132。

睡觉并祈祷别给我挂出省队了。

Day ? / 2025.03.06