官方题解 | 挑战赛22题解
2025-09-08 11:31:40
发布于：浙江
本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
| 题目编号 | 题目标题 | 难度 |
|---|---|---|
| T1 | 大大和1 | 入门 |
| T2 | 午枫的博弈 | 普及- |
| T3 | 小午的请求 | 普及- |
| T4 | 小枫爬山 | 普及/提高- |
| T5 | 午枫的双人挑战 | 普及/提高- |
| T6 | 大大和2 | 普及+/提高 |
T1 大大和1
题目大意
有一个长度为 的数组 ，判断是否存在一个区间 满足 。
解题思路
当 时，一定满足 。所以答案一定是 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 午枫的博弈
题目大意
有 个数，小午只能隐藏奇数位置的数，小枫只能隐藏偶数位置的数，两人轮流行动，小午先手，若最后剩下一个数时结束，剩下的数如果是奇数，小午获胜，否则小枫获胜。求最终谁一定会赢。
解题思路
因为每个人可以选择隐藏的数和对方没有交集，所以在隐藏数时，小午会优先选择隐藏偶数，小枫会优先先择隐藏奇数。
当 为奇数时，判断奇数位置是否有奇数，有则输出 Noon ，否则输出 Maple ； 为偶数时，判断偶数位置是否有偶数，有则输出 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 小午的请求
题目大意
有 个数字，从中选出一些数，使得选出的数之和为偶数且最大，求这些数字之和。
解题思路
考虑要选出和最大的数，因为没有负数，所以我们可以直接把所有数都选了，如果和为偶数，那这就是最大的数字和了；否则说明其中至少有一个奇数，把最小奇数剔除就可以得到最大的数字和。
参考代码
#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 小枫爬山
题目大意
有 级台阶， 位爬山者，每位爬山者腿长 ，如果下一级台阶与爬山者所在台阶的高度差大于爬山者的腿长，就无法继续往上爬了。求每位爬山者能爬到的最大高度。
解题思路
对于每一次询问，我们可以对每级台阶的高度差进行二分查找，找到第一个大于 的台阶，这级台阶的前一级就是最终到达的位置。但是二分需要有单调性，我们可以用 记录前 个位置最大的高度差，对 二分即可。
对于每一个台阶实际的高度，我们可以用前缀和快速求出。
参考代码
#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 午枫的双人挑战
题目大意
一共有 个关卡，每个关卡分为解密和战斗两部分，挑战关卡有两个限制：
-
对于不同关卡，只有完成了前一关的解密部分才能进行下一关的解密部分；
-
对于同一关卡，只有完成了这一关卡的解密部分才能进行这一关的战斗部分。
第 关的解密部分需要耗时 ，战斗部分需要耗时 ，完成了一关的揭秘和战斗部分才视为完成这一关。对于 个询问，求完成 个关卡的最短用时。
解题思路
首先考虑完成 个关卡，我们需要至少完成前 个解密部分 ，完成 之前我们需要至少完成前 个解密部分。
接下来我们需要考虑的是选择完成哪几个关卡所花的时间最少。由于询问次数只有 ，所以对于每一个询问可以尝试使用 甚至 的复杂度去完成。由于完成解密部分一定是连续的，所以我们可以先用前缀和 求出前 个解密部分所花时间是多少。
我们可以枚举最后一个被完成的关卡的哪个，此时的时间花费是 ，其余的 个战斗部分选择 最小的 个，但是这样的做法时间复杂度会来到 ，显然是不合理的。其实我们可以通过优先队列优化选 的过程，我们先选出前 关卡完成，将 都存入优先队列中，往后枚举时，设当前枚举的位置为 ，如果 小于优先队列中最大的元素，则可以把 与优先队列中最大元素替换。每次算出所需要的时间，更新答案。这样查询的时间复杂度为 。
总时间复杂度为 。
参考代码
#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
题目大意
有一个长度为 的数组 ，判断是否所有区间 满足 。
解题思路
我们考虑对于每一个位置 ，如果这个位置的数是区间最大值，首先找出所有满足这个数为最大值的区间，这部分我们可以用单调栈求出左边和右边第一个大于这个数的位置 和 ，时间复杂度是 线性的。
然后对于每一个位置 ，在区间 中，如果最大的区间和比这个数还要小的话，那么这个位置就是满足条件的。在找最大区间和时，需要注意，由于位置 一定需要在区间中，所以我们需要在 中找到最大前缀和 ，在 中找到最小前缀和 ，区间 中的最大区间和就是 。
可以用 表或者线段树快速查询区间最大最小前缀和。
时间复杂度 。
参考代码
#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();
}
}
全部评论 8
第一题测试点有点水
#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; while(n--){ cout << "YES" << endl; } return 0; }2025-09-13 来自 北京
0
有帮助，赞一个