星图找寻映夜空 摩卡排列似飞龙 ——我参加 2026 年全国青少年信息学奥林匹克竞赛省队选拔圆满落幕

· · 生活·游记

Day -125 \pm 15

NOIP 喜提算了我不想说分数，总之就是 T2 挂了 20pts。

我不挂的话这个分别人问我我还好意思说，挂了是真的没救了。

Day -12 \pm 5

我这个分是怎么进省选的？这个分我印象中不是机房一车人比我高吗？

哎反正我们这群人又进不了队，机房内 NOIP_{\max} 欠队线 100pts 左右，我欠 150pts，去省选就当休闲娱乐积累比赛经验了。

Day -7 \pm 6

网络流是好东西。

Day -2 \pm 1.5

你知道吗？省选报名费的本质是对 NOIP 考的好一点的人收的智商税。

Day 0

还能提前 1h 回去的，最善良的一集。

Day 1

6:50 出发，在罗森购买了一个元气森林的汽水（后面要考）和软糖，防止场上暴毙或大脑停止运行。

7:20 左右抵达巴蜀，没有找到知行楼，后来遇到了其他崽儿发现在学校末端。

7:50 复习博客文章，临场领悟一个非常小的 trick，但是说实话由于紧张大部分东西没有特别细的看进去。

8:00 hajimilanbeilvdou

8:10 上楼了，配置缺省源和编译选项。

8:25 事实上这个时候就发密码了。

8:30 开！

T1，随机化树剖吗？这怎么期望？

T2 啥鬼东西，感觉不难啊（因为我读错题了）。

T3 感觉像是我平时没事会胡思乱想但是认为不存在做法的题目，然后每到 CSP / NOIP / 省选等比赛的时候就会把这种题目拿出来炸死我一次。

等等怎么今年的题复杂度都是严格小于指数级但不小于 O(n^2) 的。既没有追忆那种 10^5，也没有岁月那种 15。

依据往年经验，感觉 T1 对于我们这种人是最应该冲的。后两题打满暴力即可。

因为只需要冲 T1 正解，因此压力并不大。

8:40 我尝试喝那瓶元气森林的汽水。

在 CQ 巴蜀四机房的朋友们，如果能记得那个时候听到了什么声响的话，那你就能猜到我经历了什么了。

大家以后正式赛带饮料的时候尽量不要携带碳酸饮料，就算携带碳酸饮料也要保证带过来的时候不要过度摇晃，就算过度摇晃了也要保证打开的时候饮料不要在键盘的正上方，就算溢出来倒到键盘上也要尽快把键盘倒过来防止你以为已经擦干净了但里面还残留至少 50 ml 的量。

还好那个是无糖的，花费一定时间自己处理后没有影响接下来的比赛中键盘的使用。其实就算这样子我的心态也没有太崩。

后面思考的整个思维链遍历过程记不太清楚了，总之就是大体会了 T1，T2 会 30~45，T3 会 12.

简要说一下当时的成果：

对于 T1，相当于求 1 \sim n 的答案，而这个答案只需计算每个点没有成为重儿子的概率 p_i，则 f_i = f_{fa} + p_i。

因此计算 p 即可，n \le 5000，考虑 n^2 的树形 DP。

