鬼门关里走一遭

· · 生活·游记

好久没有写游记了。

想从比较久远的地方写起。

省选 2023 是我第一次省选，那年我初一，打了若干个暴力，估分好像是 100+25+48+55+12+2，好像小挂到 238 了，考据于某集训队的游记。好像在两倍队线内，但没买 D。后来因为省选成绩获得了 ISIJ 资格，马拉松赛垫底了。怎么看我当时都充满希望。

NOIP2023 我 271->225，省选见游记，D2T2 最后过了，也是第一次场切黑。“以后还是打稳健点”。后来我因为校内限制买不到 D，我立志初三进 E。

NOIP2024 我 320->336，大概中位队线。省选 2025 Day1 写出追忆 \frac{nm}w+n^\frac35 做法，6\times10^4 根本跑不动，剩一个小时果断开 T3，拼出 52pts，估分 172，好像上了队线。省选 2025 Day2 看到岁月感觉跟重塑时光是一个类型的题，冲了一整场 T2，独立推出主旋律，最后还是没过样例，交了三份空代码。后来得知 Day1->240，Day1 考完全省 rk5，Day2 直接掉到三倍队线。我很痛苦，但也不得不尽快调整面对中考。后来在学校教练的帮助下还是买到了 D。

我高一了，停课外训。NOIP 前我认为很难 A 队，NOIP 341->361，全国 rk34，FJ rk2，我感觉我行了。WC 再度打铜有点痛苦，又开始怀疑自己。省选前 ZR、核桃、haoba 模拟赛基本打得不错，ZR rating 上了一周目，核桃主要是场均做过原，haoba 模拟赛主要是高手都在摆。以下是省选游记。

Day-?

打了若干不熟的模版。

Day-2

加训集合幂级数。晚上去学校看了一看，见了若干同机房同学，发现现在晚自习有老师看机房。

Day-1

加训集合幂级数。中午在学校群里投篮、口嗨，预言关于省队、标准分、题目考点的若干内容。下午坐动车前往福州，旁边的 hr 怎么在复习 Top Tree 相关理论，畏惧了。晚饭后去师大附踩点。看了自己写的总结反思、hba 考前提醒。很早就睡了，醒了 O(1) 次。

Day1

考前依旧没什么胃口。发现准考证上考场是 nan。进场，时间显示 16 点，不会改。旁边 sxj 怎么没来。读题，T1 看着就像我会的，T2 感觉不难，T3 感觉不易。想 T1，显然 dp，退背包，长剖分析一下复杂度是对的，写完发现不用对每个节点求答案，凭空多了一些常数，没关 -fsanitize=undefined 1.1s，应该稳了，没造极限。

1.5h，感觉打打暴力就上队线了，优势在我。

想 T2，感觉也是 dp，跟匹配有关，把串反转一下，应该是自动机上走。数据范围有点神秘，不知道答案长不长，记为值，如果转移有环也可以跑 bfs，分析出了比 s 小的后缀只有 O(\sqrt k) 个，放到状态里，拆一下贡献。一维 O(n) 记录自动机状态，一维 O(k) 记录个数，一维 O(\sqrt k) 记录比 s 小的后缀的个数，算一下空间，差不多，应该对了。

然后现在的问题是构建自动机使得能匹配所有后缀，一开始以为可以 kmp，写一半发现不行，思考，把所有后缀都插入 AC 自动机肯定是对的，但这样状态数是 O(n^2) 的，好像没什么分。我突然想起后缀自动机，在后缀自动机的基础上改一改是不是就行了。我考前复习了 SAM 板子，应该能写出来。

开写，写起来有点痛苦，发现前 n 个字符的情况好像是不同的，还得另跑一个 bitset 优化的 dp。

写写写，删删改改，写写写，删删改改，写写写，删删改改，写了一大坨，写完还剩 1h 多，应该能调出来吧。

