挑战赛#26题解 | 非官方

杰杰

2025-12-28 22:00:57

发布于：广东

12阅读

0回复

0点赞

挑战赛#26题解 | 非官方

本次题目猜测的总体难度如下，仅供参考：

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

T1. 小午的四舍五入

题目大意

给你一个实数 $n$ ，要你将 $n$ 四舍五入至整数最低位。

解题思路

可以使用 round() 函数，将 double 类型的数四舍五入。

参考代码

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

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

时间复杂度： $O(1)$

T2. 小午的排名预期

题目大意

每天考试的分数为 $300$ 分，现在有 $n$ 名考生，第 $i$ 名考生第一，二，三天的分数分别为 $a_{i,1}, a_{i, 2}, a_{i, 3}$ 。想请问，第 $i$ 名学生在考完第四天试后，能达到前 $k$ 名吗？

解题思路

可以使用结构体，把前三天的总分加起来，再用 $idx$ 记下编号。使用结构体排序，然后找出第 $k$ 名，其次，遍历每位考生。假设第 $i$ 为考生那天获得了 $300$ 分，其他都拿 $0$ 分，那么这位考生能获得前 $k$ 名的判断为 $a_i.sum + 300 \geq a_k.sum$ ，再用 $vis$ 数组记录下来输出即可。

参考代码

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

struct Node {
  	long long sum, id;  
}a[N];

bool cmp(Node x, Node y) {
 	return x.sum > y.sum;   
}

int main() {
	int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) {
     	int x, y, z; cin >> x >> y>> z;
        a[i].sum = x + y + z;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    long long s = a[k].sum;
    bool vis[N];
    for(int i = 1; i <= n; i++) {
    	if(a[i].sum + 300 >= s) vis[a[i].id] = true;
        else vis[a[i].id] = false;
    }
    for(int i = 1; i <= n; i++) {
     	if(vis[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
	return 0;
}

时间复杂度： $O(n log n)$

T3. 午枫的玩具火车

题目大意

有一个 $n$ 节车厢的火车，编号为 $1 \sim n$ ，一开始每一节车厢之间都是断开的。现在有三种操作：

1 x y 是把车厢 $x$ 的尾部和车厢 $y$ 的尾部链接。
2 x y 是把车厢 $x$ 的尾部和车厢 $y$ 的尾部断开。
3 x 是输出包含车厢 $x$ 的火车中所有车厢的编号，从头到尾输出。输出时第一个数字为列车的长度。

总共执行 $q$ 次操作。

解题思路

我们可以使用数组来模仿双向链表，实现连接和断开的操作。其中，没有连接（断开）在数组中表示为 $-1$ ，其他则表示为连接了的车厢编号。

参考代码

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

int l[N], r[N];

int main() {
	int n, q; cin >> n >> q;
    memset(l, -1, sizeof l); 
    memset(r, -1, sizeof r);
    while(q--) {
     	int x; cin >> x;
        if(x == 1) {
         	int a, b; cin >> a >> b;
            r[a] = b; 
            l[b] = a;
        } else if(x == 2) {
         	int a, b; cin >> a >> b;
            r[a] = -1; 
            l[b] =-1;
        } else if(x == 3) {
         	int a; cin >> a;   
            int h = a; 
            while(l[h] != -1) {
             	h = l[h];   
            }
            
            vector<int> ans;
            int cur = h;
            while(cur != -1) { 
                ans.push_back(cur);
                cur = r[cur];
            }
            
            cout << ans.size();
            for(int v : ans) cout << " " << v; 
            cout << endl;
        }
    }
	return 0;
}

时间复杂度： $O(q \times L)$ ，其中 $L$ 表示链表的最大长度。最坏情况为 $O(q \times n)$ 。

T4. 午枫的身高统计

题目大意

给你 $n$ 个人的身高，第 $i$ 个人的身高为 $a_i$ 。接下来，进行 $q$ 次询问，判断身高大于等于 $x$ 的人有多少个。

解题思路

可以使用 lower_bound() 函数，找出第一个不小于 $x$ 的值的下标，再拿总人数减去结果即可。

参考代码

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

int a[N];

int main() {
	int n, q; cin >> n >> q;
    for(int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    while(q--) {
     	int x; cin >> x;
        int low = lower_bound(a + 1, a + n + 1, x) - a;
        cout << n - low + 1 << endl;
    }
	return 0;
}

时间复杂度： $O((n + q) log n)$

T5. 小午的学习技能

题目大意

总共有 $n$ 个技能，每个技能都有一个学习时间，第 $i$ 个技能需要花费 $t_i$ 的时间,而第 $i$ 个技能有 $m_i$ 个前置技能， $a_{i,j}$ 表示第 $i$ 个技能的第 $j$ 个前置技能。现在，请你求出完成第 $n$ 个技能需要花费的最少时间。

解题思路

我们可以使用递归的思路，创建一个 $vis$ 数组， $vis_i$ 表示第 $i$ 个技能是否学习过。然后使用逆向思维，从第 $n$ 个技能开始，然后遍历所有的前置技能，然后重复这个步骤即可。

参考代码

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

bool vis[N];
long long a[N], sum, m[N];
vector<long long> s[N];

void dfs(int x) {
 	vis[x] = true;
    sum += a[x];
    for(auto d : s[x]) {
     	if(!vis[d]) dfs(d);   
    }
    return ;
}

int main() {
	int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> m[i];
        for(int j = 1; j <= m[i]; j++) {
         	int r; cin >> r;
            s[i].push_back(r);
        }
    }
    dfs(n);
    cout << sum;
	return 0;
}

时间复杂度： $O(n + E)$ ，其中 $E$ 表示 $\sum m_i$ 。 $O(n + E)$ 最大 $\approx O(4 \times 10 ^ 5)$ 。

T6. 小午的迷宫

题目大意

有一个 $n \times m$ 的迷宫，迷宫里分别有障碍物 # 和无障碍路径 . 。小午从迷宫的 $(1, 1)$ 作为起点，每次只能向下或者向右走一格。问，他能经过的格子数量最多是多少呢？

解题思路

可以用一个二维 $dp$ 数组，遍历所有点，而 $dp$ 的转移方程就是 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1，这样可以在这格的基础上，找上和左的点，从到达的点数更多的点走到当前个，最后取 $max$ 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char a[N][N];
long long dp[N][N];
int main() {
	int n, m; cin >> n >> m;
    for(int i = 1; i <= n;i ++) {
     	for(int j = 1; j <= m; j++) {
         	cin >> a[i][j];   
        }
    }
    if(a[1][1] != '#') dp[1][1] = 1;
    else { cout << 0; return 0; }
    long long maxn = 1;
    for(int i = 1; i <= n; i++) {
     	for(int j = 1; j <= m; j++) {
            if(i == 1 && j == 1) continue;
            if(a[i][j] == '#') continue;
            if((i > 1 && dp[i - 1][j] > 0) || (j > 1 && dp[i][j - 1] > 0)) {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;
                maxn = max(maxn, dp[i][j]);
            }
        }
    }
    cout << maxn;
}