联合省选 2025 游记

lzm0107 · 2025-02-28 18:31:19 · 生活·游记

试机，按照惯例试了一下 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，过洛谷民间数据了。

> **D1T2 $O(nq)$ 有 88pts？**