挑战赛#22全题解

yjynb666

2025-09-07 22:00:25

发布于：四川

16阅读

0回复

0点赞

挑战赛#22全题解

希望AC君能选中我的题解，感谢万分。

前言

赛时 T6 过了，但不是正解，看看就好。

~~感觉这次题挺简单的（除了T5)~~

T1(大大和1)

对于每个数对 $(i, j)$ ，可以发现，当 $i = j$ 的时候必然满足题目中所提到的条件：

$max(a _ i ,a _ i+1 ,…,a _ j−1 ,a _ j )≥a _ i +a _ i+1 +⋯+a _ j−1 +a _ j $

所以对于每组数据，我们的输出都应当是 YES。

T1代码部分

// 这种题很明显不用写注释了。
#include<bits/stdc++.h>
using namespace std;
#define int long long
main() {
    int t;
    cin >> t;
    while(t --) cout << "YES\n";
    return -1+1;
}

T2(午枫的博弈)

乍一看题目很难，其实仔细观察题目可以发现，因为这俩人都是绝对聪明的，也就是说他们采取的是最优策略，也就是贪心，因此我们可以找出规律（请看代码部分）。

T2代码部分

// 因为两人都足够聪明，所以我们采用贪心策略即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i ++) cin >> a[i];
    if(n&1) { // 当n为奇数的时候
        for(int i = 0; i < n; i += 2) { // 只要当偶数位上的数有一个是奇数就是小午赢
            if(a[i]&1) {
                cout << "Noon";
                return 0;
            }
        }
        cout << "Maple"; // 否则是小枫赢
    } else {
        for(int i = 1; i < n; i += 2) { // 于小午同理，只要当奇数位上的数有一个是奇数就是小午赢
            if(!(a[i]&1)) {
                cout << "Maple";
                return 0;
            }
        }
        cout << "Noon"; // 否则是小午赢
    }

    return !1;
}

T3(小午的请求)

~~看见题目第一眼让我想起了dp。~~

写这道题我们需要用到一个非常重要的性质：奇数减去奇数等于奇数。

因为题目要求让我们选出最大和为偶数的，那么整个序列和无非就两种情况：奇数或者偶数

如果是偶数，那肯定最好了，不用加也不用减，就是最大值。

否则的话，如果是奇数，那么我们就减去序列中最小的那个奇数，就是这道题的答案了。

T3代码部分

#include<bits/stdc++.h>
using namespace std;
#define int long long
main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n, 0);
    int cnt = 0+9999999999, ans = 0; // cnt用来查找a序列中最小的奇数。
    for(int i = 0; i < n; i ++) {
        cin >> a[i];
        ans += a[i];
        if(a[i]&1) cnt = min(cnt, a[i]); // 更新最小奇数。
    }
    if(ans&1) cout << ans-cnt; // 如果ans是奇数，便输出ans-cnt，因为奇数减奇数一定是偶数（不懂的可以去翻小学数学书）。
    else cout << ans;
    return !1;
}

T4(小枫爬山)

这道题直接模拟是会超时的，因为 $(1≤n,m≤5×10^5)$ ， $O(n^2)$ 一定过不了。

因为题目保证 $h_i≤h_i+1$ 而且需要查找第 $i$ 个爬山者最高能爬到的高度。

这很容易就能想到用二分查找来写。

但是需要注意的是，第 $i$ 个楼梯的长度需要的腿长不一定是 $h_i$ ，因为这些山呈楼梯状，所以第 $i$ 个楼梯的长度需要的腿长是 $h_i-h_{i-1}$ ，我们查找就应该查找一个已经维护好了的数组里面的数（详情请看代码部分）。

T4代码部分

#include<bits/stdc++.h>
using namespace std;
#define int long long
int h[514514], diff[514514], pre[514514], n, m;
int find(int b) { // 二分查找想必大家都会
    int l = 0, r = n - 1;
    int ans = n;
    while(l <= r) {
        int mid = l + (r - l) / 2;
        if(pre[mid] > b) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}
main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for(int i = 0; i < n; i ++) {
        cin >> h[i];
    }
    diff[0] = 0; 
    for(int i = 1; i < n; i ++) { // 在这里算差是因为它是呈楼梯状的，第 i-1 阶楼梯到第 i 阶楼梯需要的腿长是 (h[i]-h[i-1]) 长
        diff[i] = h[i] - h[i-1];
    }
    // 初始化
    pre[0] = diff[0]; 
    for(int i = 1; i < n; i ++) {
        pre[i] = max(pre[i-1], diff[i]);
    }
    for(int i = 0; i < m; i ++) {
        int b;
        cin >> b;
        if(b < h[0]) { // 因为这个吃了两发罚时。。。
            cout << 0 << ' ';
            continue;
        }
        int pos = find(b); // 二分搜索第 i 个人能够到达的最高点。
        // 接下来就是特判一下 pos 的位置并输出了。
        if(pos == 0) {
            cout << h[0] << ' ';
        } else if(pos >= n) {
            cout << h[n-1] << ' ';
        } else {
            cout << h[pos-1] << ' ';
        }
    }

    return 0;
}

