联合省选 2025 游记

· · 生活·游记

求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。求求了不要挂分，不要卡常。

温馨提示：本文可能会有对做法的剧透，如果介意请勿观看。

Day -3 ~ 0

喜报：一共只做了一个题。

前一天晚上超级紧张，凌晨一点才睡着。六点就醒了。

Day 1

开考前不想看题，但是看 B 题面比较短就看了眼 B ，10^5 6s 加上可达性明摆着就是除以个 w 就做完了。然后就开考了，没细想，先去调配置。

过了五分钟，开始看 A 。感觉把区间离散化一下做完了，于是开写，需要注意一下偶数。在 9:00 时通过了所有样例。

中间有一个小插曲，我写出了 g++ a -o a.cpp ，然后 a.cpp 就消失了，但是由于我的 VSCode 开着，所以代码还在（

然后继续做 B 。看着 6G 空间，发现可以开的下 n^2 的 bitset ，然后想着修改可以直接根号重构，但是 n^2 的 bitset 不太好修改，就不管了。想着想感觉直接每 w 个询问一起做，暴力一下就好了，可以做到 O(\frac {mq}w) 。仔细思考一下，感觉全对，于是开写。大概 9:30 过了所有样例。

然而最后一个样例要跑 5s ，而且看上去还不太满。加了点剪枝跑到 4s 。但是还是能卡满，卡满可能就过不了了。但也不好说评测机效率如何，感觉应该有 [88,100] 。此时是 9:44 。

去看 C 了。在纸上写写画画，感觉树直接做，每个子树保留最小排列就好了。然后考虑森林，注意到了一些性质：

  1. 每个连通块只要保留最小的，且最小排列一定以最小值开头。
  2. 输出答案可以直接每次取最小的，如果在一个连通块中间插入更优就插入，递归。

这样森林就做完了。感觉此时大概是 10:30 。

然后，当时我感觉没有获得非平凡分数，就先没写代码，继续往下想。我注意到一个排列是合法的，那么转一下也合法，所以总是能以最小值为第一位。以最小值为根 dfs ，发现去掉根的每个连通块都是一条链，注意到割点总是在链上，直接递归做即可。可以得到一个 O(n^2) 做法。

感觉很难写，写的很折磨。先写的树。12:30 的时候终于过了样例（甚至过了最后一个样例）。然后做了一些简单的检查工作，就结束了。

最终估分 100+[88,100]+72 。

我擦，怎么 B 满足 u<v ？那我岂不是虚空多了一些常数？有点要命，给我糖完了。

Day 2

从昨天 12 点睡到了 7 点，但是感觉比昨天困，怎么会是呢？

注意到：我是 ZJ-002 ，左边是 Nz ，右边是 fsz ，有点吓人。其实座位是不变的，昨天我也注意到了，但是昨天没啥感觉，今天不知道为什么隔一段时间就想起来一下，太恐怖了。

快进到 8:30 。先看 A 。一眼按 t 排序，然后一路推过去，但是感觉维护很麻烦。一开始想用 set 维护连续段，但是写了下感觉非常麻烦。写到一半突然发现可以直接线段树，于是换成了线段树。直接对 a_i-i 区间覆盖即可。过了样例大概是 9:15 。

然后看 B 感觉很可做，就开始做 B 。9:45 大概会了 C 性质，然后想了一下正解，发现 C 性质假了。想的是枚举集合 S 表示让恰好 S 能到其他所有点，然后考虑 S 内部强连通的概率以及 S 能到 U 的概率（ U 指全集），是 S 到 U 的概率算重了。

发现 S 到全集的概率，可以用 1 减去不合法的概率，不合法等价于存在集合 T 满足 U\backslash T 连通，且不存在 U\backslash T 到 T 的连边，可以 O(3^n) DP 了。直接枚举每个集合做是 O(4^n) 的，可以把贡献一起算，做到 O(3^n) 。写了下发现全对。中间有个很糖的事情是，调半天坚信是写挂了，结果发现模数写错了。

然后感觉搞个倒推就做完了。但是怎么搞不出来啊？

换了个思路，发现 DAG 上一个点 u 能到所有点等价于 u 是唯一的无入度点。那么直接枚举其他无入度强连通分量就做完了，不需要 DP ，还可以复用求强连通时的辅助数组。

然后就想冲 100 ，但感觉有一些很麻烦的地方。用力想，但是一直感觉做不明白。在 11:00 的时候，我做了个决定：如果十分钟内没想出来就去拼暴力以及开 C 。结果是感觉会了，于是赶紧开写。

写写写，但一直有个小数据过不去：

3 2
1 2 1
2 3 2

写到 12:00 还没过样例，非常紧张。于是先看 C 。看了一会儿感觉啥都不会，但是发现答案是 O(2^nnm) 级别的，于是准备写个暴搜跑路。写完后发现能 1.5s 过第二个和第三个样例？于是把 unordered_map 换成了手写哈希表，只要 1.1s 。感觉能有 32 。

继续看 B 。发现小数据是没有统计到 S=\{1\} 的情况，然后发现是只考虑了有用点之间的连边，稍微改了改就过了。复杂度是 O(n3^n) ，测了 T=5,n=15 的大样例跑了 1.1s ，但是 n=14 跑了 1.7s ？此时大概是 12:44 ，没想到怎么优化时间，于是开摆。

然后看了眼 C ，造了组 50,51,\dots,67 ，发现一组数据跑了 10s 没跑完？感觉只剩 8 分了，开摆。

剩下的时间做了一些平凡的检查。没有改代码。

最终估分 100+[92,100]+8 。

出来听别人说 A 大样例很水？？？然后我没拍？？？我岂不是完蛋了？？？

感觉心态炸了。

晚上的时候发现 B 对每个连通块做就是 O(3^n) 了，这个我赛时写之前想到了，但是后面忘了，有点难过。但当时时间也不太够了，可能会了也没用了。

后记

正在等成绩。正处于害怕挂分的恐惧中。

UPD：没挂！没被卡常！甚至 D2T3 不知道为什么多了 3 分。

最终得分：100+100+72+100+100+12=484 。

疑似是 ZJ A1 ，无敌了。