联合省选 2025 游记

啊啊。从 WC 之后，到省选，发生了很多事情呢。按照矩阵群博客里面有的内容写一些吧。

总之超现实数系列更了第四篇，Nimber 相关学了个 CF 洛谷能用的 pclmulqdq 。

模拟赛补了一些题，补了去年省选 d2t1 和 d2t2，当然在补 d2t2 之前学习了 主旋律。把一直想做的 [ZJOI2019] 麻将 也 AC 了。

d1t3 听了 pmd 讲解会口胡了，不过 pmd 怎么是 $n\log ^7 n\log k$ 的。d1t2 虽然可能想去做但是心有余而力不足了。d2t3 这个序数理论能拿 $60$ 我就心满意足了，虽然去年挂分挂成了 $44$。

给 UCup Final 验题，获得了神秘的 I D K 三题。

前两天打了线段树合并板子，但是不会任何应用。

Day0 在打板子。FHQ、NTT、SAM。SAM 不会任何应用。

哈啊——（困）

终于又见到大家了呢，好开心。

在走廊上唱歌。在走廊上诵读 251 经典，CF2053 经典。pmd 在放白鸟过河滩，比较无敌。

实际上上面说的 NTT 就是试机的时候打的。NTT 是矩阵群试机时唯一会打的东西。

xst 说他 NOIP 可以打中文，遂询问，结果发现他也打不会了。于是开始考虑打什么英文歌词。

诶我不是背诵了 CF2053 经典吗。

/*
you are the beginning of the letter, the development of a poem, the end of a fairy tale.
-- ilem, pinky promise
*/

（试机的时候这里是两行 // 而不是 /*，但是 day1 day2 都是）

好像少了个 and。不管了。

经典试机有人打块。pmd 在打块的时候我放了《テトリス》。对你知道我要推歌了。

啊啊。你应当阅读 作为 OI 选手不可不知的编程操作注意事项（新手向）、OI 赛制比赛 emergency kit（2024 Winter Edition）。

原来可以直接进去敲模板来着。是不是到的越早越好了来着。

先整体看一遍题。T2 题目背景好好看。

进行一个 T1 的看。诶这答案是连续的吗。思考。连续个球啊，给定若干个 $a,b,c$ 答案还能在 $\{a,b,c\}$ 以外不成。那应该就要离散化考虑每个值域区间了。容易求出比它大的最多最少有多少，然后这个判定是容易的？那就做完了。写一下。怎么 $n=2\times10^5$ RE 了。开大数组。怎么最后一个大样例 WA 了。急急急。#define int long long。我开大了啊。fsanitize 测一遍。咋还真爆炸了。原来我离散化数组没开打，尬黑了。

这时大概一个小时过去了。还是来看看远方的 T2 和 T3 吧。T2 首先可达性就得 $nm/w$ 了吧，不过这个应该能跑，但是然后咋做我毫无头绪啊。AB 性质好像是容易的，按照 B 排序然后和 A 做个按位 and 就赢了。A 性质好像胡了个除以 $2^B+n/B$，但是其实好像要写 $n/w\cdot w/B$ 才方便一些。

先摆着没写去看 T3，连通到不连通的。但是我一开始以为树就是 dfs 序在瞎写然后发现我在干什么。然后拼尽全力无法战胜，先写个暴力 $8$ 分再去看看 T2 吧。写。不太会 find prev 状物，只好手写 bitset 了。测试点 $6$ 没有大样例，生气了，只好自己手造了一个小数据测。$13\sim 14$ 本机跑了 $6$ 秒不到，会赢吗。怎么没有 $15\sim 16$ 的大样例，不过 $10\sim 12$ 都跑了十几秒的说……

感觉有点炸，但是之后也没有获得更多分了。如此如此，如何如何。总之出考场的时候报的是 $100+24+8$。好像大家都很高啊，确实爆炸了。

之后听说 madoka T3 读错题了，唉唉。