当考虑第 $i$ 个节点时，我们需要计算它所有的子节点的 $p$，即所有 $p_{son}$。同时亦可用所有 $p_{son}$ 重新 DP 推出 $dp_{i,j}$。 定义 $f_{son,j}$ 表示点 $i$ （即 $son$ 的父亲）除了儿子 $son$，其他儿子链长之和为 $j$ 的概率，它为 $\sum_{i=0}^{siz_{son}} \sum_{j=0}^{siz_i - siz_{son}} dp_{son,i} \times f_{son,j} \times \frac{i}{i+j}$。 已知树形背包上下界全都写对为 $O(n^2)$，但之前我没有阅读证明。并且如果没写对，$n = 5000$ 链就能卡掉。 我们断言（瞎猜），“树形背包上下界全都写对则为 $O(n^2)$”的本质是“复杂度不能出现某个儿子子树大小的平方，但是可以出现不同儿子之间乘积的和，并且乘上若干倍常数仍然正确”。 故若求出 $f_{son,j}$ 的复杂度正确，则全过程的复杂度等价于树形背包。主要问题为如何快速求出 $f_{i,j}$。 若到每个节点处重新现场求 $f_{son,j}$，单次复杂度就是 $O(n^2)$，菊花图或类似的结构即可卡掉。 注意到 $f_{son,j}$ 就是全部子节点 - 子节点 $son$，再加上这是期望的树形背包，联想到“背包方案数撤销”的 trick，因此求出所有子节点构成的 $f'$，再考虑如何 $O(n)$ 增删。 **此时，我口胡了一个完全错误的撤销方法，并误以为这就是正解**。 对于 T2，sub1 暴力，sub2 一定是若干 0 连续段中间隔单 1，计算贡献并背包即可。 sub3 类似的算贡献 + 背包，但是由于贡献算法只能得出 $\ge t$ 的子串数，因此还要记录长度，只有当 $len \times (len+1) / 2 - total = k$，才能得出正确方案。答案串应该不会很长，背包复杂度疑似是正确的。 对于 T3，暴力 + 判断异或和是否正确即可。 此时已经过 2h，感觉 142~157 的分数已然足够，且自己核心重要在于冲 T1，因此放心写 T1 了。 3h + eps 左右时，发现了 T1 撤销方法的错误。 **3.5h 时，提出了正确的撤销方法**： **这本质是一个分组背包下 + 期望 DP 的“背包撤销问题”**。 在普通背包下，撤销的方法很简单：顺序枚举 i，`f[i+w] -= f[i]` 即可。 想象两排点，上面的一排表示原状态，下面的一排表示新状态，上面的点向下面的连边，表示贡献倍率，上 $i$ 连下 $j$，倍率为 $k$，表示 `f_new[j] += k * f[i]`。 普通背包的连边是： - 上 $i$ 连下 $i$，倍率为 $1$； - 上 $i$ 连下 $i+w$，倍率为 $1$。 还原方法的正确性就是“从下排点考虑，则上面连的是 $i$ 和 $i-w$，假设前向点 $f_{i-w}$ 已经还原，直接减去它的贡献即可获得 $f_i$。因此顺序枚举还原，一定正确”。 但是这题的连边是： - 上 $i$ 连下 $i$，倍率为 $dp_{son,0}$； - 上 $i$ 连下 $i+1$，倍率为 $dp_{son,1}$； - 上 $i$ 连下 $i+2$，倍率为 $dp_{son,2}$； …… - 上 $i$ 连下 $i+siz_{son}$，倍率为 $dp_{son,siz_{son}}$； 现在问题是，已知下面的点权值和中间边的倍率，求上面点的权值。 我赛时的写法是：由于 $dp_{son,0}$ 实际上等于 $0$，所以连边一定向右连，且至少存在一条边倍率非 $0$。 找到上面最右侧点指向的最右侧的边（倍率非 $0$），指向的下面的点的入度一定为 $1$（$dp_{son,j}$ 对所有点都是公平的，因此左侧的点指不到这里来）。 那就可以用下面的点权除以倍率，推出上面的点。再根据所有连边，消掉上面的最右点对下面的贡献，递归进行这个过程即可。 --- 12:10 时通过 T1，大样例 0.5s。 我平时怎么就没认真研究这玩意？也没认真理解树形背包复杂度为什么对，甚至要在场上猜。 **但是这玩意大家居然会评到紫？？？trick 叠叠乐超级加倍效应发力了。** --- 后面在想 T2，写暴力写一半时忽然想到了一个**基于 KMP 的 BFS 方法，搞不好靠这个可以拿到 75~100pts**。 具体地：我们只需在意以下四个数值，作为状态： - $now$，当前 $<s$ 的子串数。 - $allgive$，这些是永远 $<s$ 的后缀数，每加一个字符，则 `now += allgive`。 - $border$，当前 $t$ 关于 $s$ 的 border 长。 - $synced$，是否匹配过（包含 $s$ 作为子串），即是否存在某一刻 $border = n$。 合法状态只需要 $now = k$ 且 $synced = 1$ 即可，状态数的上界为 $O(nk^2)$，但是由于 `now += allgive` 操作的特殊性，实际上跑不满，应该可以证明能过。赛后得知实际上是 $O(nk^{1.5})$。 那么如何转移呢？直接 KMP 自动机预处理 “$border = i$ 且加一个字符 0/1，$border$ 和 $allgive$ 该如何变化”即可。 我场上想的是，这个做法没啥问题，手玩样例也正确。虽然我都能想出来这个题的大体解法，因此应该小于去年难度。但是如果能过这个题，说不定有翻到三倍队线的机会。我已经过了 T1 有保底了，再爆也有 100。剩下的时间有可能也写不完 T2 的 30pts 和 T3 的 12pts。 于是我直接一个战斗爽上去，写写写，结局很惨淡，整个代码是完成了的，有看上去正常的输出，但我不理解为什么它无法通过任何的样例。 总之就是 T2 可能要保龄了（看数据怎么样吧），T3 有 4~12 分。 总之 Day 1 就这么 $100 + 0 + 4 = 104$ 地超级搞笑地结束了。别人听到我这个分，还以为我没过 T1 呢。 --- 总结：还好我现在初三。 - **大家以后正式赛带饮料的时候尽量不要携带碳酸饮料，就算携带碳酸饮料也要保证带过来的时候不要过度摇晃，就算过度摇晃了也要保证打开的时候饮料不要在键盘的正上方，就算溢出来倒到键盘上也要尽快把键盘倒过来防止你以为已经擦干净了但里面还残留至少 50 ml 的量**。 - 确保基本知识（树形背包、背包撤销、KMP 自动机）的熟练。 - 我赛前的预期是我只能过 T1，因此很放心地调整比赛策略为前 2h 思考，后 3h 实现，没有给 T2 留出足够的空间。 既然我现在已经有做对 T1 的实力 + 模糊想对 T2 的大约一半解法的实力，那么到明年就不可以采用这样的策略了，而是像 CSP 那样的前 20min\~1h 看题，也就是 10~25% 时间看题初步思考的策略，然后再逐题深入思考和实现。 - T1 的整个用时太长也是导致 T2 T3 爆炸的原因，因为这实际上是一个“DP 撤销”的通用典型问题。**在没有深刻理解过这个 trick 的情况下，现场推导发明它也算进你的考试时间里面**。 我觉得如果我在知道它的情况下，我应该在 1~1.5h 完成 T1 的全过程。**而“知道它”这个目标就应该通过日常训练来实现**。虽然有一定思维、天赋可能会通过现场发明帮你硬抗住一个你不知道的知识点，但这不应该是主要的手段。 - 在仅剩 1h 不到的情况下，其实求稳就应该老实打暴力（起码先把能拿的分写了再冲正解吧）而不是战斗爽了。 当然我今年休闲娱乐拼一把也算是一种策略，但是明年就不要这么玩了。 - **我没写对拍**。 把命运交给造大样例的人吗？666。 ### Day $1.01

出来问了一下 @goeswar 100 + 15 + 12 = 127， @smart_stupid [36,48] + 30 + ? = ?，其他两位没问。

感觉 T1 对于真正高中生可能是人均题，但是后来看发现紫黑黑，不知何意味。

Day 2

没写。