CSP-S 2025 游记

· · 生活·游记

比赛情况

T1 社团招新

开考后 10 分钟想出了贪心策略，简单论证了一下其正确性，本想模拟一下样例 #2，但苦于其过于复杂，就直接开始写代码。

约 30 分钟完成了最初代码，样例 #1 轻松通过，但样例 #2 出现错误，程序输出小于样例输出。又调试了 20 分钟，解决了几个没有考虑到的条件判断，依然没能调试出来。这时候我开始怀疑我贪心策略的正确性，花了点时间简单考虑了一下动态规划和其他贪心策略，发现动态规划基本不可做，我另想到的贪心策略明显错误。

继续调试原本的代码，然而没有发现什么问题。最后迫不得已，开始在草稿纸上模拟样例 #2，因其数据比较大，选择使用 Python 帮助计算（Python 在信竞中的唯一角色就是一款很好用的计算器）。手工模拟的过程是极其难受的，期间我一直在考虑是否应该放弃 T1，先写后面的暴力分。模拟样例 #2 大约花费了 15 分钟，不过好消息是在模拟的过程中，我发现了程序中的漏洞，简单修改后成功通过样例 #2。

最后跑了一下其他大样例，答案输出均正确。不过跑样例 #5 的时候程序用时 1.04 秒，我担心被卡常，加了个快读，运行时间瞬间缩短一半。

T1 耗时 2 小时，代码长度 1865 字节，期望得分：100 分。

T2 道路修复

看到题目，起初很兴奋，以为是分层图，已经开始感谢九分之二了。但随后仔细考虑了一下，发现分层图基本不可做。看了下数据范围，发现测试点 1\sim 4 就是没有村庄的情况，对于特殊性质 A 可以等价于没有村庄，可以直接跑一遍最小生成树解决。测试点 1\sim 4 和特殊性质 A 在测试数据中占比很大，达到 48\%，于是决定打部分分。

不过，很可惜的是我考前没有整理最小生成树的模板，平时很少写到最小生成树的题，算法也忘得差不多了。最后依靠着我在初赛复习的时候稍微看过 Prim 算法的模糊记忆（别问我为什么不写常数更小的 Kruskal 算法，问就是我完全忘了），调了 1 个小时，终于调出来了。最后样例 #3 跑了 1.08 秒，我依然担心被卡常，又加了个快读。

T2 耗时 1 小时，代码长度 1915 字节，期望得分：48 分。

T3 谐音替换

一看到这题就头大。根据名人名言：

字符串题都是毒瘤。 ——Awsdkl

我果断放弃。我现在甚至能一字不落地把考场代码默写出来：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);

    return 0;
}

甚至连表也没打，因为我这是最后 5 分钟写的代码（先写的 T4），没空打表。如果输出 0 有分的话，那我将亲切问候造数据的人。

T3 耗时 5 分钟，代码长度 162 字节，期望得分：0 分。

T4 员工招聘

都到 T4 了，那还说啥呢？看看部分分吧。

惊喜发现特殊性质 A，起初以为一个全排列上去，直接输出 n! 就可以了。不过发现题目中说的是“若在他之前已经有不少于 c_{i} 人被拒绝或放弃参加面试，则他也将放弃参加面试”，而数据范围中 c_{i} 是能取到 n 的，那全排列就不可行了。这个特殊性质 A 给了跟没给有什么区别？（不过赛后听说特殊性质 A 是给动态规划用的）

最后还是简单判断了一下能使用全排列的情况，又另外写了个大暴力，收工。

T4 耗时 50 分钟，代码长度 1880 字节，期望得分：20 分。

总结

总共期望得分 168 分（不过这是最理想的状况，可能实际比这要低），比赛时间也比较紧张。感觉二等有希望，一等还是算了。

赛后反思

首先，T1 贪心花费太多时间了，正常应该在 1 小时内打完的。也体现出我对于代码多种条件判断的逻辑思考不够严密。

T2 暴露出我对多种不常用算法模板不够熟悉，赛前欠准备。应当继续完善算法模板整理。

T3、T4 没什么可说的，就是我太菜了。

希望我能在 NOIP 2025 前解决这些问题。

其他

关于考前生活的感悟

周五中午从学校出发，路上花少量时间看了看《深入浅出程序设计竞赛 进阶篇》，其他时间在听歌、发呆看Awsdkl。

酒店环境还是非常好的，住得也比较舒服。我的室友是黄岩中学高一（1）班的。很尴尬的就是我们发现我们初中好像认识过……

话说现在黄岩区实验中学真是人才辈出。听说九年级有个人 CSP-S 初赛满分（又被初中生吊打了）。

让我感触最大的是：周五晚上和周六中午，吃饭是自己解决的。周五晚上我们几个人本来打算一起去找吃的，但走出去几千米，找半天没找到什么好吃的。最后散开了，自己吃自己的，我跟hqy2024和Xiashengyi123就选择在旁边一家沙县小吃解决了；周六中午，我直接单独出去了。当我一个人走在杭州的街头，四处张望，考虑着要吃点什么，然而人生地不熟，只能瞎走走，这时才第一次体会到了一种漂泊异乡的感觉。

考后

我们 18:30 考完，直接上车回台州。在车上老板请的杭州美食榜第一名——肯德基实在是太多了，给我吃撑了。一路上感觉特别疲惫，只能感叹：唉，老了……