非官方题解|挑战赛#22题解（结尾有彩蛋
2025-09-07 22:18:28
发布于：广东
防透视
题外话：我也不知道为什么，莫名其妙的最后一题就给我过了
庆祝我第一次进挑战赛前十！！！
上铂金了！！！！！！！！
@AC君 看看我的！
@dream_陆军展览（不加团队）@AAA混泥土批发ppl哥 大佬们给我提点建议
前言
整体评价
本次挑战赛的题目还是很有水平的@NoonMaple，大部分题目是从思维逻辑层面考察，小部分题目考察算法与数据结构，让许多新手有很大的发挥空间。
题目难度
本次挑战赛各题官方难度如下：
| 题目编号 | 题目名称 | 题目难度 |
|---|---|---|
| T1 | 大大和1 | 普及- |
| T2 | 午枫的博弈 | 普及- |
| T3 | 小午的请求 | 普及- |
| T4 | 小枫爬山 | 普及/提高- |
| T5 | 午枫的双人挑战 | 普及/提高- |
| T6 | 大大和2 | 普及+/提高 |
本题解若有错误，欢迎大家指出！
题解
T1：大大和1
考察内容：思维
个人难度：红
解析：
一道诈骗题/送分题，不要被题目的外表给迷惑了，仔细想想就会发现从这串数中任选一个数，就满足条件，所以所有情况都满足条件。
AC 代码：
#include<bits/stdc++.h>
using namespace std;
int t;
int main()
{
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
}
cout<<"YES"<<endl;
}
return 0;
}
T2：午枫的博弈
考察内容：思维
个人难度：红
解析：
观察发现可以覆盖位置更多的那个人有控制游戏输赢的权利，另外一个人的位置的数字最后一定会全部覆盖。
可以覆盖更多位置的那个人将尽力保留让自己获胜的数字，只要有一个，就能留下来，让自己获胜。
代码就很容易写了。
AC 代码：
#include<bits/stdc++.h>
using namespace std;
int n,a[1000005];
int main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
if(n%2==0)
{
bool flag=0;
for(int i=2;i<=n;i+=2) if(a[i]%2==0) flag=1;
if(flag==1) cout<<"Maple"<<endl;
else cout<<"Noon"<<endl;
}
else
{
bool flag=0;
for(int i=1;i<=n;i+=2) if(a[i]%2==1) flag=1;
if(flag==1) cout<<"Noon"<<endl;
else cout<<"Maple"<<endl;
}
return 0;
}
T3：小午的请求
考察内容：思维
个人难度：红
解析：
要让选出的数字加起来是偶数，必须先选上所有偶数（不改变奇偶性，还是偶数），然后选出最多个奇数（数量为偶数个），也就是说最多只会剩下一个数
那我们反过来看，就是先把所有数选了，如果是偶数，满足条件直接输出；如果是奇数，减去最小的一个奇数。
记得开 long long
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005],sum;
signed main()
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
sort(a+1,a+n+1);
if(sum%2==0) cout<<sum<<endl;
else
{
for(int i=1;i<=n;i++)
{
if(a[i]%2==1)
{
sum-=a[i];
break;
}
}
cout<<sum<<endl;
}
return 0;
}
T4：小枫爬山
考察内容：前缀和、二分
个人难度：橙
解析：
思路应该比较清晰，主要在于优化。
可以先把每两级台阶的高度差算出来，再用前缀和思想求出到达某级台阶最长所需的脚长。
接着直接使用二分求出最大能到达第几级台阶。
注意要特判连第一级台阶都跨不上的情况，否则只有 30 分。
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[500005],b[500005],h[500005],maxn[500005];
signed main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=n;i++) h[i-1]=a[i]-a[i-1];
maxn[1]=h[1];
for(int i=2;i<=n-1;i++) maxn[i]=max(maxn[i-1],h[i]);
for(int i=1;i<=m;i++)
{
cin>>b[i];
if(b[i]<a[1])
{
cout<<0<<" ";
continue;
}
int ans=upper_bound(maxn+1,maxn+n,b[i])-maxn;
cout<<a[ans]<<" ";
}
return 0;
}
T5：午枫的双人挑战
考察内容：前缀和、优先队列
个人难度：黄
解析：
如果你还不知道什么是优先队列，请先自行学习，在这里就先不讲了。
很明显，题目的意思就是说先做完前 个解密任务，再从前 个战斗任务中选择最小的 个完成。
思路显然是先考虑要完成到第几个解密任务：这一部分很简单，直接使用前缀和预处理完成到第 个解密任务的时间；
接着再考虑选出这 个解密任务中最小的 个，可以用优先队列辅助，不用每次都排序。
代码不是很难写，注意 long long 细节！！
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[200005],b[200005];
int sum[200005];
signed main()
{
cin>>n>>q;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++) cin>>b[i];
while(q--)
{
int k,summ=0,ans=1e18;
priority_queue<int>q;
cin>>k;
for(int i=1;i<=n;i++)
{
if(q.size()<k)
{
summ+=b[i];
q.push(b[i]);
}
else if(q.top()>b[i])
{
summ=summ-q.top()+b[i];
q.pop();
q.push(b[i]);
}
if(i>=k) ans=min(ans,summ+sum[i]);
}
cout<<ans<<endl;
}
return 0;
}
T6：大大和2
考察内容：思维、枚举？
个人难度：橙？
声明：本题目题解仅为个人理解，不一定完全正确完全错误，如想了解准确无误的方法/解析，请看官方题解
解析：
题目反过来就是让我们找有没有最大值小于和的情况。
自己手搓几个样例，发现出问题的点都在长度比较小的时候，大胆猜测有可能就是这样的。
直接枚举到长度为 100 时，发现直接过了？？人都傻了。
还是给大家放上代码。
AC 代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,a[500005];
signed main()
{
cin>>t;
while(t--)
{
bool flag=0;
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=2;i<=min((long long)100,n);i++)
{
for(int j=1;j<=n-i+1;j++)
{
int maxn=-1e10,sum=0;
for(int k=j;k<=j+i-1;k++)
{
maxn=max(maxn,a[k]);
sum+=a[k];
}
if(maxn<sum)
{
flag=1;
break;
}
}
}
if(flag==1) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
彩蛋
你们最喜欢的彩蛋环节到了！
有帮助，赞一个