CSP-S2025游记(FJ)

今年状态非常差，感觉发挥比平时烂了好多
真是的，上次也是这样

六点多起床，床上躺到七点

喝了一杯咖啡

有人来问我S组考不考基环树，我说不考，结果他把那道星战端出来，就看了一会怎么找环

然后继续翻大纲有没有没复习的，给人讲了一下exgcd，卡特兰数浮光掠影看了下，然后发现CRT和威尔逊定理不记得了匆匆看了几眼就去吃饭

事实证明没用，都没考

考场的风好大

先全部看了一遍，浮光掠影大致看懂题意，但是只是看懂题意没有进一步评估，导致后两题时间严重不够

被贪心做局了😭😭😭

最开始想了一个反悔贪心，涉及到三个堆互相乱跳，发现相当难写

后来考虑直接人类智慧每个位置都排序，然后一步步填

加上读题大概 $40min$ 写完，第二个样例都没过

怀疑是否读错题，读完发现没错

于是打算花 $20min$ 把显然的 $O(n^3)$ dp写掉混个50分，再特殊性质混到 $70$ 差不多得了

确实 $20min$ 打完了，第二个样例都没过，再次怀疑是否读错题

因为手模太麻烦了，于是又写了一个搜索，反复对拍找小数据

最后用 $n=6$ 的数据拍出来一个，发现是初始边界错了

因为反复的折磨已经过去了进 $2h$ ，我的心态开始爆炸

事实上 $T1$ 暴力出问题的时候就已经来看看 $T2$ 了，发现这题也是个人物

首先就是喜闻乐见的读错题环节，手模了 $5min$ 才发现那k个点是新建的点不是原来的 $[1,k]$

发现 $k$ 很小，直接暴力 $2^k$

剩下部分考虑Kruskal生成树

最开始发现如果要新加边进去的话很难处理，于是在想怎么避免，然后想到可以直接各自排好，最后用的时候用类似归并的方法拼起来

既然可以把排序提到外面，那么大头的复杂度就可以去掉一个 $\log$ ，显然这个时候并查集再用只有路径压缩的 $log$ 级别优化就不太礼貌了，写了另外带了启发式合并的 $\alpha(n)$ 并查集

于是总复杂度应该是 $O(2^k[nk+m+\alpha(n+k)]+(m+nk)\log m)$
(从来没写过这么复杂的复杂度式子，大概不太标准吧)

这个复杂度相当危险，我认为只能很少部分分

byd为什么我觉得看起来比前两题都有思路

这个时候我只能分给它 $1h$ 了，速战速决，暴力就暴力吧

手模一下发现，在 $t1,t2$ 有不同的情况下不会出现第一种情况，所以简单了一些

然后如果 $t1$ 想要变成 $t2$ ，中间不同的部分一定要被换掉，所以能换的一定是包含它的字串

那么就直接枚举字串，然后往回检查算了吧，这样还能混 $10$ 分

结果突然想起来字符串比较是 $O(n)$ 的，好像连 $10$ 分都过不了

于是又写了个hash(只剩 $15min$ 了，不讲究了，直接单模数hash)

用完hash后发现 $n$ 的部分可以用map优化掉，加上之后快乐不少，但是还是不一定能过第二块点

继续试图研究，找到一个错误思路，原本的串s直接取两个串不同的部分，随手造出来就是错的

但是依旧有价值，因为发现把不同部分切开后剩下部分可以直接变成前后缀的结构

于是可以记录前后缀hash，中间部分hash出来之后去直接二分check里面的部分是否合法，时间复杂度应该是 $O(|L|+nq\log |L|)$ 的，第二版部分分能过

但是已经没时间写了😭

$10min$ ，极限！

一眼发现阶乘写法，非常愉快地写掉了

想再贪贪 $n\le 18$ 的 $2^n$ 做法，发现时间不够推了

最后剩十分钟得检查各代码情况是否正常

最后 $3min$ ，意外发现有全 $1$ 的阶乘情况，当时顾不了判断其他了，直接赶着写了个阶乘上去，应该混不到分

仔细想想，这次真正投入认真想题推演的时间很少，很大程度上是因为我 $T1$ 心态崩了

$T1$ 心态崩了是因为耗时过多，这里就涉及到时间规划的问题，先浮光掠影地看题是没有什么意义的，真正需要的是看完题之后进行评估

以及T1这个边界问题很严重，不止一次了

等着NOIP吧，如果能进的话

一定得想办法调整每一次的考试状态