之后云斗自测。自测一下发现我 T2 怎么爆炸（RE）了，但是 $13\sim 14$ 过了。诶我怎么清空 bitset 清空到了 N/8，啊啊啊？然后改了一下发现测试点 $6$ 还不太对，还没尝试搞懂。总之如果 $6,10\sim16$ 全部都用 A 性质的话就是洛谷 $52$ 云斗 $40$，现在可能变成 $20$ 或者 $28$ 状物。好像就算是这个分也挺低的，不管了。

给 pmd T3 战神磕一个。

唉应该听小青鱼的话（emergency kit）的：

这个是不是用 fsanitize 一查就发现了。不知道为什么考场上自测的时候完全没 RE。

听说凯文爆炸了，结果发现 xqw 说自己没测大样例但是那个是对的，那看起来还好。然后 T2 xqw 说云斗给他高了，不知道什么个情况，总是还是希望凯文能翻的。我这个 $136$ 状物就别想着翻盘了吧。还是只能 keeP*drEAm&iNg 了。

先看题。T2 计数，然后还是 DAG 容斥，T3 计数，会赢吗会赢吗会赢吗会赢吗会赢吗会赢吗会赢吗会赢吗。

T1 按照 $t$ 排序模拟一下贪心的过程是不是就对了。写了一下，等下推了之后相对位置还会变化的，得线段树维护区间和、$\min$、$\max$，啊啊哦哦，不过单 $\log$ 应该跑的飞快。大概半个小时过掉了。

T2 思考。总之 A 直接爆搜，B 考虑枚举这个唯一的生成树的根容斥即可。C 是要有外向生成树。等价于有一个点能达到所有点（最短路即可），等价于……等价于缩点后只有一个零度点！要不是群友之前在讨论 P11664 的难度评级我可能都不会意识到若 DAG 上除了起点每个点都有前驱则起点可以走到所有点，这个性质真牛。总之用主旋律推一下，最后容斥这个零度点。系数是 $(-1)^{c-1}c$，$c$ 为零度点数量，这个钦定一下第一个就好了。思考了一下能不能推广到整个题。思考 Kruskal。这也太难了。还是先把 $64$ 写掉吧。写写写。诶我怎么挂了。哦原来 pw2[i]=pw2[i-1]*i%mod2; 了。怎么还不对。原来式子推错了。$O(3^n)$ 过 $5$ 组 $n=15$ 还是很余裕的吧！

T3 先写了个搜子。怎么样例 $3$ 的答案这么小，会赢吗。尝试对着爆搜找规律无果。尝试刻画 AB 性质，哦我似乎有点头绪了。为啥小数据都和爆搜对上了但是大样例不对啊。哦原来我模数写错了，真遗憾。跑了一下 $18,70$，答案居然可以到 $6\times10^7$，测了一下发现一组数据爆搜都跑不过，难过了。好像没有时间继续做 A 性质了。

好像不太了解大家都多少分，不过感觉 $100+64+28=\boxed{192}$ 不算低了，毕竟 qzx 出来都在问有没有高中生大于 $200$ 的。凯文 $208$，比较牛。pmd 又成 T3 战胜了，真无敌。

晚上看了大家一下讨论发现我线段树二分没有写 pushdown 啊啊啊啊啊啊啊。这怎么过的。哦这题是不是有特殊性质。研究了一下，江户川·萝卜老师在群里说了一些很对的东西，lmh 老师私信我也说了一些很对的东西。不过我还没理解就是了，还是谢谢大家。拍了一下，大概是没问题的。

大家都在讨论 d1t3。怎么这么多人 d2 才发现 d1t3 读错了。等等我也只会八分不会我也读错了吧。还真是。

唉心情跌宕起伏。好像有一些翻 E 的风险。总之 ReM#Ain(LoVinG 吧。

我好像真的没读错 d1t3 题面啊，那我咋只会八分啊？

出分了，和自测一样的 day1 $100+28+8=\boxed{136}$，day2 $100+64+28=\boxed{192}$。

好像 ccf d1t2 数据造水了，真原神。

看起来还是有进 E 的希望的，不过不知道别人分数有多大变化了。

总之 rk14 极限进 E 哦哦。