CSP-J/S 2025 爆炸记

_Mortis_ · 2025-11-07 21:58:38 · 生活·游记

现在终于有空写游记了，补一篇。

Day -???(2025.7.20~2025.8.2)

到 HZNU（竟然是考点！）集训 14 days。

每日午饭、晚饭后打 MC，回寝室 UNO/斗地主。

Day -5?

晚自习逃离 GF 到 YYHS 训练。

（期间做了一堆 DP 题，然后 S 组 T4 是 DP。不会做。）

Day ??

whk 分别考了一次四科联考和四校联考。吃着老本拿下 rk1。

Day -5

停课到 GF 机房训练。

不得不说 zzk 都什么时候了还整天带着耳机听歌，偶尔刷刷视频，心态真好。（被 zll 发现并骂了一顿）

Day -1

有点低烧，遂在家休息。

下午 zzk 因在 GF 机房打 florr 被 UFO 撵回家了。

Day 0

上午复习板子，打 florr。

下午出发去 HZNU。

晚上突然想起自己图论和字符串忘光了，复习 Manacher、KMP、Dijkstra、SPFA 和 Floyd（注意细节：巧妙避开 S 组 T2 和 T3 的知识点）。

7 点到 8 点和 zzk 打 florr，合了 50 张 M 没出 U。

睡觉，热，睡不着，开空调，睡着。

Day 1

进入正题。

J

解压密码是上善若水。（上午的题的确很水！）

发现 J 组纯暴力能拿 100 + 100 + 60 + 64 = 324 。

8:38~9:0?

花半小时搞定前两题。

因为是正式比赛，我还是比较谨慎的。~~要是模拟赛我直接 5 min 写完。~~

9:0?~9:3?

T3 一眼暴力 O(n^2) DP：

dp_i = \max(dp_{i - 1},\max \limits _{ 1 \le j \le i \wedge \bigoplus \limits_{x = j} ^ i a_x = k}\{ dp_{j-1} + 1 \})

然后不会优化。遂看 T4。

9:3?~9:40(?)

T4 好像是排完序后枚举最长边，搞个背包，减掉不合法方案。没写代码，我又去看 T3。

9:40(?)~9:5?

发现转移中的 j 只会取最靠近 i 的一个，然后就开了个桶存后缀异或和，预处理 j ， O(n + 2 ^ {20}) 过了（其实边转移边存前缀和就行，当时脑抽）。

9:5?^10:02

思考 T4，刚才的想法似乎可行，打完代码大样例全过。我阿克了？！

10:02~12:00

T3、T4 几乎拍了 2h。

想睡觉发现位置太小。

11:3? 发现 T1 中我没判断就 cnt[s[i]-'0']++，且 int cnt[15];。修改。

估分 100 + 100 + 100 + 100 =400 。

S

考 S 时脑子很乱，根本没怎么记时间。

解压密码“人杰地灵”是指 S 组“人皆低零”吗？

T1 不会。先写 O(n^3) DP + 特殊性质弄到 70 分。

T2 看错题目 1h，T3 会 O (nq) 。

比赛开始约 1.5h 时才过 T1。呜呜呜。

写 T3 的 nq（找出 s1 和 s2，t1 和 t2 的最长公共前后缀，对于 s1 和 t1，s2 和 t2 各分成 3 段比较哈希值）。样例 3 跑了 3.0s。

写完 T3 还剩 1.?h，发现 T2 看错题，赶紧打了 48 分的特殊性质，又想到 m 条边中只用留一开始生成树中的边，写了个 O(m \log m + 2^k n \log n) ，死活调不对。

T4 写了 n \le 8 ，其余输出阶乘。

18:30 遗憾离场。

估分 100 + 48 + 50 + [8,12] = [206,210] 。

第二天发现 S T3 没判 s1 和 t1 的右部分，以及 s2 和 t2 的左部分，总分直接挂成 [156,210] 。

Day 6

J

100 + 100 + 100 + 100 = 400

S

100 + 56 + 30 + 8 = 194

CCF 没有用手出数据，让我的 T2 多了 8 分，T3 得到了 30 分。感谢 CCF！

