省选2026游记

SnowTrace · 2026-03-12 13:59:55 · 生活·游记

被动技能：我看见我认为我会做的题大概率能做出来。

Day -inf

NOIP 使用被动会了 4 个题。

Day0

完全不记得自己干了什么。

一个多月没见到任何实体，试机一开始的时候根本不敢何任何人说话。

而且我发现我连着打了四年省选，每一年都是场上几乎一个人都不认识，但看上去别的人都组成了若干个连通块。

两天省选的策略都是打完暴力就睡觉，这样 B 队比较稳一点。

Day1

看 T1，随便 dp 一下然后撤销背包，长剖优化一下，十分钟就想明白了，写了一会，发现撤销背包并非很平凡，然后稍微改了改，结果在样例 2 挂了。我以为是我的撤销背包写挂了，瞪眼了好久，最后发现是树形 dp 过程中数组没情空，花了将近一个半小时才过。

看 T2，一开始读错题了，以为是要求小于串自身的子串个数要有恰好 k 个，怎么想怎么不可做，虚空思考到十点十五受不了了开始打表，打完表发现怎么输出和样例不一样？哦原来是我读错了。

然后我对着特殊性质 ABC 稍微做了一下，我发现怎么做点弱智部分就给了 45 了，这不对吧？然后乱编一点状态，发现只要记录一个最长匹配到的前缀就全对了，然后这个东西可以最短路转移而不是枚举答案串长度，优化了一下就过了，大概是十一点多过的。

然后看 T3，一看就很困难（然而事实并非如此），我决定拼上 m=2 就睡觉，然后我发现怎么没做明白？写了一百年写到 1：00 决定不写下班了，然后后面就一直在检查。

最后 100+100+16 遗憾离世，出场发现全世界都会做 T3 但似乎都没写明白。

Day2

拿到题发现怎么有两个交互，燃起来了！

T1 大概做了十几分钟就知道怎么问了，然后光速开始写，但我一开始完全没想明白怎么填数进去，写了两版假代码，最后花了一个小时才过，也写了一个拍子。

然后看 T2，这是可做题？看完 T2 就急了，先思考了一下指数级暴力怎么打，发现我们可以对线性基正交一下，发现它的秩很大，所以可以直接对着自由元状压，复杂度 O(n^2 2^n)，原本的想法是先写这个，写完对着 k=3 打表。

大概写了一个小时才写明白这个东西，然后我发现如果我以随机顺序插入三元环向量消出来的矩阵的形式并不好看，然后就没接着做了。我场上认为这是一个没人会的线性代数题，于是就跑路去第三题。

第三题花了不短的时间才读懂题，然后编了一个子树比较的算法，然后我发现我只需要求出每个子树的补在只考虑子树（不考虑子树补）的情况下的排名，这是因为如果我们要比较两个子树补，则一定比较的是互为祖先后代关系的两个点，实际上就是按照 (只考虑子树排名，深度) 两维进行排序，然后我懒得写了，直接写了个 long double 上去，但我好像没写明白，调了一个多小时才调出来 44（而且我写了 6kb，我现在已经无法理解我是如何做到的），后面只剩四十五分钟。

感觉 ox\times oy = 0 的部分分都很平凡，但是我前面写的求排名是 \sum deg^2 的，我还得把这玩意改成二分哈希复杂度才对，所以最后为了求稳就没有写，一直在检查。

最后三分钟告诉我延时十五分钟，这对吗？急眼了，那我相当于干坐了一个小时，不过进省队肯定没什么问题了。