CSP-S 2025 游记

_buzhidao_ · 2025-11-02 09:50:18 · 生活·游记

去年暑假基本已经 AFO 了，所以咕了游记。今年补上。

怎么不让写暴戾语言啊。

Day -41

初赛。

上场的时候比较悠闲，做着题哼着歌。

写完阅读程序 T2 的时候去上了个厕所并换了张草稿纸。感觉 50\,\text{pts} 有了。

考完回家估的满分。但后来有一题挂了，97\,\text{pts} 遗憾离场。

Day -13

SCP。

T2 磕了 2\text{h} 过了。

剩下的 1.5\text{h} 只写了后两题的暴力，220\,\text{pts} 遗憾离场。

怎么 rating 才 +100 啊，我打得不好吗。

Day -5

whk。

晚上父母向老师提出停课请求，一直没有得到答复。

Day -4

去上学了。

回家得知成功停课，救赎。

Day 0

就是在家打板子吧。

场上不一定有小熊猫，只好下了个 Code::Blocks 练手，还挺好用。

晚上摆了。

Day 1

七点醒，拼尽全力无法重新入睡。

想起自己平衡树没打、tarjan 没背、马拉车没学。而且自己如果进不了 NOIP 就要回去上学了，有点慌。

头痛。遂颓了一个上午。

愿天堂没有树论，愿天堂没有字符串。

怕什么来什么，好耶。

走进考场，一股热浪扑来，像一床棉被，压住了我昏沉的脑袋。

我扫了眼桌面，上面干干净净，只有 Dev 和 VS code 的图标。键盘被冻得硬邦邦，鼠标在屏幕上龟速爬行。

T1 5\min 才瞪出结论。然后调 Dev 人机符号匹配调鼠标灵敏度适应键位导致 25\min 才写完拍完。

开 T2。注意到 k 较小于是状压 k，但复杂度假了。

等等那个 Kru 什么的算法怎么拼的来着？不管了函数名直接叫 kru 吧。

可以直接在生成树过程中把村庄权值设为 0 然后做？火速写出来一测样例，挂了。

偷瞄了眼 T3，以为不限制替换次数，意识到不可做，逃。

观察到 n 较小，而且原图已经连通？是不是只要照着原图的生成树加就行了？

复杂度 O\left(2^k nk \log(nk)\right)，过不了 CCF 老爷机吧。而且做法怎么证？扔了。

看到乡村有点权连拆点都想出来了，但没过样例。

那只能状压 k 了吗。

当时以为状压 k 只能拿 8\,\text{pts}。有点累了，所以骗了个性质 A 走人。

写完 148\,\text{pts} 已经来到了后半场，头已经开始痛了。

还没上 200，有点慌。

开 T3。

细想一下发现不对劲，如果允许替换多次可能会导致无限循环，又推了一下样例 2，意识到读假题了。

woc CCF 搞慈善呢，用脚写一个 KMP 就是 25\,\text{pts}。

这时感觉正解是一个 AC 自动机状物。哎，我写的 AC 自动机是假的，平方复杂度，还是稳一点吧。于是去打性质 B。

注意到 \sum t_{i,j} 有限制，于是枚举一维再用屁股二分另一维又是 25\,\text{pts}。

难点在两个 25 中间的加号。

到这里估分已经来到了 198\,\text{pts}，心态稍微好了一些。

只剩 30\min 了，急急急。

开 T4。开始没看到 0 \le c_i，以为输出 n! 能拿 20\,\text{pts}。测完样例发现假。

然后以为面试者放弃面试的前提是前面有至少连续 c_i 个人失败，所以胡了个 O(n^2 2^n) \cdot O(n) 的状压。

诶这个复杂度是不是过不了 n \le 18。哦原来我又读假题了。改改改。

补兑我状压怎么写挂了。然后发现状态转移没改，笑死。

这时已经 18:10 了。对着两个性质思索 5\min 无果就去写 T2 的状压。明智地备份了 48\,\text{pts} 的代码。

写了 5\min，发现 0-index 和 1-index 混淆了，改完一个样例测炸。

草草草怎么 18:25 了。检查文件的时候手都在抖，怕把代码删了。

考完发现 T2 状压大概能过 16\,\text{pts} \sim 24\,\text{pts}，有些后悔。

忽然想到这个老爷机浪费了自己一定的时间导致没写完状压。【】考场，【】Dev。

我一直念念不忘自己没写完的代码，没有理会监考老师叫我的座位号让我上去签字，所以最后一个走的。/kk