CSP 2025 游记 & 退役记
Kei__
·
·
生活·游记
初赛
某个如去年没拿 J1= 菜得要命所以今年 J/S 全报了
初赛前一周校队仓促组织模拟赛，我已放养，不打算背那些初赛知识点了，因此被打爆。
濒临初赛，某个入非常的惨淡，家里入全跑路了，他们打算让我自己去初赛地点，路费餐费自己报销qwq
但是学校组织了大巴！
然而……初赛前一天得到通知：大巴似了，车子报废了，学校的就是不靠谱。
但！是！初赛当天蹭到了斌斌（我教练）的车！白嫖仔发力了！报销 200 块给斌斌买一袋零食，以表感谢！
在环城高速上晕车了，不嘻嘻。
然后似乎发现身份证没带……
假的。
于 8:32 来到中雅，然后与校队“五强”集结。稍作调整就拉 gjx,hyx,hutao 窜进闸机，然后发现教学楼前队排得老长，于是水 QQ，看 hyx 打音游。但是他浮木貌似不许他 van……
找到考场后闹肚子，于是在厕所水 QQ。处理完后就坐在凳子上开始发呆了。开考，近一小时砸单选题，阅读程序半个多小时就搞定了，完善程序写得更快。感觉良好。11:30 考完跑路
完善程序最后一题是猎奇的交互题，故乱蒙，挂两道扣六分。出来找人对答案，发现单选题错一堆，难绷，估分 78。
午饭怎么解决捏？蹭。和斌斌一起蹭 czh 的饭，美味。
回到中雅，在门口继续水 QQ，但是下雨没带伞，保安室角落的屋檐太窄了，又湿了。提早一小时进闸机，没事干，于是开电脑，分热点，干一些事情。颓了半小时进了考场。开考后发现单选没背诵题，光速搞定单选，用时比 J 少很多，阅读程序稍微搞得久了点，但依旧留了四十多分钟来搞定完善程序。随后开始发呆。
出来依旧对答案，但是和 czh 和 tgz 一对，发现单选就 8 个不同，他俩答案只有 3 个不同，难绷，感觉寄了。
斌斌跑路了，手机没电了，就近买了充电线拿电脑给手机充电。高德导航为我找寻地铁站。
地铁上对民间答案，发现正确率不错？单选只挂 2 道？可以想象某个入在地铁上的表情了awa，估分 84，感觉不错。
回家，写作业。
成绩出了，J76，S88，过线，躺平。
灰常遗憾，J 差预期两分，S 差预期三分……何意味？
复赛
校队赛前集训每天 2.5h 搓场数据水 + 板的模拟赛，但依旧被打爆，队里的新人还是太超标了，我们这些老一代还是当炮灰算了。
Day 0
这个入回来没有为明天的 CSP 备考，反而打起了 BA，把 Vol2 的第一部肝完了，爱丽丝棒棒哒，柯伊酱目前也还乖乖哒！
不行，我不能这么颓废下去。
最后一次模拟赛在游记里记录，思路不一定是对的。
T1：复制粘贴
初始字符串为 S，进行 N 次操作，每次将子串 [A_i, B_i) 复制插入到位置 C_i，若长度超过 M 则截断至 M。求最终字符串的前 K 个字符。
直接正序模拟不是很好做，所以我们考虑从后往前推，假设我们已经完成了所有操作，定义 P_i 表示前 K 个字符在原串 S 中的下标。我们需要求出 P_i，首先，当完成所有操作后，P_i=i，我们可以从后往前还原每个操作，分三类讨论：
- 若 C_j>P_i，则不影响 P_i 的值，直接跳过。
- 若 C_j>P_i 且 P_i \ge C_j+B_j-A_i，那么还原该操作后，P_i\gets P_i-(B_j-A_j)。
- 若 C_j>P_i 且 P_i < C_j+B_j-A_i，那么 P_i 来自复制进来的那段区间中第 P_i-C_j 个字符。那么转移为 P_i\gets A_j+P_i-C_j
还原完所有操作后输出答案即可。
T2：背单词
有 n 个互不相同的字符串，需要给它们排一个顺序，使得按以下规则计算的总代价最小：
- 若某个字符串 s 存在一个后缀字符串排在它后面，则代价 n^2。
- 否则，如果 s 没有后缀字符串，则代价为它在排列中的位置 x。
- 否则（所有后缀都在它前面），设所有后缀中位置最大的为 y，则代价为 x-y。
求最小总代价。
但我们需要考虑如何安排最优顺序使得代价最小，我们考虑贪心。对于某个字符串 $s$，其是其余若干个字符串的后缀，那么它就必须放在它们之前。我们可以发现这个关系可以构成一个树状结构，因此我们可以在先前的 dfs 中建树，并求得子树大小。然后子树越小的越应该往前处理，且每个节点的直接孩子节点与其的编号差要尽可能地小，因此我们就可以大致地猜出如下的贪心：
1. 先把所有字符串取反，插入字典树。
2. 跑一遍 dfs 建树，根节点为字典树的虚根，并统计子树大小和直接孩子节点数 $son$。
3. 把根节点插入小根堆，按子树大小排序，重复以下操作，直到堆空：
4. 把当前节点的直接孩子节点放进序列（这个不需要模拟，但需要把它们插进堆里），然后更新当前节点与其父亲节点的编号差 $eid$ ，转移式为 $eid\gets eid+son-1$。编号差即其产生的代价，更新答案即可。
5. 最后输出答案即可。
### [T3：字符合并](https://www.luogu.com.cn/problem/P3736)
给定长度为 $n$ 的 01 串，每次将相邻的 $k$ 个字符合并成一个新字符（$0$ 或 $1$），并获得对应分数。求通过若干次合并能获得的最大总分数。合并规则由长度为 $k$ 的所有 01 串对应的新字符和分数给出。
本题为石子合并变式，可以定义状态 $dp_{l,r,s}$ 表示区间 $[l,r]$ 合并成 $s$ 的最大分数，其中 $s$ 表示长度为 $k$ 的状压 01 串。
然后按区间长度从小到大枚举区间，按区间长度分两类情况：
1. 可以合并成一个字符
2. 不可以合并成一个字符
首先，合并 $k$ 个字符会使区间长度减少 $k-1$，所以我们可以通过 ```while(p >= k) p -= k - 1;``` 求出剩余字符数 $p$。
然后，对于 $p=1$ 即上述的第一种情况，枚举 $2^k$ 个状态，即长度为 $k$ 的 01 串的所以排列方式，这些状态可以通过合并规则合并成一个字符，我们可以枚举分割点 $m$ 把当前区间 $[l,r]$ 划分成 $[l,m]$ 和 $[m+1,r]$，我们可以在枚举分割点时保证 $[m+1,r]$ 可以合并成一个字母，$[l,m]$ 可以合并出剩余的字符并产生贡献 $w_s$，合并出的 01 串 $c_s$。得到以下转换方程：
$$dp_{l,r,c_s}\gets \max\left(dp_{l,r,c_s},dp_{l,m,s\gg1}+dp_{m+1,r,s\&1}+w_s\right)$$
反之，若 $p\ne1$，当前区间无法合并成一个字符，无法产生贡献，会余下长度为 $p$ 的 01 串，因此状态至多为 $2^p$ 个，就只能做普通转移，转换方程如下：
$$dp_{l,r,s}\gets \max\left(dp_{l,r,s},dp_{l,m,s\gg1}+dp_{m+1,r,s\&1}\right)$$
最后对 $[1,n]$ 中 $s$ 的所有状态取最大值即可。
### [T4：然而第六章的 A 面并没有草莓](https://vjudge.net/problem/LibreOJ-6699)
给定树，点权 $a_u$，边有双向不同权值 $w_{u,v},w_{u,v}$。进行若干次查询，问从 $u$ 到 $v$，可重复走，收益 = 首次经过的点的点权和 − 经过的边的边权和（按方向），求最大收益。
对于一个节点 $u$，其前往孩子节点 $v$ 的收益为 $a_u-w_{u,v}-w_{v,u}$。不难想到树形 DP，定义状态 $dp_u$ 表示从节点 $u$ 出发且回到节点 $u$ 可以从子树中获得的最大利益。转换方程为：
$$dp_u\gets a_u+\sum_{v是u孩子}\max\left(dp_v-w_{u,v}-w_{v,u},0\right)$$
但同时我们可以往上走，不一定只能从子树中取得利益，因此我们还要求往上走可以取得的最大利益，用状态 $f_u$ 表示。可先求出 $dp$，再进行第二次 dfs，用 $dp_u$ 算出其孩子节点的 $f_v$。转换方程为：
$$f_v\gets \max\left(f_u+dp_u-\max\left(dp_v-w_{u,v}-w_{v,u},0\right)-w_{u,v}-w_{v,u},0\right)$$
这样从 $u$ 出发可以得到的最大收益就为 $dp_u+f_u$。
但对于树链查询，其会算重，因此我们需要求出每个节点 $v$ 对其父节点 $u$ 生的贡献 $g_v$，根据转移方程可得：
$$g_v=\max\left(dp_v-w_{u,v}-w_{v,u},0\right)$$
随后，我们用预处理树上倍增，计算以下信息：
1. $dp_u$ 的和。
2. $g_u$ 的和。
3. $w_{u,v}$ 的和。
4. $w_{v,u}$ 的和。
5. LCA
这样就可以求出上述信息在从 $u$ 到 $v$ 的树链和。
分别用 $sum_1\left(u,v\right),sum_2\left(u,v\right),sum_3\left(u,v\right),sum_4\left(u,v\right)$ 表示，$LCA\left(u,v\right)$ 用 $l$ 表示。
那么每次查询的答案就为：
$$sum_1\left(u,v\right)-dp_l-sum_2\left(u,v\right)+g_l-sum_3\left(u,l\right)-sum_4\left(l,v\right)+f_l$$
那么这道题就做完了。
---
于是某个入就这么完成任务，早早睡觉觉了。
（此处应有柯伊睡觉的表情包，但我没找到）
## Day 1
早上，6 点 40 几就被赶出去蹭车了，顺便买了俩老面馒头当早餐。
又是蹭斌斌车的一天，因此又花了一百块感谢斌斌（夹杂复赛补给），这次没人指点，不知道送啥，随便乱买了点东西，后来干脆买了箱牛奶……
下雨了，顺走斌斌一把伞然后跟上大部队找到了长沙理工金盆岭，门口转悠了一阵子觉得没啥好面基的就进去了。
到考场发现与 hyx 撞车了，只隔了四个入。上午的补给是劳大饮料。
刚一坐下身旁的两个初一小朋友就不停地试探我，得知我是初三肾后马上毕恭毕敬地说了一堆 P 话，真怕他们窥我代码。8:26 完成缺省源和对排程序。8:30 就开考了，但是 8:35 监考员才收到了密码，白吃我五分钟是叭！
慢悠悠地搞完了准备工作，开始写题，并在 9 点前秒掉了前两题。于 9:01 看懂 T3，想出伪贪心做法，随后发现假了，这题要 DP。但保险起见，先打暴力。9:20 写出减枝版暴力，通过所有样例，大样例跑这么快？~~不会优化暴力可以卡过去吧~~。炫一口劳大后灵光一闪，想出正解。并于 9:42 AC T3。开 T4，花了近一个小时写出个 40 pts 的暴力。然后觉得可以 DP，搓了个暴力 DP，取得 24 pts 部分分。然后就着手像特殊性质，不久就推出 $a_i=1$ 的特殊性质做法并取得 12 pts。但感觉暴力 DP 稍微优化一下就正解了。11:34 微改后 AC T4。
这里犯糖了，11:57 脑抽了加了一个特判， $a_i=1$ 的特殊性质挂了，失去 12 pts。
总结：我是糖式，最后三分钟把 AK 送给了出题人，然后被突突兔了。
出来和 hyx 对 T4 思路发现我特殊性质伪了，难绷。然后觉得自己的石山代码一定会挂飞就没管了，今年的五级勾稳了。
中午和浮木到宾馆吃饭，但饭是家里亲手为我准备的预制菜，美味。
然后睡大觉，睁开眼就是下午了。
某个入 14:16 早早抵达机房，但是考场座位表错了，ccf 你赛外的锅是真的多。大概等了五分钟，进考场。完成缺省源和对拍程序后发现配的是渣机，满级机器十几秒完成一次小数据对拍，我打个鸡蛋，故意的吧。
开考后快速完成准备工作，看 T1 觉得不太签到，但可以贪心。随后敲了个伪贪心，获得特殊性质 $A$ 的 5 pts。然后就写暴力，获得 24 pts。增加减枝后，获得 6 pts。然后再尝试伪贪心，没过样例四，崩。
于 16:01 开 T2，发现是最小生成树，觉得可做，就没考虑 T1 的 DP 部分分了（现在想起来好后悔，干出来没准就 1= 了）。花了半个小时搓了一个 $O(2^k(m+nk)\log(m+nk))$ 的做法，并查集只路径压缩应该可以取得 48 pts。（我怎么就忘了优化并查集了啊！），随后完成特殊性质 $A$，多拿 16 pts。
17:01 去上了个厕所，觉得 T3 是哈希。回来尝试半小时后放弃，写特殊性质。结果写了一个小时，时间复杂度还是 $O(qn)$ 只获得 5 pts，不如写 T4 暴力。结果最后半小时没挣出来就下考了，输麻了。
感觉 100 分比较悬，完蛋。原地给 CCF 评测机下跪请求它跑快点（启动天河二号），数据多水一点让我多拿点分 qwq
初中最后一次比赛也是输得最彻底的一把。自入坑以来奋斗两年依旧二等，果然不是搞 OI 的料，最后一次就不能圆满一点吗 qwq
回家，发现这把是绿蓝紫黑，原地起跳，发现一个机房的几乎都 A 了 T1，直接放倒。我是 FW，一把年纪了连初一都干不过，活该退役。
然后就是写游记，作业太多了不想写了，回去和老师硬刚吧。
## Day X
太好了成绩出了，我废了！
J 组 100+100+100+100=400 -> 100+90+80+20=290
S 组 55+64+5+0=124 -> 55+80+5+0=140
综上，6√ -> 4√，获得年度最强挂分王称号！窝是废物！
谷某 T2 挂了，100+32+0+8=140，九年级输嘛了，果然老一辈就是给新人当炮灰的 qwq
估摸算着离一等就差一个暴力，诸位可以想到我此时的表情了。
搞懂 T1 的贪心为啥伪了，发现就差一点……哎呦……T2 加个优化就过了……正常发挥的话应该是 100+100+5+8=213，窝滴一等啊，窝滴七级钩啊 www
又，[窝同学都考上清华了窝是废物吗](https://news.qq.com/rain/a/20251108A02UNR00)。
半天过去……
无聊看了眼谷，发现多了五个私信……
直接呆在原地，然后看群消息……
我卡线一等了？！！！
圆梦双一等！！！
感谢 ccf 奶我 T2 到 80 分，感谢 ccf 助我 S 卡线一等！
芜湖！本赛季 SDSQ 第二代校队斩获 CSP-S 一等奖四人！是学校的第一批提高级一等选手！准备回学校听烟花！
喜报：[ARIS0_0](https://www.luogu.com.cn/user/772875) 以超过分数线 8 分的成绩斩获一等奖，这对好基友终于圆梦蓝钩。
然后……这对好基友：
悲报：[Hutao__](https://www.luogu.com.cn/user/1048620) 被卡了，貌似还被你谷蓝钩线卡了，132 分的他格外的痛苦，应该是 T2 挂成 0 分了，摸摸。
# 退役记
窝不想退役啊，信竞生的福利这么好，没了这个牌子我怎么~~摸鱼~~怎么和朋友们聊天啊……不要收我电脑啊……不要收我手机啊……哇哇哇……
你说的对，但是这个初三 oier 还是决定退役去面对现实，去面对那中考。
回顾我两年的 OI 生涯，我觉得很充实，虽然有着些许遗憾，但我很荣幸，可以接触 OI，以 oier 的身份和大家一起学习与交流。
两年前，和大多数入坑的同学们一样，我的目的也是——电脑。当然，更多的也是一份自尊吧，身处一类班却成绩不突出，贴个信竞生的牌子，也算是维持了那弱小的自尊和一点虚荣心吧，毕竟我们学校没几个信竞生，在别人看来，我很厉害，其实我自己也清楚，我的实力也就那样。
我感谢信竞，它陪伴我度过了大半个初中生活，是我在高压下坚持走下去的动力。在刚步入初一之初，周围的同学都很强，让我觉得自己啥也不是，陷入自卑、抑郁。好在家里人对我支持，让我从事信竞，也逐渐将我的信心挽回，阳光地前行。
我感谢信竞，它让我认识了许多志同道合的朋友，线下的，线上的，他们让我感到温暖、快乐。在现实里，我是一个孤僻的人，班上没什么朋友，喜欢一个人待着。在最应该交流，建立感情，体验人生最后一个单纯的友谊阶段时，选择封闭，逐步自封。而信竞，是让我融入社交的桥梁，让我感受到了人之间的温暖，让我珍惜……怀念。
现在，我即将退役，说明我将要失去上述的一切，回到最开始的那段黑暗的时光。但，我知道，我见过光明，我不会忘记。信竞给予了我信心，给予了我友谊，但这不代表退役后我会失去信心，我会失去友谊。朋友们还在等我，我会努力，去完成当前更为重要的挑战。
老实说，信竞确实拖累了我很多，致使我无法全心投入文化课的学习，使我的成绩始终在班级末尾徘徊。但，我不后悔，因为它是坚持下来的动力，是我的人生中重要的一笔。现在暂时的退役，也是为了未来更好地在赛场上角逐。因此，我不抱有遗憾。
感谢这段时间教导过我的教练：
逐月的杨教练。
童程童美的王教练。
校队的陈教练。
梦熊北京营的刘教练。
感谢你们对我的细心栽培与指导，希望你们未来工作顺利，培养出更多的精英。
感谢这段时间陪伴过我的同学：
校队的：[GJX_Algorithm](https://www.luogu.com.cn/user/617020)，[_Chronostatis_
](https://www.luogu.com.cn/user/768951)，[Hutao__](https://www.luogu.com.cn/user/1048620)。
集训营的：[SPJ2026](https://www.luogu.com.cn/user/957277)，[T_Z_H](https://www.luogu.com.cn/user/983251)，[Yuriha](https://www.luogu.com.cn/user/504979)，[New_Void](https://www.luogu.com.cn/user/1048576)。
以及 [ARIS0_0](https://www.luogu.com.cn/user/772875) 和其他谷上朋友。
感谢你们陪伴我的时光，它们让我怀念，让我充满希望。希望你们可以继续在 OI 这条充满挑战的道路上砥砺前行，成为理想中的那个自己！
致此，别过。
最后，@[ARIS0_0](https://www.luogu.com.cn/user/772875)