第一个样例就不对，发现漏考虑了已经有 k 个但还没满足 s 是子串的情况，打了一个补丁。然后一直调不过 4 17，红温了。

急急急，急急急，急急急，急急急，急急急，急急急，急急急，急急急，急急急，急急急，调了好几十次还是调不出来。

考试怎么要结束了，加了文件读写检查了一下就离场了。

问了一下周围人，都很高，sbh 翻了，队线往低了估也有 160 到 170，我一下子抑郁了，怎么要打省队保卫战了。我 T2 怎么 6KB。

我根本没有任何心情吃饭，和父母先回酒店了，躺在床上非常抑郁，睡也睡不着。

强迫自己相信 lhr 300 标准分，分析一下当前的局势，其实还在队线上下，但我非常担心我的精神状态，感觉压力骤增，感觉 Day2 很难很难很难打。和父母沟通了一下，尝试做好没进队回去学 whk 的心理准备。期间追忆了一下 T2，根本假完了，全 0 和全 1 情况下是对的，没测大样例也不指望得分了。

晚上和亲戚去万达广场吃饭，还是没什么胃口，吃着吃着忍不住哭了，说如果没进队高二还要再打一年。

回酒店后和我妈沟通，躺在床上非常痛苦，想象不出来未来，不知道几点睡了。

Day2

5 点醒了，睡不着，起来听了若干首歌，精神状态尚可。考前依旧没什么胃口。考前几乎所有人都跟我说打稳一点打满能打的暴力就进了，我觉得是对的。进场，时间显示正确，心情好像比较平静。读题，怎么两道交互，不对，T2 是伪交互，但是构造，不像我的优势场，但稳着打应该问题不大。

想 T1，做好了做不出来的心理准备。首先是排列 mex 转前后缀 min 的 trick，填数是贪心，看特殊性质，如果知道 0 的位置就可以两边前后缀分别问一下，很快就做到 n 次了，写得不快，写的过程中发现可能会越界把某个循环上界改成 <n-1 了，1h 多过了样例，造了一组 30000 的，grader 跑不动。

想 T2，感觉要求一个特殊集合的线性基，看特殊性质，感觉 k=3 最简单，猜了一手，过了大样例，分析一下发现取到下界了，然后想猜一手答案，k 是偶数取满 k 是奇数减去度数是奇数的点数的一半，偶数是对的奇数有些实际少 O(1)，感觉还要讨论，有点不敢猜了。

跳了，想 T3，这不是我出的 CF2135F 吗，发现不同的子树只有 O(n) 个，按 dfs 序扫描子树总共只会变化 O(n) 次，于是套一下做法把 O(n) 个子树统一排序然后数据结构维护一下就有不少分。时间大概还有一半，决定开写，边写边调，写完还剩 1h 多，应该能调出来吧。

出题人很良心，给了中样例，我很快就调出来了，然后疯狂拼包，ox=0 且 oy=1 倍增跳一下就行，本来想过 18,19，发现直径是 O(\sqrt n) 的就放弃了。

感觉时间再多一点可能可以拿更多分，但算了一下已经有 56pts，不能太贪，要留时间检查，想先回去打一下 T2 n\le8，但又不会了，于是回去拍 T1 ，3000 和 10 轮着拍。

考试延长 15min，没做什么事，继续拍 T1，检查。

出考场，疑似本校最高，那应该够了。我 T3 怎么比昨天 T2 长。lyf 怎么被 T2 肘了，不过他应该 A 了，sbh 好像过 T2 了（实际 T2 高分），翻进 A 了，lqh 怎么 264，太强大了，lhr 怎么声称 day1 只有 260，day1 标准分怎么小于 day2。我如翻。

如释重负，感觉不挂分就进了，去亲戚家看了一下，晚上回厦门。

Day3

