2025年CSP-S真题解析视频

#include<bits/stdc++.h>#define N 100005using namespace std;int ans,T,n,a[N][4];//ans:当前方案的总满意度vector<int> loss[4];//loss[i]:第一志愿为部门i的人改去第二志愿的满意度损失intmain(){    cin>>T;    while(T--){        ans=0;        //清空上一组数据记录的损失        for(int i=1;i<=3;i++) loss[i].clear();        cin>>n;        for(int i=1;i<=n;i++){            cin>>a[i][1]>>a[i][2]>>a[i][3];            //先让每个人进入自己满意度最高的部门            int mx=max(a[i][1],max(a[i][2],a[i][3]));//mx:当前人的最高满意度            //记录此人从第一志愿改去第二志愿时的最小损失            //若最大值有并列，优先匹配前面的部门，此时损失可能为0            if(a[i][1]==mx)                loss[1].push_back(mx-max(a[i][2],a[i][3]));            else if(a[i][2]==mx)                loss[2].push_back(mx-max(a[i][1],a[i][3]));            else                loss[3].push_back(mx-max(a[i][1],a[i][2]));            ans+=mx;        }        //最多只有一个部门会超过n/2，但直接枚举三个部门处理更方便        for(int i=1;i<=3;i++){            if(loss[i].size()>n/2){//如果部门i人数超过n/2，就需要调整                //将调整损失从小到大排序                sort(loss[i].begin(),loss[i].end());                int cnt=loss[i].size()-n/2;//cnt:需要从部门i移走的人数                //优先移走损失最小的人，使总满意度减少得最少                for(int j=0;j<cnt;j++)                    ans-=loss[i][j];            }        }        cout<<ans<<"\n";    }    return 0;}

注：可左右滑动查看全部代码

#include<bits/stdc++.h>#define N 10015#define M 1000005using namespace std;int n,m,k,fa[N],sz[N],c[15];//fa,sz:并查集，c[i]:第i个乡镇的城市化费用long long ans=4e18;//ans:最小总费用struct Edge{    int u,v,w;}e[M];//e:原城市之间的道路vector<Edge> road[15];//road[i]:第i个乡镇到所有原城市的边，按边权升序vector<Edge> tree[15];//tree[d]:DFS深度为d时当前图的MST边，按边权升序boolcmp(Edge x,Edge y){    return x.w<y.w;}//find(x):查询x所在连通块的根intfind(int x){    if(fa[x]==x) return x;    return fa[x]=find(fa[x]);}//merge(x,y):合并x,y所在连通块voidmerge(int x,int y){    x=find(x),y=find(y);    if(x==y) return;    if(sz[x]<sz[y]) swap(x,y);    fa[y]=x;    sz[x]+=sz[y];}//build(dep,x):在tree[dep]的基础上加入第x个乡镇，求出tree[dep+1]并返回其边权和longlongbuild(int dep,int x){    for(int i=1;i<=n+k;i++){        fa[i]=i;        sz[i]=1;    }    tree[dep+1].clear();    int p=0,q=0;//p,q:两个有序边数组当前扫描位置    long long sum=0;//sum:新MST的边权和    int need=n+dep;//need:加入新乡镇后MST需要的边数    while((p<tree[dep].size()||q<road[x].size())&&tree[dep+1].size()<need){        Edge now;        //两个边集都已排好序，直接像归并排序一样取较小的一条        if(q==road[x].size()||(p<tree[dep].size()&&tree[dep][p].w<=road[x][q].w))            now=tree[dep][p++];        else            now=road[x][q++];        int u=find(now.u),v=find(now.v);        //两端已经连通则加入会形成环        if(u==v) continue;        if(sz[u]<sz[v]) swap(u,v);        fa[v]=u;        sz[u]+=sz[v];        //Kruskal按边权升序选择，因此新tree仍然保持有序        tree[dep+1].push_back(now);        sum+=now.w;    }    return sum;}//dfs(last,dep,cost,sum):当前选了dep个乡镇，最后选择编号为last，城市化费用为cost，当前MST费用为sumvoiddfs(int last,int dep,longlong cost,longlong sum){    //当前乡镇集合对应一种合法方案    ans=min(ans,cost+sum);    //之后只选编号更大的乡镇，保证每个集合只枚举一次    for(int i=last+1;i<=k;i++){        long long nxt=build(dep,i);//nxt:加入乡镇i后的MST费用        dfs(i,dep+1,cost+c[i],nxt);    }}intmain(){    cin>>n>>m>>k;    for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;    //先求原图MST，作为空乡镇集合的tree[0]    sort(e+1,e+m+1,cmp);    for(int i=1;i<=n;i++){        fa[i]=i;        sz[i]=1;    }    long long sum=0;//sum:原图MST的边权和    for(int i=1;i<=m;i++){        int u=find(e[i].u),v=find(e[i].v);        if(u==v) continue;        if(sz[u]<sz[v]) swap(u,v);        fa[v]=u;        sz[u]+=sz[v];        tree[0].push_back(e[i]);        sum+=e[i].w;        if(tree[0].size()==n-1) break;    }    //读入每个乡镇的费用和n条连边，并提前分别排序    for(int j=1;j<=k;j++){        cin>>c[j];        for(int i=1;i<=n;i++){            int w;            cin>>w;            road[j].push_back({n+j,i,w});        }        sort(road[j].begin(),road[j].end(),cmp);    }    //从一个乡镇都不选的状态开始枚举所有集合    dfs(0,0,0,sum);    cout<<ans<<"\n";    return 0;}

