CSP S2025 游记

__Frozen__ · 2025-10-30 09:46:12 · 生活·游记

前记

初赛94分，J组没考。

Day -2

模拟赛是信心赛。然后打爆了，更没信心了。zhikang大神在我死调T1调不出来的时候已经在调T4了（他是顺序做的啊），HRS大佬已经AK了，超级大神 /bx。红红红红红红红红红红红红红红红红红红。今年不打J，再也没有机会AK J组了。呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜呜。虽然今年也不一定能AK。我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜我好菜。

豆包好强！

哇，然后最后全队都AK了 /bx /bx /bx。

下午颓了会duel后订题去了，好！难！啊！

Day -1

RP+=INF.

模拟赛。

叮叮铛铛荡荡丁丁猩猩在攀爬

密密麻麻麻麻密密蚂蚁在搬家

乒乒乓乓乓乓乒乒邦邦邦邦邦

叽叽喳喳喳喳叽叽鸡鸡在干架

下午订(bai)题(lan)。

Day 0（比赛日）

早上不考J。于是做S模拟。

心态一直疯狂爆炸，认为自己今年连S1都可能没有。红温。急眼。压↓力↑！

一坨。于是看了会算法。感觉没用，于是看了会kuai~kuai~的视频，压力瞬间消失了。所以关注kuai~kuai~谢谢喵。

赛前来到坐了1个小时我麻麻开的车，睡了一觉，我麻麻还给我买了一盒巧克力！巧克力好吃巧克力好吃巧克力好吃巧克力好吃巧克力好吃巧克力好吃。

然后到礼堂随机游走，面积了114514个大神。我想把他们全挂在这。但是不知道luogu id。

赛时

\Huge 开！

很好。上来T1扫了一眼就不会了。草。然后再仔细看一眼数据范围发现应该是贪心。再想想就发现是shaber题。目前总共思考10min。写写写。花了20min，过了大样例。扔了。

::::info[T1题解] 首先每人选满意度最高的。然后发现可能有一个大于 \frac{n}{2} 的（不可能有两个以上），设他有 k人。考虑进行调整。显然应该恰好调整 (k-\frac{n}{2})，证明显然。调整第 i 个人会让 ans 减去 i 的最大满意度再加上 i 的次大满意度。所以按次大满意度减最大满意度排序从小往大取即可。

code:

//
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+5;

vector<pair<int,int> > a[MAXN];
int cnt[3];
priority_queue<int,vector<int>,greater<int> > q;

signed main(){
    int t;
    scanf("%lld",&t);
    while (t--){
        while (q.size()) q.pop();
        int n;
        scanf("%lld",&n);
        for (int i=1;i<=n;i++) a[i].clear();
        for (int i=1;i<=n;i++){
            int tmp=0;
            for (int j=0;j<=2;j++){
                scanf("%lld",&tmp);
                a[i].push_back({tmp,j});
            }
            sort(a[i].begin(),a[i].end(),greater<pair<int,int> >());
        }
        cnt[0]=cnt[1]=cnt[2]=0;
        int ans=0;
        for (int i=1;i<=n;i++) cnt[a[i][0].second]++,ans+=a[i][0].first;
        if (cnt[0]>(n/2)){
            for (int i=1;i<=n;i++)
                if (a[i][0].second==0)
                    q.push(a[i][0].first-a[i][1].first);
            while (cnt[0]>(n/2)){
                ans-=q.top();
                q.pop();
                cnt[0]--;
            }
        }
        if (cnt[1]>(n/2)){
            for (int i=1;i<=n;i++)
                if (a[i][0].second==1)
                    q.push(a[i][0].first-a[i][1].first);
            while (cnt[1]>(n/2)){
                ans-=q.top();
                q.pop();
                cnt[1]--;
            }
        }
        if (cnt[2]>(n/2)){
            for (int i=1;i<=n;i++)
                if (a[i][0].second==2)
                    q.push(a[i][0].first-a[i][1].first);
            while (cnt[2]>(n/2)){
                ans-=q.top();
                q.pop();
                cnt[2]--;
            }
        }
        printf("%lld\n",ans);
    }

    return 0;
}

::::

然后开T2。完了也不会。我去年都200分了，今年不会切不了两题吧？

PS：还真是。

