CSP-S 2026 游记

· · 生活·游记

day -3

上午依旧文化课，下午一场模拟赛

T1橙题快速签到

T2绿题刚开始不会，去打T3绿题，发现是个BFS秒了

回去想T2，最后1h想到正解，是个类似扫描线的玩意，快速一写，样例错了，半天没调出来，遗憾离场

赛后发现我T2有一个0写成1了，不然就AC了，可惜了

day 0

中午12:30吃完饭就准备上大巴车了

成功获得qy吧唧

Air在车上就开始玩电脑了，sc又开始看他的小说了，后面xhz开始抽卡了，甚至还有5人五排王者（难道只有我没事干吗？）

经过慎重考虑，我决定睡觉（失败了）

过了一会儿Air又开始玩音游了，一看手速直接吓哭了

到了酒店，直接耍起

下午和lhh，xhz，sc，wzj，lmz一起买了个蜜雪冰城，继续耍起

晚上准备出去吃饭，结果到外边转了一圈发现没有啥吃的，于是做出了重要决定（bushi）：回去点外卖

坐在一楼等外卖，和Air，sc，lhh，wzj，lmz玩了会儿UNO（Air：动动小手点点举报），又和sc，lmz玩了会儿飞行棋（怎么我好几次都是快赢了，结果连摇三次6回家了，太菜了）

外卖送隔壁酒店了，太可恶了

晚上8:00，dyw过去收手机，于是开始看电视

发现《伟大的长征》，《西北往事》和《我们的队伍向太阳》，直接严肃观看（没想到一集1h）

不看时间，成功到11:50，直接严肃睡觉

day 1

上午7:05起床下楼，成功逮捕dyw和qy

去吃早饭，一碗炸酱面成功辣死自己

等待领手机

8:00胜利获得手机，依旧耍起

11:30点外卖并吃饭，12:30退房并进入大巴车

所有轻步兵进入车辆（kards混入）

继续耍起

到达考点，提前进去合照去了（谨防dyw偷拍）

13:30进入考场，先坐牢了40min（可能）

发现电脑甚至没有Dev-C++

打开压缩包（神秘嵌套压缩包和猎奇密码）

开考了我的lemon还没调好（力竭了）

打开T1，发现答案具有单调性，二分答案即可，对于验证，排序a之后双指针就行

主要代码：

inline int read(){int x;cin>>x;return x;}
const int N=500010;
int a[N];
n=read(),m=read();
for(int i=1;i<=n;i++) {
    a[i]=read();
}
sort(a+1,a+n+1);
int l=1,r=n,mid,res=0;
inline bool check(int len) {
    int sum=0;
    for(int i=1;i<len;i++) {
        sum+=(i-1)*(a[i]-a[i-1]);
    }
    for(int i=len;i<=n;i++) {
        sum+=(len-1)*(a[i]-a[i-1]);
        if(sum<=m) return 1;
        sum-=a[i]-a[i-len+1];
    }
    return 0;
}
while(l<=r) {
    mid=(l+r)>>1;
    if(check(mid)) {
        l=mid+1;
        res=mid;
    }
    else {
        r=mid-1;
    }
}
cout<<res;

用了大约30min

打开T2，注意到n\leq 500+题目有图论最短路问题，考虑Floyd得出两条线路的最短路

考虑如何存储输入，注意到有d\leq 20，可以记录一个站点的每一条线路经过的线路编号，于是显然有O(md^2)处理Floyd初值

考虑如何求出答案，发现可以O(d^2)地枚举在起点时去哪个铁路以及终点是从哪个铁路过来的，直接用w_x+t_{x,i}+e_{id_{x,i},id_{y,j}}+t_{y,j}+w_y得出

时间复杂度为O(md^2+n^3+qd^2)，可过

快速一写，欸！一遍过了！（嘻嘻）

主要代码：

