[C/C++] 迈出在 CSP 的第五步 CSP-S 2025

_Weslie_ · 2022-07-10 13:32:25 · 生活·游记

大家好，我是靳皓旭，没错，就是那个人见人爱，花见花开的靳皓旭。你是否对即将到来的 CSP-S 2025 游记感到十分期待与激动呢？我也是的。废话不多说，我们开始吧！

这次让我们迈出万里 CSP 路的第五步，这是历史性的一步，更是意义深远的一步，上升到人民，社会，国家。。。。。。扯多了，让我们回到正题，一起看游记：CSP-S 2025 游记，嗯很深奥，这份游记看上去很难理解。点进去笑了，这是某 AFO 高一 OIer 做的题吧！一起看一下题目：

P14361 [CSP-S 2025] 社团招新

小 L 是学校算法协会的成员。在今年的学校社团招新中，小 L 一共招收了 n 个新成员，其中 n 为偶数。现在小 L 希望将他们分到协会不同的部门。

算法协会共设有三个部门，其中第 i (1 \leq i \leq n) 个新成员对第 j (1 \leq j \leq 3) 个部门的满意度为 a_{i,j}。定义一个分配方案的满意度为所有新成员对分配到的部门的满意度之和，也就是说，若将第 i (1 \leq i \leq n) 个新成员分配到了第 d_i \in \{1,2,3\} 个部门，则该分配方案的满意度为 \sum_{i=1}^{n} a_{i,d_i}。

小 L 不希望某一个部门的新成员数量过多。具体地，他要求在分配方案中，不存在一个部门被分配多于 \frac{n}{2} 个新成员。你需要帮助小 L 求出，满足他要求的分配方案的满意度的最大值。

这个题我不会！我不会！啊啊啊啊啊啊啊啊啊啊啊啊啊！考场上我以为这是个橙。

30min 想到反悔贪心，40min 写完发现不对，55min 调完。

样例一看，突然间仿佛回到了小学那时候，懵懂无知，天真无邪。。。咔，又跑题了。其实就是输入两个数，求这两个数的和（两个数相加的结果）。听到这里，你应该很胸有成竹，但是在打代码前我们先注意一些小细节哦！

我们在打代码时应该行首对齐，最好不要顶格，因为以后代码太长会很乱。 2.注意每句末尾加上分号 " 这其实相当于我们C语言中的句号，说活不能一口气一直说下去，要合理添加句号。

一定要做到以上两点哦，从开始就养成好的编程习惯，一定会给你带来好处。

