CSP2025第二轮游寄

· · 生活·游记

坐标 \text{NX}，目标 \ne 0，估分 [0,100]. 感觉要碎了呜呜

赛大前

这一周过的都不怎么顺利...状态不是很好。

不过对于CSP到是心态放的很平，去年参加CSP/S的高中生比NOIP名额都要少，所以只要不爆 0 其实没什么可怕的。

晚上想随便打道题就睡觉，随机了一道黄题花半个小时写了一个DP然后测试后发现是错解。然后换了一道橙题写完发现又想错啦！本来想增强增强自信力的结果反而打击了我QAQ. 计划九点休息最后十一点才躺床上。

赛前

早上九点起床，写了一套数学卷子，和 rj 玩了会儿MCw。到了一点，准备睡一小时养精蓄锐，在床上翻来覆去根本睡不着，虽然目标定的这样但还是害怕爆零。

躺了半个小时一想貌似不对啊，车程就得要一个小时，我这躺到两点不直接迟到了嘛，然后着急忙慌的拿了个文件袋装了点吃的就走了，呜呜好笨啊。

车上，还是好紧张看了看对拍、倍增和树状数组。到了考场门口，问教练今年是怎么递交的，教练说今年是给个网址在那上面下载题目和提交程序，只用把程序提交上去就可以了，所以不会出现哪些文件夹的问题了。那很好了

赛时

进入

在NX大学，有两间屋子，大概有近百人参加，好庞大。坐了五分钟后终于解除黑屏了

下载

进入网址登录，下载题目给我吓一雷，这压缩包名字还叫的CSPJ，打开pdf发现是提高级的就开始答卷了。

读题

用了30min读题，T1不就是个贪心+模拟，依旧是橙嘛；T2图加个并查集，最多是个绿；T3T4读完了想到了零个思路，我甚至连暴力怎么打都不知道。读完后想到蓝钩很激动啊喵！

T1

T1初步思考，每个人都只选他对这 3 个部门里头最满意的不就可以了嘛。进一步思考不对啊，那 \displaystyle\frac{n}{2} 这个条件怎么贪啊qwq。

写了写第二个样例发现，如果选一个部门的人数超过了 \displaystyle\frac{n}{2}，那么选其他两个部门的人数就不可能再超过 \displaystyle\frac{n}{2} 了，所以答案只会与每个员工的最大满意度和次大满意度有关。因此，如果某个部门人数超过了 \displaystyle\frac{n}{2}，就把最大满意度从大到小排序，超过 \displaystyle\frac{n}{2} 的部分就用那个成员的次大值（即让他去别的部门，根据上述证明所以其他部门不可能再超过 \displaystyle\frac{n}{2} ，所以可以直接用次大值）。

想到这里写了一个小时终于糊好了喵！测试后发现，样例的第三个又错了呜呜，把第三个样例一看，

2
10 9 8
4 0 0
10 -> 13

发现这种思路对于这个样例来说就是错误的。心态好受打击qwq，当时就应该把样例看完的呜呜，好糖好笨QAQ，不能说我从开始花了一个半小时写出来的程序是错的吧QAQ.

痛定思痛，突然发现还是与最大值和次大值有关，只不过与最大值和次大值的差值有关，第一个的差值为 10-9=1 而第二个就为 4-0=4， 4>1，所以只需要把排序规则变一下下应该就可以啦！

果然这回输出的就是正确答案了！将后头的几个大样例测试后发现都是对的喵！所以应该是对的w，不过还是挺害怕这种方法是错的从而一分都没有的...

T2

再想了想，发现并查集根本就做不了。然后就没有思路了...想试着做一做特殊性质A？诶？！最短路是不是可以？就把所有路都连起来，然后把加上的路也连起来（c_j=0）然后跑最短路，之后求出来里头的最大值是不是就可以啦喵！复杂度 O(m \log n)似乎也可以！

写完发现，大样例也过不去，就算是修改后的小样例还是过不去！（思考）

啊！最短路不会经过所有点哇，这种方法就是错的彻彻底底的QAQ，呜呜哭哭

都怪这个笨蛋最近最短路打多了，只要是个图都想打个最短路... 那没办法了。尝试暴力，调了一个小时依旧是错的...

好难呜呜！

T3T4

嗯看不懂qwq，不知道怎么做，连暴力都打不出来/kel

交卷

还剩十分钟就一直催着我们交卷，坏！仔细检查了一下 freopen()，在 CodeBlocks 上也运行了一下，交卷了。

最后，让我们一个一个去前面看自己交了几个文件以及有多大，不知道有什么用qwq。做完后我对于难度评价是 橙 绿 蓝 紫 吧，暴力也打不出来分...

（上述思维和证明过程都是赛时所想，不含赛后主观判断qwq）

赛后

和同学聊天，T1 全都是用DP做的？？什么三维DP四维DP轮番上场，还有一个不是DP的硬说自己是DP的。不是，那如果是DP的话怎么转移哇，所以只要是个有容量的背包就是DP嘛！可能是我DP学的太差，真的一点都没看出来是DP...

T1难度居然评了个绿？T2怎么是蓝，怎么是最小生成树啊... 还没复习到w，而且我连最小生成树是什么都不知道... 呜呜我的蓝钩破产了...

今年难度逗我雷霆啊，西西挨服泥让我们蒻省这些没有资源没有技术力的怎么生存捏，感觉今年爆零的会有很多...

嗯对，我们弱省就是这么命苦。