CSP-S 2025 游记

· · 生活·游记

初赛待补。

先喷一下今年地方上的一个提交系统，提前提交给我们砍了 5 分钟时间。

一些缩写：

Alfa = A

Bravo = B

Charlie = C

Delta = D

由于在 11 月 1 日以前一个月，本人的练习少得可怜，所以去的时候一直在被《葛底斯堡演讲》，可惜全文仍有问题。

到 NXU 的路上经过凤凰公园，里边儿全是看秋叶的人。

13:30 到达学校门口，在 13:40-14:05 的区间里有一个蓝发 coser 在门口徘徊给我高兴坏了。谁知此人并没有参加比赛。 与此同时，我和我的朋友 @WRT_Partisan 和 @Chiang_Chao 先生聊了聊天，前者给了我一块黑巧，算是回应了初赛我给他扔过去一块丝滑，不过我带上了一块长条士力架。

14:15 我们上二楼，我的位置就在门口的 B02。14:30 时我们下载压缩包，然后就开始了。

大概用 5min 浏览了一遍题面，然后我发现 Bravo 似乎是可做的。于是我就做了。我认为跑一个连辅助点和边的 Kruskal 就出来了。然而 20 min 以后，程序输出了 2，而正确答案是 13。

于是滚去老老实实地做 Alfa。令人疑惑的是，用 dp 来写 Alfa，时间复杂度是 O(n^3)的，于是就开始动手写。花了一整张草稿纸和 2 h 的时间，75% 的分数至少有点指望了。不幸的是后 25% 一直跑不过去。在此期间 Bravo 的思路没断过。

赛后提示：塔们（包括 @WRT_Partisan）说要用反悔贪心。

于是乎洗了把脸去接着解 Bravo，然后我才发现 \mathbf{k\leq 10}（这个叹号不是阶乘）！所以，在先跑了一遍 MST 把原图的太长的边筛掉以后，我写了一个 O(2^k(n\log n)) 的诡异玩意儿跑过了全部样例。给我高兴坏了，于是我去看 Charlie 和 Delta。

赛后提示：Unaccepted_Zhou 先生在这儿说，Bravo 的最大样例是数据范围的 \mathbf{1/10}。草。

Delta 让我看到的一个令人惊恐的事实是：n\leq 500。按照 CCF 的一贯习惯，n 越小，时间复杂度和算法就越抽象。所以，我直接弃坑了 Delta，开始看 Charlie。

看了几分钟后，我认为特殊性质 B 是可以做的，因此在 30 分钟后通过了特性 B 的样例；后 25 分钟我试图用哈希拿到一些 A 和 n 较小的部分分。不幸的是砍掉了 5 分钟，再写两个条件就写完了。

就这样吧，估分大概 15x（比刚出场时低了40pts），氦。

NOIP 再战吧，最后一年了。

Success is not final, failure is not fatal: it is the courage to continue that counts.

-- Winston Churchill

补充说明：Alfa 45（挂了 30），Bravo 80（比预期高20），Charlie 10（符合预期），Delta 0。

我怎么做不出来第一题的？！！！