CSP-S 2025 AFO 记
省流：
Part 初赛
Day -1（9.18）
S：
继续 whk。最近作业都很多，没时间搞 OI 了。
而且今天上课时即使听到了声音我们也没有暂停三分钟，足以说明目前 whk 学习的紧张性。
说不定可以以 CSP 初赛为由逃掉一个周末的作业，但是要是以后还得补回来的话就不好了。所以还是尽量都写了吧。（溜去晚自习）
几乎卡点晚自习结束时把作业写完了。然而第二天语文课还有作文考试。想到这个就有点焦虑，呃。
Day 0（9.19）
S：
凌晨有人在宿舍开声打 phi，导致睡眠质量堪忧。
继续 whk。今天作文考试毫无征兆的来了个时评题，要围绕一件事写个 900 字的议论文，以前根本没写过啊，还是太抽象了，而且还是我根本没听说过的什么扁担女孩。于是前前后后写了一个小时十五分钟，延迟交卷到下一节课都上课了。要是正式考试考这种我真的要寄了啊。幸好 OI 不会考手写代码之类，不然都得整份代码构思好才能开始写。
有台风今天登陆这里。对明天考场天气可能有点影响啊。
不过 A 喜欢下雨来着（但是仅限于不用打伞的那种小雨）。
然后今天下午就如愿下了让 A 开心的雨！感谢台风米娜桑
下午做完因为迟到导致的值日后打开手机发现 RS 更了两个关，今天晚上可能要打好一会了，打完再复习也不迟（x
我草，这个格赫罗斯好帅，秒了。
我草，这个未来隐都怎么这么难，感觉一时过不了了 qaq。
发个帖子真心求问被说批话，哎，我服了。合着有七钩就不能问问题了？七钩一定很厉害吗？我去年这会完善程序错一大半，要是全蒙 A 都不至于扣成这个样子。说不定到时候今年初赛都过不了，就好笑了。
到时候找找洛谷先前那个模拟卷做做吧……还有历年真题。
←实际上他继续玩 RS 去了，并且直到 Day 1 还没完美。
A：
额，总之快点复习。
Day 1（9.20）
S：
初赛所以可以写暴戾吗，那很好了。
梦到我洛谷号因为发布敏感内容被封禁了。
在早上十点成功完美 RS 的未来隐都，然后尝试复习初赛。
我草，我忘记 Kruskal 里面有并查集了。
？等一下 J 组考了 ARC070F？
好神秘。希望 S 组别太难。
12:00 出发去考场。雨下的很大，不小心踩到一个水坑，把两个裤腿都弄湿了。
听说考点那里从头堵到脚趾尖了，有点害怕。加上那么大的雨。
12:55 抵达考场，雨小了很多。
找了一圈好像没找到能面积的，除了原来的同学。qwq
后面的 NOIP 或者省选应该是最后的机会了（），可能还是别指望能遇到谁好点。
A：
其实这个赛季也就是随便玩玩啦，能拿 NOIP 1= 就已经不错了。希望能拿吧。
至于钩子之类的，金钩还能有什么机会（）教练不允许参加 WC 和 APIO 的话，那就只有 NOI，晋级 NOI 这可能吗？很蓝的啦。
S：
确实很蓝……
听到了熟悉的开考前的声音：
3.....3.4.5.5.......6.7.8.....7...6.5.......34586.......34585.........3.2.....1...3.2.........
* 8 指高音 1。
以前我这期中期末考也都放的这个 BGM，这是统一的吗？
又看了一眼，我的座位号是 5，看上去不会在前排。之前有一次考试（生地会考）就是因为我坐在最前面被老师一直盯着很紧张导致没发挥好的。说实话，心态也是很重要的。
原来考场有好几个候考室（报告厅）。到五号报告厅和学校的“小部队”集合了。
13:30 考场可以进了，不知道还有什么可以复习，再随便看看吧。
13:50 在某 Q 群内被同考场的 @jqQt0220 @ 询问是否在考场了，随后成功碰头。
然后再次印证了两个 OIer 碰面后会各看各的手机的定律。233
考场门口居然有积水，这里教学楼上边排水做的不是很好啊。正常来说是不是应该往一个有漏水口的地方流？
14:00 可以进考场了，但是进去也是坐牢半小时，不如等等。
14:03 算了反正好像也没事了……排队进考场了。
大概是做完剩半个小时。
然后检查，发现第三题当时没有注意到下标是 0-15，赶紧修改了答案。
继续检查，看到一直有疑问的 24 题，重算了半天感觉都没有问题，直到我想起来可能输入格式看错了，再一看怎么是 k p k p k p 这样输入的？赶紧重算，最后得到正确答案确实是选项中有的 8。
虽然其实并没有改答案——在看成 k k k p p p 这样输入的时候，会算出 7 的答案，这个选项中没有，所以我刚开始就选了更接近的 8。
哈哈。
16:40 经过十分钟紧张刺激的收卷，终于走出了考场。
基本上比想象的简单，除了中间发现自己踩了一点小坑。
对了下洛谷答案，大概是 94 分吧。
阅读程序第一题的第一个选项错选了 B，阅读程序第二题判断选了个 TTF。那个 F 是因为，我觉得当 n 很大的时候，那个 w 计算过程中会溢出成负数，导致那个循环结束不了，我认为这个算没有猜测成功。不了解 CCF 以及这类题的出题规则导致的。这个 T 就单纯的是看错了，我以为是最大的查询次数而不是对于任意查询的次数。
至于前面阅读程序的那个，我也不知道我是怎么选错的，我连题面都忘了。可能就是单纯傻逼导致的吧。
晋级第二轮应该是有的了。
A：
虽然这次简单一点，但是晋级线肯定是小于 95 的吧，我猜。再多错几个也没什么问题喵。
S：
update：前面那个错的是当输入 4 时候输出什么，这个能数不对我也是服了。
Day 2（9.21）
S：
你真棒。
Day 3（9.22）
S：
哈。
Day 6（9.25）
S：
出分了，确实是 94。
Rolling Sky 十周年快乐。
Part 复赛
Day -9（10.22）
S：
qwq。
Day -4（10.27）
S：
好久没写过代码了，随便挑一题试试。
写着写着代码 dev 居然炸了，没保存，何意味。
（请找出上面代码的若干个错误）
花了两个半小时做了洛谷 S 模拟赛的前两题，以及题解（见下）。后两题的话我头有点疼，先摆一会。
https://www.luogu.com.cn/article/im7v2xsb
https://www.luogu.com.cn/article/jjrkd3dl
这个月写最多题的一次。
Day -3（10.28）
S：
原本想写点题的，但是发现读错了一个小时的题，在知道真正的题意后想出怎么写了但是已经完全不想动了。可能也有没吃晚饭的原因吧。
Day -1（10.30）
S：
发现 mx 的 CSP-S 模拟赛是 NOIP 难度的。
Day 0（10.31）
S：
RS 新关可能因为万圣节的原因迟迟卡在审核没更新，于是我选择再随便看点题。
打卡原来前一天晚上就会准备好的。之前我哪次比赛当天因为打卡太早还打出个大凶，可能是为了避免这种情况（）
20:00 打最小生成树。
20:03 打并查集的时候忽然想到“可撤销并查集怎么写来着？”。
20:05 严肃学习，发现只能按顺序撤销，于是觉得“那这不难啊”。
20:06 忘记怎么获取 tuple 内元素了（谁会用那个 get？？）。
20:11 通过 P3366 【模板】最小生成树。
20:14 “反悔贪心是几级算法”
20:19 与同学交谈得知教练押 J 组考莫队。
20:21 发现洛谷搜索“最短路”无法得到【模板】单源最短路径。
20:34 成功在 P4779 【模板】单源最短路径（标准版）获得 TLE 56pts 的成绩，难绷。
20:37 成功在 P3371 【模板】单源最短路径（弱化版）获得 WA 90pts 的成绩，难绷。
20:39 发现 P3371 有无法到达的情况，特判了一下，于是通过了。
20:42 发现 P4779 TLE 是因为没有写 vis，于是通过了。
20:43 发现自己没有通过 P5960 【模板】差分约束。
20:54 利用 SPFA 通过 P3371 【模板】单源最短路径（弱化版）。
20:59 成功通过 P3385 【模板】负环。
21:07 发现自己判定成了无负环时输出 NO 并且调了五分钟，改正后成功通过 P5960 【模板】差分约束。
21:11 发现自己差点把 pbds 说成 bdtp。
21:13 决定跳过欧拉路径的复习。
21:17 决定摸鱼，剩下一些等会再看。
23:47 发现时间比较晚了。
Day 1（11.1）
S：
00:00 发现时间比较晚了。
00:08 成功想起来 Tarjan 怎么写。
00:20 成功通过 B3609 [图论与代数结构 701] 强连通分量。
00:40 决定追忆自己多年前失散的记忆碎片得到 LCA 的做法。
00:48 在 P3379 【模板】最近公共祖先（LCA）获得 RE 0pts 的成绩，难绷。
00:58 发现只是 dfs 函数不小心写成 int 类型了，然后还提交了一份有中间调试输出的 WA 0pts 代码，令人忍俊不禁。
00:58 在 P3379 【模板】最近公共祖先（LCA）获得 WA 20pts 的成绩，难绷。
01:00 在某处加上 assert(d[x]==d[y]); 后发现先前 WA 的点全变成了 RE，难绷。
01:30 我（其实是 deepseek）发现我在递归完子树后才更新 fa 数组。这会导致子树计算时这个 fa 根本没初始化，子树跑完了才会到这里，而这里的父节点也没初始化。样例对的是因为它根本不用跳两层。
我常常追忆 LCA 的写法。
倍增瞬间定格在脑海。我将背后的 fa 数组裁剪、折叠、蜷曲，揉捻成树上个个结点。
结点之间亦有分别：fa[x][0] 更近，而 fa[x][20] 更远。代码里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的 AC 在时间的冲刷下只留下些许残骸。LCA 宛如内投，一次走太急则无法忽略真实的位置，走太少却又失去向上的意识。只有最近的公共祖先，那恰到好处的朦胧，才能满足我对追忆的苛求。
LCA 总在不经意间将我裹进树论里。分别又重聚的 fa[x][_] 和 fa[y][_]，推倒又重建的数组，种种线索协助着我从一个具体的结点出发沿树的边逆流而上。起点和终点无法决定，比赛半途结束。CSP 的光芒投向大地，机房里的学生开始去洛谷写题。子树的初始化无法重来，我只不过是一个 AFOer。但我仍然渴望在每一次 LCA 之旅中留下闲暇空间，在数据范围前驻足，在越界的空间里瞭望过去的内存，感受尽可能多的混乱。没好的代码曾流过我的电脑，我不心满意足。
我的起点，是学校的 whk 太难了。这决定了很多，比如我每天去逃一个。银河系是由几百亿个星星组成的。星星点缀在夜空上，忍不住再把旋律轻轻唱。永远不会忘，心中有微光，能够带来新的希望。三百六十五天的时光，化成温柔的夜曲在播放。没必要失落，没必要悲伤，我会永远陪在你身旁。每天只有到十点才能下晚自习，不然我就只能食用我的手指了，这是宇宙中多么一个莫大的不幸。但是想写什么代码，为什么什么都写不出来啊。
WA 已经凝固，我带着修改的 dfs 向前，只是时常疏于注意顺序，答案也在改变着各自的形态。这给我的追忆 LCA 旅程带来些许挑战。
我该在哪里初始化？我问我自己。
初赛无论怎么选都会选中错误的选项，复赛怎么挣扎都改变不了些什么代码呢，怎么搞都必定会失败吧，AFO 之时已至。不如去多学几个 whk。
享受当下，我能摸几天，我就摸几天。还有几天就再也学不到 OI 了，学校马上就要抓我 whk 了，这也是真的吧，同我那可笑的荒诞的错觉一样，都是很难忽略的吧。
三角的函数在试卷里放着剧毒的光，这是真的吗，从来我一点都不累的，竟然有些疲惫了，OI 群要不活跃了，必定会被踢吧，AFO 之时已至，打摆吧。
whk 还剩下最后几个分数，都是不及格的了！每一个都要尽情拿分，在干不下去之前，AFO 之时已至，不如多学点 whk 吧。
01:31 追忆结束，AC P3379 【模板】最近公共祖先（LCA）。
01:59 前面还剩下一段编不下去了，写了也是烂活，也没人会认真看完，放弃了，早点睡吧。
05:00 睡觉。
12:30 醒来然后去考场。
13:06 看完 J 题目，感觉是红橙黄绿，或者低一个难度。第一题像 AI 出的，第二题需要排序之类的难一点点，第三题想到了就能随便做，第四题需要思考出一些转化。然后再看一下上次因为忘记怎么写丢的 pbds。
13:19 外环上修路占了两个车道，堵了好几分钟。
13:40 到达考场。来参加考试的学生家长请把车停在左边停车场。
13:46 进入考点。在门口听到有工作人员讨论说 45 分开始不让进考点，给我吓一跳。原来是 14:45。
13:50 尝试更新游记发现请求被拒绝，以为是被屏蔽词了，结果单纯是神秘网络问题。
13:54 和机房会合，然后随即就被要求跟着大部队走了（我在创新高中）。在 SZ-OIers 群里好像被拍了，但其实我没看到我在哪，因为我拍完位置的照为了和机房会合换了座位。
13:59 喜闻乐见的爬楼。
14:00 RS 更新了！玩你妈。
同考场没有深中的。
14:10 再看了点东西，准备进考场！
考场时的游记我记在代码里了。我回忆一下。
考场居然要我们自己输入题目名称和自己打开考场须知。
开始花了五分钟把前三题看了一遍。T1 看上去不是很难，T2 来个图论我吓了一跳，我去，别后三题全不会做啊。第一眼看上去，我以为有两层土图，如果这个放 T2 我都不一定能做出来。看到 T3 两眼一黑，我草，字符串。考前我还说希望别考字符串，我都不怎么会。现在来个字符串，我直接束手无策了。trie 什么的我都半年没写过了。T4，看了一眼，题目有点长，于是回去写 T1 了。
认真看 T1，注意到只会有一个超过 n/2，于是刚开始贪心，然后反悔即可。反悔贪心？昨天我还在群里问它几级，会不会考呢……其实我也没怎么写过反悔贪心。但是，总之大概是开考二十几分钟的时候写完并且过完样例了。
然后是 T2。我尝试画样例，才意识到原来乡镇是另外的新点。我发现 k 的范围很小，于是看 k=0 的情况，那就是最小生成树了。而 k=1……那就是在这个基础上，加上一个乡镇。可以枚举乡镇是否升级。
但是这样图的边好像会爆掉。我又画了一下，想到其实可以只把原图的 MST 保留下来，这样边就和 m 无关了，看上去能过。
于是我开始写。写到一半，突然意识到，我这里复杂度还应该乘上一个 log。log 是 20 左右的数，乘上一个 10 我的算法就爆了！于是我尝试思考其它 poly 的枚举 k 的方法。
我想到了两个方法，结果写出来全都是假了。……然后还得回去写原来的 80 分代码。这里看似就是一点思考，但是实际上花了 2 个小时。考试只剩下 2 个小时了。
我不能再想 T2 了，决定看看 T3 T4 能骗多少。然后想起，我去，T3 是串！
我看了下 T4。然后打了个输出 0 的代码。
我不抱希望的看了一下 T3，发现，可以把一个变换看成它的本质，也就是找到第一个和最后一个不一样的字符，然后取中间的串。两个同样计数的 s，它们的本质一定是都和 t 相同的。于是我把中间不同的部分拎出来，放到一个 map* 里，那么前面后面的部分就可以拿出来建 trie 了。然后就这么匹配就行。但是我很久没写过 trie 了，怎么办？我开始追忆，然后发现我不用追忆，我可以现推。于是我就把 trie 的写法推出来了。其实我第一次写 trie 的题我也是现推的。……
*后来我发现我直接丢进去，复杂度可能会爆炸。我应该用字符串哈希的。还是字符串的问题……那这次炸了。
T3 写的时候出现了很多插曲，对我的发挥造成了不小的影响……首先是我鼠标指针开始莫名的往下跑。我把监考员叫过来，他看到直接憋不住笑了，然后让我尽量忍一会。
然后我运行的时候电脑突然就这么炸了哦哦哦。按什么都没反应。我正要举手它突然又好了。然后又浪费好一会。
T3 调完，发现只剩半小时了。于是 T4 打了个暴力，8pts。
比赛结束前忽然想到把显示 warning 打开，然后我一开，T3 一大堆 warning，哈哈。
没时间改了，就这样吧。
听 CCF 评测机由命。
考场当时觉得自己可能是 100 80 100 8。但是发现我的 map 那里出问题后，现在 T3 已经生死未卜了。最低可能 200 都没上。
后来听说 T2 要改成归并。但是其实我当时都想到归并了，但是觉得这个空间得炸吧，加上看上去要没时间看后面的题了，然后就没写。
19:47 决定看看 RS 新关。
和大家交谈后惊奇的发现我 T3 其实每个地方都没有达到我想的复杂度，难绷。
Day 6（11.6）
分数出来了，是 100+80+50+12=242 分。理论上是挂了 46 分，但是实际上也是在期望的分数内的。1= 应该是有的，WC 大概率没了，NOIP 见。
但是在 NOIP 之前！我 whk 还有一大堆考试！所以先死了 qwq。