回归 && CSP-S2025游记

· · 生活·游记

博客传送门

utd 2025.11.25:更新了后续

去年打完 CSP-S 拿了 2= 没过线就退役回 whk 了，回归之后的第一站：CSP2025

坐标 HA

DAY 0

初赛前一周回归复习了一下 （其实复习的基本上都没考）

DAY 0.5 CSP-S第一轮(2025.9.28)

起的不早，因为下午才考。。又看了看数据结构就上场了

估分: 52.5pts 实际: 54pts

没想到初赛比去年认真复习考的还高

分数线 42.5pts

听说今年CCF升级机器了，希望不要卡常了

DAY 1 CSP-S第二轮(2025.11.1)

原来我也是个考试之前会紧张到手抖的蒟蒻qwq

比初赛起得早。

看了看 图论最短路，st表，线段树，树状数组 （这些都是去年 AFO 之后基本上没碰过的东西……） 切了两道 dp 找了找手感，发现我忘记 freopen 格式了，赶紧去搜。。。

中午听说 J组 题很简单，小小激动了一下（赛后证明这是多余的）

$14:20$ 电脑解控，一边打快读板子，一边做梦……（幻想这次切掉T1，T2T3暴力加性质拿个 $100$，T4暴个 $10$，拿下 $210pts$ ） $14:30$ 发了解压密码，开始看题。 $14:30-15:00$ 浏览四道题， 看到 [$T1$](https://www.luogu.com.cn/problem/P14361) 有 $O(3^n)$ 暴搜 $+性质A$一共 $25pts$ 。 [$T2$](https://www.luogu.com.cn/problem/P14362) 最小生成树模版 $20pts$ 。 [$T3$](https://www.luogu.com.cn/problem/P14363) 暴力 $O(qnL^2) = O(n^2L^2)$ $10pts$ 。 [$T4$](https://www.luogu.com.cn/problem/P14364) 感觉暴力加性质有 $40pts$ 又小小激动了一下，感觉今年要好起来了。 $15：00$ 我一直认为我能切掉 $T1$，直到写了两个贪心策略都假了之后才感觉不对劲，想到 $dp$ 了，但我想 ~~提高组T1应该不会考 $dp$ 吧~~（确实没考，是反悔贪心，但是dp能拿高分） 直到 $16:20$ 才放弃，看 $T2$， 发现最小生成树 $Kruskal$ 模版忘了哈哈哈。。。被自己气笑了，试了半天也没对，放弃的时候已经过去 $2.5h$ 了…… $16:00$ 只剩下 $1.5h$ 手里只有 $25pts$ 其实心态已经炸了，$T3$ 看出来了是字典树但是不会写， $10min$ 打了 $10pts$ 的暴力之后看到性质 $B$ 突然有一个大胆的的想法，对于每个 $s_{i,1},s_{i,2}$ 开 $a_{1_{n,3}}$ 和 $a_{2_{n,3}}$ ，对于 $a_{i,1}$ 存这个字符串中 $a_{i,1}$ 表示 字符 $'b'$ 前面 $'a'$ 的数量，$a_{i,1}$代表 $'b'$ 的位置, $a_{i,1}$代表 $'b'$ 之后 $'a'$ 的数量，再把每次 $q$ 询问的 $t_{j,1},t_{j,2}$ 用 $k_1,k_2,k_3,j_1,j_2,j_3$ 其含义同上，（因为对于所有字符串都满足 $1 \leq j \leq q$, $t_{j,1}, t_{j,2}$ 均为 **特别的** 性质B ）所以对于每个 $s_1,s_2$ 遍历一遍 $a_{1_{n,3}}$，可以证明当且仅当满足 $$(a_{1_{i,1}} \leq k_1)且( a_{2_{i,3}} \leq k_3)$$ 时，有 $$j_i = k_1-a_{1_{i,1}}+a_{2_{i,1}}$$ 然后与 $j$ 比较即可，大样例跑得很快，时间复杂度为$O(n)$, $T3$ 有 $35pts$ 。 最后 $T4$ 也是没时间写了，瞎写了几行。 预计：$$25+0+35+0 = 60pts$$ 实际 ## ## 感想 几年的遗憾主要是在 $T2$ 的20分最小生成树和 $T1$ 的 $dp$ 分，这次还是栽到做题策略上了，但是 $T3$ 推出来性质的时候真的很开心，可能这就是我热爱 $OI$ 的原因吧……希望能进 $NOIP$ 。 ## 其他的等分出来再更新吧。。。 ## （2025.11.25） 后续来啦…… 实际：$$25+0+0+0 = 25pts$$ $T3$ 没有去重。。。报鸭蛋了。。。AFO咯 ~~实则不然~~ B类名额居然补到我了www $NOIP$ 见啦（蒟蒻第一次打 $NOIP