Update on 2025.11.8 22:14：T3 数组开小了（5e6 开成 2e5）！ 214 \rightarrow 194 。这说明实际上我的神秘错误代码能过 CCF 的数据。我被 zsh 挂 debuff 了！同样数组越界。

:::warning[我的 T3 code]

注意第 5 行：const int N=2e5+10;

注意第 56~57 行：只判了 1 的左边，2 的右边。

~~注意我的模数：2833~~

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10;
const ull Base=2833;
string s1[N],s2[N],t1,t2;
vector<ull>H1[N],H2[N];
ull Pow[N],T1[N],T2[N];
int n,q,sz[N],l[N],r[N],L,R,ans;
ull gethash1(int x,int l,int r){
    return H1[x][r]-H1[x][l-1]*Pow[r-l+1];
}
ull gethash2(int x,int l,int r){
    return H2[x][r]-H2[x][l-1]*Pow[r-l+1];
}
ull gethasht1(int l,int r){
    return T1[r]-T1[l-1]*Pow[r-l+1];
}
ull gethasht2(int l,int r){
    return T2[r]-T2[l-1]*Pow[r-l+1];
}
void solve1(){
    while(q--){
        ans=0;
        cin>>t1>>t2;
        if(t1.size()!=t2.size()){
            cout<<"0\n";
            continue;
        }
        if(t1==t2){
            for(int i=1;i<=n;i++)
                if(l[i]>r[i])ans++;
            cout<<ans<<'\n';
            continue;
        }
        int szt=t1.size();
        t1=" "+t1,t2="*"+t2;
        for(int i=1;i<=szt;i++){
            T1[i]=T1[i-1]*Base+t1[i];
            T2[i]=T2[i-1]*Base+t2[i];
        }
        L=1,R=szt;
        while(L<=szt&&t1[L]==t2[L])L++;
        while(R>=1&&t1[R]==t2[R])R--;
        for(int i=1;i<=n;i++){
            if(l[i]>r[i])continue;
            if(r[i]-l[i]+1!=R-L+1)continue;
            if(gethash1(i,l[i],r[i])!=gethasht1(L,R)||
            gethash2(i,l[i],r[i])!=gethasht2(L,R))continue;
            if(L<l[i]||szt-R<sz[i]-r[i]){
//              cout<<"ooop! "<<q<<' '<<i<<'\n';
//              cout<<L<<' '<<R<<' '<<l[i]<<' '<<r[i]<<' '<<szt<<'\n';
                continue;
            }
            if(gethash1(i,1,l[i]-1)==gethasht1(L-l[i]+1,L-1)
            &&gethash2(i,r[i]+1,sz[i])==gethasht2(R+1,sz[i]-r[i]+R))ans++;
        }
        cout<<ans<<'\n';
    }
}
int main(){
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q;
    Pow[0]=1;
    for(int i=1;i<=2e5;i++)Pow[i]=Pow[i-1]*Base;
    for(int i=1;i<=n;i++){
        cin>>s1[i]>>s2[i];
        sz[i]=int(s1[i].size());
        s1[i]=" "+s1[i],s2[i]="*"+s2[i];
        H1[i].push_back(0ull),H2[i].push_back(0ull);
        for(int j=1;j<=sz[i];j++){
            H1[i].push_back(H1[i].back()*Base+s1[i][j]);
            H2[i].push_back(H2[i].back()*Base+s2[i][j]);
        }
        l[i]=1,r[i]=sz[i];
        while(l[i]<=sz[i]&&s1[i][l[i]]==s2[i][l[i]])l[i]++;
        while(r[i]>=1&&s1[i][r[i]]==s2[i][r[i]])r[i]--;
    }
    solve1();
    return 0;
}

:::

血的教训。

闲话

50 + days 不写作业，5 days 不上课，whk 炸光了。我在 11.5~11.6 晚自习的培优班四科联考中拿下四科 rk8,rk2,rk3,rk2 和总分 rk1 的“好成绩”。值得一提的是，我的理科直接从 rk1 掉到了 rk2。从总分来看，我与 rk2 的分差仅剩 7 分。我该如何复健 whk？？？

GF 三人组另两人情况

zzk J 没阿克，S 120，退役了，该。

zsh J 阿克，S 数组越界导致 194 \rightarrow 178 。