CSP2025游记

​和同校的朋友都是在深外高中园考场，所以伙伴挺多的，这次不孤单。

​早上:坐lfz家的车去考场，车上给lfz以全排列为例讲了怎么暴搜

​CSP-J:
T1桶排

T2想出来了 $O(1)$ 的解法，结果发现nm小的可怜，而且输入输入就 $O(nm)了$……

​T3:神秘 DP。我也不知道自己是怎么想出来的，想了一下异或的性质，然后冥冥之中想到怎么做就做出来了。值域小，开个通

​T4:一个小时写完前三道题基本就稳 J1 了，补充点体力就休息了会。T4 打了个 $n^2$ 乘值域的暴力dp。赛后lfz说用我教的暴搜骗了 20 分

​总结:个人感觉红红黄绿。当然 T4 没认真看。估分 340
中午:吃了个午饭。在4个考场深外高中园是唯一一个不提供餐食的（）

CSP-S:一坨大的

开局不利，我的考场是一般考场的两倍长，然后我坐最后一排的最角落，老师在最前面的黑板上写解压密码[再见]

​我们的考场贼多人，开考了才进的场，我都不知道开始做题了，小心翼翼地在打头文件

​拿到pdf先看了 T1 和 T2:T2 一眼 mst，这我不稳了！然后开始正序做题

​T1:一个半小时……低估了，以为和去年一样是橙，最后按最大值分组，超过一半的就有优先替换成与最大值差距最小的次大值。一开始写了一坨屎山还开了两个结构体

​T2:看数据范围知道要大概要 $2^k nlogn$ ，并且也猜出来了原来的 $m$ 条边只有 mst 的 $n-1$ 条边有用的结论，但是代码能力弱心态不好写了屎山

​打算去厕所找灵感，监考老师答应带我去。当我从最后一排走到第一排，老师跟我说，有人去了，你先回去吧等他回来再上

​然后等了一会又让我去上，洗了把脸神清气爽去厕所外结果一阵冷风吹过打了个喷嚏

​回来把T2特殊性质拿了。就是对于距离为0的村庄和城市，把村庄放在城市上然后连边跑 kruskal，$(kn+m)\log m$

​T3:看到一眼就懵了，我学了大半年的数据结构，dp，图论，树，你就考我我最薄弱的字符串？我 KMP，Trie，字符串哈希全都忘了啊。

​最后 $qL_1L_2\log n$，遗憾离场

​以为T4肯定是不可做的黑，就去想T2正解了。最后半小时看了一眼，是排列组合就输出了n!骗分，也是用的rp作变量名。赛后他们跟我说暴力能骗20分

​T2不敢赌自己的结论，对拍也不熟练，就没写正解
笑点解析:S组 T2 想出来了 $2^k$ 枚举用哪些村庄，然后 $kn$ 连边 kruskal。这复杂度就算我常数大，至少也是 80 分的。我在草稿纸上把这个复杂度圈起来 3 次，告诫自己很有可能是正解，并且画图也只画了 mst 的边
​然后

​我竟然在想，那些我枚举的村庄不一定要联通啊？题目甚至给“原来”两字加粗加点，我就想怎么判断只让城市联通就行。那你猜猜，枚举的意义在哪？

​我就卡在这个很弱智的点上，红温了一个小时，脑子越想越糊，全在想怎么解决这个问题，而没有考虑这个问题是否真的存在。也就是说，如果我当初没有考虑那么多，48->100

​等我脑袋清醒，赛后干了一会其他事后，才想起来我卡在了一个多么离谱的点

​正所谓当局者迷，旁观者清吧，这么一看变成mst模板黄题了

​可能是没有占到地利，导致上厕所时间被压缩，没有足够的清醒时间。可能算法学的比去年多，但心态却不如去年了

​心态很重要，这一年我的学习长期与烦躁绑定啊……

​总结:难得要死。个人感觉黄蓝紫，T4先入为主当做黑。洛谷评的是绿蓝紫紫，整体比去年难了一个档次。估分100+48+10+？

​一等奖又悬又有希望，太折磨了。原本想在中考前给OI画上一个完美的逗号呢……

PS:按考场的思路做真的是 80 分，把排序提出来之后就 AC 了 Link