官方题解 | 挑战赛#32题解

userId_undefined
集团 黄晔莹
管理员

2026-06-10 13:10:27

发布于：浙江

396阅读
0回复
0点赞

赛纲介绍

本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。

题目编号 题目名称 题目难度
T1 项目计划 入门
T2 千载难逢的良缘 普及-
T3 保险金 普及-
T4 晋级赛 普及-
T5 科技展示 普及-
T6 活动筹备计划 普及-

T1 项目计划

题目大意

给出项目数量和产线数量，并给出完成项目所需的时间，所有项目的时间都是给出的这个时间。求完成所有项目所需的总时间。

题解思路

先用取余运算确定完成所有项目所需的轮数，如果无法整除则需要单独再增加一轮时间。确定轮次之后计算总时间，可以先单独计算时分秒，再按秒分时的顺序进行进位判断。

需要注意输入的格式中存在 : 分隔符，需要用提示中的 scanf 获取，或在读取时注意 : 的位置。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int hh,mm,ss;
    scanf("%d:%d:%d",&hh,&mm,&ss);

    int num=n/m;
    if(n%m!=0){
        num++;
    }

    hh=hh*num;
    mm=mm*num;
    ss=ss*num;

    mm=mm+ss/60;
    ss=ss%60;
    
    hh=hh+mm/60;
    mm=mm%60;

    cout<<hh<<":"<<mm<<":"<<ss<<endl;
    return 0;
}

T2 千载难逢的良缘

题目大意

给出每个人的平分，评分差值的绝对值越小越有缘，求最有缘的两个分数以及他们的差值绝对值。

题解思路

差值绝对值最小的两个分数一定是大小最接近的，所以整体排序后遍历整个数组，记录其中差值绝对值最小的情况。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int main() {
    int n;
    cin >> n;
    
    for(int i=1;i<=n;i++){
		cin >> a[i];
	}
    sort(a+1, a+n+1);

    int minn=a[2]-a[1];
	int x=1;
	int y=2;

    for(int i=3;i<=n;i++){
        if(a[i]-a[i-1]<minn){
			minn=a[i]-a[i-1];
			x=i-1;
			y=i;
		}
    }

    cout << minn << endl;
    cout << a[x] << " " << a[y] << endl;

    return 0;
}

T3 保险金

题目大意

给出每个客户的 mm 条事故保险金，要求按照客户顺序处理，每个客户内按金额从小到大处理，直到当天能发放的保险金总额不够继续发放。

题解思路

按题目要求的顺序排序，可以使用结构体排序，按客户编号和金额大小排序，再模拟发放过程即可。

需要注意题目要求的输出格式，当遇到新客户时要输出名字和发放事故数，再输出每个事故的保险金数量。所以这里要记录上一个发放事故的客户编号，区分不同的客户。在输出时也要先遍历统计数量，再遍历输出对应的面额。

参考代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    string name;
    int id;
    int num;
}a[1000010];

bool cmp(node x,node y){
    if(x.id!=y.id){
        return x.id<y.id;
    }
    else{
        return x.num<y.num;
    }
}

int main(){
    int T,n;
    cin>>T>>n;
    int x=0;
    for(int i=1;i<=n;i++){
        string namei;
        int m;
        cin>>namei>>m;
        for(int j=1;j<=m;j++){
            x++;
            cin>>a[x].num;
            a[x].name=namei;
            a[x].id=i;
        }
    }

    sort(a+1,a+x+1,cmp);

    int sum=0;
    int cnt=0;
    string lastname="";
    for(int i=1;i<=x;i++){
        if(sum+a[i].num<=T){
            if(a[i].name!=lastname){
                if(i!=1){
                    cout<<endl;
                }
                cout<<a[i].name;
                lastname=a[i].name;
            }

            cout<<" "<<a[i].num;
            sum=sum+a[i].num;
            cnt++;
        }
        else{
            break;
        }
    }
    cout<<endl;
    cout<<cnt<<" "<<sum<<endl;
    return 0;
}

T4 晋级赛

题目大意

给出选手分数，查询多个分数对应的无法晋级人数。

题解思路

由于是多次查询，因此可以先排序，再使用二分查找的方法查询晋级分数所在的数组下标，从而得到无法晋级的下标范围。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[1000010];
int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++){
        int x;
        cin>>x;
        int l=1;
        int r=n;
        int ans=n+1;
        while(l<=r){
            int mid=(l+r)/2;
            if(a[mid]>=x){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        cout<<ans-1<<endl;
    }

    return 0;
}

T5 科技展示

题目大意

给出 n 件展品，选择 m 件展品，要求方案输出时编号按升序排列。

题解思路

经典深度优先搜索抽小球，需要注意用 vis 数组记录哪些展品已经选择。但本题中要求编号按升序排列，因此在递归时可以加入编号范围的参数，用于控制选取时的循环范围，确保选取编号是升序。

参考代码

#include <bits/stdc++.h>
using namespace std;

int n,m;
int a[30];
int vis[30];

void dfs(int x,int start) {
    if (x==m+1) {
        for (int i=1;i<=m;i++) {
            cout<<a[i]<< " ";
        }
        cout<<endl;
        return;
    }

    for (int i=start;i<=n;i++){
		if(vis[i]==0){
        	a[x]=i;
			vis[i]=1;
        	dfs(x+1,i+1);
			vis[i]=0;
		}
    }
}

int main() {
    cin>>n>>m;
    dfs(1,1);
    return 0;
}

T6 活动筹备计划

题目大意

三种任务在每天有不同的效果值，不能连续两天选择相同的任务，切换任务会获得对应的切换效果值。求 nn 填的最大总效果值。

题解思路

由于每天每个任务的效果值都可能变化，所以选择动态规划，状态转移方程形如 dp[i][0]=max(dp[i-1][1]+w[1][0],dp[i-1][2]+w[2][0])+val[i][0];，其中 w[i][j] 表示切换任务 i 到任务 j 的效果值，val[i][j] 表示第 i 天完成任务 j 的效果值。

类似于涂色问题，由于选择任务时不能和前一天的任务相同，因此需要记录前一天选择的任务编号，重复的情况是无法转移的，同时前一天的任务编号也参与了切换效果值的计算。在 dp 数组的设计中选择二维形式，dp[i][j] 表示第 i 天选择任务 j 的最大总效果值。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long dp[200010][3];
long long val[200010][3];
long long w[3][3];

int main() {
    int n;
    cin>>n;

    for (int i=0;i<3;i++){
        for (int j=0;j<3;j++){
            cin>>w[i][j];
        }
    }

    for (int i=1;i<=n;i++){
        cin>>val[i][0]>>val[i][1]>>val[i][2];
    }

    dp[1][0]=val[1][0];
    dp[1][1]=val[1][1];
    dp[1][2]=val[1][2];

    for (int i=2;i<=n;i++){
        dp[i][0]=max(dp[i-1][1]+w[1][0],dp[i-1][2]+w[2][0])+val[i][0];
        dp[i][1]=max(dp[i-1][0]+w[0][1],dp[i-1][2]+w[2][1])+val[i][1];
        dp[i][2]=max(dp[i-1][0]+w[0][2],dp[i-1][1]+w[1][2])+val[i][2];
    }

    cout <<max(dp[n][0],max(dp[n][1],dp[n][2]))<<endl;
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 30

热门讨论