CSP 2025 游记

c_legg · 2025-10-22 21:49:08 · 生活·游记

初赛

J 组 94，S 组 83.5。

白天一直在忙文化课，晚上才能做题，每天十一点以后睡，累亖我了。

请了假（逃掉一个英语晚自习），去南京，住在南航附近的酒店里。

晚上老师讲了一些注意事项，然而我一直在想倍增答案，且没有做出旅游巴士这题。

把困扰我一整年（2024 年 CSP 前夕到 2025 年 CSP 前夕）的橙题公路做出来了。

膜拜 @not_so_littlekayen，写完这段文字，然后睡觉。

几乎是近半年来唯一一次十点前睡觉！

起床，小跑去南航。

很有趣的题目，很有趣的密码（我记得是 #Shang3Shan4Ruo6Shui4）；好像 AK 了，又好像没有；电脑好像死机了，又好像没有；游戏好像玩到了，又好像没有玩到。

去南航的食堂吃炒面，环境很好，面也很好吃，就是有一点油了，再加上我的腿很疼，所以还是有点感觉不好的。

和我爸骑自行车回酒店，把水杯放在前面的车篓里，但它总是不停地颠着，还发出很大的响声。所以我尝试去把它拿到手里，然后就在南京市江宁区静淮路上磕了一个了。

试图复习并查集并失败。

又回到了南航的六楼机房，一开始感觉电脑的饱和度很差，但也只能将就了。

先做 A 题，发现是极水的贪心，就花了半个小时过掉大样例了。

然后是 B、C、D，发现一题都不会做，于是随机水部分分直到大约四点半。

此时我已经知道 B 要用 MST 了，于是胡了若干种得分在 20 分以内的方案，最终搞了一个 \Theta(2^kn^2) 的纸张暴力做法，以及一个结合了部分分的 \Theta(m\log n) 的做法，揉到一起，估分就成了 64，于六点二十九分写完。

回来一看题解才发现半路中被我证伪的 \Theta(m\log m+2^kkn\log kn) 的做法是正解，我是纸张。