CSP-J/S 2025游记

HuangBarry · 2025-09-20 18:13:06 · 生活·游记

坐标 SC。

下面是本文提到的人名简写与洛谷 UID 对应表：

初赛Day0（19th September）：

重学排列组合，又做了一套模拟题，把老师发的知识点大全过了一遍后，睡。

初赛Day1（20th September）：

七点半：

起床。

八点：

出门，依旧早饭麦当劳（去年初赛那天早上也是麦当劳）。

八点半：

路过考点门口，停车去了，看到 HJM 站在校门口，QQ 群里 HJM 问有人到没，WZH 说刚醒。

停好车后往校门口走，路上同时遇到了核桃编程和有道小图灵的发传单的老婆婆，她们两因为我扫哪个机构的码还争吵起来了。

和 HJM 碰面，在门口瞎转悠，等三个教练来。

教练来了又给每人发了一张准考证，然后我去买了瓶东方树叶就进学校了。

九点：

教学楼楼下排队，和 CS 等人交流，我说肯定要考哈夫曼编码。

过了一会就要进考场了，我和 CS、WZH 和一个我们学校但是我不认识的一个人一个考场。我和 CS 一起在教室门口准备安检，看到教室内的大屏上写的是：

CSP-S XXX 考试
试卷共 4 张 14 页
XXX

我和 CS 就知道了 S 组的题量，但没过多久就改了，

LJX 进了我们考场结果转了一圈发现走错了，快开考了 WZH 才进考场。

九点半（\textcolor{red}{J组初赛开考}）：

第 1 题，注意到是无符号。

第 4 题，真考了哈夫曼但是这题不会。

第 9 题，怀疑了自己的语法能力，思考 string 类型能直接加 char 吗，后面第一个完善程序看到了这个用法，回来把这题补上了。

第 14 题，错了，基础知识不牢。

第 15 题，简单但是错了，因为 A、C 两个选项可以看成一个是从队头开始遍历，一个是从队尾开始遍历，所以不知道哪个是对的。

阅读程序略。

第一个完善第 5 题，没看到 for 没有 i++，以为有，就选了个 D.// 不执行任何操作。

第二个完善没想到是一道交互，到现在我都没懂它是怎么实现的，但是靠联系上下文把这 5 道题做满了。

十一点半：

出考场和 CS、WZH 瞎聊，一起慢慢下楼，走到一楼了 CS 说他包忘拿了然后赶回去拿，然后我和 WZH 就先走了。

出学校遇到了高手 LJX，跟我们说没有橡皮涂卡涂错了 5 个，然后 KZY 没看到第一题是 无符号整形，然后选了 C.$2\times 10^9$（代码段怎么不支持打 \LaTeX），其实还遇到了好几个同样错误的人。

在学校门口一堆人聊了一会儿，我就和 LYJ、WZH、HJM 吃饭去了。

我们到了一家猪肘饭门口，坐下准备凑合吃了，然后杨教练发消息问我们在哪，考虑去他们那边，然后我们就赶紧跑去教练那吃砂锅，此处感谢杨教练请吃饭。

吃的时候我一直在关心答案，教练还说我一直施压力，还说了我一顿。

中午我在我爸车上午休，起来后买了杯古茗就进学校了。

十四点：

教室里遇到 HZT，他拉着我去拜文翁，去磕了三个头就坐在教室里等开考了。

十四点半（\textcolor{red}{S组初赛开考}）：

开考，教室里一大半人没来。

过程略。// 懒得写了

大致是选择一眼没瞪出答案的就跳，后面大题做一大道就回来看一眼。

第二个完善还是交互，我连题面都没看懂，纯靠代码片段联系上下文给做对了五道还是四道。

十六点半：

出考场，依旧和人瞎聊，一出学校，想起手机落考场了，赶紧跑回去拿，然后慢慢走出来的时候偶遇 ZZQ，和他边聊边走出来。

没想到洛谷这么快就出答案了，赶紧对，对完人傻了，83 分，但是细想这次题确实简单，然后和其他人聊了一会拍了个合照就跑路了。

回去还剪了个头，丑死了。

二十点半：

怎么还要打 abc。

