CSP-S 2025 游记

Bonely_Muffin · 2025-11-02 20:36:03 · 生活·游记

前言

其实不知道挂了多少分。

正文

上午还得打 J。

大家上午都在爽爽摆，输输输。

下午在考点等了一会，两点多进场。发现机子的显示屏非常难蚌，跟监考人员说，竟然给换了座位。这下舒服了。

2:30 开考。

T1 这不是糖糖贪心。秒秒秒。

T2 这啥玩意啊？想了一下根本不会做。这时发现 k=10，直接看懂了。枚举 2^k 种 case，分别跑一遍 MST。还注意到给定的边中，只有 (n-1) 条是有用的，也就是初始 MST 中的所有边。

糊出来 O(m \log m + 2^k nk^2)。这 1e9 啊，真能跑么？算了 cy 说今年机子很牛，就当能跑吧，直接严肃开写。

一直写挂。好像写到了 15:30 才过所有大样例。输！

开 T3。哎呦 CCF 你干嘛怎么出串串。想了一下按照不同的段分组，然后上 AC 自动机好像就行了，问题是不会写 AC 自动机。倒闭！

内心挣扎了一会。

大概知道 AC 自动机在干嘛。尝试重新发明 AC 自动机。好像建 fail 的时候要 bfs 来着，好像 cnt 要前缀和来着。

好像编出来了。写写写。

还在写挂。中间做法有点假修了修。

写完过不去样例三，发现 AC 自动机编的有点假继续修。

一直改，最后过了所有大样例。距离比赛结束还有一个多小时。倒闭！

担心 AC 自动机写挂，写对拍。暴力和数据生成器都在挂，调调调。怎么能糖成这样的？！？！

因为暴力太慢了，所以拍了 3000 组小数据，没有挂，我就默认对了。T2 感觉对拍不好写，遂不写。

就剩四十分钟了。感觉 T4 根本就不可能正着做（并非），然后发现编不出来任何做法。想了很久不会。开始拼暴力，先打了阶乘，然后想 A 性质。好像我从小往大插入可以做（该做法和本题的正解毫无关系）？完了完了就剩十分钟了，然后没写完 O(n^3) 的 A 性质，遗憾离场。

最后 100 + [??,100] + [??,100] + 8 = [??,308] ？？

出来发现同机房 AK 了一车人。倒闭！

九阳怎么又无敌了，\%\%\%。

发现 T2 可以 O(m \log m + 2^k nk)，甚至还可以做到 O(m \log m + 2^k n)。倒闭！