联合省选 2025 游记

· · 生活·游记

Day -5：

模拟赛，t1 是个需要点脑子的背包，t2 是个需要点脑子的回滚莫队，t3 是个非常困难的思维型 dp。

场切了 t1，t2；赛后发现 t2 是黑，t3 是 3500，第二次场切黑，好诶。

100 + 100 + 2

Day -3：

模拟赛，t1 是一个很 shi 的数学计数，写了 2h+，而且 10^{18} 还被数论分块艹过去了？？？

t2 是一个有些特殊性质的异或卷积，当时不会异或卷积，暴力分都没打，然后省选前学会了 FWT；然后 t3 是个维护凸包的困难 ds 题，弱化版之前做过，就是个紫的贪心/模拟费用流。

100 + 0 + 40

Day -1：

全真模拟赛，t1 放计数题，先打了个表，发现很多位置的贡献是相同的就做完了，貌似推 dp 的话有些复杂且不好想；t2 也是维护凸包的题，没学过，只打了暴力；t3 是一个很牛的加速模拟贪心，只打了暴力贪心的分。

100 + 0 + 42

Day 1：

离开考 20min 进考场，先打了下快读快输，然后敲了下 FWT，NTT 练练手（显然用不到）。

然后开题，没有通读，先只看了 T1，然后想一下怎么判一个数 x 的合法性，胡了一个 n^2 做法，大样例过了，然后换成树状数组就是 n \log n，后面发现我唐了，直接扫过去就行，复杂度是 O(N)，瓶颈是排序离散化（耗时 40min~50min）。

然后看 T2，不是，这个题面，很 lxl 啊；摸清题意后，感觉 DAG 可达性很难做啊，想了带修莫队，询问分块，一直想 \sqrt{n}, \sqrt{n} \log n；想了接近 1h 后依旧没想法，于是先写了下暴力，然后 AB 性质发现可以对于每个块跑一遍 topo 预处理答案，复杂度就是根号的。

目前 T2 已经 24pts 了，然后注意到了时间和空间开的很大啊，于是想到了 bitset 维护可达性，试了一下，发现开一个 \frac{n^2}{\omega} 需要 1.2GB；然后想到了使用线段树维护区间 [l, r] 的 a 对应的 i 的 bitset，与询问的做与，然后在线段树上二分 b；这样是 O(\frac{N^2}{\omega} \log N)，发现 6 \times 10^4 都要跑 10s，倒闭了。

卡常几个小时无果，荣获暴力分；然后就去开 T3 了，感觉不可做啊，不交或包含？写了暴力后就回去继续卡 T2 了。

100 + 24 + 8

赛后 T2 交流，有朋友结合随机化与根号分治跑过了大样例，非确定性算法太强了orz；还有朋友写了个 B 层线段树（就我傻傻的建了整棵），很牛啊。

然后发现 SC 初二全体 T3 都是 8pts，有点 6 了。

Day 2：

昨晚在卡 T2 的常，睡的晚了，提前 15min 进考场；这次学乖了，只打了快读快输。

开题，诶，这个 T1，怎么这么眼熟呢？？？等下，我好像看过原啊！那是不是贪心策略要复杂很多？瞎想了半天，还是决定开写，直接冲正解，耗时 1.5h，写了 4~5k，希望大样例强度强一点。

然后开 T2，感觉很不可做啊，状压后也不好转移啊，这个最小外向生成树是不是有啥性质？摸索半天，没有发现什么，于是去做 B 性质，发现合法的生成树数量只有 1 个，然后容斥初始的点，那么这些初始点两两之间路径上的边都必须是无向边（即虚树上的边），然后就可以算贡献了。

然后去向正解，先容斥初始点，然后发现还有再容斥一波生成树集合，这肯定倒闭完了，于是打算换个思路，可能是状压啥的，但是依旧不会转移，猜想每次加个耳可能有啥性质，手摸一下发现没有。

于是开始写 T2 的暴力，这比 B 性质可难写多了，写了 3k 调了下就得到了 24pts；然后开 T3，发现也非常不可做啊，打了暴力后思考了一下单增的性质，无果。。。

100 + 24 + 8

不是，怎么两天连分数构成都一样。

赛后，发现和大众分差不多，过于困难啊。

最后放下目前已经写好的 sol：

Day1T1 Day1T2 Day2T1