CSP2025游记

曾经的巅峰实力在2025年2月的寒假里在lz冬令营集训的日子（不过也很弱）。

自进了初三，便没怎么碰OI了

来到ez后选了数竞，一暑假没碰过OI

CSPS考前一周临时抱佛脚，复习了一下以前的东西（尤其是线段树和莫队，以及一点点dp）

CSP-S考场在gdf，时间为2：30-6：30

早上，打了一个回滚莫队模板

中午1点10分，出发前往考场

吸取了去年的教训。考前半个小时先拉完了再进了考场。此时距离考试开始还有8分钟

坐在左边的是gdf的大神

心里默念几句：暴力打满=1=

开始，解压缩，看题面

T1入眼看了看，一眼dp，$O(n^3)$ 是容易想到的. 于是思考能否 $O(n\log n)$ 的 $dp$ 转移+优化。一时间没思路.过去大概10分钟

看T2，神秘道路修复经典，一眼板子题是 $O(2^k m\log m)$ 的，鉴于我考前完全没有复习最小生成树，不记得 Prim 咋写了，因为一眼稠密图，用 Prim 显然好过另外那个，先放着。

T3，字符串？这一眼哈希吧，看起来很 KMP，但是我考前特地没有复习 KMP（因为不熟悉），太好了。。然后开推，只需要考虑 $s_{i,0}$ 与 $s_{i,1}$ 本质不同的子串 $L_{i,0},L_{i,1}$，$t_{i,0}$ 与 $t_{i,1}$ 本质不同的子串 $T_{i,0},T_{i,1}$，于是每个

$s_{i}=M_i+\{L_{i,0},L_{i,1}\}+m_i$ $\;t_{i}=N_i+\{T_{i,0},T_{i,1}\}+n_i$

直接把 $\{L_{i,0},L_{i,1}\}$ 拼成 $L_i$，另一个同理。

于是 $s_i=\{M_i,L_i,m_i\},t_i=\{N_i,T_i,n_i\}$

只要 $T_i=L_i,M_i=(N_i)_{suf},m_i=(n_i)_{pre}$ 即可产生一个贡献

对每个 $N_i$ 的后缀和每个 $n_i$ 的前缀用哈希存到桶里，或者直接用 $map$ 存，然后对每个 $t_i$ 枚举所有的 $s_i$，时间复杂度 $O(nq)$ 能拿 $50pts$. 但是考场我唐了怕哈希会冲突因为不会处理哈希冲突先溜了。

看T4，一眼dp题，前面有8分搜索送分，发现一下子设计不出状态。溜了。

此时考试开始40分钟过去。我左边的gdf大神码得好用力，声音蛮大的，我还没开始码。。

看回 T1 苦思冥想 20分钟没想到怎么 dp，手摸样例忽然感觉是贪心，然后多手摸了几个，考虑把三个数减去中间大的那个，这样出现了一个非负数，一个0，一个非正数，ans预先加上所有中间大的数，然后把所有数排序加，判断一下能不能加，能加就直接加上去，不能就不要那个数。似乎对了。过了大样例。此时考试过去80分钟。看下一题。

苦思冥想，我不记得 Prim 咋写了，我考场上笃定这题用 Prim 的思想优化能做，而 $O(m\log m)$ 是困难优化的，难搞……

看T3，延申思路，但是哈希不太会写，难搞……

在这里徘徊了很长时间，最终导致后期没时间打暴力。

去厕所冷静了一下。走廊外的树与天空似乎黯然失色。

回到考场，还是想不起 Prim 咋写。好吧开始打暴力，因为笃定了 kruskal 优化不了，所以没细思。

码完怎么还调不出来，心态有点小崩。调出来了。距离考试结束还有30分钟。
感觉哈希没时间打了，本来就不熟悉，直接暴力飞快码完了T3，结果还要调。调完了。还剩5分钟。第四题蒙了个 cout<<0; 检查了一遍 freopen 没啥问题。

考完估分 100+20+10+0

太菜了/ku

上洛谷测了下T1没问题。看题解发现T2暴力似乎是48pts的，发现T4在m=n的那个点有可能为0. 那么可能100+48+10+4。

T2还真是 kruskal 优化啊？而且这么水的优化？/ku

太菜了/555

不过没关系，只要我错的都对了我就AK了。

语文课一结束就飞快地跑上来差分了

T3 有 25 分，出乎意料，T2 有 32 分，少爷机看来还是不太行。不过与最终预计的仅差了 1 分。

发现了公众号有点好玩。
把 T2 代码交到洛谷，发现 8AC 8WA 9TLE
原来不是少爷机太慢，又被小细节干掉了TT

感觉我左边的 gdf 大神 AK 了