CSP2025 游记

· · 生活·游记

前情提要

当天

提前 30 min 进场了，遇到了很多同学，和 @Ericwan 一个考场。头有点晕，老师还不让我开教室里的窗户。由于喉咙痛，还需要定期喷一种药物。

14:20。开始深呼吸，感觉精神好了不少。一直在暗示自己“努力都是有用的，水平没问题”，感觉还是有点用的。

14:26。发密码了，人杰地灵，好像是我们某次语文考试的题目。发现是单层密码，直接开始看题。

先简单看了一遍题，发现是贪心，图论，串串，计数，竟然是大逆风吗...？本场胜负手 T2,T3 全是我不喜欢的考点，考前确实预测对了会考图论，幸好不是 tarjan，但串串是真的完蛋了，我真一点没复习，只会写 KMP。

想到 dx 所述的心态调整，感觉心态好一点点了，开始做题。

大概 3 分钟就想到了贪心排序，然后过程中反悔的方法，但我一直很讨厌反悔贪心，每次都写不对，于是我考虑了一点更优美的做法。后来发现可以先贪心，然后统一反悔绝对众数，这样就过了，大概 15~20 min 就把大样例过了，我觉得出的不错。

开 T2，刚开始以为乡村和城市是合并在一起的，也就是说可以把城市变成乡村，后来过了 5 分钟重读一遍题就发现我唐了。

刚开始想到了 nk2^k log (nk) 的雏形，后来不知道怎么着又否了。然后后来想想想，转化成把乡村当做虚点，发现虚点很少，然后跑最短路之类的东西建边，显然假了。

发现枚举要用哪些乡村是必要的，于是我有回滚会原来的暴力做法，发现每次直接等价于对“选择的”乡村和原图跑最小生成树，这个显然是对的。等我实现完立刻意识到可以统一排序，加上按秩合并就是 O(m\ log m+nk\ log (nk) \text{α}(nk)+n2^k(k+\text α(n+k)))，大概 2e8，可以通过！于是我又切了一道不那么擅长的题，挺开心的，我以为会特别难。

然后很快就写完了，发现 WA 了。原来是没有初始化 father 数组。然后又 RE 了，原来是 father 没开够，然后极限数据跑了 6s！卡了半天常数，想到 rhn7 的换 vector 卡常法，就快了一倍，然后把 e 开到了 1e7（flag1）。卡着卡着突然发现我自始至终没有开 O2！然后就过了，大概 100+\varepsilon min。

场上的这个时候，我认为前两题相对较难，大家切的都比较慢，但我显然忽略了前两题都是我不擅长的题。。。于是我换成了稳健打法，打算先花 [45,60] min 去搞 T4 然后全力 T3，因为我认为 T3 可能只是诈骗（就像上次一样）。

花了 10 min 终于理解题意，花 10 min 把 m=n 和 n,m \le 10 的分打了，然后又花 15 min 把 n,m\le 18 打了。我一度认为 T4 有巨量部分分（m=1,A性质），因为这题很像我们校内模拟赛的两道题（球球&夏日朦胧），但显然我又失策了。

中间有一段时间记忆缺失了，我似乎调 m=1 的分调了很久。容斥几乎是显然的，但中间我犯了若干错误，耗费大量时间，最后 25 +\varepsilon min 才调完，思路跟第一篇 tj 很像，但我对于 A 性质，并没有对容斥进行深入思考，转而考虑类似“夏日朦胧”一题的 dp。

我后来试图实现了 B 限制，但又中道崩阻了。然后我发现时间竟然只有 50 \pm \varepsilon min 了！！！

瞬间慌了，大脑一片空白， 这时候我 T3 一点都没想。我迅速判断这是道 AC 自动机题并且我做过类似题并且 trie 做法极难实现，所以我认为这题的正解根本不可能实现，去想暴力。先打了个 hash 但是又挂了/fn！！！！调半天加了剪枝过了第三个大样例。

后来想到了 50 pts 的类似题（P8022），以及满分解类似题（某 JOI 题），但是我真的大脑运转不过来了，最后 20 min 我冷静了一下，翻了一下原来的代码，发现我 T2 中 define int long long 并开了 4 个 1e7 数组，瞬间一阵后怕，改成 4e6 交上去了，这下应该不会 MLE（flag1 回收）。

我觉得去冲 T4 的 A 性质，我迅速列出了状态——f_{i,j,k} 表示到第 i 个，前边死了 j 个，目前用了 k 个人的 c \le j。 我发现这个东西能表示绝大部分信息，但我对转移毫无头绪，对着这个东西写了半天（15 min）无果，就放弃了。

最后 5 min 就开始摆了，检查了一下文件名，没什么问题开始 yy 【数据删除】了。报的分数是 271，得分区间是 100+100+[25,40]+36=[261,276]。

赛后跟 lzc 打 bloxd，没开挂杀了一堆人，开心，同时被 dice 带飞了。赛后看到群里发的 T4_tj，发现自己的 ans 式子和状态都对了，但我真的一点不会转移，可能期中之后自己推推吧。