联合省选 2025 游记

试机，按照惯例试了一下 $2000$ 的 ULL Floyd，8s。

进场、发密码、看题。

看完 T1 感觉可能的中位数应该是一段连续区间，这样两个二分就做完了，至于 check，可以 $O(n)$ 计算最多有多少个 mid，比 mid 小的数和比 mid 大的数的个数差的最小值，简单判一下。

写写写，发现不对劲，这东西可能会把不存在的数算进答案里。

至少 check 的思路没问题，那就直接离散化把值域搞成 $O(n)$ 个区间，每个数能不能成为中位数只和它所属的区间有关，check 可以用一个扫描线和一堆树状数组做到总共 $O(n\log n)$。

T2 先写了一个 $O(nq)$ 暴力。

看一看，发现它时间 6s，空间 2G。算一算，发现 $10^{10}$ 个 bit 比 2G 小。

那就 bitset 处理能否到达。然后怎么做呢？看一眼部分分，AB 性质可以分块做，赶紧写了，拼上 $O(nq)$ 20pts，有测试点编号就是好写！

T3 根本不会！暴力只会 $O(Tn!m^2)$，算下来 $n \le 10$ 卡满都 $10^{10}$ 了，不太能过。

然后还是写上去了，发现样例跑得飞快，完全不像 $10^{10}$，不管了。

出考场，听说 T2 是根号重构，太强啦！但我怎么不会？

一看 T1 怎么这么熟悉？ABC 原题？线段树维护 $pos_i-i$，写几个线段树上二分和区间推平秒了。

第二个样例怎么错得离谱？哦原来还可以往前推的啊。往线段树里加了个区间最小值之后标记下传又错得离谱了，调了不知道多久后过样例了。

完全不拍！相信大样例！开 T2！

性质 A 纯暴力，先写了个 $O(4^m)$ 枚举边的存活状态，然后爆改 prim 再乘个 $O(n^2)$，一看怎么样例二第一组数据没过？$1280\rightarrow 1256$，重写了两遍还是不对，合理怀疑 prim 没正确性，直接枚举外向生成树的 $n-1$ 条边过了。

性质 B 生成树唯一，容斥枚举哪些点能够到达其他所有点，样例能过。

试图将性质 A 与性质 B 进行对拍，发现每棵树拍出来的答案都一样，猜测树的形态没有影响，不过容斥都写完了。

开 T3，暴搜启动！

还原了一下自己的 D1T1 和 D2T1，过洛谷民间数据了。

$100+24+8+100+24+8=264$。感觉还行。