CSP-S 2025 总结

· · 生活·游记

CSP-S 2025 总结

省流：原地爆炸，拿下 jz 倒数的“好成绩”。

赛前的那个上午

各个学长给我们分享了各种各样的小 trick。我们也是有认真的听，我知道，每一个小 trick 都可能是大巨们通过各种奇怪的方式总结出来的，或是因为这个 trick 场切难题，或是因为这个 trick 赛季报销（应该没有这么恐怖）。

我们也是有认真总结的。

赛时

提前大概 15 分钟进入考场，熟悉一下机位后就静静等待考试开始。

比赛开始，根据我们赛前的打算，在半个小时的时间内熟悉题意并大概思考出前两题的思路。本着这个策略，我们开始速通前两题。

T1 看到一个 \frac{n}{2} 的限制，很明显的贪心，直接拿下。

T2 跟我们赛前的一道模拟赛的题很像，应该也是最小生成树，思考了一下，感觉想到了一个复杂度差不多的做法，也算拿下，下一题！

T3 字符串题。看懂题意后稍微想了一下。无从下手，跳了。

T4 计数题，看懂题意后感觉有点思路，我觉得应该比 T3 简单，好的，等会就冲它了，回去打前面两题。

此时时间只过去了大概 40 分钟。还好不算很超出预期。

T1 的贪心挺好写的，就是考虑调整法，先将每个人放到自己最想去的部门，这样极有可能会导致一个部门人数超出 \frac{n}{2}。我们考虑把这个部门的人往另外两个部门放，对于这个部门的每个人算出一个 \Delta，表示把这个人放到别的部门去的最小减量，根据这个贪心即可。此时距离比赛结束还有 3 个多小时。

T2 我的想法刚开始比较猎奇。刚开始是以为这 k 乡镇是原 n 座城市里选出来的，后来发现了，立刻观察出一个性质就是只保留原来 m 条边里的最小生成树的那 n-1 条边即可。然后我们知道要是每次都排序的话时间复杂度肯定会起飞的，所以我们想到假如说新加入一个乡镇，它一定会连最小的那条边，这样在这个树上跑树形 dp 应该就行了。

我们猜这个做法是对的，实现出来后第 3 个大样例死活过不去。我们有点红温，打个暴力排序求最小生成树的程序对拍一下。意外发现暴力比我们这个 dp 还快，答案还是对的。我们果断弃掉 dp，开始优化暴力。

暴力时间复杂度算一下发现是 \mathcal O(2^k\times n\times k\times \log nk\times\alpha(n+k))。拿计算器敲一下，大概过不去。我们想到可以提前排序，每次把最小的丢进一个堆存起来，这样时间复杂度来到 \mathcal O(2^k\times n\times k\times \log k\times \alpha(n+k))。测一下极限数据只需要 1.22s。加一个如果目前答案已经劣于以前答案就结束操作的剪枝，就把时间缩进 1s 以内了。

此时距离比赛结束还有 2 个半小时。

后面我们的操作就很迷惑了。

T3 字符串题，我们一概不会字符串，直接跳了，我们考虑打完 T4 回来打 T3 的暴力。

T4 我们想到 s 是固定的，然后我们转化一下题意：

对于每个位置求一个 d_i，如果在这个位置放的 c 大于 d_i，就会产生 1 的贡献，统计贡献 \ge m 的方案。

我们认为 d_i 是固定的，是好求的。我们现在开始考虑计数方案，然后我们发现 d_i 是单调不增的，意思对于任意一个 c。它能造成贡献是是一段前缀，我们发现这个可以做 dp。

想到这里我们兴致冲冲的就要开打了，我们天真的以为我们切了这道题。其实现在回来看一下，你会很容易发现 d_i 不是固定的，你这样算的话就相当于没考虑那些自己放弃的人。所以我们的算法从一开始就错了。

中途我们还因没有理清思路和状态就开打导致打了删，删了打，浪费了很多时间。最后也只是打出来个 \mathcal O(n^4) 的。然后我们调了半天调过了小样例，发现第二个样例根本算不出来。当时脑子开始发热，我红温啦！

出去上了个厕所，也没找到转移哪里有问题（当然找不到啦，一开始就错了）。

发现还剩 40 分钟，不是，怎么打了这么久，回去打 T3 的暴力。

打 T3 暴力也是心不在焉，脑子里还想着 T4，再加上人有点红温，发现自己根本不会暴力，只想到一个最暴力的 \mathcal O(n L^3)，一分都没有。当时人就更红温了。最后只想到 10 分的暴力，打出来，测过最小的样例就没管了，连第二个大样例都没测。

回去继续冲 T4，越冲越红温。最后 20 分钟，想着不能爆 0 吧，打了个指数级暴力，但是是根据我们之前那个想法打的，发现也过不去大样例。我真的——！！！

红温到极致的我终于意识到想法的不对劲，可没时间补救了。检查一下 freopen，遗憾离场。

赛后

估分： 100 + [80,100] + 0  + 0 = 200
实际： 100 + 100      + 35 + 0 = 235

不是，T3 还能送我 35 分？

总结一下这场比赛。

优点：

缺点：

感觉没有发挥出自己应有的实力，但好在一等奖还算是勉强保住了。

看看能不能去 NOIP 吧，能去的话争取把 NOIP 2025 稳住。