CSP-S 2025 游寄

粥2414 · 2025-11-02 13:31:07 · 生活·游记

坐标 HA。

开考前

坐车来到考点。

吃饭被坑了 QAQ。

与同校 oier 集合并合影。

考场厕所十分小且十分简陋，排了半天队。注意到有些坑位没有人，但是锁上了？？！不过运气非常好排到某个坑位前刚好那人出来了，享受到了包间待遇。

进考场试试键盘，手感还行，比上次省选的键盘强多了。

电脑上装了十几个输入法\dots何意味？配置也是蒻爆了的 i3-3220\dots

dev 还得自己下\dots

T1

初看感觉像图论，想到了一个费用流写法。

不是 T1 用费用流太抽象了吧！

复杂度不对，而且我早就忘了费用流咋写了。

按照以往的经验，T1 一般是简单模拟或贪心。于是再想。

发现只有一个组别是可能满员的。可以贪心地把所有人放入贡献最大的组别。当出现一个组别人满但是还要加人时，有以下两个选择：

• 把当前这人放入贡献第二大的组别。
• 求出人满组别最大贡献和次大贡献差最小的人，记为 i，把 i 放入次大组，把当前这个人放入最大组。

用 set 维护 i，贪心地选择上面两个方案中贡献最大的即可。

不放心敲了个暴力和对拍，拍到结束也没问题。

应该是 A 了。

总用时 1h。

T2

是我并不擅长的图论题。

看第一眼发现没思路，乡村和城市不太好维护。注意到 k\le10，范围十分特殊。这或许是突破口。

发现可以暴力枚举乡村城市化的状态，然后跑 kruskal。

复杂度 O(2^km\log m)。加上特殊性质 A 能拿 72 分。

错误地认为复杂度瓶颈是在枚举乡村状态，于是想了好几个贪心都错了。

放弃去看后两题。

T3

是我更不擅长的字符串。

感觉好像能加特殊字符然后跑 AC 自动机，好像也不是特别难。那就敲吧！

等等，我好像不会 AC 自动机\dots

考前看了考纲里面没有 AC 自动机所以就没复习\dots

陷入无尽地悔恨当中\dots

于是只能敲个暴力 kmp。

应该能拿 25 分。

T4

敲了个暴力还没过样例。

赛后

第二天写作业时突然想到我 T2 特殊性质好像判错了，我只判了 c=0 就直接改造，但没判是否有长度为 0 的边。

啊啊啊啊啊啊啊啊啊心情一下跌落谷底。

如果 CCF 非常毒瘤地给每个数据都加了 c=0 的乡村，那我岂不是要 72->32 了？？？

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。

再出现一次不可以总司令那样的数据吧，哈基 F！！！

T2 炸了就只能 100+32+25+0=157 了。

我才高一还不至于退役。

感觉这辈子就这样了 wwww\dots