官方题解 | 挑战赛22题解

userId_undefined

NoonMaple

7月全勤卷王出道萌新时空双修者快乐小狗

2025-09-08 11:31:40

发布于：浙江

89阅读
0回复
0点赞

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

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

T1 大大和1

题目大意

有一个长度为 nn 的数组 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=ji=j 时，一定满足 ai=aia_i=a_i 。所以答案一定是 YES

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];

    cout<<"YES"<<endl;
}

signed main(){
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}

T2 午枫的博弈

题目大意

有 nn 个数，小午只能隐藏奇数位置的数，小枫只能隐藏偶数位置的数，两人轮流行动，小午先手，若最后剩下一个数时结束，剩下的数如果是奇数，小午获胜，否则小枫获胜。求最终谁一定会赢。

解题思路

因为每个人可以选择隐藏的数和对方没有交集，所以在隐藏数时，小午会优先选择隐藏偶数，小枫会优先先择隐藏奇数。

当 nn 为奇数时，判断奇数位置是否有奇数，有则输出 Noon ，否则输出 Maple ； nn 为偶数时，判断偶数位置是否有偶数，有则输出 Maple ；否则输出 Noon。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n;cin>>n;
    vector<int>a(n+1);
    for(int i=1;i<=n;i++) cin>>a[i];
    
    bool odd=0,eve=0;
    for(int i=1;i<=n;i+=2){
        if(a[i]&1) odd=true;
    }
    for(int i=2;i<=n;i+=2){
        if((a[i]&1)==0) eve=true;
    }

    if(n&1){
        if(odd) cout<<"Noon"<<endl;
        else cout<<"Maple"<<endl;
    }
    else{
        if(eve) cout<<"Maple"<<endl;
        else cout<<"Noon"<<endl;
    }
}

T3 小午的请求

题目大意

有 nn 个数字，从中选出一些数，使得选出的数之和为偶数且最大，求这些数字之和。

解题思路

考虑要选出和最大的数，因为没有负数，所以我们可以直接把所有数都选了，如果和为偶数，那这就是最大的数字和了；否则说明其中至少有一个奇数，把最小奇数剔除就可以得到最大的数字和。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int INF = 1e18+10;

signed main(){
    int n;cin>>n;
    vector<int>a(n+1);
    int res=0;
    int mi=INF;
    for(int i=0;i<n;i++){
        cin>>a[i];
        res+=a[i];
        if(a[i]&1) mi=min(mi,a[i]);
    }
    if(res&1) res-=mi;
    cout<<res<<endl;
}

T4 小枫爬山

题目大意

有 nn 级台阶，mm 位爬山者，每位爬山者腿长 bib_i ，如果下一级台阶与爬山者所在台阶的高度差大于爬山者的腿长，就无法继续往上爬了。求每位爬山者能爬到的最大高度。

解题思路

对于每一次询问，我们可以对每级台阶的高度差进行二分查找，找到第一个大于 bb 的台阶，这级台阶的前一级就是最终到达的位置。但是二分需要有单调性，我们可以用 viv_i 记录前 ii 个位置最大的高度差，对 vv 二分即可。

对于每一个台阶实际的高度，我们可以用前缀和快速求出。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

signed main(){
    int n,m;cin>>n>>m;
    vector<int>h(n+1),d(n+1);
    vector<int>v;
    for(int i=1;i<=n;i++){
        cin>>h[i];
        d[i]=h[i]-h[i-1];
        
        if(v.size()==0) v.push_back(d[i]);
        else{
            int t=v.back();
            if(d[i]<t) v.push_back(t);
            else v.push_back(d[i]);
        }
    }
    while(m--){
        int x;
        cin>>x;
        int pos=upper_bound(v.begin(),v.end(),x)-v.begin();
        cout<<h[pos]<<" ";
    }
    cout<<endl;
}

T5 午枫的双人挑战

题目大意

一共有 nn 个关卡，每个关卡分为解密和战斗两部分，挑战关卡有两个限制：

  • 对于不同关卡，只有完成了前一关的解密部分才能进行下一关的解密部分；

  • 对于同一关卡，只有完成了这一关卡的解密部分才能进行这一关的战斗部分。

第 ii 关的解密部分需要耗时 aia_i ，战斗部分需要耗时 bib_i ，完成了一关的揭秘和战斗部分才视为完成这一关。对于 qq 个询问，求完成 kk 个关卡的最短用时。

解题思路

首先考虑完成 kk 个关卡，我们需要至少完成前 kk 个解密部分 ，完成 bib_i 之前我们需要至少完成前 ii 个解密部分。

接下来我们需要考虑的是选择完成哪几个关卡所花的时间最少。由于询问次数只有 100100 ，所以对于每一个询问可以尝试使用 O(n)O(n) 甚至 O(nlogn)O(nlogn) 的复杂度去完成。由于完成解密部分一定是连续的，所以我们可以先用前缀和 sis_i 求出前 ii 个解密部分所花时间是多少。

我们可以枚举最后一个被完成的关卡的哪个，此时的时间花费是 si+bis_i+b_i ，其余的 k−1k-1 个战斗部分选择 bib_i 最小的 k−1k-1 个，但是这样的做法时间复杂度会来到 O(n2)O(n^2) ，显然是不合理的。其实我们可以通过优先队列优化选 bib_i 的过程，我们先选出前 kk 关卡完成，将 bib_i 都存入优先队列中，往后枚举时，设当前枚举的位置为 jj ，如果 bjb_j 小于优先队列中最大的元素，则可以把 bjb_j 与优先队列中最大元素替换。每次算出所需要的时间，更新答案。这样查询的时间复杂度为 O(nlogn)O(nlogn) 。

