挑战赛#22 题解

杰杰

2025-09-07 22:02:56

发布于：香港

11阅读

0回复

0点赞

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

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

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

T1. 大大和1

题目大意：

给你一个数组 $a$ ，让你求出是否存在任何一个 $(i, j)$ 数对满足以下条件：
$max(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 \leq j$ ，所以 $i = j$ 是可能的， $max(a_i$ 至 $a_j)$ 的结果自然就是 $a_i$ 或者 $a_j$ (是一样的)，而 $a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j}$ 就自然是 $a_i$ 或者 $a_j$ ， $a_i$ 必定 = $a_i$ ，所以不论是什么数，结果都是YES。

参考代码：

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

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

T2. 午枫的博弈

题目大意：

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

解题思路：

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

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

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

参考代码：

#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)$

T3. 小午的请求

题目大意：

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

解题思路：

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

例如：

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(n logn)$

T4. 小枫爬山

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

题目大意：

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

解题思路：

如果一个一个判断会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 + m log m)$

T5. 午枫的双人挑战

题目大意：

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

解题思路：

在这题里面，我们可以先用前缀和优化，然后使用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)$

T6. 大大和2

题目大意：

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

解题思路：

这题分出几种情况。

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

-1 -4 -2 -5

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

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

1 2 3

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

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

$\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;
}