CSP2026游记:梦结束的地方

· · 生活·游记

人生最后一场比赛。

报名费太 tm 贵了,就没去 J 组。

9/19

没复习,直接上考场,在考场门口看了眼 st 表板子,正好考到了。

进考场之前在门口逗留了好久,可惜一个人都没面基到……这下好了,整个 oi 生涯没面基到一个人。

考场在华师大四附中,怎么桌子是坏的,一动就晃,我就擦了几次答题卡直接给我干晕车了。

前面好简单啊,我一定可以 90+ 吧……

这最后一大题什么东西,看不懂,瞎选了。

出考场一看:全 tm 蒙错了?

没事,丢了 15 分照样过线。

10/10

查分:69,丢了两个 15 分轻松过线。

10/17

打 scp,由于上午教练刚带我们打完模拟赛,下午处于脱力状态,想着随便玩玩了。

看了眼 T1,耗时 20 分钟理解题意,好在直接秒了。然后看 T2,直接一个 不会,搓了个平方暴力润了,T3 看出来了长链剖分但是不会写,把 dij 板子改一个正负号当暴力交了,T4 看都没看。以为 150 稳 1= 就直接离场休息去了,非常稳定的 100+35+15+0=150 ……伏笔啊。

10/28-10/30

复习复习复习复习复习,疯狂打板子,三天打了 50 个板子,燃尽了,考前 24 小时有 14 个小时在复习。

10/31

还是来了,上午还在复习,看了 tarjan 全家桶。中午随便吃了几口,没吃饱就出门了,带了板巧克力和三包薯条。

OCT31==DEC25?

我旁边的一个人说应该把表达式的值填进去,于是我试图用 true 解压表情包。还好失败了。

一边读题一边敲文件头。

等一下这个 t1,先不读题了,把 t1 写掉再说。

ok 五分钟秒掉。

看 t2 题面……

呃呃呃呃呃呃呃啊,

这题面是给人看的吗。

口胡了一个 32 pts 思路但对着样例解释手模怎么模也模不对,怕读错题。

果断跳过,寻思着把 t3 t4 暴力敲了回来写 t2。

读题读题读题。

t3 写了 15 分钟,没创过大样例,不出意外没调出来。

t4 有很神秘的搜索剪枝,写写写写写写写写写写写写,由于我不会倍增 lca,于是直接树剖维护了,由于我不会 dfs 染色,所以直接并查集维护了。代码暴涨到 110 行。写 t4 的时候天还亮着,写完抬头一看天黑了,五点三刻了????!!!!!!

?????

我操了一个暴力我写了俩小时半是吧,这下完了,沉迷调试没看时间导致的。

创过了些许大样例赶紧回来看 t2。

紧张地读题,发现先前的拆点思路没错,看不懂样例解释就不看了,反正输出是对的,直接跑 dij 可以稳定拿 32 分。叮铃咣啷敲完代码还剩半个小时,要不是我肾上腺素发力了我半小时肯定写不完这代码。这时候有人进来喊了一声 t2 样例解释有误??????

sb ccf

仍然在想正解,想到了把地铁线当作点处理但发现自己没办法在 30 分钟内良好地处理建边和重边。而且头脑不清的我没想到这个时间复杂度是正确的,没注意到 d 的限制,以为是地铁站的个数的平方。

知道我一场考试下来发现复杂度和 d 没挂上关系有多绝望吗/ll

交卷的时候还出了一些小插曲,我以为我交上去了,手一抖没点到提交,文件还是挂起状态,我直接关机愤然离开座位,在门口准备签字离场。

排队的时候听见老师喊我考号,说我代码是空的。

我承认我怕了。

好在代码在 D 盘,开机之后还在,在交了一发老师说交上去了。

不过这样我就在队尾了,喜提最后一个离场。

排队的时候随机抽样聊天发现都写出来 t2 了我就知道这把完了。

出考场和同学们碰了碰头,回家附近吃了顿散伙饭,没了。

11/5

查分 100+32+0+5=137 和 scp 几乎一模一样……

去不了 noip 就直接退役了,剩下的事看我的退役回忆录吧。

就这样吧。

