CSP2025 游记

· · 生活·游记

-J

为什么我们考场 8:44 才把试题发下来/kel

T1 秒了。

T2 刚开始想用数学推，卡了一会，然后大概 9:20 左右过了 3 个样例。

T3 这不显然贪心，内心狂喜，在 map 和 unordered_map 之间纠结了一会，还是决定用 map。9：40 多的时候写完过全部样例。

T4 神秘 dp，一开始也想用容斥的发现我太菜了。然后考虑直接 dp。最开始写了个 O(n^2\times \max a_i) 的 dp，瓶颈在值域。9：52 过除所有大样例（但大样例没给满）。

然后开始优化，发现类似区间加就先写了一发线段树，结果毫无卵用。然后灵机一动发现可以把 \max a_i 之后的所有 dp 数组用一个变量存，因为并不关心具体大小。然后尝试写了一下，发现好像能用，此时还有 1h。

写完再测，发现居然也过了，欣喜地造一组数据对拍——过了。此时 11：27。

我 AK J组了？

然后想起模拟赛时的教训于是赶紧平复心情来检查。中途 T3 的值域看成 2^{50} 了赶紧开 long long 后面又发现是 2^{20} 赶紧关 long long。

最重要的：11：40 多对拍 T2 发现 n,m 打反了，一看才发现样例都是 n=m，好险！

最后预估 100+100+100+100=400。希望别挂分。

-S

开 T1 发现反悔贪心板子题（按最大与次大差值排序不是显然的吗），才把结构体优先队列打出来发现不一定要实时反悔，可以最后再反，于是简单 sort 搞定。

还有看很多人在考场写了半天分 a_{i,1},a_{i,2},a_{i,3} 的大小十几行代码。其实我们可以直接结构体排序，看似大费周章实则节省时间。

大约三点零几的时候开 T2。k=0 最小生成树秒了。然后没看数据范围以为 n,m 同级，想了半天想不到复杂度低的写法，再看数据范围（本来想算暴力能拿多少）结果发现好像跑不满就能过。

直接 O(2^k\times k\times n\log n+m\log m) 走起。最大的大样例跑了 1 秒左右。自己造的卡满的数据跑了 8 秒，感觉没救了。不过 80 分也不错。

忘了几点开的 T3，然后我居然想到的不是哈希而是 AC自动机（因为 2048 MB 的内存），并且一点思路没有。

随便写个暴力和性质 B 吧，写了 40 分钟发现性质 B 的复杂度只能过点 6。不想思考了，拿个 15 分得了。

T4 看起来好像比 T3 简单？然后我就先把 10 分的暴力写了。发现 m=n 非常好写也顺便拿了。

闲话：写到这里我环顾四周发现有个哥们还在调 T1 并且已经写到 200 行了。

然后想着 m=1 应该和 m=n 差不多吧？其实差很多。

在 18：05 的时候会了，容斥+简单双指针即可。18：17 写完并一次过大样例。

然后检查，并没发现任何问题。

最后预估 100+[80,100]+[10,20]+24=[214,244]。希望别挂分。

后记

考完以为考得很差，结果随便问几个同学没有上 150 的，洛谷上的大佬也有很多 T3 挂了的，大部分都在 190\sim 250 之间，突然有信心了。一定要进 NOIP 啊。

另外，我在每道题结尾都写了注释：xxx 保佑我这题不挂分，拿到xxx分，到时候哪题挂了就怪谁。（透露一下，J T3 写的是 @New_Void，S T1 写的是 @fyc_lc，S T4 写的是 @P2441M）

出分

J 组 100+100+100+100=400 没挂分，AK！

S 组 100+80+5+24 T2 带 \log 真被卡了，T3 不知道为什么挂了 10 分，感觉还行（千万不要跟我说不挂分就有7钩了啊）