联合省选 2026 游记

qifan_maker · 2026-03-09 21:33:27 · 生活·游记

前情提要：NOIP 三倍队线，要翻 80\text{pts}，详见 NOIP 2025 游记。

2.22～3.1

在 fdu 集训，食堂吃不太惯，发现大家都觉得难吃，看来不是我的问题！

上课听不懂，断断续续的听一会就会掉线，不过云浅和多头上课都很牛！模拟赛被肘飞了。

3.1～3.6

回学校了，停课。

发现自己 DP 又烂完了，于是训了五天 DP。

思考了一下，翻盘需要两天都高于 \text{100pts}，因此策略是 all in T1。

Day 1

宿舍的床睡得腰痛，\text{6:40} 起床，吃完饭 \text{7:10} 前往 jxnu，\text{8:00} 到了考场楼下，等了会 gb_lw，\text{8:20} 进了考场，怎么坐在 xzy_AK_IOI 正前方。

状态烂完了，大概是本就没有翻盘的实力，也没有翻盘的希望吧。

T1 怎么是期望，完全不懂啊，研究了一会似乎搞懂了，把性质 A 送的 \text{8pts} 先拿了。我怎么读不懂这题是啥意思，选择重儿子的概率是按照重链长度期望还是按照重链剖分实际长度啊，怎么样例解释只给了第一个，手玩了一下样例二发现玩不出来，那姑且认为是前者吧，但是这玩意不是 \mathcal O(n) 的吗，不过对于各个子树的期望并不好存储，可能这是一道模拟题吧，欸怎么 \text{11:00} 了，先跳了。

T2 是串串题，不想看，先跳。

T3 看着挺有意思，观察了一下数据范围，发现 \text{Task 1,2,3} 都是送的，写完思考 \text{Task 4,5,6}，猜了一个当 m=2 时，b 一定由 a 的某个子串异或值及其补集异或值构成的结论，手玩了一下发现很有道理，写完调了一会过了样例。

烂完了，问了一圈大家都暴力打满了。晚上回机房写不动题了，打了会 Celeste。

Day 2

由于已经没救了，心态好了很多，策略是打满暴力。

我草怎么有交互题，怎么还是函数式交互，研究了一下，似乎懂了，不敢写 using namespace std;，怎么首页写了 io 文件名题目里又说标准 io，要不要 freopen 来着。

这个 T1 感觉典完了，想了一个 \mathcal O(n \log n) 的二分做法，先二分找 0，再向两边二分扩展，写着写着发现可以优化到 \mathcal O(n)，考虑二分找到当前值位置后，由于小于该区间 mex 值一定在区间内，于是存储没有填写的位置，在求出更大区间 mex 后填写即可，过了 n\le 100 的样例，手搓了一个 n=3\times 10^4 的数据，怎么跑不出来，为啥 \mathcal O(n) 过不了 3e4？？查了 \text{20min} 才反应过来是交互库卡住了，跳过交互库输出结果发现在数值连续的情况下会被卡到只有 25\% 的分，决定乱搞一下，记录每一次二分结果的距离，取平均值作为下一次结果的预测，先以该预测进行一次二分，做了到查询 90000 次左右，发现会有重复询问，于是用一个 map 存储询问结果，优化到了 30013 次，多了一个找 0 的 \log，可以获得 75\% 的分数，D2T1 [80,90] 知足了！赛时没想到过 D2T1 会小于 D1T1。

gb_lw 过了 T1，膜拜。晚上依旧 Celeste。

总结