2025联合省选游记

wangif424 · 2025-03-01 22:47:30 · 生活·游记

前言

NOIP 只有 \dfrac{120}{272}\times40\approx17 分，假设省选有人 AK，那么想要进队需要本省至多 5 人大于我的分数加大约 106，希望约等于没有。

已经报名并通过了川大网络安全少年班初审，集主要精力准备校测，只在省选前一周抽空看看往年题和板子。

题外话

前年考号 SX-44，去年 SX-34，今年 SX-24。

Day 1

进场前

7:20 赶到了考点，发现自己是全场来的最早的，甚至比承办方来的还早。一个人在寒风中苦苦等待教练和同学，经赶来的监考老师提醒，发现室内还有座位,于是一个人在暖风中苦苦等待教练和同学……终于 7:50 人齐了，拍了两张合照后进场。

进场后

进考场，签名，草草看了眼考场名单，发现严格没有强于我的我是考场第一。

坐下开始打缺省源，调试快写时听监考老师宣读考场纪律：“正式开考前禁止操作鼠标和键盘”。笑话，我第三年省选了于是保存并关掉了 vscode，并在监考老师读完后重新打开 vscode 写快读（注意有伏笔）。

约 8:28 公布密码，比赛开始。

先看 T1，没思路，看 T2，没思路，看 T3，没思路，想 T1。

呵呵，计数题么，快快去请计数 dp 老祖隐居深山。不难看出，虽然是求中位数种类数，且值域较大，但我们只需要二分出最大和最小的中位数，在和所有 [l_{i,2},r_{i,2}] 的并取交并输出区间大小就做完了。

看 T2 不难想到 O(n^2) 做法。优化是简单的，我们考虑维护一个【数据删除】，在里面存【数据删除】和【数据删除】，在修改时【数据删除】，查询时先【数据删除】，再【数据删除】，最后【数据删除】一下就做完了。

最后的最后，我们要给“【数据删除】”内填上合适的算法等名词或动词，这是极难的。于是考虑小数据暴力，大数据乱搞：拿 bitset 可以存下邻接表，拓扑一下得到每个点能被哪些点到达，再用线段树维护 a 在某个区间时 b 的最大值，交换的时候就是线段树上两次操作，查询的时候我们取出 a\in[l,r] 的最值以及对应的点，并判断这个点能否被 x 到达，不能就标成零重新取即可。尝试运行大样例，发现代码 RE，然后发现自己快读在缓冲区满了以后只把缓冲区输出而忘记了清空，险些直接趋势（回收伏笔）。再次运行大样例，发现跑的极慢。于是这部分以 O(q\log n\sim qn^2log n) 的时间复杂度再暴力基础上多打了 \lim\limits_{h\to0}h 分。

时间线回到刚打完 T2 暴力。看 T3，尝试理解题意，没看到 a<b，提出了一个 O(n) 验证一个排列是否合法的算法好思路用在刀把上，在看清后重新考虑，发现自己只会爆搜。不甘心，尝试分析特殊性质。最弱的性质形如只有一条链，可以从两端入手，然后发现自己没手了，遂停止思考，并完成了上述 T2 乱搞。

估分：100+20+8，顶级大众分。

Day 2

进场前

今天选择进场前吃个早餐，但吃完早餐再赶到考点依然是全场来得最早的，再次在暖风中苦苦等待教练和同学。

突然有强烈欲望想看看 NTT，但手机没流量了，借同学手机看，快速看了一遍大致记下了写法。

进场后

先快速打了一遍 NTT，再打完了缺省源，特地检查了快写有没有问题。

先看 T1，没思路，看 T2，没思路，看 T3，没思路，想 T1。

想了半天，想到按时间做肯定最优，并且最后的总时间一定是距离和。A 可以直接统计总时间，B 正常做就行，C 的做法应该是半个正解。想不出来正解，打了个 O(n^2) 的暴力，拿下 60pts。