挑战赛#22 题解

userId_undefined
杰杰
8月全勤卷王出道萌新快乐小狗秩序白银勇敢小狗GESP5级

2025-09-07 22:02:56

发布于：香港

49阅读
0回复
0点赞

以上是本人猜测题目难度，仅供参考：

题号 题目 难度
T1 大大和1 入门
T2 午枫的博弈 普及-
T3 小午的请求 入门
T4 小枫爬山 普及-
T5 午枫的双人挑战 普及/提高-
T6 大大和2 普及+/提高

以上为猜测 一定正确 以官方(@NoonMaple)为准。

T1. 大大和1

题目大意：

给你一个数组aa，让你求出是否存在任何一个(i,j)(i, j)数对满足以下条件：
max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i, a_{i + 1}, \dots,a_{j-1},a_j) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}。

解题思路：

这题里面，(i,j)(i, j)数对可以满足一个条件，就是i≤ji \leq j，所以i=ji = j是可能的，max(aimax(a_i 至 aj)a_j)的结果自然就是aia_i或者aja_j (是一样的)，而ai+ai+1+⋯+aj−1+aja_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}就自然是aia_i或者aja_j，aia_i必定 = aia_i，所以不论是什么数，结果都是YES。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    while(n--) {
        //甚至输入可以都不用
        cout << "YES\n";
    }
}

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

T2. 午枫的博弈

题目大意：

给你nn个数的数组AA，小午只能隐藏奇数下标的数，小枫只能隐藏偶数下标的数，当场上只剩下一个数未被隐藏时，如果数字本身是奇数，小午胜；反之，小枫胜。

解题思路：

题目说了双方都足够聪明，所以双方都会尽量让剩下的数是 奇数/偶数。而小午是先隐藏的，所以我们可以得出这样的结论：

奇数下标有没有奇数 偶数下标有没有偶数 胜利方 解释
有 有 偶数数量多则小枫；反之，小午 --
有 没有 小午 --
没有 有 小枫 --
没有 没有 小枫 由于小枫是后翻牌的，所以翻到最后剩下偶数就可以了

总结出后，就可以写出以下代码。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int a[100010];
int main() {
 	long long n;
    cin >> n;
    long long odd = 0, even = 0;
    bool o = 0, v = 0;
    for(long long i = 1; i <= n; i++) {
        cin >> a[i];
        if(i % 2 == 0) {
            even++;
            if(a[i] % 2 == 0) {
             	v = true;   
            }
        }
        else { 
            odd++;
            if(a[i] % 2 == 1) {
             	o = true;   
            }
        }
    }
    if(o && v) {
     	if(even >= odd) {
            cout << "Maple"; 
        } else {
            cout << "Noon";  
        }
    } else if(o && !v) {
    	cout << "Noon";
    } else if(!o && v) {
     	cout << "Maple";   
    } else {
     	cout << "Maple";   
    }
}

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

T3. 小午的请求

题目大意：

给出你nn个数，求最大的和，结果为偶数

解题思路：

我们可以将所有数相加，如果是偶数，那就肯定是最大的。反之，则减去最小奇数即可。

例如：

5
1 2 3 4 5

所有数相加结果是15，不为偶数，所以减去最小奇数(1)，结果为14。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int main() {
 	int n;
    cin >> n;
    int a[n + 5];
    long long sum = 0;
    bool q = false;
    int odd = 0;
    for(int i = 1; i <= n; i++) {
     	cin >> a[i];
        sum += a[i];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++) { //求出最小奇数
        if(a[i] % 2 == 1 && !q) {
         	odd = a[i];
            q = true;
        }
    } if(sum % 2 == 0) {
     	cout << sum;   
    } else {
     	cout << sum - odd;   
    }
}

时间复杂度：O(nlogn)O(n logn)

T4. 小枫爬山

小枫有病，爬山看别人腿长

题目大意：

现在有nn级台阶，mm个爬山者（腿长），请问这mm个爬山者最高能爬到的高度。

解题思路：

如果一个一个判断会TLE 别问我怎么知道，所以我们可以使用一个巧妙的方法！给爬山者的腿长排序，上一个爬山者能爬到的高度，这一个肯定可以，就判断是不是能 更上一层楼 再爬多几层。

参考代码：

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

long long stair[500010], ans[500010], height[500010];

struct Node {
  	long long num, id;  //使用结构体
}leg[500010];

bool cmp(Node x, Node y) {
	return x.num < y.num;   
}
int main() {
 	int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
    	cin >> stair[i];
        height[i] = stair[i] - stair[i - 1]; //算出差值
    }
    for(int i = 1; i <= m; i++) {
     	cin >> leg[i].num;
        leg[i].id = i;
    }
    sort(leg + 1, leg + m + 1, cmp); //排序
    int last_i = 1;
    bool key = false;
    for(int i = 1; i <= m; i++) { //m个人
		if(key) { //如果有人爬到最高层了 直接不用运算
            ans[leg[i].id] = ans[leg[i - 1].id]; //赋值
         	continue;   
        }
    	for(int j = last_i; j <= n; j++) { //从上一个人爬到的台阶继续
        	if(leg[i].num >= height[j]) { //如果能上去
                ans[leg[i].id] += height[j];       
            	if (j == n) { //判断是否爬到最上的台阶
                	key = true;
                }    
            } else {
                last_i = j; //爬不到 下一个从这个开始
                break;
            }
        }
        ans[leg[i + 1].id] = ans[leg[i].id]; //赋值
    }
    for(int i = 1; i <= m; i++) {
     	cout << ans[i] << " ";   //输出
    }
}

