2025 CSP-S游记

省流：人麻了，真就不知道啥感觉，浑浑噩噩的处于有分和没分之间。

（PS：我都有点怕我第一题爆掉真就退役了）

考前杂记

• 前一天晚上在洛谷犇犇敲赛博木鱼。rp++;

• 考试那天白天没去上文化课，在机房先是摸鱼爽，后来把线段树模板、dijkstra、SPFA之类的打打熟，翻了翻NOI大纲发现多了个扫描线和马拉车就把马拉车学了一下。

• WS说他昨天做梦给杜子德嗦了半个小时，梦见第一道贪心、第二道图论、第三道字符串、难度分布绿蓝紫紫。

• 在路上的时候睡不着，想着不睡会犯困，躺来躺去差点把脖子扭了。

前一小时T1

T1：P14361 [CSP-S 2025] 社团招新 / club（民间数据） - 洛谷

差不多黄题（实则绿题）贪心，我第一遍想太简单了，直接把 a_i,b_i,c_i 三组打散存进去排序，写了个 struct 代表第几个之类的数据维护，然后小样例就过不了…还好小样例就把我卡过了不然还要找好久。

然后就思考在草稿纸上画了一下，想了一下是不是dp背包之类的，要是它是背包的话它可能要维护数到第k个、a组取了几个、b组取了几个、c组取了几个，总共四维dp肯定炸。

继续思考，应该还是贪心算法，考虑到每组都能取 n/2 个，即使不能取到 a_i,b_i,c_i 中的最大值也能求其次取到次大值。看到 1.in 的第三组，直接取10并非最优，可能要反悔贪心（但是我写不来）。这时候我发现如果最大值和次大值相差不大时，可能可以取次大值，为后面的数据创造机会；反之如果最大值和次大值相差大时，那肯定取最大值贡献更大。这样就保存最大值和次大值及其属于的组，然后照着差排序一下，取过去，最大值那组满了就取次大值那组。

struct  node  {

int fir;//最大值

int fig;//first group 最大值属于的组

int sec;//次大值

int seg;//second group 次大值属于的组

}  abc[114514];

bool  cmp(node  x,node  y)  {

return  x.fir-x.sec>y.fir-y.sec;

}

后两个小时T2

T2：P14362 [CSP-S 2025] 道路修复 / road（民间数据） - 洛谷

这道真麻了。

一眼最小生成树，调了好久（去年似乎也是T2卡好久，去年大模拟😭）。他有那个特别的村庄节点，这个怎么处理一下呢，就是说当它还没有加入树里面的时候加上建设它的费用作为边权，再从它扩展出去的时候就不要用建设的费用了。再开个 used 的数组来存这个点有没有用到过，fa 数组存是哪个地方绑过来的 ，最后跑完生成树后减掉没用过的村庄。

一小时一气呵成，小样例一遍过，然后不出意外地出事了：样例2跑的异常缓慢跑到1.7s，样例3直接爆了，检查了一下没想那么多，以为是哪里越界了，结果一堆事调不出来。

• 因为用了优先队列，我写了一堆 pair<int,pair<int,int> > 之类的东西，这种严重影响了我自己看代码的效率。

• 我用的邻接表，于是把每个vector的size都输出了一遍，在大数据下前面几百个还是多少可能因为MLE炸了，输出了很奇怪的数字。

• 我查了一遍它那个输入发现有很多点重复，得用邻接矩阵，但我史山都已经堆完了再全改也不大现实，于是我写了个先跑邻接矩阵再转到邻接表的输入。（？

• 当时跑了一下1.04s差不多。我想着再优化一下争取多过一点，将遍历边的循环换成 auto 了，我也不知道CSP里面能不能用，要是不能用就全炸了😭。（而且这样打了以后没啥显著效果。）

• 就这土它图论史山我写了好久。

考完以后才知道不能用优先队列维护边，复杂度 O(m\log m)，但是要知道他家 m 有 1e7 哎。比较正确的做法是每次跑点上的边松弛一下，再枚举点集找下一个距离最小的点，复杂度 O(n^2)。n 取到 1e5 似乎也没啥区别，但应该是能跑过 n\le 1000 的所有点的，前者它那个点给你塞一堆重复边，加上我邻接表转邻接矩阵之类的神人操作，以至于跑的还是很慢Orz。

最后一个小时挣扎的T3,T4

T3：P14363 [CSP-S 2025] 谐音替换 / replace（暂无数据） - 洛谷

T4：P14364 [CSP-S 2025] 员工招聘 / employ（民间数据） - 洛谷

先看的T4，于是打了个递归暴力成功打炸了（上次似乎也是这个结局，浪费三十分钟）

考试前提前买了瓶大水，一紧张就喝水，我打了一下T4膀胱肿胀…（比一次赛开赛一个小时的时候出去了一次，快结束的时候又出去了一次…）

再看T3，一眼哈希，当时我看到T3的时候真的单纯以为它是每个规定可替换字串先求哈希，对于每次询问，哈希扫一下搞到下标以后去第二个字符串上再扫一遍，最后比较其余部分，只用 O(n) 扫一遍跑的飞快。我在想没早点打到T3真是可惜了。（赛后一看洛谷不是我能做的，好像是AC自动机。）

还有5分钟的时候已经差不多放弃了，我在注释里面写了些莫名其妙的东西，好像直接写中文会变成锟斤拷，我就打拼音和Chinglish，大致这种。

//Why I have no time?It is a easy Hash?!****

//No Li Back Sky (后期：无力回天)

//Wu Li Hui Tian

  

//wo de bei shang~ shi shui zuo de~ （后期：我的悲伤是水做的）

  
  

//CCF I give you too much money you make me ac T2 plz

//**** *** Why MLE

当时我看洛谷水帖的时候感觉这种好抽象没想到自己到最后也只能沦为别人的笑柄。

后

和同学们一起回来他们战况也差不多，我们指导老师给我们买了两个肯德基的整鸡（实际上我觉得还是汉堡简单一点吃起来也方便，但有总比没有好谢谢指导老师Orz，那个鸡的皮比较好吃，里面的肉有股树叶的味道可能撒了什么特色香料理吧）。

哎一言难尽睡觉了。