专栏文章

CSP 2025 游记 & 退役记

KKei__
生活·游记参与者 8已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@minjyyyy
此快照首次捕获于
2025/12/02 03:39
3 个月前
此快照最后确认于
2025/12/02 03:39
3 个月前
查看原文

初赛

某个如去年没拿 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：复制粘贴

初始字符串为 SS，进行 N 次操作，每次将子串 [Ai,Bi)[A_i, B_i) 复制插入到位置 CiC_i，若长度超过 MM 则截断至 MM。求最终字符串的前 KK 个字符。
直接正序模拟不是很好做，所以我们考虑从后往前推，假设我们已经完成了所有操作，定义 PiP_i 表示前 KK 个字符在原串 SS 中的下标。我们需要求出 PiP_i，首先，当完成所有操作后，Pi=iP_i=i，我们可以从后往前还原每个操作，分三类讨论：
  1. 若 Cj>PiC_j>P_i，则不影响 PiP_i 的值，直接跳过。
  2. 若 Cj>PiC_j>P_i 且 Pi≥Cj+Bj−AiP_i \ge C_j+B_j-A_i，那么还原该操作后，Pi←Pi−(Bj−Aj)P_i\gets P_i-(B_j-A_j)。
  3. 若 Cj>PiC_j>P_i 且 Pi<Cj+Bj−AiP_i < C_j+B_j-A_i，那么 PiP_i 来自复制进来的那段区间中第 Pi−CjP_i-C_j 个字符。那么转移为 Pi←Aj+Pi−CjP_i\gets A_j+P_i-C_j
还原完所有操作后输出答案即可。

T2：背单词

有 nn 个互不相同的字符串，需要给它们排一个顺序，使得按以下规则计算的总代价最小：
  • 若某个字符串 ss 存在一个后缀字符串排在它后面，则代价 n2n^2。
  • 否则，如果 ss 没有后缀字符串，则代价为它在排列中的位置 xx。
  • 否则（所有后缀都在它前面），设所有后缀中位置最大的为 yy，则代价为 x−yx-y。
求最小总代价。
n2n^2 的代价显然要规避，即满足某个字符串 ss 之后不存在其后缀。判断哪些字符串是哪些字符串的后缀，可以无脑 Trie，每个字符串取反后插入 Trie，然后跑一遍 dfs 即可。
但我们需要考虑如何安排最优顺序使得代价最小，我们考虑贪心。对于某个字符串 ss，其是其余若干个字符串的后缀，那么它就必须放在它们之前。我们可以发现这个关系可以构成一个树状结构，因此我们可以在先前的 dfs 中建树，并求得子树大小。然后子树越小的越应该往前处理，且每个节点的直接孩子节点与其的编号差要尽可能地小，因此我们就可以大致地猜出如下的贪心：
  1. 先把所有字符串取反，插入字典树。
  2. 跑一遍 dfs 建树，根节点为字典树的虚根，并统计子树大小和直接孩子节点数 sonson。
  3. 把根节点插入小根堆，按子树大小排序，重复以下操作，直到堆空：
  4. 把当前节点的直接孩子节点放进序列（这个不需要模拟，但需要把它们插进堆里），然后更新当前节点与其父亲节点的编号差 eideid ，转移式为 eid←eid+son−1eid\gets eid+son-1。编号差即其产生的代价，更新答案即可。
  5. 最后输出答案即可。

T3：字符合并

给定长度为 nn 的 01 串，每次将相邻的 kk 个字符合并成一个新字符（00 或 11），并获得对应分数。求通过若干次合并能获得的最大总分数。合并规则由长度为 kk 的所有 01 串对应的新字符和分数给出。
本题为石子合并变式，可以定义状态 dpl,r,sdp_{l,r,s} 表示区间 [l,r][l,r] 合并成 ss 的最大分数，其中 ss 表示长度为 kk 的状压 01 串。
然后按区间长度从小到大枚举区间，按区间长度分两类情况：
  1. 可以合并成一个字符
  2. 不可以合并成一个字符
