官方题解 | 挑战赛#26
2025-12-29 11:22:24
发布于：浙江
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 小午的四舍五入 | 入门 |
| T2 | 小午的排名预期 | 入门 |
| T3 | 午枫的玩具火车 | 普及- |
| T4 | 午枫的身高统计 | 普及- |
| T5 | 小午的学习技能 | 普及- |
| T6 | 小午的迷宫 | 普及- |
T1 小午的四舍五入
题目大意
给定一个小数，输出四舍五入后的结果。
解题思路
可以先将输入的浮点数乘以 ，判断个位数是否大于等于 ，如果是的话，将整个数加上 模拟进位，最后再将当前的数除以 并取整即可。或使用 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 小午的排名预期
题目大意
已知前三天 个人的考试分数，每天的考试总分为 分，问第四天考完每个人的排名是否可以进入前 名。
解题思路
将所有人前三天的分数求和并排序，然后第四天对于每个人按照本人拿满分，其他人为 的情况去考虑，检查是否能到达前 名。
参考代码
#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 x y ，我们可以用以下代码完成：
r[x]=y;
l[y]=x;
注意这里是有顺序的，所以 和 的顺序不能反。
对于第二种操作 2 x y ，我们可以用以下代码完成：
r[x]=l[y]=0;
对于第三种操作，我们可以直接先暴力找到 所在链的最左侧点，然后再依次向后遍历，存储所有的数，最后输出其个数以及所有数字即可。
参考代码
#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 午枫的身高统计
题目大意
个人，每个人身高已知，有 次询问，找出身高大于等于 的人数。
解题思路
对于每次查询，如果都遍历所有人的身高的话，时间复杂度为 ，无法通过。
容易发现对所有人的身高进行排序，那么大于等于 的身高就会出现在一段后缀当中，因此容易想到使用二分查找能够快速找出分解点。
时间复杂度 。
参考代码
#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 小午的学习技能
题目大意
有 个技能，学习每个技能需要花费 时间，在学习每个技能之前，需要已学习若干个前置技能，需要求出学习第 个技能的最小花费。
解题思路
可以使用队列存储需要学习的技能，最初存入第 个技能，每次取出当前需要学习的技能，然后将其还未学习的前置技能放入队列中，重复此操作即可。
另外，本题需要使用 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 小午的迷宫
题目大意
有一个 的迷宫，有 . 和 # 两种图形， # 表示障碍物，. 表示可以走的路。起点为 每次只能向下或向右走，问当无法移动时，最多可以经过多少个格子。
解题思路
使用 进行二方向遍历，并用距离数组 记录从起点到每个点的所经过的格子数。最终取 数组的最大值即可。
参考代码
#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;
}
有帮助，赞一个