CSP2025游记

· · 生活·游记

前言：集训时打联考被打破防了，次次考次次挂，没信心了都。

上午

来考 -J，刚打开题目就傻眼了，今年折磨简单的吗。

T1秒，没啥好说的。

T2秒，没啥好说的。

T3，一开始想到找每个点所对应的最右区间再区间选点，然后卡在找区间上了，之后想到异或也有前缀和性质，也算是秒掉了。

T4 一眼 dp，但是和太大不好处理，于是考虑单独处理和大于 5000 的，甚至没有 T3 想的久。

之后玩了一小时冲浪又睡了两小时，实在挺无聊，但是看旁边的哥们调了 4 小时的 freopen 还是没过编真有点好笑，还是说我笑点太低了。

中午

打 phi，但是 rks 没涨。

下午

T1，感觉像贪心，加点反悔过了大样例。

T2，抽象生成树，一开始想到枚举选哪些点，但是发现 O(2^k(m+nk)\log (m+nk)) 实在太劣，于是去想别的做法，最后发现只要保留原图的生成树即可，O(2^knk\log nk) 的复杂度感觉像是对的，但是大样例最慢 1.3，挺悬的，希望评测机给点力，但是大概只有 80 pts。赛后发现只要先排序，拿优先队列维护一下就能把 O(\log nk) 优化成 O(\log k) 了，挺可惜的。

T3 没看题面，以为能无限次换，想了一小时的 AC 自动机上 DP 发现用不上，最后潦草打了个估计只能过 1，2 个点暴力。

T4，还是没看题，调了将近一小时的装压还是错的，最后也只能打前两个点的暴力，赛后想到了 2^nn^2 的暴力，应该能过八个点。

总结

想思路前一定要先看题！然后考场上别喝太多水，不然上厕所要排队很难受。

这次考的一般般，有没有 7 钩得看运气了。