2026 省选游记 | 下辈子我还学 OI

· · 生活·游记

:::epigraph[] 注意到 recollector 和 recall 是同义词。 :::

同步发布在博客，2026 省选游记 | 下辈子我还学 OI。

省流：倒闭了，放心阅读。

\text{Day -inf}

NOIP 暂时在三倍队线以内，毕竟高一赛季了，省队无望了，还是想冲一下 D 类。

算起来今年已经是第三次参加省选了。

三年合起来看，感觉确实进步挺多的，作为没有停产过的 HA 选手，尽力了。

\text{Day -10} \sim \text{-3}

去参加了 dmy 的公益集训。

不知道咋了，从报道就开始感冒，头疼流鼻涕咳嗽，一直到结营才好了一点。

集训场地说有床垫，结果去了没有，睡了好几天硬板床。

过了两天，dmy 突然说没法用原来的集训场地了，给我们换到了四星级酒店，加量不加价。

我必须在这说一下，dmy 就是最良心的集训机构，酒店睡的比硬板床好多了，还能点外卖。

集训四场模拟赛，获得了总分 93\text{pts} 的好成绩！大概是我去年省选的 \frac{2}{3}。

太合理了，初三半年没咋学 OI，进步了惊人的 \frac{2}{3} \cdot \frac{1}{4} = \frac{1}{6} 倍！

\text{Day -2}

开学了，嗯对。集训和开学无缝衔接。

因为分班了，所以先去班里报了个道，跟班主任说过之后就来机房了。

下午打了场模拟赛，我怎么切紫了，我咋这么强！

\text{Day -1}

上午打了场模拟赛，我怎么蓝豆没切，我咋这么菜！

随机切题是吧，那我省选是不是有概率切黑，很合理吧。

\text{Day 0}

中午直接请假提前离校了，出来吃了个火锅鸡，店员上错了，给我们多上了一斤鸡，爽吃。

吃完回家收拾了一下东西，就出发去焦作了，郑州离焦作就不到一个小时，还挺快的。

在酒店大厅领了参赛证，今年质量比去年好啊。而且换成了前年的酒店，比去年好多了。

玩了一下午，到晚上跟 Archy_ 去武陟虹兴砂锅吃的，去年前年都来这个店吃过，还挺好吃的。

来了刚好遇见 shw0000 也来这吃了，这么巧。

\text{Day 1}

早上 06:25 准时起床，去酒店吃了个饭，没吃啥东西感觉，喝了碗胡辣汤。

在大巴上跟 Archy_ 和 shw0000 坐在一起，在窗户上写了个 rp++，并发至朋友圈。

刚下大巴就去检验证件进校了，成为 Day1 第一个进校的选手。

开题先通读了一下全部题面，T1 啥玩意，怎么还有随机链剖分，怎么还有期望，完蛋了。 T2 T3 感觉有挺多部分分的，先写 T1 吧。 先写了个特殊性质 A，这不送分，一个链显然本身就是重链，答案肯定为 $0$。这是安慰分吗。 别急，这暴力咋打，我咋不会打暴力，算了，先去把 T2 T3 的暴力和部分分打了。 T2 这 A 性质暴力还挺好打的吧，迭代加深搜索就完了。 特殊性质 B，感觉像个贪心放，直接打。 诶，怎么比大样例输出多了一位，好像不能直接贪，那就搜索吧，剪剪枝，能不能过啊。 不管了，剩下的都不太会，去看 T3 了。 有 $8\text{pts}$ 的暴力分，直接打。然后 $m=1$ 也是简单的，白拿的 $4\text{pts}$。 这个 $m=2$ 感觉是分成两个子集，没啥思路，跳了（实际上并不是随便的两个子集，当时没手玩数据，应该是选一个区间，分成内外两个子集。 性质 ABC，我怎么都不会，诶不看了。回去看 T1。 怎么感觉可以用链长期望求，打打打，样例都过不了啊。噢不能用链长期望。 倒闭了，浪费这么多时间，感觉没啥好思路了啊，而且这个做法的时间复杂度瓶颈在于枚举轻边，注定是不小于 $O(2^n)$ 的，写了也没啥优化空间感觉。 但是没啥好思路（感觉今天被 T1 搞的脑子都不转了，怎么当时连 dp 都没想到。 倒是想到了用 $f_{i,j}$ 表示以 $i$ 为根，重链长为 $j$ 的概率，但是上传感觉很不好写啊。 实现了一会，感觉写了一坨，现在脑子里有点混乱，上个厕所刷新一下。 回来之后感觉思路有点清晰了，写了一下。 终于过了样例，诶不是，怎么大样例 $2$ 挂了，倒闭了，只有半个小时左右了。 调不出来，检查吧，怎么五个小时过这么快。 观察到 T3 的 C 性质大样例全是 `Yes`，于是我直接输出 `Yes` 看能不能拿分。 最后十分钟交卷。 中午由于基本大餐厅都停止营业了，在一家小餐馆吃的饭，上菜太慢了，也不咋好吃。 回酒店又玩了一下午，看了看 luogu 的帖子，怎么 Day1 T1 是个多项式除法啥的。 我没学过啊，正常发挥了属于？ 晚上和 Archy_ 开黑王者，就跪了一把排位一把娱乐，可以。 ## $\text{Day 2}