其实依旧折磨。5 点醒了，睡不着，去学校。我怎么还要备战 NOISG。第二节课和同班的 hr、dyc、syy 打乒乓球，感谢他们的陪伴。自招上了的 wxy 来了，给他讲解了一下 D1T1。感觉完全做不动题，写不动代码，写了一道简单题就摆了。

下午发现 wxy 在 QOJ 被卡常了，帮他卡了卡，有点担心自己被卡常，追忆了一下可能的挂分点，有点担心自己 freopen 写错，虽然检查了但还是放不下心。后来发现 wxy 退完背包又算回去了。晚上听说 DT 中学被校长做局了。浑浑噩噩地就过去了。

Day4

早上 cjld 来了，zzp 来了，开始考后口嗨，感觉 zzp 和 lyf、sbh 差不多，有希望进 A，我不挂分是稳的，cjld 应该在队线上。然后开始和 cjld 造题。读了若干道 NOISG 真题的英文题面，大概能看懂。DW 说 ICPC 深圳站一中有一个免费名额，我、cjld、zzp 报名了。给 wxy 讲解了一下杂分选约。一天下来也没做什么事，时间过得很慢也很快。

Day5

继续口嗨，继续造题，继续读英文题面。晚上填了一下队伍信息，定了队名。也不知道做了什么。

Day6

早上临行前出分了，我 100+0+0+100+12+56，和估的一致，没仔细算，但应该稳了，后来出了民间榜，我居然 B2，福建强度有点低了。Day1 标准分怎么 252，我说 lhr 该申诉了。A 队是去年四块金牌。zzp 是 B1，他 D1T1 被卡常了，申诉了一手，有希望翻进 A。cjld 挂分了，在队线外 O(1) 名，很遗憾。

感觉我达成了一百万项成就，包括但不限于：

我也太类人了。坐飞机抵达重庆，看了一下其他省的榜，有点抑郁，晚上写了一道简单题。

Day7

在洛谷上交了 D1T1，跑得很快，刷 NOISG 近几年真题，没做难题，一天下来过了 6 题，很高效。午觉醒来发现 zzp 说我 D1T2 能得 15pts，但 freopen 写错了。本来要反向挂分了，结果正向挂分了，我真的是人类吗。不过多 15pts 也只能翻一个 E，和解了。真的和解了吗。

Day8

NOISG 比赛日，早上和厦门教育局副局长合影，有点绷不住。遇到 djx，他居然和我说话了，他省选 D2T1 挂大分退役了，很遗憾。试机时发现自己不会编译，不过题目有给编译指令。比赛过程简单写写，前 4 题过得比较顺，期间想查一个报错信息中的单词字典里却没有。后半场冲击 T5，没什么接近正解的思路，后面比较摆，有一些优化没加，最后拿下 32.37 的不知道如何的成绩。出场发现 lyr 429 多，那我应该还行。周围人感觉不强，不敢去问高手的分。晚上摆了，打 OI 重开模拟器困难版，打了很久才出一个高二 NOI 金牌。

Day9

早上主席讲话。怎么讲题讲的是初赛的题，学到了 0 个东西。晚上和我爸去明月湖边散步，没什么灯，很暗。

Day10

坐飞机回到厦门，晚上上 haoba 的课，难题想不出来。

Day11

上午写摩卡串被卡常了，学习二分图最大匹配期望，下午单独去体检，有点烦。正式成绩出来了，尘埃落定，zzp 没申诉成功，没进 A，有点遗憾。开始加训构造，补了做题计划里的一道简单题。

After

游记是出分后写的，断断续续写的，写到这里差不多了。再怎么说也要打 NOI，怎么加训还没想好，但可能要做出一些改变了。有点痛苦，但还不能停下脚步。

总结反思

会写的。

趣事

考前某四人群。

lyf：@我，省选有没有你的题。

我：暂时不能给你明确的答复，需要你自己进行衡量。

考后。

zzp：起初大家都以为这是一句玩笑。

lyf：起初大家都以为这是一句玩笑。