不行我必须放一下我的 t2 和 t4 代码(已去除 freopen)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int c,n,m,d,Q,w[510000],k[510],dis[1100000],dcnt,x,y;
bool vis[1100000];
vector<int>a[510],t[510],mp[510];
vector<pair<int,int>>sons[510000];
priority_queue<pair<int,int>>Qu;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>c>>n>>m>>d>>Q;
    dcnt=m;
    for(int i=1;i<=m;i++)cin>>w[i];
    for(int i=1;i<=n;i++){
        cin>>k[i];
        a[i].resize(k[i]+5);
        t[i].resize(k[i]+5);
        mp[i].resize(k[i]+5);
        for(int j=1;j<=k[i];j++)cin>>a[i][j]>>t[i][j];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k[i];j++){//枚举线路i经过的地铁站j 
            dcnt++;
            sons[a[i][j]].push_back({dcnt,t[i][j]});
            sons[dcnt].push_back({a[i][j],t[i][j]});
            mp[i][j]=dcnt;
        }
        for(int j=1;j<k[i];j++){
            for(int kk=j+1;kk<=k[i];kk++){
                sons[mp[i][j]].push_back({mp[i][kk],0});
                sons[mp[i][kk]].push_back({mp[i][j],0});
            }
        }
    }
    while(Q--){
        cin>>x>>y;
        memset(dis,0,sizeof dis);
        memset(vis,0,sizeof vis);
        for(int i=1;i<=dcnt;i++)dis[i]=LLONG_MAX-10000;
        while(!Qu.empty())Qu.pop();
        dis[x]=0;
        vis[x]=1;
        Qu.push({0,x});
        while(!Qu.empty()){
            pair<int,int>f=Qu.top();
            Qu.pop();
            vis[f.second]=1;
            for(pair<int,int> son:sons[f.second]){
                if(vis[son.first])continue;
                if(dis[son.first]>dis[f.second]+son.second){
                    dis[son.first]=dis[f.second]+son.second;
                    Qu.push({-dis[son.first],son.first});
                }
            }
        }
        cout<<dis[y]+w[x]+w[y]<<"\n";
    }
    return 0;
}
#include<bits/stdc++.h>//疑似读错题 
using namespace std;
int c,T,n,k,dep[1100000],fa[1100000],top[1100000],sz[1100000],wc[1100000],ans=INT_MAX,dsu[1100000];
bool flg[1100000],bkt[1100000];
vector<int>sons[1100000];
void dfs1(int pos,int lst){
    fa[pos]=lst,sz[pos]=1,dep[pos]=dep[lst]+1;
    for(int son:sons[pos]){
        if(son==lst)continue;
        dfs1(son,pos);
        sz[pos]+=sz[son];
        if(sz[son]>=sz[wc[pos]])wc[pos]=son;
    }
    return;
}
void dfs2(int pos,int topnow){
    top[pos]=topnow;
    if(wc[pos])dfs2(wc[pos],topnow);
    for(int son:sons[pos]){
        if(son==fa[pos]||son==wc[pos])continue;
        dfs2(son,son);
    }
    return;
}
int lca(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]<dep[top[b]])swap(a,b);
        a=fa[top[a]];
    }
    if(dep[a]>dep[b])swap(a,b);
    return a;
}
int dis(int a,int b){
    return dep[a]+dep[b]-2*dep[lca(a,b)];
}
void init(){
    for(int i=1;i<=n;i++)dsu[i]=i;
    return;
}
int find(int x){
    if(dsu[x]==x)return x;
    dsu[x]=find(dsu[x]);
    return dsu[x];
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y)return;
    dsu[x]=y;
    return;
}
void dfs3(int pos,int dcnt){
    if(dcnt==k){
        int tmpcnt=0;
        memset(bkt,0,sizeof bkt);
        init();
        for(int i=1;i<=n;i++){
            if(!flg[i])continue;
            for(int son:sons[i]){
                if(!flg[son])continue;
                if(find(i)==find(son))continue;
                merge(i,son);
                //cout<<"mer "<<i<<" "<<son<<"\n";
            }
        }
        for(int i=1;i<=n;i++){
            if(!flg[i])continue;
            if(!bkt[find(i)])tmpcnt++,bkt[find(i)]=1;
        }
        if(tmpcnt>2)return;
        //cout<<"aaa "<<pos<<" "<<" "<<dcnt<<"\n";
        //for(int i=1;i<=n;i++)if(flg[i])cout<<i<<" ";
        //cout<<"\n";
        int tans=0;
        for(int i=1;i<=n;i++)if(!flg[i])for(int j=1;j<=n;j++)tans=max(tans,dis(i,j));
        //cout<<tans<<"\n";
        //for(int i=1;i<=n;i++)if(!flg[i])for(int j=1;j<=n;j++)//cout<<i<<" "<<j<<"\n";
        ans=min(ans,tans);
        return;
    }
    if(pos==n+1)return;
    flg[pos]=1;
    dfs3(pos+1,dcnt+1);
    flg[pos]=0;
    dfs3(pos+1,dcnt);
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>c>>T;
    while(T--){
        cin>>n>>k;
        for(int i=1;i<=n;i++)sons[i].clear();
        ans=INT_MAX,memset(flg,0,sizeof flg),memset(dep,0,sizeof dep),memset(sz,0,sizeof sz),memset(fa,0,sizeof fa),memset(wc,0,sizeof wc),memset(top,0,sizeof top);
        for(int i=1,a,b;i<n;i++){
            cin>>a>>b;
            sons[a].push_back(b);
            sons[b].push_back(a);
        }
        dfs1(1,0);
        dfs2(1,1);
        //for(int i=1;i<=n;i++)cout<<dep[i]<<" "<<fa[i]<<" "<<sz[i]<<" "<<top[i]<<" "<<wc[i]<<"\n";
        //for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cout<<i<<" "<<j<<" "<<lca(i,j)<<" "<<dis(i,j)<<"\n";
        dfs3(1,0);
        cout<<ans/3<<"\n";
    }
    return 0;
}