联合省选2026游记

· · 生活·游记

Day0

试机。

比起上次省选，这次认识的人就多了很多。

试机写了个对比大样例的 checker，测了下机子速度，多快忘了，反正感觉不是很慢。

Day1

到场写了个用来对比大样例 checker，打算写个对拍器不过写到一半开始了。

看一眼，三个传统题，T1 期望，T2 字符串，T3 神秘题，先看 T1。

发现 T1 期望可以拆到每一条边上，只要能求出每条边在链上的概率就行了。

发现这玩意似乎可以 dp，使用可删背包好像就做完了。

认真分析了一下发现时间是 O(n^2) 的，那还行，直接开写。

写了 30 min 突然发现这个背包好像并不是很好删，倒闭了。

思考了一会儿发现这玩意可以看成多项式，把 x 的项提出来就可删了。

调了一会儿过大样例了，但是大样例跑了 1.6s，先扔了，此时过去了 1 h 感觉还行。

T2 是个字符串题，追忆起我被 csp-s T3 创死的经历，不过这题看起来也不是很字符串（？）。

答案长度不超过 15 的直接暴力枚举就行了，先来手玩一下全 0 的。

发现答案是一个关于 0 的连续段的式子，直接 dp 就行。

手玩一下 1 的，发现需要记录前面有多少个后面 1 数量小于 n 的。

突然发现这玩意好像相当于记录前面确定比它小的有多少个，然后比它大的肯定不用管，和它相同的一定是公共前后缀。

这个直接用 dp 维护一下，发现比它大的只会有 O(\sqrt k) 个，那直接 dp 是 O(kn\sqrt n) 大常数的。观察发现 dp 转移可能会有环，手玩一下感觉跑两遍就行了。

先写一下，调了一会儿发现输出的答案都是对的。

dp 回溯感觉有点困难，不过想到了一种只需要将原 dp 倒过来跑一遍的回溯，写一下，感觉应该是过了，不过怎么没有 checker，大样例跑了 3.8s，不知道 ccf 机子速度如何，蓝的写 checker 了，先做做 T3。

T3 感觉很困难，先看看特殊性质。

发现 T3 应该会暴力，m=1 直接看异或总和就行了，m=2 似乎有点困难（？）。

推+假+修了 2h 终于写完了 24 分，而且还跑得有点慢，此时只剩 eps min，T1 也没时间卡常，T2 也没有 check 答案正确性，感觉给我打倒闭了。

认为难度是蓝紫黑，出场发现似乎并非。

Day2

打了个 checker 就蓝的干其他的了。

开题，发现 T1 是交互，先看 T1。

发现可以二分出 1 的位置，然后向左右拓展是不是就做完了，这样是 2n+\log n，怎么给了 6 \times 10^5 次？

仔细一看发现并非，需要 n 次才能拿到满分。

思考一下发现只会优化成 1.5n+\log n 的，感觉和正解完全没关系。

发现 mex 的区间如果比较小的话感觉信息量也是比较小的。

开始考虑删去元素，发现可以删开头来得知开头的值，但是似乎不能拓展到后面（？）。

继续思考了一下发现好像需要知道的是一个到 0 单调递减，后面单调递增的东西。

写了一下过大样例了，此时已经过去 1 h 30 min 了，但感觉这题不是很简单，那还行。

然后开 T2，怎么是神秘构造，手玩一下突然发现是线性基，不过大数据跑不过去。

想了一会儿毫无头绪，先看看 T3，这是啥防 AK 题，烧烤发现只会 eps 分。

还是回来想 T2，先写一个线性基吧，此时还剩 2.5h。

写+调 1 h 后：

我去这玩意不能用线性基求。

赶紧回来想 n\le 18，怎么完全不会？？？

看看 k=3 的特殊性质，手玩手玩手玩，发现是奇偶性，对于两条相交的反边取反该三角形就行，写完还剩 50 min。

回来看看 T3，写一下菊花，直接随便搞搞，过样例了，还剩 15 min，感觉已经倒闭了。

检查了一下文件就准备结束了。

还剩 10 min 时加了 15min 的时，突然感觉又能写一下 T3 n,m\le 10 了，速写，还剩 5 min 时测完了样例。

就是这样了。

出场发现 Day2 打得实在太差了。

以及 D2T1 的边界我判的是错的（恼）。

如果不挂分的话是 280+224+124，不过肯定会挂，除非我 D1T1 没有漏取模，没有被卡常，D1T2 构造的是正确的且没有被卡常，D2T1 肯定会被卡，只能希望卡少点，D2T2 和 D2T3 极限写的是对的。

期望的话应该是 280+160+54。

希望至少能进 D 吧。