CSP2025游记

unicorn1220 · 2025-11-02 20:32:39 · 生活·游记

目标：J组AK，S组200以上。

吐槽一句屏幕好扁。

J组

开考，解压花了五分钟，但不慌。

回想了一下策略：

顺手的题先打了，有不会就全看一遍

（J组应该没有不会的吧）

T1T2没什么好说的，十分钟过了所有样例。

T3先在草稿纸上写了个 O(n^2) 的DP，遂发现可以优化成 O(n^2)，又花了十多分钟打完。

此时还没到九点，感觉能AK。

T4真良心把能组成多边形的条件都告诉了。不知道哪里得出个找合法方案数不好写（实则好写）的结论，遂正难则反，诶真好写。立了个一小时以内AK的flag。

依旧十分钟码完，但是条件有点混乱，没算上等于的情况。对着样例调调调，把小样例调过后大样例全都过了。此时一看时间：

欲哭无泪。

去了趟厕所后开始写对拍。发现D盘有个名叫public的文件夹，这不就是量身定做的吗，把代码复制了过去。T1实在不知道怎么写了。T2写的暴力实际上是能过的，O(nm)，一运行发现错了，吓出一身冷汗，遂发现数据不符合题目要求（有相等），虚惊一场。

T3在 O(2^n) 和 O(n^2) 中选择了后者，应该问题不大。

T4只会写 O(2^n) 暴力，写完后担心特殊情况太少，于是又写了个值域很小的版本（有相等）一起跑，正好补上第一题的空缺！

这时总共过了两小时，又瞪了半小时代码开始发呆。

后面有人提醒写txt文件，我之前甚至忘了。

估分：100+100+100+100=400

S组

这次解压快点，两分钟。

T1秒想了个贪心，不把同一个人的合起来，全部扔一起排序，五分钟码完发现过不了样例。

发现假了，推了一会发现只会有一个部门超过半数，且把超过的扔到哪个部门都没关系，于是写了个反悔贪心（其实考场上并没有意识到）。又写了十分钟过了所有样例。

T1竟然写了半个小时，有点慌。

T2开始把乡村看成城市了，有点懵先去看了后面的题，都没啥想法。

重新看了一遍把题意看懂了，感觉不太可写，结果发现乡村数最大才10，可以 O(2^k) 枚举。

但是m很大，没法全部暴力。想了一个推论，先不管乡村，跑一遍最小生成树，然后没选上的边以后也不会选，所以只剩n-1条边了。

感觉很对，没算复杂度就开打了。细节有点多，写了半个小时过了样例，大样例竟然跑了 1.7s，感觉要卡常，打了个快读就 0.9s 了。

其实我一直都把这个写法当成一个暴力，可是却没想过算一下复杂度，只是觉得 0.9s 有点悬。我还想到了一个优化的思路，类似把以前建的图拿来用，事实证明是正解，但又觉得官方评测的CPU应该很快，而且不太好打，于是就放了。（唯一败笔+埋下伏笔）

开T3。一直在想KMP，后来突发奇想Trie，没细想就开写了（还觉得出水了），算空间的时候发现超了512MB，一瞄空间限制发现2GB，顿时感觉是正解，信心大增。结果写到一半就假掉了。

重新审视了一下，才意识到可能是AC自动机。但我考前因为仓促，又想着是NOI级的，没复习。主要思路都还记得，但是怕细节错不敢写，于是全力安慰自己不能超纲，而且好像AC自动机也写不过。

感觉没啥希望写正解了，想了想以前的比赛打部分分就没输过，于是打部分分。

发现哈希可以 O(1) 判断，打算写个 O(qL_{1})(L_{1} \leq 5 \times 10^6)，应该有50，还瞄了一眼性质，发现把B给打了能有70，遂开写。

因为没怎么打过字符串哈希，打的很慢，写了半个小时。小样例很快过了，样例三和答案完全不一样，还跑了 7s，有点难受，去写了T4的8pts再回来调。

是的，在只剩下十几分钟的时候才意识到是哈希冲突。我用的进制数是自己的生日，换成班里某天天被开的音游哥的生日竟然过了，保险打了个双哈希。

最后还是没时间检查了，只能听天由命了。

赛后听大家说T2大样例不是极端数据，哭哭哭。

估分：100+[80,100]+50+8=[238,258]。

总结

其实问题不多，没有死磕不出来的情况，目标也达成了。J组把能打的对拍都打了，S组最后也惊险调完了。

可能简单题写得太慢了，代码能力不足。

同时学新算法的时候做的练习少了，打板子就很不熟。

对于我来说是很好的结果了，上限摆在这。