联合省选2025游记

· · 生活·游记

希望大家一直记得我

“希望大家永远忘了我”

老年OIer最后一次省选，由于noip抽象发挥必不可能进队，目标省选上个队线挽回一下颜面。

Day ?~998244351

教练找 MX 买了一堆高质量模拟赛，一天一场，原题到处搬，一半以上可以在 gym 上找到，最离谱的一天拿了三个 EC Final2022。最后一周更是抽象每天三个签到基本每天AK（除去挂分），打成信心赛了属于是。

Day 998244352

最后两天没模拟赛，早上写了前两年NOI D2T2，下午打了湖北省选模拟的luogu同步赛，A题想了1.5h polylog 不会然后同学说可以 O(n\sqrt{n\log n}) 然后想了一下就会了随便写了一下过了。

B题发现大样例答案不大然后胡了一个根据 height 数组大到小扫描线然后发现不会维护但是感觉暴力跳分应该不低。最后懒得写。

C题发现可以类似最大独立集做dp，然后就胡了个枚举根 O(n^2m) 的然后感觉可以换根 dp 做到 O(nm) 发现不会，问了一下 lzk 说枚举最大值不要把最大值放在状态里就可以换根 dp 了，感觉我是唐诗。

然后才 100+0+25，甚至打不过 OpenAI_Agent 的三个暴力加起来，成功倒闭。

如此状态，如何省选？？？

Day0

早上教练叫我们要来学校，下午出发去福州。

zbr 车上突然收到他妈妈的消息说他身份证在他妈那里，然后临时又赶来给他身份证，主播人还是太有实力了。

晚上一起去吃饭然后那家店把我和 cjr 的面给漏了，别人都吃完了我们还没上，然后店里面送了两盘小菜。

回酒店后玩血染钟楼然后被 hbh 整天针对我，很没有体验感。

Day1

8:22才到机房，密码都下发了，疑似全机房最晚进场。

考场 vscode 居然配置好了c++扩展，有自动补全和动态编译，爽。

由于 WC 题目没按难度排序，担心有坑就先看了一样发现题目不是按字典序排序，但是发现 B 题 6s,2G，意识到了不对劲。

先看了一眼题目看 A 题给出每个二元组的值和个数的取值区间，然后求中位数的可能值有多少个，感觉是冰冰题。想了 10s 发现区间如果包含当前要判断的中位数一定取这个值并且个数取到最大，那么可以扫描线判断 x 是否能成为答案，把区间分为最大取值小于 x 的，能包含 x 的和最小取值大于 x 的，设这三种区间的数的个数的个数区间分别为 [L_1,R_1]，[L_2,R_2]，[L_3,R_3]，中间的区间直接取到 R_2 最大，猜了个贪心就是只需要判前后两个区间取到端点是的情况，写完发现大样例没过，然后退了一下式子，假设枚举了小于，等于，大于 x 的数分别有 a,b,c 个，那么当且仅当 a < \lfloor \frac{a+b+c+1}{2} \rfloor 且 a+b \ge \lfloor \frac{a+b+c+1}{2} \rfloor 时中位数是 x，首先 b = R_2 最优，不妨设 a 为已知量，拆掉下取整后可以得到 a-b < c+1 \le a+b，于是就可以二分（其实有点像三分） a，然后判一下是否有满足条件的 c。然后由于我们刚开始把下取整去掉了，所以最后再枚举一下 a 加减常数判一下，然后就过大样例了，这时大概 9:40。复杂度 O(Tn\log n)。

看 B 题，题目背景看起来写的很有文采，然而我连第一句话都没耐心看完就直接看题目描述了。

首先有向图可达性上的问题疑似不太能 polylog，由于空间 2G 算了一下 10^{10} 的 bitset 空间大概是 1G 多，想了 10min 没什么思路，由于自己 ds 水平确实不高，觉得应该不太做得出来这题就去看 C 了。

C 的题意大概是给一张无向图，要求一个字典序最小的排列，然后对于无向图每条边 (u,v)，排列上 u 和 v 对应位置的区间只有包含关系，没有相交关系。

看完题感觉没什么思路，就先打了 n! 的暴力，然后担心暴力跑不过就把判区间相交写了个扫描线的 O(m) check，调了 20min 发现假的离谱，于是改成 O(m^2) 由于答案字典序比较小所以跑得飞快，浪费了好多时间 \fn。

然后看了一下特殊性质，发现链有 4 分，以为是像 noip T3 输出 1 那种送的，然后开始猜答案可能是 1,2,3,...,n 打开大样例发现不是，但是由于只给 4 分于是我感觉链一定是唐诗东西，想了半小时还不太会，有点破防，4分都不会。然后拿我的暴力开始打表找规律，发现答案是从 1 开始，然后找到子树内中最小的那个点，直接跳过去，直到叶子节点，再一直返祖回到 1，如果 1 还有一个儿子就继续跳过去。然后就开始写，写了不知道多久写过了链的大样例。稍微去证明了一下这个贪心发现了一些结论，首先一棵子树在排列上肯定是连续的一段，不然会有交，其次就是每个节点和它所有儿子的子树构成的区间的整体是可以随意排序的，直接贪心搞就行，然后疑似就会树了，由于担心写挂就又加了一个 namespace Sub3，调了一会儿就调出来了树，然后发现森林直接弄一个类似归并的操作就行了，又加了一个 namespace Sub4，很快也调出来了，疑似写了350行，全是复制粘贴而且实现比较唐，然后就有了 52 分，这时大概 11:40。

尝试想了一下 C 的正解发现没什么思路，就回去写 B 了。

