CSP-S2025游记(FJ)

· · 生活·游记

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

赛前

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

喝了一杯咖啡

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

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

事实证明没用，都没考

考场的风好大

赛中

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

T1

被贪心做局了😭😭😭

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

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

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

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

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

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

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

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

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

T2

事实上 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)

(从来没写过这么复杂的复杂度式子，大概不太标准吧)

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

T3

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|) 的，第二版部分分能过

但是已经没时间写了😭

T4

一眼发现阶乘写法，非常愉快地写掉了 想再贪贪 $n\le 18$ 的 $2^n$ 做法，发现时间不够推了 最后剩十分钟得检查各代码情况是否正常 最后 $3min$ ，意外发现有全 $1$ 的阶乘情况，当时顾不了判断其他了，直接赶着写了个阶乘上去，应该混不到分 ## 总结 仔细想想，这次真正投入认真想题推演的时间很少，很大程度上是因为我 $T1$ 心态崩了 $T1$ 心态崩了是因为耗时过多，这里就涉及到时间规划的问题，先浮光掠影地看题是没有什么意义的，真正需要的是看完题之后进行评估 以及T1这个边界问题很严重，不止一次了 --- 等着NOIP吧，如果能进的话 一定得想办法调整每一次的考试状态