#include<bits/stdc++.h>#define N 200005#define M 3000005using namespace std;int n,q,tot,nodecnt;//tot:替换核心数量，nodecnt:Trie节点数int rt1[N],rt2[N],ans[N];//rt1/rt2:每种核心的左右Trie根，ans[i]:第i个询问答案int son[M][26],cnt[M];//son:Trie儿子，cnt[u]:当前左Trie根链上右Trie节点u出现次数struct Query{    int v,id;};vector<int> w[M];//w[u]:左Trie节点u上挂载的规则对应的右Trie节点vector<Query> ask[M];//ask[u]:左Trie节点u上挂载的询问unordered_map<string,int> mp;//mp:替换核心到编号的映射//insert(u,s,l,r,d):从节点u开始，将s[l...r]按方向d插入Trieintinsert(int u,string &s,int l,int r,int d){    for(int i=l;d==1?i<=r:i>=r;i+=d){        int c=s[i]-'a';        if(!son[u][c]) son[u][c]=++nodecnt;        u=son[u][c];    }    return u;}//dfs(u):维护根到u路径上的所有规则并回答询问voiddfs(int u){    for(int v:w[u]) cnt[v]++;    for(auto x:ask[u]) ans[x.id]+=cnt[x.v];    for(int i=0;i<26;i++)        if(son[u][i]) dfs(son[u][i]);    for(int v:w[u]) cnt[v]--;}intmain(){    cin>>n>>q;    for(int i=1;i<=n;i++){        string a,b;        cin>>a>>b;        if(a==b) continue;        int l=0,r=a.size()-1;        //l,r:第一个和最后一个不同的位置        while(a[l]==b[l]) l++;        while(a[r]==b[r]) r--;        //key:两个字符串真正发生变化的部分        string key=a.substr(l,r-l+1)+"#"+b.substr(l,r-l+1);        int &id=mp[key];        if(!id){            id=++tot;            rt1[id]=++nodecnt;            rt2[id]=++nodecnt;        }        //公共后缀正序插入右Trie        int v=insert(rt2[id],a,r+1,a.size()-1,1);        //公共前缀倒序插入左Trie        int u=insert(rt1[id],a,l-1,0,-1);        //在左Trie节点u挂上这条规则的右Trie节点        w[u].push_back(v);    }    for(int id=1;id<=q;id++){        string a,b;        cin>>a>>b;        //一次替换不会改变字符串长度        if(a.size()!=b.size()) continue;        int l=0,r=a.size()-1;        while(a[l]==b[l]) l++;        while(a[r]==b[r]) r--;        string key=a.substr(l,r-l+1)+"#"+b.substr(l,r-l+1);        int t=mp[key];        if(!t) continue;        //匹配公共前缀的倒序，走不下去时停在当前节点        int u=rt1[t];        for(int j=l-1;j>=0;j--){            int c=a[j]-'a';            if(!son[u][c]) break;            u=son[u][c];        }//u=l[t];        //枚举r[t]到跟路径上的点p，求l[t]到跟的w中有几个p        //空串也是公共后缀的前缀        int v=rt2[t];        ask[u].push_back({v,id});        //枚举公共后缀在右Trie中存在的所有前缀        for(int j=r+1;j<a.size();j++){            int c=a[j]-'a';            if(!son[v][c]) break;            v=son[v][c];            ask[u].push_back({v,id});        }    }    //不同替换核心分别处理    for(int i=1;i<=tot;i++) dfs(rt1[i]);    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";    return 0;}

