当前位置：首页 > news >正文

回归 CSP-S2025游记

news 2026/5/12 2:09:59

洛谷传送门

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

坐标 $HA$

DAY 0

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

DAY 0.5 CSP-S第一轮(2025.9.28)

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

估分: $$52.5pts$$
实际: $$54pts$$

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

分数线 $42.5pts$

DAY 1 CSP-S第二轮(2025.11.1)

比初赛起得早。

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

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

$14:10$ 进场，（考场好挤，但比去年好多了）

$14:20$ 电脑解控，一边打快读板子，一边做梦……（幻想这次切掉T1，T2T3暴力加性质拿个 $100$，T4暴个 $10$，拿下 $210pts$ ）

$14:30$ 发了解压密码，开始看题。

$14:30-15:00$ 浏览四道题，

看到 $T1$ 有 $O(3^n)$ 暴搜 $+性质A$一共 $25pts$ 。

$T2$ 最小生成树模版 $20pts$ 。

$T3$ 暴力 $O(qnL^2) = O(n^2L^2)$ $10pts$ 。

$T4$ 感觉暴力加性质有 $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$ 。