总时间复杂度为 O(n+knlogn)O(n+knlogn) 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 400010;

int n,Q;
int a[N],b[N];
int s[N];
int ans[N];

signed main(){
    cin>>n>>Q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

    while(Q--){
        int k;cin>>k;
        priority_queue<int>q;
        
        int sumb=0;
        for(int i=1;i<=k;i++){
            q.push(b[i]);
            sumb+=b[i];
        }

        int ans=s[k]+sumb;
        for(int i=k+1;i<=n;i++){
            auto t=q.top();
            if(b[i]<t){
                sumb=sumb-t+b[i];
                q.pop();
                q.push(b[i]);
            }
            ans=min(ans,s[i]+sumb);
        }
        cout<<ans<<endl;
    }
}

T6 大大和2

题目大意

有一个长度为 nn 的数组 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 。

解题思路

我们考虑对于每一个位置 ii ，如果这个位置的数是区间最大值，首先找出所有满足这个数为最大值的区间，这部分我们可以用单调栈求出左边和右边第一个大于这个数的位置 LiL_i 和 RiR_i ，时间复杂度是 O(n)O(n) 线性的。

然后对于每一个位置 ii ，在区间 [Li,Ri][L_i,R_i] 中，如果最大的区间和比这个数还要小的话，那么这个位置就是满足条件的。在找最大区间和时，需要注意，由于位置 ii 一定需要在区间中，所以我们需要在 [i,Ri−1][i,R_i-1] 中找到最大前缀和 mxsmxs ，在 [Li,i−1][L_i,i-1] 中找到最小前缀和 mismis ，区间 [Li,Ri][L_i,R_i] 中的最大区间和就是 mxs−mismxs-mis 。

可以用 stst 表或者线段树快速查询区间最大最小前缀和。

时间复杂度 O(nlogn)O(nlogn) 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
const int N = 200010;

int lg[N];

void solve(){
    int n;cin>>n;
    vector<int>a(n+1);
    vector<int>l(n+1),r(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        l[i]=0;
        r[i]=n+1;
    }
    stack<PII>stk;
    for(int i=1;i<=n;i++){
        while(!stk.empty() && stk.top().second<a[i]){
            r[stk.top().first]=i;
            stk.pop();
        }
        stk.push({i,a[i]});
    }
    while(!stk.empty()) stk.pop();
    for(int i=n;i>=1;i--){
        while(!stk.empty() && stk.top().second<a[i]){
            l[stk.top().first]=i;
            stk.pop();
        }
        stk.push({i,a[i]});
    }

    vector<int>s(n+1);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];

    vector<vector<int>>mx(31,vector<int>(n+1)),mi(31,vector<int>(n+1));
    for(int i=0;i<=n;i++) mx[0][i]=mi[0][i]=s[i];
    for(int j=1;j<=30;j++){
        for(int i=0;i+(1ll<<(j-1))<=n;i++){
            mx[j][i]=max(mx[j-1][i],mx[j-1][i+(1ll<<(j-1))]);
            mi[j][i]=min(mi[j-1][i],mi[j-1][i+(1ll<<(j-1))]);
        }
    }

    auto querymx=[&](int l,int r)->int {
        int k=lg[r-l+1];
        return max(mx[k][l],mx[k][r-(1<<k)+1]);
    };
    auto querymi=[&](int l,int r)->int {
        int k=lg[r-l+1];
        return min(mi[k][l],mi[k][r-(1<<k)+1]);
    };
    
    for(int i=1;i<=n;i++){
        int MI=querymi(l[i],i-1);
        int MX=querymx(i,r[i]-1);
        if(MX-MI>a[i]){
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"YES"<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	for(int i=2;i<=N-10;i++) lg[i]=lg[i>>1]+1;
    
    int T=1;cin>>T;
    while(T--){
        solve();
    }
}
userId_undefined
去预览
0/2000

全部评论 7

  • userId_undefined

    zsy

    7月全勤卷王8月全勤卷王时空双修者题解仙人快乐小狗秩序白银

    为什么不写return 0呢

    昨天 来自 江苏

    1
    • userId_undefined

      Stars_Seeker

      回复zsy

      为什么要写呢？

      18小时前 来自 重庆

      0
    • userId_undefined

      zsy

      回复Stars_Seeker

      不应该写吗

      18小时前 来自 江苏

      0
    • userId_undefined

      Stars_Seeker

      回复zsy

      个人习惯问题，写不写都没事，我写代码从来没有写过return 0

      18小时前 来自 重庆

      0
  • userId_undefined

    114514

    荣耀黄金空间掌握者分支·分支解题者时空双修者I/O·IO入门者循环·循环打卡人

    活着，是最好的选择

    19小时前 来自 浙江

    0
  • userId_undefined

    隆江猪脚饭~

    时间刺客空间掌握者

    而且第一题………………

    昨天 来自 浙江

    0
  • userId_undefined

    隆江猪脚饭~

    时间刺客空间掌握者

    怎么感觉有点像ai

    昨天 来自 浙江

    0
  • userId_undefined

    longpipi

    为什么要q次询问为什么要q次询问为什么要q次询问为什么要q次询问为什么要q次询问

    2天前 来自 广东

    0
  • userId_undefined

    杰杰

    8月全勤卷王秩序白银出道萌新快乐小狗

    不用30，10就可以了

    2天前 来自 香港

    0
  • userId_undefined

    AC是最好的

    顾家豪老师，找你啦

    2天前 来自 福建

    0

热门讨论