生きろ。 | 联合省选 2026 游记

· · 生活·游记

省选前

总之 WC 倒闭了啊。不知道在加训什么。hb 请 jsy 给我们讲了数据结构，但是感觉还是学不明白。

补了去年省选的追忆和前年的魔法手杖。稍微复习了一点 DAG 容斥。

hb 在近两个月的模拟赛放了第二次 PQ 树，写了一下，好长啊！！！

云斗模拟赛六场恰好打了四场，虽然没钱拿但是可以等着拿省队奖励/fendou

总之没咋打板子就是了。

保个省队就挺满足了啊。

Day 0

试机。又见到大家了呢。不过似乎也没有什么特别的喜悦……

打 NTT。感觉这 VSCode 有点卡啊，不知道是不是错觉，不管了。好像没打歌词。打块。

你应当阅读 作为 OI 选手不可不知的编程操作注意事项（新手向）、OI 赛制比赛 emergency kit（2024 Winter Edition）。

Day 1

鼠标咋这么不好用。找监考要了个鼠标垫好用多了。

歌词想了一分钟根本不知道打啥啊。直接把九重最后一句呼上去了。

浏览一下 T1 T2 T3。鉴定为 应当是简单题 困难题 困难题。

recallector 这个 T1 题目背景怎么一股追忆味。总之就是设 dp_{i,j} 表示 i 子树内长链长度为 j 的概率，转移大概是要做去掉每个子树的背包的样子？额那如果说单独去掉一个子树是它的长链长度乘以总长度的复杂度，那是不是长剖分析一下复杂度就对了。写一下。写。写。写。怎么在最大的样例上面 buffer overflow 了，开 sanitizer 也只告诉我这个，咋回事。开大一点数组，现在最大的样例可以飞慢地跑出来，看下 sanitizer 咋访问了不该访问的东西。研究一下，咋是有的地方清空了背包数组但是没把长度清零。改了一下，跑得飞快，花了大概一个小时多吧，总之大样例跑得飞快。

看下 T2。感觉根本刻画不明白，咋数比给定串小的子串数量啊。咋数啊。咋数啊。咋数啊。诶好像确实可以数，记录一下当前已经严格小的子串数量，前缀匹配最长长度，答案就能数了。那子串的限制也无非是加个 0/1，做完了……？等等「严格小的子串数量」的量级该是多少呢……想了挺一会儿的发现一个上界是 \sqrt{2k}，那数组还可以开挺多个的。稍微写一下，写写写，怎么小样例根本不对啊。好像根本没处理明白对于匹配到完整串时的处理，随便改改……好的小样例过了，写了个判断答案长度是否与 std 一致的小 checker，没问题了那就输出答案看看，咋和标准输出一模一样？根本不需要写 checker 了 ooo

前两题大概花了 2h50min，去看 T3。思考。感觉一眼根本看不出来这个答案序列有什么能做的点。仔细思考了一下才发现最终就是一些环上的区间，大概是要在上面来回跳跳跳的事情？那 m\le 2 写个 dp 判断每个双终点组合不合法就做完了，拼上暴搜有 24 分。先写一下。写完了继续思考，我毫无头绪。这咋做啊。这咋做啊。这咋做啊。特殊性质我也根本不会做，虽然看起来就是简化版的问题。这咋办。打表发现 m=2 的时候判定的充要条件，但还是毫无头绪。不过看 checker 学习到了如何输出颜色。

回去写了一个暴力判断构造出来答案是不是 k 的东西来拍。感觉强度还行，直接给你拍上个一千万组。确实没拍出来 bug 就是了。

估分 100+100+24=\boxed{224}。好像好多群友都做出来了 T3 的非平凡分数。pmd T3 战神直接演都不演了直接阿克，那还说啥了。

三个 dp 也是有点魔怔的。是不是直接把省选 dp 额度用干净了。

Day 2

一开始入睡有些困难，后来倒是没有醒来太多次。不过还是有点困的呐。

歌词不知道打啥了写了一句 ikiro。

浏览一下……等等什么叫两个题有 grader.cpp？？？浏览一下题目。T1 是真交互，T2 是个构造，T3 是个神秘东西。总之还是按顺序开吧。

思考 T1。首先发现排列区间 \operatorname{mex} 是骗骗你的。一开始想的是分治往 0 那边靠，发现和二分 0 位置的 n+\log n 本质相同。那二分改成直接找就是 n 次操作了，开写。稍微写一下。咋给的 grader 写的是暴力求 \operatorname{mex} 啊，无敌了。有点懒，就随便手造几个小排列测了以下，应该问题不大。

来看看 T2 吧。额首先这个次数限制不会影响答案，因为如果超过 n(n-1)/2 次的话肯定有一组线性相关的。先做做 k=3 啊嗯。那三元环能构造任意长度的环所以就是只要保持度数奇偶性就行了。做做 k=4 啊嗯。构造了一会儿发现只要保证边数奇偶性就行了。诶我其实就有任意 k 的四元环构造，以及发现了 k 为奇数时度数奇偶性不变、\dfrac{k(k-1)}{2} 为偶数时边数奇偶性不变。看下四元环就可以把一个度数和边数都是偶数的图清空了。那不管操作次数限制的情况那就做完了。操作次数限制咋办。限制咋办。限制咋办。想了一会儿发现可以用不超过 n-1 次把 n 减一，而 n=k+2 时操作去重一下就行了。那就做完了？开写！先写一发 report 对一下。咋错了咋错了咋错了。发现怎么是缺省源里的 rep1 定义出问题了？？怎么写的是 0 到 n 的循环。赶紧把所有代码里的这部分都改掉。这下总该没问题了吧。写了好一会儿。

做完 T1T2 大概是两个半小时，然后 11:17 去上了个厕所看到凯文在笑，不知道在骄傲什么。总之思考了一会儿 T3 毫无头猪，只发现了可以改成只收集子结点的产物。思考。看眼部分分。前两个测试点比较 trivial，写个暴力应该能过 5\sim 8？没什么想法，先写了再说吧。总之写了一会儿暴力拿了 24 分，一开始还有个地方写错了来着，导致恰好一个答案 WA 了。接下来还是没啥想法。咋办啊。怎么又在更新样例解释，草台班子。

拍下 T2 吧。report 应该没啥问题应该那直接拍构造正确性得了。咋拍出问题了？只有一个小时了，哈人。赶紧对着拍出的问题调调调。好像是写的不太好 k=2 会出问题。改掉了。再拍一下。咋还有问题？赶紧调调调改改改。现在应该没啥问题了吧，大数据小数据都拍了……虽然开了 sanitizer 的时候大数据根本跑不动，不管了。T1 瞪眼了一会儿，应该没啥问题了。

那又是 100+100+24=\boxed{224}？好像挺多群友没做出来 T2，那是不是优势在我。不管了。考完试是不是应该啥也不管。别管了。

省选后

总之 zxx 在藏分，xqw d2t1 100\to 10，以及一堆人分数有变动，估计的省选名单也是变来变去。不过我的分数确实和估分没有区别，获得了六个题有两个本质不同分数的好成绩。应该是有 A 了吧。

恭喜成功进入省队的大家，也对没有进入省队的大家说声祝好。