联合省选 2025 游记

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

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

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

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

开考前不想看题，但是看 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 了。在纸上写写画画，感觉树直接做，每个子树保留最小排列就好了。然后考虑森林，注意到了一些性质：

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

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

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

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

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

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

注意到：我是 ZJ-002 ，左边是 N_z_ ，右边是 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 ，无敌了。