官方题解 | 挑战赛#26

NoonMaple

2025-12-29 11:22:24

发布于：浙江

102阅读

0回复

0点赞

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

题目编号	题目标题	难度
T1	小午的四舍五入	入门
T2	小午的排名预期	入门
T3	午枫的玩具火车	普及-
T4	午枫的身高统计	普及-
T5	小午的学习技能	普及-
T6	小午的迷宫	普及-

T1 小午的四舍五入

题目大意

给定一个小数，输出四舍五入后的结果。

解题思路

可以先将输入的浮点数乘以 $10$ ，判断个位数是否大于等于 $5$ ，如果是的话，将整个数加上 $10$ 模拟进位，最后再将当前的数除以 $10$ 并取整即可。或使用 round(x) 函数，即可得到四舍五入的结果。

参考代码

方法一

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int main(){
    double a;cin>>a;
    cout<<(int)round(a);
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int main(){
    double a;cin>>a;
    int b=a*10;
    if(b%10>=5){
        b+=10;
    }
    cout<<b/10;
    return 0;
}

T2 小午的排名预期

题目大意

已知前三天 $n$ 个人的考试分数，每天的考试总分为 $300$ 分，问第四天考完每个人的排名是否可以进入前 $k$ 名。

解题思路

将所有人前三天的分数求和并排序，然后第四天对于每个人按照本人拿满分，其他人为 $0$ 的情况去考虑，检查是否能到达前 $k$ 名。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int a[N],b[N];

bool cmp(int a,int b){
    return a>b;
}

int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=3;j++){
            int x;cin>>x;
            a[i]+=x;
        }
        b[i]=a[i];
    }
    sort(b+1,b+n+1,cmp);

    for(int i=1;i<=n;i++){
        if(a[i]+300<b[k]) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    
    return 0;
}

T3 午枫的玩具火车

题目大意

起初，数字 $1\sim n$ 之间相互独立，给出 $q$ 次查询，每次查询为以下三种的一种：

将两个没有连接起来的数字按顺序前后连接起来；
将两个已经连接起来的数字分开；
输出某一个数字所有链上从头到尾所有的数字以及个数。

解题思路

由于要涉及到按顺序连接和断开的操作，不难想到我们可以通过使用数组模拟链表的方式进行这一系列操作。

$l_i$ ：表示 $i$ 这个数字左边的数字是多少，如果没有则为 $0$ 。

$r_i$ ：表示 $i$ 这个数字右边的数字是多少，如果没有则为 $0$ 。

于是，对于第一种操作 1 x y ，我们可以用以下代码完成：

r[x]=y;
l[y]=x;

注意这里是有顺序的，所以 $x$ 和 $y$ 的顺序不能反。

对于第二种操作 2 x y ，我们可以用以下代码完成：

r[x]=l[y]=0;

对于第三种操作，我们可以直接先暴力找到 $x$ 所在链的最左侧点，然后再依次向后遍历，存储所有的数，最后输出其个数以及所有数字即可。

参考代码

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

const int N = 100010;

int l[N],r[N];
int ans[N];
int idx;

int main(){
    int n,q;cin>>n>>q;
    while(q--){
        int op;cin>>op;
        if(op==1){
            int x,y;cin>>x>>y;
            r[x]=y;
            l[y]=x;
        }
        else if(op==2){
            int x,y;cin>>x>>y;
            r[x]=0;
            l[y]=0;
        }
        else{
            int x;cin>>x;
            int rt=x;
            while(l[rt]) rt=l[rt];

            idx=0;
            while(rt){
                ans[++idx]=rt;
                rt=r[rt];
            }
            cout<<idx<<" ";
            for(int i=1;i<=idx;i++) cout<<ans[i]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

T4 午枫的身高统计

题目大意

$n$ 个人，每个人身高已知，有 $q$ 次询问，找出身高大于等于 $x_j$ 的人数。

解题思路

对于每次查询，如果都遍历所有人的身高的话，时间复杂度为 $O(nq)$ ，无法通过。

容易发现对所有人的身高进行排序，那么大于等于 $x_j$ 的身高就会出现在一段后缀当中，因此容易想到使用二分查找能够快速找出分解点。

时间复杂度 $O(nlog(n)+qlog(n))$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;

int h[N];

int main(){
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>h[i];
    sort(h+1,h+n+1);

    while(q--){
        int x;cin>>x;
        int pos=lower_bound(h+1,h+n+1,x)-h;
        cout<<n-pos+1<<endl;
    }
    return 0;
}

T5 小午的学习技能

题目大意

有 $n$ 个技能，学习每个技能需要花费 $t_i$ 时间，在学习每个技能之前，需要已学习若干个前置技能，需要求出学习第 $n$ 个技能的最小花费。

解题思路

可以使用队列存储需要学习的技能，最初存入第 $n$ 个技能，每次取出当前需要学习的技能，然后将其还未学习的前置技能放入队列中，重复此操作即可。

另外，本题需要使用 vector 存储数据。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 200010;

ll t[N];
vector<ll>a[N];
bool vis[N];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t[i];
        int m;cin>>m;
        for(int j=1;j<=m;j++){
            int x;cin>>x;
            a[i].push_back(x);
        }
    }

    ll res=0;
    queue<ll>q;
    q.push(n);
    vis[n]=true;
    while(!q.empty()){
        auto pos=q.front();q.pop();
        res+=t[pos];

        for(auto x:a[pos]){
            if(vis[x]) continue;

            q.push(x);
            vis[x]=true;
        }
    }
    cout<<res<<endl;
    return 0;
}

T6 小午的迷宫

题目大意

有一个 $n\times m$ 的迷宫，有 . 和 # 两种图形， # 表示障碍物，. 表示可以走的路。起点为 $(1,1)$ 每次只能向下或向右走，问当无法移动时，最多可以经过多少个格子。

解题思路

使用 $bfs$ 进行二方向遍历，并用距离数组 $d$ 记录从起点到每个点的所经过的格子数。最终取 $d$ 数组的最大值即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;

char g[N][N];
int d[N][N];
bool vis[N][N];

int dx[2] = {0, 1}, dy[2] = {1, 0};

int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
        }
    }

    queue<pair<int,int>>q;
    q.push({1,1});
    vis[1][1]=true;
    d[1][1]=1;
    while(!q.empty()){
        auto [x,y]=q.front();q.pop();

        for(int i=0;i<2;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx<1 || nx>n || ny<1 || ny>m || vis[nx][ny] || g[nx][ny]=='#') continue;

            q.push({nx,ny});
            d[nx][ny]=d[x][y]+1;
            vis[nx][ny]=true;
        }
    }
    
    int res=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            res=max(res,d[i][j]);
        }
    }
    cout<<res<<endl;
    return 0;
}