CSP 2025 追忆
声明
追忆阴魂不散。
坐标JS，J组整了活欢迎去查但是爆炸了。不接受开盒。
正文
我常常追忆过去。
很好的CSPS2024压线一等，NOIP反向挂分奈何期望过低。很好的NOIP模拟赛311->74，机房九人稳居排名前十。
由于我不是高贵的氪金用户，因此我需要考初赛。pst的J组“只考了三位数”，显然是405分。
生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。
J组开赛。
A需要脑子吗。B需要脑子吗。C需要脑子吗。D需要……哦好像需要。
浅浅背包（?）一下，期间写炸了一发，最终使用1h+ AK。
罚坐。期间学会了让我们说中文和修改codeblocks的garner时间。
出考场，认为难度红红橙黄，but经过和某人的沟通意外发现自己的C的数组大小假了，要开
云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。
经过赛后讨论，得出人均400的暴论。卒。南部新城的食堂不作评价，前面忘了，反正能吃，后面忘了。
中午拉了一帮OIer蹴，完成了1防4的壮举，然后被八打一爆了。
考S组，由于蹴得太久错过了整队，于是直接莽去了机房，怎么门口还要排队啊。
开赛。这是A？
10min后大概有了思路，先贪心分配，然后多轮微调？等一下是
B题怎么做，我不会不会B了吧。草稿纸手搓了几组数据和特殊情况后仍然未注意到性质，此时总时间已经过去1h。怎么办怎么办怎么办。
考虑爆搜，每次枚举城市化什么然后加入边集，排序，求最小生成树。这样显然是拿不到全分的，猜测了几个性质后均错误，于是先去打了C和D的暴力压压惊。
追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。
拜了拜zeyuanliu，好像会了C的A性质，写写写，回去看B。
在心态爆炸濒临AFO的边缘突然想到每次重新排序所有的边集显然是多余的，因为有一大半都不需要修改（原边），所以想到了先预排序原边，然后每次枚举后加入新边并合并排序，可以大幅降低复杂度。
写了，效果显著，大样例最慢0.8s。然而考场上没有想到一个重要的优化：其实可以对所有边预排序，省掉每次check里面的log（考场上以为这里是log k所以没有在意，但我排序的是边所以是log nk！）。也可以只留下原图最小生成树里面的边，不用一遍遍跑那些不可能用到的边。随便挑一个都能让我代码的速度再翻一倍。
引用一篇tj：
对于原图，只需要保留其 Kruskal 最小生成树。因为其余边显然没有竞争力。
求出原图 Kruskal 最小生成树后，我们可以对 n−1+kn 条边预排序，然后暴力枚举改造集合，暴力求最小生成树。离它就差一步，但就是这一步让我-20pts。
警示后人。
出考场，估分100+100+?+?，预计200\~272，最终217。北都内城文教园年七（可能）。
又一次卡在了退役的边缘。
下面引用《追忆》的最后一段话结尾吧，文采远比我强还生动形象地表达了我的感受。
曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。
过去已经凝固，我带着回忆向前。
我该在哪里停留？我问我自己。