0 罚时写了四题，rk1617，涨了 23 分。

25th September：

上完晚自习回家知道出成绩了，没啥说的，在学校信竞 qq 群里说了几句话就被禁言了。

最后 J76，S83。

3rd October：

去世界线漫展了，可惜没 1 号去，有柜子学院的 cos 看，前两天去集训去了。

还在绘画区画了个学校校徽（图片损坏了）。

18th October：

停课集训的分班考试，但是因为我才初二，这个考试还决定我是否停课。

结果是排名正中间，和 ZZQ 同分，原本常教练给我定的目标就是超越 ZZQ。

也是顺利停上课了。

集训期间（19th October到31st October）：

去高中部集训了，伙食比初中部好，每天还有 1 节体育课，第一周做专题，第二周打模拟赛，还逃过了一场数学期中考试。

复赛Day0（31st October）：

这天的模拟赛是信心赛，但还是挂分了，晚上扫共享电瓶回家，WZH 非要坐，给他送到我家小区门口他又不乐意了。

晚上背了一堆板子，然后就睡了。

复赛Day1（1st November）：

七点：

起床收拾东西，出发。

早饭不知道吃啥依旧麦当劳。

飞速到考场门口，依旧和他们瞎聊。

八点：

进学校，等开考。

八点半（\textcolor{red}{J组复赛开考}）：

前两题直接秒了，然后看 T3，一眼 dp，然后就没管看 T4 了。

T4 知道是 dp，但是不会写，于是写了个暴力和组合数学就跑了。

T3 写了半天只能说写了一坨，dp 也写的是部分分，赛场也没想到贪心，调也调了特别久。

十二点：

出考场，猜到学校里会有 AK 的，XJH 就估分 400，CS、HYX 380，感觉就我一个(100+100+60+60=)320。

出考场依旧瞎聊，写游记的时候啥都想不起来了，中午和 CS 他们一起吃饭，没想到又吃一顿麦当劳，让他们帮我抽卡，明日方舟半周年刚更新，40 抽出了银灰。

快吃完了还遇到教练。

依旧在我爸车上午休。

十四点：

到校门口，随便说了几句就进去了。

十四点半（\textcolor{red}{S组复赛开考}）：

开考。

考的一坨不想写。

大概是，T1 写了个 dp，T2 写了个跑 2^k 遍 Kruscal 的暴力，T3 写了个暴力，T4 写了个输出 0，T4 代码甚至是最后 30s 才交的。

T1 第一眼就是反悔贪心或 dp，但是不会写反悔贪心。

T3 其实赛时想到了 Hash 可以拿大部分分但是写完双 Hash 后调了 1h 无果，于是写了个暴力就走了。

T1、T3 小聪明写了几个特判略减复杂度然后 WA 了。

十八点半：

刚下楼发现手机又忘拿了赶紧跑回去拿。

出考场和他们聊，发现大家估分差不多，心里舒坦了点，然后去聚餐了。

到了初中部后面一个商业体，全部考 S 的和教练（除杨教练）在那吃饭。

跟教练说 8 道题的 freopen 一个没测过，教练也无语了，但最后也没有因 freopen 挂分。

吃完就回去了。

八百年后的某天：

出成绩了，J(100+100+75+64=)339，S(55+40+5+0=)100。

屎。

今年考的屎，游记也写的水，就这样吧，明年再战。

赛时代码：

J：

number：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
string s;
void solve(){
    cin>>s;
    string ans="";
    for(char c:s)
        if('0'<=c&&c<='9')
            ans+=c;
    sort(ans.begin(),ans.end(),greater<char>());
    while(ans.front()==0)
        ans.erase(ans.begin());
    if(ans.empty())
        cout<<0<<endl;
    else
        cout<<ans<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    int T=1;
    // cin>>T;
    while(T--)
        solve();
    return 0;
}