跟昨天一样，06:25 起床，去吃了个早餐，发现餐厅没多少人怎么。

原来今天大巴延迟了 15 分钟，吃完饭上楼休息了会。

然后就是跟昨天一样的流程。怎么还一天一个座位号。

开题之后还是先通读了题面，不是哥，两道交互？你逗我呢。

花了好久理解如何交互，感觉这个 T1 不怎么难的样子。读完题就会了 AB 性质的 20\text{pts}。

写完 AB 性质，想编译的时候发现怎么 Windows 没有 g++ 环境，加了环境变量还是不行（赛后才知道要重启才会生效，但是重启不就刷机了吗，这么坑。

本来准备换 Linux 了，然后想到可以用 g++.exe 的绝对路径，试了试发现可行。

过了 AB 性质之后，想了想 n^2 询问次数的还原方式，感觉不太好写的样子，先写 T2 T3。

这个 T2 是个啥玩意，完全不会啊，k=3 感觉可写，但想了一会还是没啥思路。

感觉没必要在这上面耗太多时间，毕竟 T1 感觉可写的样子。

看了 T3 感觉也不太会，这个样例怎么这么难理解。o_x = o_y = 0 我也不会啊。菜完了。

瞎胡了 T2 T3，还是看 T1 吧。

首先这个 n = 10 的点可以 n^2 写啊，但是不太好实现，先不写。

手玩了很多样例，感觉这个询问一遍 [0,i],i \in [0,n) 很有用啊，每一个连续段的末尾实际上就是末尾下一位的值，这个性质感觉很好用。剩下不能确定的升序排？

发现过不了大样例，原来有区间限制，比如若 \text{query}(l,r)=5，那么 [l,r] 区间内一定包含 0 \sim 4。

那么虽然可能 1,2,3 没法确定位置，但能确定的是一定在 [l,r] 区间内放着。

又注意到数据给的有 n \log n 的部分分，于是想到了可以二分找 0，然后二分找 1，以此类推，找的过程中顺便记录每个数的区间范围，最后不能确定的数就放它可能的最小区间内。

这样就是 n \log n 的询问次数，可以拿到 45.5\text{pts} 大概，但是感觉这个做法没什么前途，先不写了。

这个 \log 感觉不太能优化掉的样子，正解的方向应该不是这样，去上个厕所刷新一下脑子。

然后就又注意到有 2n 的部分分，就想这个 2n 次询问能怎么用。

前面感觉 [0,i],i \in [0,n) 的询问挺有用的，于是就想到了倒着询问一遍 [i,n)。

诶，发现正好又能确定一些数的位置，加上前面想到的区间限制。

又发现正着扫可以确定一个数的最小右区间，倒着扫可以确定一个数的最大左区间。

于是这样就得到了个 2n 次询问次数的做法，可以拿到 75\text{pts}。

感觉离正解很近了啊。

又手玩了一万个样例，通过瞪眼法发现正着扫个倒着扫一定有且仅有一个位置都不为 0。

设这个位置的下标为 x，正着扫 [0,i] 的答案记为 a_i，倒着扫 [i,n) 的答案记为 b_i。

那么一定满足 p_x = 0；\forall i \in [0,x), a_i = 0；\forall i \in (x,n), b_i = 0，这是显然的。

这个性质很有用啊，我们只用倒着询问 a_i，问到 0 就不再询问，记录 x 的位置。

这样使用询问 b_{0 \dots x} 的答案，这样的询问次数是 n+2 的，可以拿到 93\text{pts}。

感觉很有机会，想想有没有什么不需要的询问。

中间肯定优化不了了，然后就看了两边，发现多询问了两次 [0,n)。

完全没有必要啊，因为答案一定为 n，这样询问次数就是不大于 n 次的。

我真切了 Day2 T1？我这么菜居然在省选切题了。

其实现在已经 13:13 了，没什么时间了，延长了 15 分钟，也没什么用了，T2 T3 没什么能骗的分。

检查完就在那静静等着时间流完，高一这个赛季可能就这么结束了。

三场比赛以来，起起伏伏，也就这样了。

\text{Day 3}

晚上来机房复现了 Day2 T1，过了 qoj 和 yd 的数据。

luogu 评级紫黑黑蓝黑黑，也算正常吧，Day2 T1 确实没那么难，出来之后发现一万个人切了。

怎么今年总分跟去年差不了多少，这不倒闭了吗。

下辈子我还要学 OI，因为 CCF 能让我在省选提前获得 IOI 的做题体验。