wmc的CSPS2025游记

· · 生活·游记

转眼又是一年过去了啊，这也是我作为 OIER 的最后一个赛季，最后28天希望能不留遗憾吧。\ 由于去年成绩并不好，被勒令专心学了一年的 whk（其实 whk 成绩也并不怎么样），裸考首轮 74 分通过，在完全没有任何准备，仅复习了 NOI Linux 基本操作的情况下来到了武汉 （这里蛐蛐一句 HBOI 全面使用 Linux）\ 周六早 8 点上火车，10 点到达汉口站，乘坐地铁前往华中科技大学。由于时间尚早，约 11 点到达了光谷世界城吃（chu）饭（qin），赶路期间一直在看各种 dp 、图论模板代码。地铁上顺便还凹了个一刀 EX（）\ 然后发现世界城居然有 wmdx，于是临时决定和同队的两位队友一起出勤，抽排队时间吃饭，此时还在笑谈手感守恒（之后xxseven大佬也赶来了）。结果服务器抽风导致时间被拖延，最后差点没赶上进场（警示后人，不要在考试前进行你无法控制结束时间的活动）

13:45，YLOI集合完毕，准备进场。 与一中的朋友们互相祝了RP++，这次和去年在同一个考场。

14:30，时间到，我的OI最后一舞正式开始。不是很熟练地创建好文件夹，写好代码框架，打开PDF开始看题。

T1

初看题，总结题意，共 n ( n为偶数 ) 个元素，每个元素有 3 个权值，从每个元素的 3 个权值中选一个求和，求没有权值下标被选中大于 n/2 次的前提下最大权值和。\ 首先想到贪心和 DP 。初步构思了一下 DP 的状态设计和转移，发现这个问题的转移貌似相当复杂，因为选择会对之后的选择造成影响。于是初步确定使用贪心策略。首先想出的处理方式是以某一个下标权值为第一关键字优先选出 n/2 个人，然后去分配剩下的 n/2 个人。\ 然而，略一思考，我对这个策略举出了无法解决的实例：若 n = 2 ,两人的权值分别为(200,150,0)，(100，0，0)，如果按照上述方法以下标 1 的权值进行选择，那么会使最终的权值和为 200 ，然而显然存在更优解能够使权值和达到 250。 此时的时间是 3:10 。\ 注意到可能存在某种情况下的最优解，使每个社团都不招满 n/2 人，因此我完全放弃了优先分配的方法。\ 这时，我注意到题目中刷黑的字“偶数”和“n/2”。强调这些用意何在？可以发现如果某社团招满 n/2 人，剩下的人可以自由安排最优解，因为剩下 n/2 人不可能再超出限制。\ 很奇怪地，我想起了whk老师告诉我们关于gk报志愿调剂专业的一些事，我猛然醒悟：这道题的关键就在此处！

先满足所有人的要求，然后把超出部分的人调剂到他第二满意的社团即可！这样，一个社团为 n/2 人，剩下两个社团人数之和也为 n/2 人，完全满足要求！应该怎么决定调剂谁呢？发现如果调剂某人，从他的最大满意度变为次大满意度会对理想答案产生负的贡献，我们需求答案最大，把这个负贡献按绝对值从小到大排，一个一个调剂，直到人数满足条件，这样得到的就是最优解！开码！

代码花了30分钟，调了15分钟，期间自查发现了包括\ 多测未清空数组\ sort范围过大\ 等问题，被我一一解决\ 最后一个大样例通过，此时时间4:00

T2

初读题，一眼最小生成树。 细读题，节点分两类：所有城市原本就已经连通，说明存在一个原图的最小生成树。乡镇建造费用只计算一次，可以向所有城市（已经注意到只有城市）建边。题目的要求是所有原图中的点联通。这表示我们需要选择性地建造乡镇。一开始考虑直接一次 Kruskal 求最小生成树，对由乡镇引出的边进行附加权值的计算。但是发现这样行不通，因为无法解决乡镇建造费用的计算。发现乡镇数量最大为10，n的最大值为10的4次方，考虑对所有乡镇的是否建造情况进行一个状态压缩的枚举。全集大小为 2047，叠加kruskal和路径压缩并查集的复杂度，是可以接受的。提前将所有边（包括乡镇边）加入边集，加边时先判断是否为乡镇边以及乡镇是否建立，即可通过此题。

读题+思考+码+调试 一共花了1h

期间发现诸如最大值开得太小、全集过大等问题。

最后有惊无险通过大样例，此时时间5:00。

T3

怎么是字符串啊，怎么还要匹配啊，我不会kmp和AC自动机啊\ track skip（）

T4

初看感觉可做，如果把每个排列按位组成一个数字从小到大遍历，那么可录用人数是单调不升的。但是n最多500，这就会产生天量数字，是不行的，思考了20min，果断开始写部分分。最后特殊性质拿到8分没时间写暴力了。

6:30，美美撤离

最终估分100+100+0+8 = 208/400\ 美美撤离！\ 说实话，我自己都没料到能做出两道题，听xxseven大佬说t2是蓝我都懵了，对这个结果还算挺满意的，至少不会因为考前wm被蛐蛐了（

最后在返程火车上打了一路的雀()

总而言之，这次CSPS经历有惊无险，其实路途中我的感触还挺多的，不过要既然还有机会备战NOIP，这些话就等到NOIP考完再来慢慢讲出来。

OI对我而言不仅是一门竞赛，更是我热爱的东西，它见证了我从一个跳脱的显眼包经历许多事情成长为一个成熟的人的全部过程，也在其中有不小的影响。OI，和它给我带来的伙伴们，是我的青春里最难以忘却的美好。

行了，既然获得了继续竞争的资格，就把离别的话留到最后吧

28天，NOIP加油！

// 11/4更新：回来复刻代码算了下复杂度，T2假了（所以最终分数应该只有168