【随笔】省选联考 2025 游记
Day -1
整天呆在机房,上午打了 nfls 最后一场省选模拟赛,三道题全都挂分了,下午补了题顺便看了眼 HBOI 出的模拟赛,T1 想到了一个 的乱搞做法但是 TLE 成了 分,加了一个根号分治的记忆化极限卡过了。
Day 0
上午 点整起来的,但还是很困,吃完饭就赶去火车站了,中途还把身份证落在出租车上了……到达上饶已经快六点了,吃完回到家就顺便看了一下自己的笔记,顺便刷了刷 LA 群,虽然这次比赛已经无所谓了但还是很紧张,大晚上的睡不着觉,差不多凌晨两点才完全入睡。
Day 1
睡了 个小时,起来有些神志不清了,去餐厅随便吃了点早饭(感觉完全没有怎么吃),徒步前往考场。到考场已经 左右了,随手发了条朋友圈,然后排队进入考场,当时到了一堆人啊。查完身份后坐到机位上,是非常舒服的看片位角落,而且我右边的人缺考了,非常好。
打开编辑器的那一瞬间就感觉不对劲,没错,这键盘延迟高的离谱,感觉不会打字了,把显示器刷新率调回 60Hz 后状况没有变好,不管这么多了,剩下十几分钟赶紧把缺省源打完。打到快输的时候开考了,通读了一下所有题目,T1 很好懂,感觉也可做。T2 逆天的时间限制和空间限制还有数据范围不禁让人浮想联翩,多刷 Ynoi 的第六感告诉我要么是 ds 要么 bitset 优化,果然后者被我猜对了(但没什么用),T3 感觉很不可做。
回到 T1,观察了一下性质 A 和 B,感觉性质 B 很直接,先考虑一下 A,再套一个离散化应该就行了。首先枚举中位数,然后判断是否合法。我冥冥之中口胡了几个结论,例如中位数个数尽可能多一定不劣,同时中位数前后的个数上下界可以分别确定了。
想到这里差不多了,但是当时有点神志不清了,暂时没有什么优美的做法,先写了 的暴力,然后挂了,然后 debug 发现这暴力假了但是也可以优化。不管了,先保证正确性,花了 min 乱搞出了一个绝妙的做法,把预处理和 check 的复杂度降为了 。
然后把一堆注释和 debug 删了,发现预处理就是一个前缀和和一个后缀和还有一个差分,直接线性(不知道当时怎么先写的 )关键在于 check 还是 的。
不管了,先套一个离散化,感觉知道是离散化的话很自然,因为性质很显然,这里没有什么阻碍。
然后发现 check 中在性质 B 的时候可以做到 的,以防万一我也写上了。
现在关键就是一个问题,知道一个中位数的个数和它前面后面所有数分别的总数上下界,判断是否合法。现在想想我真是唐完了,我先写了一个判断无解的,发现答案仍然偏大,然后我乱搞了一个枚举的做法,时间复杂度 ,已经能拿 了。然后我就跳了。
此时已经过半了,看 T2,看半天数据范围不知道是什么,然后根据之前的猜想试了一下大小为 的 bitset<100000>
数组,发现内存刚好差不多 GB,看起来确实可以维护 DAG 的可达性。
先写了 分的暴力,然后看性质,性质很多感觉高低得捞一点把,先写个可达性统计先。然后我又糖了,题目暗示本身就是一个 DAG,我没注意到,还写了一个 Tarjan 维护,代码变得又臭又长,不知道如何下手了。
盯着 A,B,C 性质看半天,最后选了一个 AC 性质的,要求每次询问可达路径中点数最大的,支持单点权值交换,但是想半天还是不会,最后写了一个特殊性质的暴力。
就剩一个半小时了,转过头去看 T3,T3 显然比 T2 不可做,打了一个 的 ,应该有吧。性质怎么跟树扯上关系的没有管,还以为 T2 性质更好拿,没想到 T3 有 更可做。
最后一小时看 T1,想了枚举二分啥的都不行,然后我突发奇想把所有本身不合法却判定错误的数据输出出来,才发现它们本身就不存在,加上一个特判就满分了。
直到最后都在想 T2,但是没结果,可惜了。拿了一个大众分:。
回去一直再刷 LA 群,T2 的解法杂七杂八的,有人还说 T3 在 nfls 有人搬过原题,当然我太菜了看都没看,唯一懊悔的就是没有及时看 T3 的特殊性质,很多人大众分 都是做了 T3 的部分分。
Day 2
睡眠质量略好于昨天,起的也比昨天早。但是早上没有去餐厅吃早饭,然后再次赶往考场。
自然地到的比昨天早,差不多半个小时的时间,闲得无聊默写了网络流和线段树的模板,还看了会昨天写的代码。
题面下发了,直接盯着第一题看,很显然的可以想到一个时间戳从小到大的一个贪心并且模拟即可。然后顺着思维写了一个 的做法,轮到每一个人就暴力检查所有人的位置是否合法。但是这份暴力我居然大样例挂了,调了大约半小时才发现整体平移写挂了。剩下来的事情大概就是将暴力筛查的时间复杂度降到线性以下。
这绝对是数据结构,而且暴力代码验证了一个人只会往一个方向移动,否则就无解。但是严格偏序的关系使得我要维护一个公差为 的等差数列,这不好用线段树或平衡树实现。然后我想到了珂朵莉树,我觉得 set
可以很好的维护这个连续段的关系,但是我当时没打算写(最后悔的一集),毕竟我珂朵莉树只写过 次。时间过去了将近两个小时,我隐约感觉这题能上紫,目前拿了 而且性质还没着手写,然后开始看 T2。
T2 显然的 NP 问题,有向图的生成树概念还是第一次听说,读题读了好久才想到一个暴力的思路。刚好给了较为富裕的 的 做法,我就无脑写了一个暴力,然后用 prim 算法每一个点跑一次,判断这个点是否是合法的,这样的话时间复杂度是 的,但是还是可以过的,就是写了非常的久。然后考虑特殊性质 B,性质也算比较好想,算是 MST 中的一个典型 trick,时间复杂度也刚好够,我直接在原来代码的基础上修正好了。写完后测了一些大样例,突然发现我第一部分的纯暴力写挂了,答案总是偏小,这大概率是算法的问题还是啥的,我看了半天代码没发现问题,直到出考场才直到我那一部分是 fake 的,然后这 小时就被耗费拿了 了。
最后仅剩 分钟,我的心态爆炸了,T1 的性质完全没来得及看,光速把 T3 题看完了瞄着纯暴力部分思考,显然用哈希数组即可,加上深搜暴力,时间复杂度我没算,反正就是 往上的级别了,通过样例后也没心情看回去 T1,整理了一下文件就交了。
然后这一天就唐完了,总分 ,最致命的还是被 T1 狠狠的区分了。
回去看 T1 解法,果然大多数人都写了 set
或者珂朵莉树,见过 trick 的线段树二分十分简单。有很多人写过这道题的原题,感觉还是强度不弱于的,出在去年十月的 ABC 里面,要是我那一场打了就可以秒了这一题的,况且这个权值减去下标将严格偏序关系弱化的 trick 我也见过。
晚上回到家中报复性玩了会游戏,直接把 GTA5 线下三个结局通了,很爽。
Day 3
今天去到学校,高一的已经回去上文化课了,我还留在机房等待老师给我下放,学了会数学的数列。然后想到昨天考试的 T1 越想越气,直接把那道题连带着原题给刷了,也算是 OI 生涯中的最后一道题了吧。