联合省选/GXOI 2025游寄

· · 生活·游记

前言

又幻想了，唉！幻想 GX 变成 OI 强省，坐拥 17 个省队名额，在 NOI 中拳打 ZJ，脚踢 CQ！

高二老登选手这辈子第一次去省选，也是最后一次去省选。

同年级的选手很多都已经 AFO 了，只有为数不多的同学还在为省选努力。

鉴于我的 NOIP 成绩相对没这么失败（在 GX 有前五了），考试策略的选择上比较保守一点，主要通过做出两天的 T1 来保证分数，并且尽量打暴力分。

不知道从哪里传出消息说今年省选评测姬要用 N100，想着像我这样人傻常数大的选手，要变成耐卡王了，还好最后实锤下来是 i5-11500，据说肥肠的快，这对我这种大常数选手十分甚至九分的友好了。

Day 0

因为我 Day -1 刚刚结束外地集训，坐飞机回来，所以变得很虚，上午 11 点钟才从床上爬起来。

在颓废了一整个下午之后，五点钟去考场试姬。考场在 nnez，我久仰贵校的大名，因为听说那里的键盘很难用。
试机的时候打了少量的板子，果然不失所望，一个小时的试机都让我的手指累趴下了。键盘的键程极其短而且触感拖泥带水，在薄膜键盘中也是属于最拉的，堪称赛博刑具。

Day 1

迷迷糊糊地到考场，干上一罐红牛来提神醒脑。

T1 应该比较签到。首先想了特殊性质 A 的做法。发现只需要逐个检查每一个 x\in[1,\max_{r_2}] 是否满可以成为中位数，并且使用双指针来扫描即可。因为实现的时候使用了优先队列，复杂度是 O(n\log n+\max_{r_2}) 的。实现并调试出来之后已经过去了一个多小时了。
然后考虑把这个东西推广到正解。把所有的 l_{i,2},r_{i,2} 放到区间 [1,\max_{r_2}] 的上面，发现点的数量是 O(n) 的，然后可以发现这些点将整个值域分割成 O(n) 个区间，然后就可以套用上面的特殊性质 A 的做法了，只需要使用双指针来检查一个区间里面的数是不是都可以成为中位数就可以了。写完 T1 耗时有 2.5h 了。

T2：我常常追忆过去。
神必题目，不会一点。打完暴力分跑路。

T3：打完暴力分跑路。

下午就颓废，刷 B 站，打 CODM，一点与 OI 有关的东西都没碰。

Day 2

T1 应该也是签到题。依旧是先考虑拿到部分分，尝试在 O(n^2) 的时间内解决这个问题：
因为 a,b 两个数组都是单调递增的，所以考虑一个贪心的策略：将物体按照 t 递增排序，每次移动还没有归位的 t 最小的那个物体，然后暴力的更新被它的移动影响到的其他物体的位置，使得所有物体都尽量少的进行移动。如果在移动某个物体的时候发现不能在给定的 t 之内把它和受它移动影响到的物体全部完成移动，那么就输出 No 并且返回；如果可以满足条件地移动所有的物体就输出 Yes。不难证明这个贪心是正确的。
然后考虑从部分分推到正解，即在 O(n\ poly(\log n)) 的时间复杂度内解决问题：容易发现当我们移动一个物体的时候，受到影响的物体都是连续的一段。如果我们要将一个物体向左边移动，那么就要移动它左边连续一段的物体（也有可能只移动它自己），向右边移动是同理的。需要移动的物体的范围可以使用二分来确定。对于修改，我们要先查询区间的范围和来计算需要移动的距离，然后将区间变成等差数列，表示移动之后的位置。使用线段树可以方便的维护这个东西，我写了 O(n\log^2n) 的做法，希望不要被卡常。使用线段树上的二分可以做到单 \log 但是我不会懒得写。
写完 T1 并且完成调试都用了 3h 了。然后发现二分的时候有一个问题，改过来又用了一点时间。

T2 和 T3 都是神秘题，拼尽全力只能打少量暴力分。

晚上就回校学 whk 了。

后记

这次省选打了两天的 T1 以及少量的暴力分。在 GX 虽然 200+ 已经算比较高的分了，但是感觉今年的省选，两天的 T1 都是比较大众的分，而且我这种菜鸡选手说不定还会四处挂分。还是希望能进省队吧，都高二了也只能放手一搏了。

今天有个群友问 D 菜鸡发生甚麽事了？原来打了一场联合省选，保龄了，原地 AFO，叕被嘲讽了。