#include<bits/stdc++.h>#define N 501#define MOD 998244353using namespace std;int n,m,a[N],b[N],fac[N],C[N][N];//a[i]:c=i的人数，b[i]:c<=i的人数，fac[i]:i的阶乘int f[N][N][N];//f[i][j][k]:前i天有j人未录用，其中有k个c>j且尚未确定具体人的空位string s;intmain(){    cin>>n>>m>>s;    for(int i=1,x;i<=n;i++){        cin>>x;        a[x]++;    }    //b[i]:c<=i的总人数    b[0]=a[0];    for(int i=1;i<=n;i++) b[i]=b[i-1]+a[i];    //预处理组合数    for(int i=0;i<=n;i++){        C[i][0]=C[i][i]=1;        for(int j=1;j<i;j++)            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;    }    //预处理阶乘    fac[0]=1;    for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%MOD;    f[0][0][0]=1;    //由处理完前i天的状态转移到处理完前i+1天    for(int i=0;i<n;i++){        for(int j=0;j<=i;j++){            for(int k=0;k<=i;k++){                if(!f[i][j][k]) continue;                if(s[i]=='1'){                    //当前人c>j，会被录用，新增一个空位                    f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%MOD;                    //当前人c<=j，会直接放弃，因此j->j+1                    int num=b[j]-(i-k);//num:还没有使用的c<=j的人数                    if(num<=0) continue;                    //t:原来k个空位中实际有多少个放的是c=j+1的人                    for(int t=0;t<=min(k,a[j+1]);t++){                        long long way=1LL*f[i][j][k]*C[a[j+1]][t]%MOD*C[k][t]%MOD*fac[t]%MOD;                        f[i+1][j+1][k-t]=(f[i+1][j+1][k-t]+way*num)%MOD;                    }                }else{                    //题目做不出，无论当前是谁都不会被录用，因此j->j+1                    for(int t=0;t<=min(k,a[j+1]);t++){                        //确定t个原空位实际放的是c=j+1的人                        long long way=1LL*f[i][j][k]*C[a[j+1]][t]%MOD*C[k][t]%MOD*fac[t]%MOD;                        //当前人c<=j+1，需要立即确定具体是哪一个人                        int num=b[j+1]-(i-(k-t));                        if(num>0)                            f[i+1][j+1][k-t]=(f[i+1][j+1][k-t]+way*num)%MOD;                        //当前人c>j+1，新增一个仍未确定具体人的空位                        f[i+1][j+1][k-t+1]=(f[i+1][j+1][k-t+1]+way)%MOD;                    }                }            }        }    }    int ans=0;//ans:至少录用m人的排列数    for(int j=0;j<=n-m;j++){        int k=n-b[j];//最终剩下的空位数恰好等于c>j的人数        ans=(ans+1LL*f[n][j][k]*fac[k])%MOD;    }    cout<<ans<<"\n";    return 0;}