seat：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m,a[111];
void solve(){
    cin>>n>>m;
    for(int i=1;i<=n*m;i++)
        cin>>a[i];
    int R=a[1];
    sort(a+1,a+1+n*m,greater<int>());
    int pos=1;
    for(int i=1;i<=m;i++){
        if(i&1){
            for(int j=1;j<=n;j++,pos++){
                if(a[pos]==R){
                    cout<<i<<" "<<j<<endl;
                    return;
                }
            }
        }else{
            for(int j=n;j>=1;j--,pos++){
                if(a[pos]==R){
                    cout<<i<<" "<<j<<endl;
                    return;
                }
            }
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("seat.in","r",stdin);
    freopen("seat.out","w",stdout);
    int T=1;
    // cin>>T;
    while(T--)
        solve();
    return 0;
}

xor：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=5e5+55;
int n,k,a[N],dp[N];
vector<int>cnt;
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    int last=1;
    cnt.push_back(0);
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1];
        if(find(cnt.begin(),cnt.end(),k^a[i])!=cnt.end()){
            dp[i]++;
            last=i+1;
        }
        cnt.clear();
        cnt.push_back(0);
        if(dp[i]==dp[i-1]){
            int sum=a[i];
            cnt.push_back(a[i]);
            for(int j=i-1;j>=last;j--){
                sum^=a[j];
                cnt.push_back(sum);
            }
        }
    }
    cout<<dp[n]<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
    int T=1;
    // cin>>T;
    while(T--)
        solve();
    return 0;
}

polygon：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int mod=998244353;
int n,a[5555];
long long fact[5555],invfact[5555];
long long ans=0;
void dfs(int pos,int sum,int maxx,int cnt,int last){
    if(cnt>=3&&sum>2*maxx&&last!=cnt){
        ans++,ans%=mod;
        last=cnt;
    }
    if(pos>n)
        return;
    dfs(pos+1,sum,maxx,cnt,last);
    dfs(pos+1,sum+a[pos],max(maxx,a[pos]),cnt+1,last);
    return;
}
long long qpow(long long base,long long power=mod-2,int mod=mod){
    long long res=1;
    while(power){
        if(power&1)
            res*=base,res%=mod;
        base*=base,base%=mod;
        power>>=1;
    }
    return res;
}
void init(){
    fact[0]=1;
    for(int i=1;i<=5000;i++)
        fact[i]=fact[i-1]*i%mod;
    invfact[5000]=qpow(fact[5000]);
    for(int i=4999;i>=0;i--)
        invfact[i]=invfact[i+1]*(i+1)%mod;
    return;
}
long long C(int m,int n){
    if(n==0||n>m)
        return 0;
    return fact[m]*invfact[n]%mod*invfact[m-n]%mod;
}
void solve(){
    cin>>n;
    int maxx=-1;
    for(int i=1;i<=n;i++)
        cin>>a[i],maxx=max(a[i],maxx);
    if(maxx!=1){
        dfs(1,0,0,0,0);
        cout<<ans<<endl;
    }else{
        init();
        long long ans=0;
        for(int i=3;i<=n;i++)
            ans+=C(n,i),ans%=mod;
        cout<<ans<<endl;
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("polygon.in","r",stdin);
    freopen("polygon.out","w",stdout);
    int T=1;
    // cin>>T;
    while(T--)
        solve();
    return 0;
}

S：

club：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+15;
struct node{
    int a,b,c;
}A[N];
int n;
void solve(){
    cin>>n;
    int suma=0,sumb=0,sumc=0;
    for(int i=1;i<=n;i++)
        cin>>A[i].a>>A[i].b>>A[i].c,suma+=A[i].a,sumb+=A[i].b,sumc+=A[i].c;
    if(sumb==0&&sumc==0){
        cout<<suma<<endl;
        return;
    }
    if(sumc==0){
        bool now=0;
        vector<vector<int>>dp(2,vector<int>(n/2+1,0));
        for(int i=1;i<=n;i++){
            for(int j=0;j<=min(i,n/2);j++){
                int k=i-j;
                dp[now][j]=dp[!now][j];
                if(j>0)
                    dp[now][j]=max(dp[now][j],dp[!now][j-1]+A[i].a);
                if(k>0)
                    dp[now][j]=max(dp[now][j],dp[!now][j]+A[i].b);
            }
            now=!now;
        }
        int ans=-1;
        cout<<dp[!now][n/2]<<endl;
        return;
    }
    bool now=0;
    vector<vector<vector<int>>>dp(2,vector<vector<int>>(n/2+1,vector<int>(n/2+1,0)));
    for(int i=1;i<=n;i++){
        for(int j=0;j<=min(i,n/2);j++)
            for(int k=0;k<=min(i,n/2);k++){
                    int l=i-j-k;
                    if(l>n/2)
                        continue;
                    dp[now][j][k]=dp[!now][j][k];
                    if(j>0)
                        dp[now][j][k]=max(dp[now][j][k],dp[!now][j-1][k]+A[i].a);
                    if(k>0)
                        dp[now][j][k]=max(dp[now][j][k],dp[!now][j][k-1]+A[i].b);
                    if(l>0)
                        dp[now][j][k]=max(dp[now][j][k],dp[!now][j][k]+A[i].c);
            }
        now=!now;
    }
    int ans=-1;
    for(int j=0;j<=n/2;j++)
        for(int k=0;k<=n/2;k++)
            ans=max(ans,dp[!now][j][k]);
    cout<<ans<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    int T=1;
    cin>>T;
    while(T--)
        solve();
    return 0;
}

road：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e4+14,M=2e6+26;
int dad[N];
int Find(int x){
    if(dad[x]!=x)
        dad[x]=Find(dad[x]);
    return dad[x];
}
void Union(int x,int y){
    int fx=Find(x),fy=Find(y);
    dad[fy]=fx;
    return;
}
struct edge{
    int u,v,w;
}e[M],e_[M];
int n,m,k;
int c[11],a[11][N];
long long ans=1e18;
void solve(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[i]=edge{u,v,w};
    }
    for(int i=1;i<=k;i++){
        cin>>c[i];
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    }
    for(int t=0;t<(1<<k);t++){
        for(int i=1;i<=m;i++)
            e_[i]=e[i];
        long long sum=0;
        int cnt=0,pos=m;
        for(int i=1;i<=k;i++)
            if((t>>(i-1))&1){
                cnt++;
                sum+=c[i];
                for(int j=1;j<=n;j++)
                    e_[++pos]=edge{n+cnt,j,a[i][j]};
            }
        if(sum>=ans)
            continue;
        sort(e_+1,e_+1+pos,[&](const edge&X,const edge&Y)->bool{
            return X.w<Y.w;
        });
        for(int i=1;i<=cnt+n;i++)
            dad[i]=i;
        int cnte=0;
        for(int i=1;i<=pos;i++){
            if(sum>=ans)
                break;
            if(cnte==n+cnt-1)
                break;
            edge E=e_[i];
            if(Find(E.u)!=Find(E.v)){
                sum+=E.w;
                cnte++;
                Union(E.u,E.v);
            }
        }
        ans=min(ans,sum);
    }
    cout<<ans<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    int T=1;
    // cin>>T;
    while(T--)
        solve();
    return 0;
}

