2025 CSP-S

· · 个人记录

2025 CSP-S

T1 T2 T3 T4
黄 蓝 紫 紫

T1 [CSP-S 2025] 社团招新 / club

题意：

将n个人分到3个部门，每个部门人数不能超过\frac{n}{2}，求满意值最大可以为多少？

思路：

先将每个人分到其最满意的部门，再把人数超过 \frac{n}{2}人的部门人数减到 \frac{n}{2}人，因为不可能同时有两个部门超过 \frac{n}{2}人，对于要移除到其他部门的则使其最大满意值与次大满意值差最小

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N(1e5+10);
int n,ans(0);
struct node{
    int a,b,c;
    int maxx,next;
}e[N];
vector<int>x,y,z,sc;
void solve(){
    cin>>n;
    ans=0;
    x.clear();y.clear();
    z.clear();sc.clear();
    for(int i(1);i<=n;i++){
        cin>>e[i].a>>e[i].b>>e[i].c;
        e[i].maxx=max(e[i].a,max(e[i].b,e[i].c));
        ans+=e[i].maxx;
        if(e[i].maxx==e[i].a){
            x.push_back(i);
            e[i].next=max(e[i].b,e[i].c);
        }
        if(e[i].maxx==e[i].b){
            y.push_back(i);
            e[i].next=max(e[i].a,e[i].c);
        }
        if(e[i].maxx==e[i].c){
            z.push_back(i);
            e[i].next=max(e[i].b,e[i].a);
        }
    }
    int siz(max(x.size(),max(y.size(),z.size())));
    if(siz>n/2){
        if(siz==x.size()){
            for(int i(0);i<siz;i++){
                sc.push_back(e[x[i]].maxx-e[x[i]].next);
            }
        }
        if(siz==y.size()){
            for(int i(0);i<siz;i++){
                sc.push_back(e[y[i]].maxx-e[y[i]].next);
            }
        }
        if(siz==z.size()){
            for(int i(0);i<siz;i++){
                sc.push_back(e[z[i]].maxx-e[z[i]].next);
            }
        }
    }
    sort(sc.begin(),sc.end());
    for(int i(0);sc.size()>n/2&&i<sc.size()-n/2;i++){
        ans-=sc[i];
    }
    cout<<ans<<'\n';
}
int main(){
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

T2 [CSP-S 2025] 道路修复 / road

题意：

n个城市，m条路，k个乡村，修条路要钱，将乡村升级要钱，在升级后的乡村到城市之间建路也要钱，最少要多少钱才能把n个城市都连接起来？

思路：

  1. 先把不是最小生成树上的边都剪掉（此最小生成树仅考虑m条边
  2. 使用二进制枚举每个乡村建不建，如果建就把可以建的路都放到队列里去，再跑一遍最小生成树

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N(1e5+10);
ll n,m,k;
ll ans(1e18+7);
ll f[N],cost[15];
bool vis[15];
struct node{
    ll u,v,w;
};
vector<node>e,ee;
ll find(ll x){
    if(f[x]==x){
        return x;
    }
    return f[x]=find(f[x]);
}
bool cmp(node a,node b){
    return a.w<b.w;
}
int main(){
    cin>>n>>m>>k;
    // cout<<n<<'\n';
    for(ll i(1);i<=n;i++){
        f[i]=i;
    }
    for(ll i(1);i<=m;i++){
        ll u,v,w;
        cin>>u>>v>>w;
        ee.push_back({u,v,w});
    }
    sort(ee.begin(),ee.end(),cmp);
    ll tot(0);
    for(ll i(1);i<=m&&tot!=n-1;i++){
        ll u(find(ee[i].u)),v(find(ee[i].v));
        if(u!=v){
            f[v]=u;
            tot++;
            e.push_back(ee[i]);
        }
    }
    for(ll i(1);i<=k;i++){
        ll c;
        cin>>c;
        cost[i]=c;
        for(ll j(1);j<=n;j++){
            ll w;
            cin>>w;
            e.push_back({j,n+i,w});
        }
    }
    sort(e.begin(),e.end(),cmp);
    for(ll stat(0);stat<(1<<k);stat++){
        ll now(0);
        ll num(0);
        for(ll i(1);i<=k;i++){
            if((stat>>(i-1))&1){
                num++;
                vis[i]=true;
                now+=cost[i];
            }else{
                vis[i]=false;
            }
        }
        for(ll i(1);i<=n+k;i++){
            f[i]=i;
        }
        ll need(n+num-1);
        for(ll i(0);i<e.size();i++){
            ll u(e[i].u),v(e[i].v);
            if(v>n&&!vis[v-n]){
                continue;
            }
            ll fu(find(u)),fv(find(v));
            if(fu!=fv){
                f[fv]=fu;
                now+=e[i].w;
                if(!(--need)){
                    break;
                }
            }
        }
        if(!need){
            ans=min(ans,now);
        }
    }
    cout<<ans<<'\n';
    return 0;
}