联合省选 2025 & NOI2025 谢幕记

cyffff · 2025-07-16 21:57:11 · 生活·游记

联合省选 2025

最后一次省选。

NOIP 低于队线，省选能翻盘吗？

Day 1

A 是简单题，写写写。

B 我草是 DAG 可达点对，难道是时间分块 bitset。然而没能坚持这个想法，转而写了个 O(\dfrac{nq}{\log n}) 的四毛子，怎么只有 44 分。

先看 C 吧，这个树不是送分吗，这个森林不也是送分吗，获得 52 分。

剩下的 1h 时间怎么开始乱调块长发呆了。估分 100+44+52=196。

Day 2

A 是简单题，写写写。

B 我草是 DAG 图计数。花了很长时间写暴力然而只过了 AB 性质，C 性质凑了一个 (-1)^{i}\cdot i 的容斥系数但 DP 始终调不出来。

C 完全没有思路。

最终 100+24+8=132 遗憾离场。

Day ?

彻夜难眠。

Day ??

出分了，30\cdot 340/400+70\cdot (200+132)/448=77.375，队线外第三名。

在教练的支持下以退役选手身份加训了两个月，终于等到了 C 的消息。

NOI 2025

第一次也是最后一次参加 NOI。

Day -6

UNR Day1，完完全全被打爆了。信心被击碎，躲在厕所里哭了十分钟。

经过漫长的调整，接受了 Ag 的展开，毕竟日常的训练就比较放松。付出越多，收获越多，既然没有选择超额付出，就不要期待过多收获。

Day -5

UNR Day2，1h 过了 A，感觉找回了一点信心。

Day -4/-3/-2

几天来心态一直在反复横跳，打完最后三场模拟赛，离开机房时又有几分惆怅呢。

Day -1/0

报到，和同学校的三位选手住一起。笔试没出差错。随机打板子。

根据近年 NOI 的部分分情况制定了目标，D1T3 和 D2T3 必须做且需要拿到 \sim50 的分数，两天总分预期要 \ge 250,\ge 200。

Day 1

紧张地坐了二十分钟。开题。

？这个 A 是能出现在 NOI 的题？20min 过掉了。

做 B，发现考虑 \to x\gets 这样的结构可以 O(n^2\log n) 做掉第一问，但是在有 \gets\to 这样的结构时会算重，可以过随机数据，做了 60min 获得 61 分。

这时打算先弃掉 B 做 C 去，直接考虑多项式级别做法，考虑性质 A，发现对于一个左子树内的点 x，若确定了其先走左儿子还是右儿子，那么右子树中有一些点 y 的选择也被相应地固定住，其中 x,y 的左右子树分别有交。用并查集处理，由于保证有解，答案就是 2 的连通块数次方。

再考虑无特殊性质的情况，若 p 的子树内有颜色需要合并，那么它们必须靠在中间，同时比特殊性质 A 多的情况是会有还未合并的颜色干扰合并，则如果有一个点 x 的两个子树内分别有需要合并的颜色以及还未合并的颜色，那么 x,p 也会互相固定。

每加入一个颜色便枚举路径上的点对进行更新即可，时间复杂度 O(\sum \text{dis}^2(x,y))，用时 140min 获得 80 分的高分！

回过头补了 B 的爆搜以及性质 A，获得 73 分。

剩余 1h 随便检查了一下，忘记写 B 的高复杂度多项式做法了（

总分 100+73+80=253，自我感觉相当不错。出考场发现 GD 选手很多都 280 了，意料之内。

查分没有变化。

Day 1.5

玩玩玩睡睡睡。希望 Day2 不要出交互/字符串。

Day 2

紧张地坐了二十分钟。开题。

？开幕大分讨，讨论了半个小时找 11,11\dots0,101 并在 70min 时通过 A。

然后做 B，容斥一下，对于每一位钦定是否属于 P,Q 的交，系数分别为 1,-1,-1,2，然后扫一遍每个数计算贡献，时间复杂度 O(8^n)。扫的时候只用枚举包含 P,Q 交的数，时间复杂度变为 O(7^n) 不过仍然是 16 分。

做了 60min 还是没有进展，故暂时放弃。

做 C，考虑判断一个 k 的合法性，扫过 k+2i，则要求这段内进行特殊操作的次数 f_i 需要满足 f_i\in[i-c_1,c_0-i]，同时 f_{i-1}\le f_{i}\le f_{\max(i-3,0)}+1，维护 f_i 的取值区间即可，时间复杂度 O(nq\log n)，获得 40 分，花费 50min。

回去做 B，发现将上面的容斥描述为选取 \{0,1,\dots,n-1\} 的三个不交子集 A,B,C，式子就变为了 (-1)^{|A|+|B|}2^{|C|}\prod(1+[A\sube S][C\sube S]a_s+[B\sube S][C\sube S]a_s)。写成二维集合幂级数的形式做 or 卷积，即可做到 O(6^n)，获得 24 分。

注意到最终只有形如 x^Sy^S 的项的系数有用，据此反推出 IFWT 前的每一项 x^Sy^T 的贡献系数 (-1)^{|S|+|T|}2^{|S\cap T|}。

注意到每一项是 x^Uy^U+x^Sy^Ua_i+x^Uy^Sa_i，这样做 FWT 即高维后缀和后相当于只需要做两个单维的高维后缀乘积，由于有对 a_i+1 的除法，则非 B 性质的部分需要维护一下乘的 0 的个数。做到 O(4^n)，获得 36 分。

瓶颈仅为计算 (-1)^{|S|+|T|}2^{|S\cap T|}f_Sf_Tg_{S\cup T}，拆一下 |S\cap T| 就变成 or 卷积了，但是 f_S 其实被扩域为多项式了，直接做可以通过 B 性质获得 68 分，注意到只有最低次项可能有用，直接通过了！获得 100 分。

当 Right Output!!! 出现的那一刻，我的 OI 生涯画上了一个完美的句号。

总分 100+100+40=240，正式数据 100+100+35=235，才发现有一个情况没有考虑，庆幸只挂了 5 分。