replace：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=2e5+25;
int n,q;
string t1[N],t2[N];
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>t1[i]>>t2[i];
    while(q--){
        string s1,s2;
        cin>>s1>>s2;
        int len=s1.size();
        if(len!=s2.size()){
            cout<<0<<endl;
            continue;
        }
        int ___=int(s1[0]!=s2[0]);
        for(int i=1;i<len;i++)
            if(s1[i]!=s2[i]&&s1[i-1]==s2[i-1])
                ___++;
        if(___!=1){
            cout<<0<<endl;
            continue;
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            int L=t1[i].size();
            int _=0;
            for(int j=0;j<len-L+1;j++)
                if(t1[i]==s1.substr(j,L)&&t2[i]==s2.substr(j,L))
                    _++;
            cnt+=int(_==1);
        }
        cout<<cnt<<endl;
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    freopen("replace.in","r",stdin);
    freopen("replace.out","w",stdout);
    int T=1;
    // cin>>T;
    while(T--)
        solve();
    return 0;
}

employ：

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e5+15;
struct node{
    int a,b,c;
}A[N];
int n;
void solve(){
    cout<<0<<endl; 
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
     freopen("employ.in","r",stdin);
     freopen("employ.out","w",stdout);
    int T=1;
    cin>>T;
    while(T--)
        solve();
    return 0;
}