时间复杂度：O(n+mlogm)O(n + m log m)

T5. 午枫的双人挑战

题目大意：

观众要求小午和小枫完成kk个关卡。要是完成这个关卡的战斗部分，就算完成了一个关卡。但是，如果你要完成战斗部分的关卡，必须先完成本关解密部分的关卡。示意图如下：

解题思路：

在这题里面，我们可以先用前缀和优化，然后使用priority_queue [1]。在这题里面，要求是尽量小，所以每次弹出的是最大的元素。因此，可以求出最小值。

为什么不用queue？

其实，用queue也是可行的，不过时间复杂度会更高，因为每次都要找出最大值/排序。

参考代码：

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

long long puz[200010], fight[200010], sp[200010], level[200010], n, q, x;

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> puz[i];
        sp[i] = sp[i - 1] + puz[i]; //算出前缀和
    }
    for(int i = 1; i <= n; i++) {
        cin >> fight[i];
    }
    while(q--) {
        cin >> x;
        priority_queue<long long> q; //定义优先队列
        long long sum = 0, minn = LLONG_MAX; //minn表示最小值，sum表示本次的结果
        for(int m = 1; m <= n; m++) {
         	if(q.size() < x) { //如果还没有做到x各关卡
             	q.push(fight[m]); //进入队列
                sum += fight[m]; //增加时间
            } else if(fight[m] < q.top()) { //如果该数比q队列里的最大值小，说明找到更优方案
             	long long top = q.top(); //保存
                q.pop(); //出队列
                sum -= top; //减去时间
                q.push(fight[m]); //进队列
                sum += fight[m]; //加时间
            } 
            if(m >= x) { //如果处理了至少x关后
                long long ans = sp[m] + sum; //计算总时间
             	if(ans < minn) { //如果为更优解
                 	minn = ans; //赋值
                }
            }
        }
        cout << minn << endl; //输出
    }
}

时间复杂度：O(n+q⋅nlogx)O(n+q⋅nlogx)

T6. 大大和2

题目大意：

给你一个数组aa，让你求出是否所有(i,j)(i, j)的数对都满足以下条件：
max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i, a_{i + 1}, \dots,a_{j-1},a_j) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}。

解题思路：

这题分出几种情况。

  1. 最大值是负数，那答案肯定是YES。不论什么区间，负数加起来肯定是更小的。例如：
-1 -4 -2 -5

随便拿取任何区间，都能满足条件。

  1. 相邻的数是整数，答案肯定是NO。因为任何的整数加起来肯定是更大的。例如：
1 2 3

例如2 3，max(2,3)<2+3max(2, 3) < 2 + 3，所以是NO。

  1. 遍历所有数组里面的正整数，遍历 (左十,右十)(左十, 右十) 这个区间是否满足条件。

（测试点有点水，不然不能这么做）\color{yellow}{（测试点有点水，不然不能这么做）}

参考代码：

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

void solve() {
    int n;
    cin >> n;
    long long a[n + 5];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long global_max = *max_element(a, a + n); //获取数组最大值
    if (global_max <= 0) { //如果最大值小于0
        cout << "YES" << endl; //一定满足条件
        return;
    }
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > 0 && a[i + 1] > 0) { //如果相邻的数都是整数
            cout << "NO" << endl; //一定不满足条件
            return;
        }
    }
    for (int i = 0; i < n; i++) { //遍历每个数
        if (a[i] > 0) { //是正整数才判断
            for (int left = max(0, i - 10); left <= i; left++) { //遍历前十
                for (int right = i; right < min(n, i + 11); right++) { //遍历后十
                    if (left == right) continue; //跳过判断相等
                    
                    long long sum = 0;
                    long long max_val = LLONG_MIN;
                    for (int k = left; k <= right; k++) {
                        sum += a[k]; //加结果
                        max_val = max(max_val, a[k]); //取max
                    }      
                    if (max_val < sum) { //如果小于
                        cout << "NO" << endl; //输出
                        return;
                    }
                }
            }
        }
    }
    cout << "YES" << endl; //输出
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

时间复杂度：O(t⋅n)O(t \cdot n)

写的好的话点个赞吧！第一次写，写的不好见谅

午枫这次出题变简单了\color{yellow}{午枫这次出题变简单了}

  1. priority_queue，是一种STL容器，他并非queue一样是FIFO(First In Fist Out) ，而每次弹出的是最高优先级的元素。 ↩︎

userId_undefined
去预览
0/2000

全部评论 1

  • userId_undefined
    Smile
    出道萌新秩序白银GESP5级

    顶
    顶
    顶

    2025-09-20 来自 北京

    0

热门讨论