首先，合并 kk 个字符会使区间长度减少 k−1k-1，所以我们可以通过 while(p >= k) p -= k - 1; 求出剩余字符数 pp。
然后，对于 p=1p=1 即上述的第一种情况，枚举 2k2^k 个状态，即长度为 kk 的 01 串的所以排列方式，这些状态可以通过合并规则合并成一个字符，我们可以枚举分割点 mm 把当前区间 [l,r][l,r] 划分成 [l,m][l,m] 和 [m+1,r][m+1,r]，我们可以在枚举分割点时保证 [m+1,r][m+1,r] 可以合并成一个字母，[l,m][l,m] 可以合并出剩余的字符并产生贡献 wsw_s，合并出的 01 串 csc_s。得到以下转换方程：
dpl,r,cs←max⁡(dpl,r,cs,dpl,m,s≫1+dpm+1,r,s&1+ws)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≠1p\ne1，当前区间无法合并成一个字符，无法产生贡献，会余下长度为 pp 的 01 串，因此状态至多为 2p2^p 个，就只能做普通转移，转换方程如下：
dpl,r,s←max⁡(dpl,r,s,dpl,m,s≫1+dpm+1,r,s&1)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][1,n] 中 ss 的所有状态取最大值即可。

T4：然而第六章的 A 面并没有草莓

给定树，点权 aua_u，边有双向不同权值 wu,v,wu,vw_{u,v},w_{u,v}。进行若干次查询，问从 uu 到 vv，可重复走，收益 = 首次经过的点的点权和 − 经过的边的边权和（按方向），求最大收益。
对于一个节点 uu，其前往孩子节点 vv 的收益为 au−wu,v−wv,ua_u-w_{u,v}-w_{v,u}。不难想到树形 DP，定义状态 dpudp_u 表示从节点 uu 出发且回到节点 uu 可以从子树中获得的最大利益。转换方程为：
dpu←au+∑v是u孩子max⁡(dpv−wu,v−wv,u,0)dp_u\gets a_u+\sum_{v是u孩子}\max\left(dp_v-w_{u,v}-w_{v,u},0\right)
但同时我们可以往上走，不一定只能从子树中取得利益，因此我们还要求往上走可以取得的最大利益，用状态 fuf_u 表示。可先求出 dpdp，再进行第二次 dfs，用 dpudp_u 算出其孩子节点的 fvf_v。转换方程为：
fv←max⁡(fu+dpu−max⁡(dpv−wu,v−wv,u,0)−wu,v−wv,u,0)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)
这样从 uu 出发可以得到的最大收益就为 dpu+fudp_u+f_u。
但对于树链查询，其会算重，因此我们需要求出每个节点 vv 对其父节点 uu 生的贡献 gvg_v，根据转移方程可得：
gv=max⁡(dpv−wu,v−wv,u,0)g_v=\max\left(dp_v-w_{u,v}-w_{v,u},0\right)
随后，我们用预处理树上倍增，计算以下信息：
  1. dpudp_u 的和。
  2. gug_u 的和。
  3. wu,vw_{u,v} 的和。
  4. wv,uw_{v,u} 的和。
  5. LCA