慌慌慌。上个厕所。诶要连通还最小代价不就是最小生成树吗。k\le10 直接枚举每个乡镇要不要用。对于每一种情况做一次MST不就完事了？但好像会超时。边太多了。然而原图中貌似只有原图MST中的边会用上。于是就得到了一个复杂度 O(2^k nklog_{2}nk) 的算法。瓶颈在排序。边数还是太多，只有80分，对于 n=10^4,m=10^6 还是过不了。然而我考场上太唐完了。把后来加入的边数从 nk 算成了 n 于是以为自己能过了，然后测完大样例就扔了。（T2思考10min，code 20min)

::::info[code]

//
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e4+5,MAXM=1e6+5;

pair<int,pair<int,int> > a[MAXM];
vector<pair<int,pair<int,int> > > b,c;
int fa[MAXN],val[15],dis[15][MAXN];

int fath(int id){
    if (fa[id]==id) return id;
    return fa[id]=fath(fa[id]);
}

void mer(int x,int y){
    fa[fath(x)]=fath(y);
}

signed main(){
    int n,m,k;
    scanf("%lld %lld %lld",&n,&m,&k);
    for (int i=1;i<=n;i++) fa[i]=i;
    for (int i=1;i<=m;i++)
        scanf("%lld %lld %lld",&a[i].second.first,&a[i].second.second,&a[i].first);

    for (int i=1;i<=k;i++){
        scanf("%lld",&val[i]);
        for (int j=1;j<=n;j++)
            scanf("%lld",&dis[i][j]);
    }

    sort(a+1,a+1+m);

    for (int i=1;i<=m;i++)
        if (fath(a[i].second.first)!=fath(a[i].second.second)){
            mer(a[i].second.first,a[i].second.second);
            b.push_back(a[i]);
        }

    int ans=1e18;
    for (int i=0;i<(1<<k);i++){
        int sum=0;
        c.clear();
        for (auto j:b) c.push_back(j);
        for (int j=1;j<=n+k;j++) fa[j]=j;
        for (int j=1;j<=k;j++)
            if ((i>>(j-1))&1){
                sum+=val[j];
                for (int z=1;z<=n;z++) c.push_back({dis[j][z],{z,j+n}});
            }
        sort(c.begin(),c.end());
        for (int j=0;j<c.size();j++){
            if (fath(c[j].second.first)!=fath(c[j].second.second)){
                sum+=c[j].first;
                mer(c[j].second.first,c[j].second.second);
            }
        }
        ans=min(ans,sum);
    }
    printf("%lld",ans);

    return 0;
}

::::

1h切两题，怎么输！！！！！

好。3h T3T4。T3傻逼字符串题暴力都不会写。T4以为能搞70分。写写写。发现读错题了。只有32pts。写完了。罚坐。

估分：100+100+0+32=232。以为很差。出场才发现大家都说难。

赛后

在luogu民间数据上测。发现T2复杂度有问题挂了20分。没事还有212。上200了就没事。然后又发现T4读错题了爆挂 [24,32] 分，于是分数来到了 [180,188] ，好了，草了。没有成功场切蓝题，没有上200分。CCF /bangbangt。已红温。/fn /fn /fn。T2根据SZ-OIer……说到SZ-OIer，这是一款由SZ-OIers开发的开放聊天群聊，QQ群号1033778947，快点来。好了，T2根据SZ-OIer群友加了个优化，就是在加乡镇的边时，可以不加入比原图MST的边权最大值还大的边，这样就可以过民间数据。代码和我赛时的没啥差别，就加一点东西，就不放了。 zhikang大神350%%%，韦神358%%%，shx大神四题都会只是写了T1T4就没时间了，于是得到逆天分数100+48+10+100。但也比我强得多%%%。

查分

T4反向挂12分。T3官方数据就是个【数据删除】，但是我没写，于是被原本比我低的tallnut同学反向挂分超飞了。100+80+0+12=192.草拟吗，T3。10分暴力可以有30。玄学复杂度的HRS做法能有80分。HRS大神因此获得了280分%%%。tym获得186pts.tallnut大奖杯获得了210分。草草。

我写的题被卡常（其实没卡），没写的题是随机数据。

题外话

暴论之 T1黄，T2绿，T3紫，T4蓝。 ——HRS

（其实我也是这么觉得的，但我是傻逼，没切掉T2.