inline int read(){int x;cin>>x;return x;}
const int N=510,M=500010,D=30,INF=1000000000000000000;
int w[M],id[M][D],cnt[M],t[M][D],e[N][N];
read();
int n=read();
int m=read();
read();
int q=read();
for(int i=1;i<=m;i++) {
    w[i]=read();
}
for(int i=1;i<=n;i++) {
    int k=read();
    for(int j=1;j<=k;j++) {
        int a=read();
        cnt[a]++;
        id[a][cnt[a]]=i;
        t[a][cnt[a]]=read();
    }
}
for(int i=1;i<=n;i++) {
    for(int j=1;j<=n;j++) {
        e[i][j]=INF;
    }
}
for(int i=1;i<=m;i++) {
    for(int x=1;x<=cnt[i];x++) {
        for(int y=1;y<=cnt[i];y++) {
            e[id[i][x]][id[i][y]]=min(e[id[i][x]][id[i][y]],t[i][x]+t[i][y]);
        }
    }
}
for(int i=1;i<=n;i++)  {
    e[i][i]=0;
}
for(int k=1;k<=n;k++) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
        }
    }
}
for(int r=1;r<=q;r++) {
    int x=read(),y=read();
    int ans=INF;
    for(int i=1;i<=cnt[x];i++) {
        for(int j=1;j<=cnt[y];j++) {
            ans=min(ans,w[x]+t[x][i]+e[id[x][i]][id[y][j]]+t[y][j]+w[y]);
        }
    }
    cout<<ans<<"\n";
}

也是用了大约30min

至此过了一小时，而我已经完成了T1和T2，然后开T3，发现这很诡异，于是打了一个O(n^3)暴力（用Floyd写的）后直接跑路

主要代码：

inline int read(){int x;cin>>x;return x;}
const int N=2000010,N1=310,INF=1000000000000000000;
int x[N],e[N1][N1],cnt[N1][N1];
int c=read();
for(int t=read();t>0;t--) {
    int n=read(),d=read();
    for(int i=1;i<=n;i++) {
        x[i]=read();
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            e[i][j]=INF;
            cnt[i][j]=0;
        }
    }
    for(int l=1,r=0;l<=n;l++) {
        while(r<n&&x[r+1]-x[l]<=d) {
            r++;
        }
        for(int i=l;i<=r;i++) {
            e[l][i]=1;
            cnt[l][i]=1;
        }
    }
    for(int i=1;i<=n;i++) {
        e[i][i]=1;
        cnt[i][i]=1;
    }
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(e[i][j]>e[i][k]+e[k][j]) {
                    e[i][j]=e[i][k]+e[k][j];
                    cnt[i][j]=cnt[i][k]*cnt[k][j];
                }
                else if(e[i][j]==e[i][k]+e[k][j]) {
                    cnt[i][j]+=cnt[i][k]*cnt[k][j];
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(cnt[i][j]==2) {
                ans++;
            }
        }
    }
    cout<<ans<<"\n";
}

打开T4，发现太难了，直接跑路

剩下三小时猛想T3，没有一点思路，试图写特殊性质还假了😭

比赛结束了，一共100+100+24+0=224分，应该有一等了

出了考场和其他人集合，四处打听，发现和我一届的10人里，只有我和lhh写出了T2

发现Air T3 AC了并拿到了340（日常被Air吓哭）

听说赛场机器跑的很慢，但是我用lemon T2跑到了最多515ms，不懂

晚上打开luogu，发现：黄青紫黑！那我知道为什么我做不出来T3T4了（太菜了）

复现T1 T2考场代码，直接AC

day 2

听同学说T1可以直接O(n)用双指针完成，还真是

inline int read(){int x;cin>>x;return x;}
const int N=500010;
int a[N];
int n=read(),m=read();
for(int i=1;i<=n;i++) {
    a[i]=read();
}
sort(a+1,a+n+1);
int ans=0;
for(int l=1,r=0,s=0;l<=n;l++) {
    while(r<n&&s+(a[r+1]-a[r])*(r-l+1)<=m) {
        s+=(a[r+1]-a[r])*(r-l+1);
        r++;
    }
    ans=max(ans,r-l+1);
    s-=a[r]-a[l];
}
cout<<ans;

发现T2降绿了，那我知道我为什么能1h切T1 T2了

回学校继续上课

没了