【游记】CSP 2025

· · 生活·游记

Day 0

复习了一下板子。发现不会串串。觉得不会考，直接扔了。

Day 1

13:40 到了考点。发现同学们全都进去了。一个人都没见到。

14:10 进场。发现桌子和旁边人们的都不一样。很神秘。

开考后先看了一遍题面，决定顺序开题。T1 观察了几分钟发现显然是反悔贪心。15:00 过了大样例。

然后看 T2，一眼最小生成树。想了一会后会了 A 性质，先写了上去。又想了一会，发现可以 O(2^k) 枚举使用哪些村庄，然后加边跑最小生成树。此时尚未意识到直接 O(2^k m \log m) 是肯定超时的，直接写完去看 T3 了。

此时已经过去 2h 了。发现 T3 是神秘串串题。伏笔了。发现似乎是 AC 自动机板题，但我不会敲 AC 自动机。恼。准备随便糊个 25 分暴力上去，写了一半发现复杂度似乎错了。扔了不写了。

还有 1.5h。T4 没有一点思路。部分分看着很好写的样子，先写了个 m=n 的测试点，然后写前 8 分的全排列。然而写完后莫名觉得全排列是 O(n^n) 复杂度的，于是我把它删了。令人无法理解。

最后 0.5h 回来检查 T2，发现复杂度错了。观察到只取 n-1 条原树边加上村庄的边即可通过。忘了并查集怎么按稚优化了，感觉过不了。发现来不及实现了，莫名给原做法加了个只在前 8 个点运行的特判。令人无法理解。

最后整体检查了一遍，发现 T3 的 25 分做法复杂度其实是对的，我又算错了。令人无法理解。但来不及补全了，遗憾立场。

估分：100 + 56 + 0 + 4 = 160

赛后发现 T2 不加特判能多拿 24 分。加上 T3 没写完的 25 分，T4 删掉的 8 分。总共挂了 57 分。没实力。

Day N

出分了。100 + 64 + 20 + 4 = 188。

T2 怎么拿的分？T3 怎么拿的分？

CCF 神秘数据。