CSP 2025 挂分记

· · 生活·游记

省流：拼尽全力无法战胜 s组 t3&t4。

Day -?

初赛 j 97，s gesp过。

Day 0

为了逃课提早到杭州，列车上过了csp-s 2023 t3 结构体。到酒店后复习了树剖和马拉车，然后打了一晚上 generals 和 florr。

Day 1

9:10 AK 上午比赛，然后试机+对拍，没有问题。
10:00 睡觉到11：40。然后填表格。

早上AK过于兴奋，中午没怎么休息，于是下午挂分了。

t1鉴定为送分贪心，30行完成，通过大样例时是 14:52。

看见t2是最小生成树相关图论，就知道200pts已经到手了。
对于这种问题，一律先找一棵最小生成树出来，再考虑优化接下来的过程。写了 O(2^{k}nk\alpha(nk)) 的，大样例跑的飞快，在手搓极限数据的情况下跑了 1.5s，应该过了。

t3 字符串 t4 DP，我更倾向于做 t4，但是还是高估了自己的 DP 能力，只能状压+(n=m)+输出0=24+eps pts。
t3 的话只会 kmp 暴力的 O(nL2+qL1)，想到了trie树但感觉做不了，因为我太蒻了，从来没有做过这种题型。于是只能 25 pts。

回去和同学及学长交流，发现学长们几乎都做出了 t3，300+pts。又发现他们 t1 大多写了七八十行。于是非常担心挂分。

在列车上复现了 t1&t2 代码，都顺利通过。于是放下了心。

Day 2

复现 t4 代码并顺利拿下 24pts。然后写 t3 代码时发现kmp写挂了：

    for(int j=0;j<x.size();j++){
                while(now&&s[i][now]!=x[j])now=kmp[now-1];
                if(s[i][now]==x[j])now++;
                if(now==s[i].size()){
                    vis[j]=1;
                    now=kmp[now];//应为不写或kmp[now-1]
                } 
            }

但是民间数据还给我拿到 25pts，祈祷 ccf 数据水一点。

最终基本尘埃落定了，100+100+[0,25]+[24,24+eps]=[224,249+eps]分，基本是我的全部实力了。

看来是时候向紫题进军了。