我们一起看一下我打的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100005;
ll a[N][4];
int f[N][4];
int uuuu;
int n;
struct node{
    int pos;ll dl;
    friend bool operator <(node _,node __){
        return _.dl>__.dl;
    }
};
node make_node(int pos,int dl){
    node rrat;
    rrat.pos=pos;rrat.dl=dl;
    return rrat;
}
priority_queue<node>q[4];
vector<pair<int,int>>g;
void solve(){
    scanf("%d",&n);
    for(int i=1;i<=3;i++)while(!q[i].empty())q[i].pop();
    memset(a,0,sizeof a);
    memset(f,0,sizeof f);
    long long ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&a[i][1],&a[i][2],&a[i][3]);
        g.clear();
        for(int j=1;j<=3;j++){
            g.push_back(make_pair(-a[i][j],j));
        }
        sort(g.begin(),g.end());
        for(int j=0;j<=2;j++){
            f[i][j+1]=g[j].second;
        }
    }
    for(int i=1;i<=n;i++){
        q[f[i][1]].push(make_node(i,a[i][f[i][1]]-a[i][f[i][2]]));
        ans=ans+a[i][f[i][1]];
        if(q[f[i][1]].size()>n/2){
            node u=q[f[i][1]].top();q[f[i][1]].pop();
            ans=ans-u.dl;
            int pos=u.pos;
            q[f[pos][2]].push(make_node(pos,a[pos][f[pos][2]]-a[pos][f[pos][3]]));
        }
    }
    printf("%lld\n",ans);
}
int main(){
    freopen("club.in","r",stdin);
    freopen("club.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}

P14362 [CSP-S 2025] 道路修复

C 国的交通系统由 n 座城市与 m 条连接两座城市的双向道路构成，第 i (1 \leq i \leq m) 条道路连接城市 u_i 和 v_i。任意两座城市都能通过若干条道路相互到达。

然而，近期由于一场大地震，所有 m 条道路都被破坏了，修复第 i (1 \leq i \leq m) 条道路的费用为 w_i。与此同时，C 国还有 k 个准备进行城市化改造的乡镇。对于第 j (1 \leq j \leq k) 个乡镇，C 国对其进行城市化改造的费用为 c_j。在城市化改造完第 j (1 \leq j \leq k) 个乡镇后，可以在这个乡镇与原来的 n 座城市间建造若干条道路，其中在它与第 i (1 \leq i \leq n) 座城市间建造一条道路的费用为 a_{j,i}。C 国可以在这 k 个乡镇中选择任意多个进行城市化改造，也可以不选择任何乡镇进行城市化改造。

为尽快恢复城市间的交通，C 国希望以最低的费用将原有的 n 座城市两两连通，也即任意两座原有的城市都能通过若干条修复或新建造的道路相互到达。你需要帮助他们求出，将原有的 n 座城市两两连通的最小费用。

吓死我了，我好害怕啊，不知道以后怎么打代码了，只会 64。呜呜呜。呃呃，其实很简单，这是规则，不能违反。我们只能遵守咯。

我们在打代码时应该行首对齐，最好不要顶格，因为以后代码太长会很乱。 2.注意每句末尾加上分号 " 这其实相当于我们C语言中的句号，说活不能一口气一直说下去，要合理添加句号。

一定要做到以上两点哦，从开始就养成好的编程习惯，一定会给你带来好处。

我们一起看一下我打的代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1100005;
struct node{
    int u,v;
    ll w;
    friend bool operator <(node _,node __){
        return _.w<__.w;
    }
}e[N];
ll c[15];
int n,m,k,p[15],fa[N];
ll ans=0x3f3f3f3f3f3f3f3f;
int findd(int x){
    if(fa[x]==x)return x;
    return fa[x]=findd(fa[x]);
}
void vnion(int u,int v){
    u=findd(u);v=findd(v);
    if(u==v)return;
    fa[u]=v;
}
void dfs(int po,ll sum,int cho){
    if(po==k+1){
        for(int i=1;i<=n+k;i++)fa[i]=i;
        int cnt=0;
        for(int i=1,u,v;i<=m;i++){
            u=e[i].u;v=e[i].v;
            if(u>n&&!p[u-n])continue;
            if(v>n&&!p[v-n])continue;
            if(findd(u)!=findd(v)){
                vnion(u,v);
                sum+=e[i].w;
                cnt++;
            }
            if(cnt==n+cho-1)break;
        }
        if(cnt==n+cho-1)ans=min(ans,sum);
        return;
    }
    p[po]=0;dfs(po+1,sum,cho);
    p[po]=1;dfs(po+1,sum+c[po],cho+1);
    p[po]=0;
}
int main(){
    freopen("road.in","r",stdin);
    freopen("road.out","w",stdout);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
    }
    for(int i=1;i<=k;i++){
        scanf("%lld",&c[i]);
        ll w=0;
        for(int j=1;j<=n;j++){
            scanf("%lld",&w);
            e[++m].u=j;e[m].v=i+n;e[m].w=w;
        }
    }
    sort(e+1,e+m+1);
    dfs(1,0,0);
    printf("%lld\n",ans);
    return 0;
}

P14363 [CSP-S 2025] 谐音替换

小 W 是一名喜欢语言学的算法竞赛选手。在语言学中，谐音替换是指将原有的字词替换为读音相同或相近的字词。小 W 发现，谐音替换的过程可以用字符串来进行描述。具体地，小 W 将谐音替换定义为以下字符串问题：

给定 n 个字符串二元组，第 i (1 \leq i \leq n) 个字符串二元组为 (s_{i,1}, s_{i,2})，满足 |s_{i,1}| = |s_{i,2}|，其中 |s| 表示字符串 s 的长度。

对于字符串 s，定义 s 的替换如下：

对于 s 的某个子串 y，若存在 1 \leq i \leq n 满足 y = s_{i,1}，则将 y 替换为 y' = s_{i,2}。具体地，设 s = x + y + z，其中 x 和 z 可以为空，“+” 表示字符串拼接，则 s 的替换将得到字符串 s' = x + y' + z。

小 W 提出了 q 个问题，第 j (1 \leq j \leq q) 个问题会给定两个不同的字符串 t_{j,1}, t_{j,2}，她想知道有多少种字符串 t_{j,1} 的替换能够得到字符串 t_{j,2}。两种 s 的替换不同当且仅当子串 y 的位置不同或用于替换的二元组 (s_{i,1}, s_{i,2}) 不同，即 x, z 不同或 i 不同。你需要回答小 W 提出的所有问题。

今年出题人有病吧，怎么出字符串啊。写个 10 分的哈希跑路吧。

P14364 [CSP-S 2025] 员工招聘

小 Z 和小 H 想要合伙开一家公司，共有 n 人前来应聘，编号为 1 \sim n。小 Z 和小 H 希望录用至少 m 人。

小 H 是面试官，将在接下来 n 天每天面试一个人。小 Z 负责决定应聘人前来面试的顺序。具体地，小 Z 可以选择一个 1 \sim n 的排列 p，然后在第 i (1 \leq i \leq n) 天通知编号为 p_i 的人前来面试。

小 H 准备了 n 套难度不一的面试题。由于 n 个前来应聘的人水平大致相同，因此对于同一套题，所有人的作答结果是一致的。具体地，第 i (1 \leq i \leq n) 天的面试题的难度为 s_i \in \{0,1\}，其中 s_i = 0 表示这套题的难度较高，没有人能够做出；s_i = 1 表示这套题的难度较低，所有人都能做出。小 H 会根据面试者的作答结果决定是否录用，即如果面试者没有做出面试题，则会拒绝，否则会录用。

然而，每个人的耐心都有一定的上限，如果在他面试之前未录用的人数过多，则他会直接放弃参加面试。具体地，编号为 i (1 \leq i \leq n) 的人的耐心上限可以用非负整数 c_i 描述，若在他之前已经有不少于 c_i 人被拒绝或放弃参加面试，则他也将放弃参加面试。

小 Z 想知道一共有多少种面试的顺序 p 能够让他们录用至少 m 人。你需要帮助小 Z 求出，能够录用至少 m 人的排列 p 的数量。由于答案可能较大，你只需要求出答案对 998\,244\,353 取模后的结果。

序列计数题纯史。

已完成今日今天我们来学习的内容是头文件iostream看度娘怎么解释的iostream是指iostream库iostream的意思是输入输出流其实iostream就是 input output stream输入输出流，主要用cin标准输入流函数和cout标准输出流函数用法如下cin>>输入的数据变量名称注意分号cout<<输出数据变量名称注意分号或者cout<<输出数据变量名称<<endl注意分号由此我们可以看出C++中的iostream头文件与C语言中stdio.h中的格式函数都不同区别是cin/cout不需要像printf/scanf一样判断数据的类型所以更简练，但是给程序的运行速度施加的很大的压力对于有些题会超时，所以我还是建议大家使用stdio.h中的printf和scanf，多打一些减少程序运行时间这就跟杠杆一样，不可能既省力又省距离。今天的收获可真多，我们学习了打代码的注意事项iostream头文件还有它与stdio.h头文件的区别讲解之后是不是让你更加了解了编程知识呢记得消化吸收哦我是靳皓旭下次再见jinhaoxu的题解怎么被撤下了他写的多好啊我们都要瞻仰靳皓旭的[C/C++]迈出在编程世界的第一步P1001我喜欢靳皓旭的题解靳皓旭的题解讲的好透彻啊大学习。

嘟嘟嘟。