ACGO挑战赛#22 题解
2025-09-08 11:52:45
发布于：江苏
20阅读
0回复
0点赞
前言
这是一篇挑战赛题解，看在作者这么辛苦的份上，给个赞不介意吧（T o T）。
个人认为的难度是这样的：
| 题目 | 难度 |
|---|---|
| T1 | |
| T2 | |
| T3 | |
| T4 | |
| T5 | |
| T6 |
T1 大大和1
个人难度：入门|考察内容：输出
这道题就是一道只需动动脑，无需任何算法的题。这道题乍一看很复杂，但只要仔细看就会发现：
我们又得知。但是对于任意。
所以只需输出个YES就行了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
int t;
int main(){
cin>>t;
while(t--)cout<<"YES\n";
}
T2 午枫的博弈
个人难度：入门|考察内容：贪心
“当最后只剩下一个数没被隐藏时，游戏结束。”
所以这道题需要考虑最后一个数在谁的手里，当是奇数时，拿奇数的小午有选择权，反之则是拿偶数的小枫有选择权。
接下来考虑获胜条件，如果小午有选择权并且奇数位置中有偶数或小枫有选择权但偶数位置没有奇数，小午胜，否则小枫胜。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long n,x,y,z;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>z;
if(i%2&&z%2==0)x=1;
else if(z%2==1)y=1;
}
if(n%2&&x||n%2==0&&!y)cout<<"Noon";
else cout<<"Maple";
}
T3 小午的请求
个人难度：入门|考察内容：贪心
如果所有数之和是奇数，减去最小的奇数输出就行。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long n,a,minn=0x3f3f3f3f,num;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
if(a%2)minn=min(minn,a);
num+=a;
}
if(num%2)num-=minn;
cout<<num;
}
T4 小枫爬山
个人难度：普及-|考察内容：二分查找
我们可以先用一个数组来存放每个台阶的高度，再用一个数组来存放到当前台阶的爬升的最高高度。
数组的存储方式是这样的：，这样就可以保证数组是一个非降序的数组。
接下来将输入个人的腿长，设数组中第一个大于第个人腿长的下标为，那么即为答案。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long n,m,h[500005],A[500005],x;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>h[i];
A[i]=max(h[i]-h[i-1],A[i-1]);
}
while(m--){
cin>>x;
cout<<h[upper_bound(A+1,A+n+1,x)-A-1]<<" ";
}
}
T5 午枫的双人挑战
个人难度：普及/提高-|考察内容：贪心
初始化：这道题需要先用数组存放输入数据，紧接着再用数组分别存放其前缀和。
对于每一个样例，我们用一个变量存储最小值和一个变量存储到当前位置时战斗部分的最小用时，其中当位置为时，，其次，我们肯定要至少做到第个关卡的解密，所以初始值为，初始值为。
对于如何处理,只需使用一个优先队列即可，当走到第个位置时，将存入优先队列并将，接着再将减去队首并删除队首。
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long n,q,k,a[200005],b[200005],c[200005],d[200005],,minn;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
c[i]=c[i-1]+a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
d[i]=d[i-1]+b[i];
}
while(q--){
cin>>k;
long long now=0;
priority_queue<int>pq;
for(int i=1;i<=k;i++){
pq.push(b[i]);
now+=b[i];
}
minn=now;
minn+=c[k];
for(int i=k+1;i<=n;i++){
pq.push(b[i]);
now+=b[i]-pq.top();
pq.pop();
minn=min(minn,now+c[i]);
}
cout<<minn<<endl;
}
}
T6 大大和2
个人难度：普及+/提高|考察内容：---
下面这个是马上要被hank的做法
代码如下：
#include<bits/stdc++.h>
using namespace std;
long long t,n,a[500005],b[500005],c[500005],d[500005],v,num;
int main(){
cin>>t;
while(t--){
cin>>n;
if(n>40000){//样例大但粗略
v=num=0;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>0){
if(num>0)v=1;
else num=0;
}
num=max(a[i],num+a[i]);
}
}else{//样例小但情况多
v=0;
for(int i=1;i<=n;i++){
b[i]=c[i]=0;
cin>>a[i];
d[i]=d[i-1]+a[i];
}
stack<int>s,t;
for(int i=n;i>=1;i--){
while(s.size()&&a[s.top()]<a[i]){
b[s.top()]=i;
s.pop();
}
s.push(i);
while(t.size()&&a[t.top()]<a[n-i+1]){
c[t.top()]=n-i+1;
t.pop();
}
t.push(n-i+1);
}
for(int i=1;i<=n;i++)if(!c[i])c[i]=n+1;
for(int i=1;i<=n;i++){
for(int j=b[i]+1;j<i;j++)if(d[i-1]-d[j-1]>0)v=1;
for(int j=i+1;j<c[i];j++)if(d[j]-d[i]>0)v=1;
if(v)break;
}
}
if(v)cout<<"NO\n";
else cout<<"YES\n";
}
}
有帮助，赞一个