CSP-S 2025 游记

· · 生活·游记

Day -1

心情有点紧张，没什么心情写题。

上午做了去年 SCP-S 的 T2，感觉不是我能做出来的题。

下午和同学比赛打板子，【模板】缩点第一发竟然 0 pts。ed 跑到我们机房投足球，砸掉了一块天花板。

晚上稍微复习了一会，打了几把糖豆人，总是过不去第二关，破防了。

Day 0

早上睡到了 8:40 才起来，嗯，错过了 J 组。上午复习了一些常见的模板和 trick，后来发现这些东西一个也没用上。想起去年考前把联考中出现的一些 trick 总结了一遍，放到了一个 .md 文件里，结果找了半天没找到。我怎么就不晓得把它存博客里呢。

1:20 到了考场，真是不知道怎么 HN 每年都在长沙理工，机子烂的要死。想在车上眯一会，但是有点紧张导致睡不着。母亲大人给我点了一杯星巴克，因为我表示星巴克太贵了，我还从来没喝过。结果这东西带不进考场，只能在进去前匆匆喝两口然后放在了外面。

发现自己好像过于紧张了，心率怎么都下不来，尝试让自己放松，但好像没什么用。

Day 1

首先是经典密码晚发。

先开 T1，发现有点糖，秒掉，没急着写，去看了 T2。发现秒不掉，又回来写 T1，结果因为一些棒棒糖错误，30 min 时才过。

然后开 T2，先考虑了贪心，把 MST 建出来，用新点去替换 MST 上的边，发现不太可做。然后发现 k \le 10，于是想到状压，但是好像被思维定式束缚住了，感觉状压就一定是 dp，于是一直在想 dp。先想了个明显错误的 dp，设 f_{s,i} 表示选了 s 这些村庄，前 i 个点已经连通的最小代价。错误点在于前 i 个点不一定需要连通。此时已经过去一个多小时，接下来半个多小时我毫无头绪，此时已经差不多 2h 了，于是开始心态爆炸。后来及时调整心态，开始分析题目的性质。发现如果要选原来的边，必然只会选 MST 上的边，于是枚举 MST 上的边，考虑是否保留这条边。如果按照顺序加边，当加到某条中间边时需要将两个连通块连起来。发现这样的话每个村庄只会连接一个连通块，所以设 f_{i,s} 表示连通块 i 有 s 村庄连接的最小代价。复杂度 \mathcal O(3^kn)。17:30 写完。

剩下的时间写了 T3 的 \mathcal O(L_2n) 和 T4 的 \mathcal O(n!)。压着时间写完，非常慌张。

预估 100+100+30+8=238。出来发现大家都在 250+。

和同学对了一下 T2 做法，发现我的完全不一样，心情特别慌张。

晚上复现了 T2 代码，发现最后一个大样例死活过不去，点开一看发现和场上的输出是一样的。我记得我过了大样例的啊？？？哦，原来我场上不小心输出到答案文件里了。当场破防，洛谷 36，云斗 52。尝试证伪思路，发现若原边不连我不一定要将两个连通块连起来。

死了。

Day 2

出去玩，看了一部垃圾电影，在影院里 tyx 突然给我打电话问我 T3 有没有判 |t_1| \not= |t_2|。更破防了。

沈金得分：[124,238]。