这样就可以求出上述信息在从 uu 到 vv 的树链和。
分别用 sum1(u,v),sum2(u,v),sum3(u,v),sum4(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(u,v)LCA\left(u,v\right) 用 ll 表示。
那么每次查询的答案就为：
sum1(u,v)−dpl−sum2(u,v)+gl−sum3(u,l)−sum4(l,v)+flsum_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 部分分。然后就着手像特殊性质，不久就推出 ai=1a_i=1 的特殊性质做法并取得 12 pts。但感觉暴力 DP 稍微优化一下就正解了。11:34 微改后 AC T4。
这里犯糖了，11:57 脑抽了加了一个特判， ai=1a_i=1 的特殊性质挂了，失去 12 pts。
总结：我是糖式，最后三分钟把 AK 送给了出题人，然后被突突兔了。
出来和 hyx 对 T4 思路发现我特殊性质伪了，难绷。然后觉得自己的石山代码一定会挂飞就没管了，今年的五级勾稳了。
中午和浮木到宾馆吃饭，但饭是家里亲手为我准备的预制菜，美味。
然后睡大觉，睁开眼就是下午了。
某个入 14:16 早早抵达机房，但是考场座位表错了，ccf 你赛外的锅是真的多。大概等了五分钟，进考场。完成缺省源和对拍程序后发现配的是渣机，满级机器十几秒完成一次小数据对拍，我打个鸡蛋，故意的吧。
开考后快速完成准备工作，看 T1 觉得不太签到，但可以贪心。随后敲了个伪贪心，获得特殊性质 AA 的 5 pts。然后就写暴力，获得 24 pts。增加减枝后，获得 6 pts。然后再尝试伪贪心，没过样例四，崩。
于 16:01 开 T2，发现是最小生成树，觉得可做，就没考虑 T1 的 DP 部分分了（现在想起来好后悔，干出来没准就 1= 了）。花了半个小时搓了一个 O(2k(m+nk)log⁡(m+nk))O(2^k(m+nk)\log(m+nk)) 的做法，并查集只路径压缩应该可以取得 48 pts。（我怎么就忘了优化并查集了啊！），随后完成特殊性质 AA，多拿 16 pts。
17:01 去上了个厕所，觉得 T3 是哈希。回来尝试半小时后放弃，写特殊性质。结果写了一个小时，时间复杂度还是 O(qn)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
又，窝同学都考上清华了窝是废物吗。
半天过去……
无聊看了眼谷，发现多了五个私信……
直接呆在原地，然后看群消息……
我卡线一等了？！！！
圆梦双一等！！！
感谢 ccf 奶我 T2 到 80 分，感谢 ccf 助我 S 卡线一等！
芜湖！本赛季 SDSQ 第二代校队斩获 CSP-S 一等奖四人！是学校的第一批提高级一等选手！准备回学校听烟花！
喜报：ARIS0_0 以超过分数线 8 分的成绩斩获一等奖，这对好基友终于圆梦蓝钩。
然后……这对好基友：
悲报：Hutao__ 被卡了，貌似还被你谷蓝钩线卡了，132 分的他格外的痛苦，应该是 T2 挂成 0 分了，摸摸。

退役记

窝不想退役啊，信竞生的福利这么好，没了这个牌子我怎么摸鱼怎么和朋友们聊天啊……不要收我电脑啊……不要收我手机啊……哇哇哇……
爱丽丝哭脸
你说的对，但是这个初三 oier 还是决定退役去面对现实，去面对那中考。
回顾我两年的 OI 生涯，我觉得很充实，虽然有着些许遗憾，但我很荣幸，可以接触 OI，以 oier 的身份和大家一起学习与交流。
两年前，和大多数入坑的同学们一样，我的目的也是——电脑。当然，更多的也是一份自尊吧，身处一类班却成绩不突出，贴个信竞生的牌子，也算是维持了那弱小的自尊和一点虚荣心吧，毕竟我们学校没几个信竞生，在别人看来，我很厉害，其实我自己也清楚，我的实力也就那样。
我感谢信竞，它陪伴我度过了大半个初中生活，是我在高压下坚持走下去的动力。在刚步入初一之初，周围的同学都很强，让我觉得自己啥也不是，陷入自卑、抑郁。好在家里人对我支持，让我从事信竞，也逐渐将我的信心挽回，阳光地前行。
我感谢信竞，它让我认识了许多志同道合的朋友，线下的，线上的，他们让我感到温暖、快乐。在现实里，我是一个孤僻的人，班上没什么朋友，喜欢一个人待着。在最应该交流，建立感情，体验人生最后一个单纯的友谊阶段时，选择封闭，逐步自封。而信竞，是让我融入社交的桥梁，让我感受到了人之间的温暖，让我珍惜……怀念。
现在，我即将退役，说明我将要失去上述的一切，回到最开始的那段黑暗的时光。但，我知道，我见过光明，我不会忘记。信竞给予了我信心，给予了我友谊，但这不代表退役后我会失去信心，我会失去友谊。朋友们还在等我，我会努力，去完成当前更为重要的挑战。
老实说，信竞确实拖累了我很多，致使我无法全心投入文化课的学习，使我的成绩始终在班级末尾徘徊。但，我不后悔，因为它是坚持下来的动力，是我的人生中重要的一笔。现在暂时的退役，也是为了未来更好地在赛场上角逐。因此，我不抱有遗憾。
感谢这段时间教导过我的教练：
逐月的杨教练。
童程童美的王教练。
校队的陈教练。
梦熊北京营的刘教练。
感谢你们对我的细心栽培与指导，希望你们未来工作顺利，培养出更多的精英。
感谢这段时间陪伴过我的同学：
校队的：GJX_Algorithm，Chronostatis ，Hutao__。
集训营的：SPJ2026，T_Z_H，Yuriha，New_Void。
以及 ARIS0_0 和其他谷上朋友。
感谢你们陪伴我的时光，它们让我怀念，让我充满希望。希望你们可以继续在 OI 这条充满挑战的道路上砥砺前行，成为理想中的那个自己！
致此，别过。
最后，ARIS0_0

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...