先把 O(n^2) 写了，然后对着每一个特殊性质想，发现没一个会的，然后就开始想乱搞，什么强连通分量缩点完减小图的规模后再暴力，根据操作的修改次数多还是查询次数多分讨啥的，然后测了一下大样例发现跑了几十秒后程序自动 RE 了，最后一个数只输出了前一两个数字，没搞懂为什么，然后感觉这么乱搞应该也没什么用，最后交了最朴素的 O(n^2) 代码上去，喜提 20 分。

估分是 100+20+52 = 172，寄了。

出来后发现所有人都过了 A，lck说 B 是什么分块后操作分块还要bitset维护连通性，O(\frac{n^2}{w}+n\sqrt{n})，不太听懂的样子。

根 minilong 一起喷了半天 B 题出根号数据结构，然后听说卡常一下 O(n^2) 能过 6\times10^4，被幽默到了。

感觉大家 A 题做法完全不同？

下午继续玩血染钟楼，晚上玩平板，然后 22:00 多就睡觉了。

Day2

今天早到了一些，坐到位置上之后才发密码（

看 A 题，推箱子，感觉是我喜欢的贪心题，B 跟去年一样出了个图论状压计数（连续两年出这东西？？？），C还是神秘计数，作为数数飞舞感觉要寄。

先想 A 的暴力怎么做，首先显然的是按照 t 排序后一个一个推箱子，遇到障碍就一起推，直接暴力往 b_i 的方向扫就行了，然后花了 10min 写完了暴力，稍微调了 2min 过了所有样例，而且跑得挺快？

然后考虑这个操作本质是什么，无非就是把 x 从 a_x 到 b_x 路径上的所有障碍一起移，不妨设 a_x < b_x，需要移动的箱子的数量为 cnt，无非就是把这些箱子移到分别移到 b_x,b_x+1,b_x+2,...,b_x+cnt-1 的位置于是可以二分 cnt，check 一下在 [a_x,,b_x+cnt-1] 的数的个数和 cnt 的大小关系，然后就是一个区间一次函数赋值，直接上 FHQ check 就是把这个区间 split 出来查询 siz，区间赋一次函数也先把区间 split 出来，令标记 tag 表示这个区间最小的元素要改成 tag，push_down 左儿子下传然后右儿子加上左边的 siz 再下传就行，区间权值和就是 (tag+tag+siz-1)\times siz/2。写一半发现由于 a_x 始终保持递增，所以直接上线段树维护就行了，然后改成线段树，发现非常好写，根平衡树的不同之处就是二分可以改成判断 a_{x+mid} 与 b_x+mid-1，写完发现没大样例，刚好可以拿暴力对拍一下每个值的输出，发现是区间赋一次函数的时候往右儿子走的时候弄错了，发现可以直接改成

if(ql <= l && r <= qr) return change(rt,d+l-ql);

然后下面就没什么细节了，于是在大概 9:10 通过了这题的大样例，发现可以把二分放到线段树上变成 1log 但是由于本地大样例只跑了 0.22s 感觉能过就没管。

看了一下 B 题，发现没有任何思路，然后开始想暴力，发现枚举完图之后不会 check，然后想性质 B，发现边都是固定的，想了几个容斥疑似全假了，因为没打暴力不方便调，于是先去看 C。

C 又是什么神秘方案计数，先写了个爆搜，用 map 判重复，拿了 8 分，然后看 n \le 18，感觉不是多项式复杂度的东西，然后看了一下样例三发现答案不是很大，推了一下发现答案应该是 O(nm2^n) 量级，然后把 map 换成 umap+哈希，卡到了 1.4s，本来想把 umap 换成 gp_hashtable，但是忘了头文件，然后就没管了。

想了一下性质 B，发现操作相当于只有一个类似循环位移和删除一些数，貌似只需要对差分来计数就行了。想了一下发现不太会写，权衡了一下决定回去写 B 题，

然后就开始写 B 的超级暴力，写完胡了好几个 check 都假了，甚至写出了什么有向图 prim 算法，想了一堆贪心，一看时间只剩半小时了，于是想出了一个先枚举根，然后给每个点暴力枚举一条边作为连向父亲的边，然后再 check，然后写完还是没过第二个样例第一个点，12:58 发现我连边判环写错了，然后因为没什么时间就改成了跳 fa 跳超过 n 次就是有环，然后过了这个点，然后只剩一分钟没时间测别的地方只能稍微检查一下文件名就离场了。

预估是 100+12+32 = 144，然后有人跟我说 C 题那个大样例挺弱的实现不好的暴力能卡，于是 C 题变成了随机分数。

问了一下 B 的暴力怎么写结果说是状压 dp，发现我是唐诗，想了半天poly复杂度做法，去年D2T2也是对着特殊性质想poly复杂度，没吸取教训。

好像除了 cjr 大家都会 A，whc 说他两只 log 要跑四五秒？可能要寄。

晚上看到云斗的估分，day1 没挂分，day2挂成了 100+0+8，day1 T2 过了一大堆，day1 队线都上 200 了，两天分数加起来 FJ 排 rk25，打不过。

Day3~inf

最后是 100+20+52+100+0+8=280 两天总分高中 rk21 显然无法进队。

算了一下如果 noip 没炸正常发挥 332 的话可以以 0.03 分标准分的微弱优势进到 rk14。

也曾幻想 noip 没有看错题目死磕，幻想场上能想到值域分块，幻想 day2 能不降智意识到 check 不一定要poly算法。

可惜我们不能重塑时光，我们只能追忆过去。

后希望我的朋友们进队的都能 Au，还有机会的明年都能进队，退役读文化课都能成为文化课高手。

也许路上布满荆棘，但是我们都有璀璨的未来。