T5(午枫的双人挑战)

~~应该是本场最难。~~

通过遍历所有可能的终点关卡 $M$ ，计算完成前 $M$ 关解密的总时间加上从 1 到 $M$ 关中选取最小的 $k$ 个战斗时间的总和。使用大根堆维护当前最小的 $k$ 个战斗值，确保每次都能高效更新最优解。最终取所有 $M$ 情况中的最小值作为完成 $k$ 个关卡的最短时间。(更详细的请看代码部分)。

T5代码部分

/*
这里要注意的是：
1.完成第i-1关解密才能开始第i关
2.战斗必须在对应关卡的解密完成后才能进行
3.两人不能同时进行战斗或者解密，只能等一个人先干完了另一个人才能干
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, q;
    cin >> n >> q;
    vector<ll> a(n+1), b(n+1);
    for(ll i = 1; i <= n; i ++) cin >> a[i];
    for(ll i = 1; i <= n; i ++) cin >> b[i];
    vector<ll> pre(n+1);
    for(ll i = 1; i <= n; i ++) pre[i] = pre[i-1] + a[i]; // 计算前缀和，pre[i]表示前i关解密总时间。
    while(q --) {
        ll k;
        cin >> k;
        priority_queue<ll> pq; // pq维护当前最小的k个战斗时间
        ll sum = 0; // 大根堆优先队列里面战斗时间的总和
        ll ans = LLONG_MAX; // 初始化
        // 维护大小为k的大根堆优先队列，队头为当前k个最小值中的最大值
        for(ll i = 1; i <= n; i ++) {
            if(pq.size() < k) {
                pq.push(b[i]); // 还未满足答案，直接加入当前战斗时间
                sum += b[i]; // 更新战斗时间总和
            } else {
                if(b[i] < pq.top()) { // 当前战斗时间小于队中最大值便入队
                    sum -= pq.top();
                    pq.pop();
                    sum += b[i];
                    pq.push(b[i]);
                }
            }

            // 当已经满足当前 k 了的话就找最优的答案。
            if(i >= k) {
                ll cur = pre[i] + sum; // 总时间 = 前i关解密时间 + 最小的k个战斗时间
                ans = min(ans, cur); // 更新最小值
            }
        }
        cout << ans << '\n';
    }
    return !1;
}

T6(大大和2)

~~倒不如T5来当T6合适~~

说实话我赛时过的真的很迷（应该是数据太水了）。

这道题与 T1 有所不同的是，T1只要求要一对满足即可，这道题需要满足所有对数才是 YES。

很显然，只需要检查连续长度为 2 和 3 的子数组即可（正确性还证明不出来）。

当 $n ≤ 5000$ 时，模拟是肯定能过的，所以为了稳妥，我采取用模拟来写。

否则则用检查连续长度为 2 和 3 的子数组的方法来写。

T6代码部分

// 虽说是T6，但个人感觉比T5简单。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t --) {
        int n;
        cin >> n;
        vector<ll> a(n);
        for(int i = 0; i < n; i ++) cin >> a[i];
        if(n <= 5000) { // 如果说 n 的大小足以让我们O(n^2)过的话就选择模拟写法
            bool ok = true;
            for(int i = 0; i < n && ok; i ++) {
                ll mx = a[i];
                ll s = a[i];
                for(int j = i + 1; j < n && ok; j ++) {
                    mx = max(mx, a[j]);
                    s += a[j];
                    if(mx < s) ok = false;
                }
            }
            cout << (ok ? "YES" : "NO") << '\n';
        } else { // 否则就检查长度为2 3大小的连续子数组是否满足条件即可。
            bool ok = true;
            for(int i = 0; i < n - 1 && ok; i ++) {
                if (a[i] > 0 && a[i + 1] > 0) ok = false;
            }
            for(int i = 0; i < n - 2 && ok; i ++) {
                int cnt = 0;
                if(a[i]) cnt ++;
                if(a[i + 1]) cnt ++;
                if(a[i + 2]) cnt ++;
                if(cnt >= 2) {
                    ll mx = max({a[i], a[i + 1], a[i + 2]});
                    ll s = a[i] + a[i + 1] + a[i + 2];
                    if (mx < s) ok = false;
                }
            }
            cout << (ok ? "YES" : "NO") << '\n';
        }
    }

    return 0;
}