CSP J／S 2025-复赛
0.前言
上高中后，学校终于有OI训练了。在初中的时候，都是自己在暑假跟着机构随便学学，没有什么明确的目标，如今有了些许方向。
课余的时间虽然被占掉了一部分，但能摸摸电脑，与计算机技术相伴，也算值得
初赛的分数还算理想，顺利拿到了复赛的入场券（初赛详见CSP J／S 2025-初赛）
1. 故事的前页
在学校的时候，复习了一些板子，比如线段树啥的 虽然这次并没有用到
回家后，又复习了一下图论相关内容，搞了一下堆优化SPFA，同时准备了一下freopen模板之类的东西。上次用freopen还是一年前，如果不时不时拂去上面的尘埃，这确实会变得陌生
吃过午饭，天光正好，该动身了
2. 踏上征途
CCF似乎总是喜欢让考试地点与“遥远”二字结缘
这次的目的地是深圳外国语学校高中园，四十多公里的路程，即便驱车也需近一个小时。
在路途中小憩，再睁眼时，窗外的风景已然变换——市中心紧凑的楼宇悄然退去，大片绿地舒展着，点缀着几排香蕉树，这是在市中心不曾见过的。
下车，走到南门进去。这次相比上次确实好了许多，没几辆车，至少免去了那份赛前的焦灼
迈入学校，赞叹从心中涌上来，这是一座崭新而宏大的校园，硬件设施的优势不言而喻，连操场似乎都望不到尽头。
顺着一道架空层中的小径，更大的一片绿茵场映入眼帘。遇上同学，寒暄几句，互相鼓励一番，就静候去考场了。rp++;
甚至还看到了我们学校同款的一体机）
照往常来看，到了两点零六，理应放我们进考场了。但是还是把我们留在下面。
到十三分，往常似乎我们应该已经坐在电脑前了，但是依然没放我们上楼。空气中渐渐弥漫着焦灼，当然也不乏一些有趣的猜测:
- 电脑死机了
- 考题和程序是手动用U盘拷的
- 考场烧起来了
两点十五分，终于能上考场了。一群人涌上楼梯，盘旋至五楼。
爬上五楼，从上空俯视，才更能感受到这校园的宏大与静谧
不过，这校园外很清净，远处没什么高大的天际线，干脆利落。
3. 正式比赛
当在位置上坐定，已经28分了。压缩包已经可以解压了CCF在干什么
把dev c艹的格式化快捷键修改一下，windows10切个深色模式，来看看题吧。
一眼看过去，这次的题面长度都还行，没有去年那种又臭又长的一大长串题面了。而且CCF的配置也更新了，去年的评测机还是i7 8700k 32GB 来着，今年换成Ultra 9 96GB 了
第一题，似乎是贪心？当时感觉难度不会太大。第二题一眼图论，第三题字符串....不是我能碰的，第四题混个部分分也不算困难
那么，第一题，开干！
P1 club
把人分到三个俱乐部里面，让总满意度最大？
似乎不是很困难 贪心一下他们最想去的就行了。
但是尝试一下手跑样例，怎么跑不出来呢.jpg
记事本和画图对这题来说有点力不从心了，甚至还没计算器，只能开个python代替。
想了一会，只能开个Excel表格来做一些基本的处理了。填好数据，写几个公式，确实挺方便模拟
首先尝试一下最简单的规则，按他们对不同club的满意度来选，如果第一个已经满了就第二个，每个里面按照贡献的满意度来选择留下还是换。
可惜，这没奏效，最后总贡献偏少。
细细观察一下，似乎这个需要看他换之后的贡献度，如果换掉之后少了一大截，得不偿失。所以引入Delta作为三个满意度之间的差值，按差值自小到大来选，换的代价越小，就越优先换
这次，几乎要成功了，虽然差20，但是就当我算错了吧，无所谓了
然后开始动手实现，照例使用结构体（数组是坏文明）
大致思路是先处理出每个人对选择的倾向性（优先选满意度最高的）然后按照最高的倾向和第二高的倾向Delta排序，把Delta最小的排在最前面。最后，根据倾向性数组把这些Delta最小的发送到第二倾向性的club里面，重复处理。
为了处理完全，写了个循环，重复处理三次。
而且，因为我忘记STL的方法了，而且Dev C++的补全....不敢恭维，所以为了去掉vector里面的第一个元素，用了一个临时vector进行中转...
好抽象，为什么我没想起来 earse方法
最后写了150多行代码，真的是屎山了。
不过好在，所有样例均通过了。居然不用调我是没想到的。一开始最后的极大样例没过，开了cin/cout优化后就能过了，0.5s，希望不会TLE。滥用vector的后果就是极大的常数
看起来代码复杂度过高还是会丢分的，用vector有指针越界，而且在最开始的时候没有处理好flag，会出现把一个人多次压入不同的club的情况，最后喜丢25pts为什么我们需要rust
P2 road
要我们求最小生成树，但是有额外的节点，提供一定的开销后可以有更小的路径。
想半天没想出思路，写了个最小生成树，把那四个没有额外节点的题给过了（
最小生成树给我干挂了，本来应该循环边的，循环成节点了
P3 replace
字符串的题，这是真的一点思路没有了。
看题目样例有输出一堆0的情况，那就写个简单的输入输出一堆0，退而求其次吧。
一分没有
P4 employ
让我们计算一下雇佣方案....
感觉正解应该需要dp之类的递推（？反正我是没想出来
打个dfs，拿两个点算了，加个剪枝，剩下就看造化了。
而且这状态数也多的离谱，记忆化优化不是很能加的样子（似乎可以状态压缩（？）
八分，两个暴力的点。不过本来输出0也可以再混个4分的，没拿到
4. 赛场之后
取消掉最后一道题的输入/输出的注释，剩余的时间已经不足15分钟了。匆匆检查一下各种文件，确认无误，两手一摊，听天由命吧。
至少，终究是有些进步的，相比上次发呆几个小时好多了，至少能让双眼、大脑、双手有些事情做
踏出机房，日暮已然西沉，留下一片寂静的夜空。找一辆共享单车，滑向远处的地铁站。归途路漫漫，耗时两个小时的车程，正适合写下本文的一部分
这段旅程，也就画上了一个分号。
5. 后记
最后只拿了83分，还是没打过去年的自己。
不过今年的T1确实难度略高，而且代码复杂性肯定是比去年高的。
所以，希望还是能顺利进入NOIP，这样这几分的差距也就无所谓了。