ACGO挑战赛#23全题解（1.4版本）
2025-10-19 12:51:17
发布于：江苏
前言
那么首先感谢@egogaming提出的宝贵意见，现对题解内部分繁杂的、多余的、累赘的公式改为更详细的解释。
作者第三篇挑战赛题解（awa）
个人难度：
| 题目 | 难度 | 知识点 |
|---|---|---|
| T1：NOON | 字符串基础 | |
| T2：maple序列 | 双指针 | |
| T3：午枫的石子合并 | 贪心 | |
| T4：午枫的彩排2 | 枚举 | |
| T5：午枫勇闯移动迷宫 | 广搜，优先队列 | |
| T6：午枫的创造 | 模拟 |
T1：NOON
这道题只需一一比较并计数即可，时间复杂度
#include<bits/stdc++.h>
using namespace std;
int num;
string s;
int main(){
cin>>s;
for(int i=0;i<s.size()-3;i++){
if(s[i]=='N'&&s[i+1]=='O'&&s[i+2]=='O'&&s[i+3]=='N'){
num++;
}
}
cout<<num;
}
T2：maple序列
这道题目明显不能直接去求，但是我们注意到，那么我们可以运用桶标记的思想，去统计在数组中出现了多少次并用一个数组统计。
接着，我们得知要求出最长的数组使得
又因为，所以。只需找到使最长的即可。
时间复杂度为
#include<bits/stdc++.h>
using namespace std;
long long n,a[200005],c[10005],num,maxn;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
c[a[i]]++;
}
for(int i=2;i<=10000;i++){
num=0;
for(int j=1;j<=i/2;j++){
if(j*2!=i)num+=min(c[j],c[i-j]);
else num+=c[j]/2;
}
maxn=max(maxn,num*2);
}
cout<<maxn;
}
T3 午枫的石子合并
这道题可以使用双端队列来做，首先需创建一个双端队列来存储堆石子的数量，然后重复比较前后端并合并较小者，直到只剩下最后一堆，时间复杂度
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[200005],num,b,c;
deque<long long>q;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
q.push_back(a[i]);
}
while(q.size()>1){
b=c=0;
if(q.front()<=q.back()){
b=q.front(); q.pop_front();
c=q.front(); q.pop_front();
q.push_front(b+c);
num+=(b+k-1)/k;
}else{
b=q.back();q.pop_back();
c=q.back();q.pop_back();
q.push_back(b+c);
num+=(b+k-1)/k;
}
}
cout<<num;
}
T4 午枫的彩排2
这道题需要定义一个结构体数组，分别来记录调亮和调暗多少次能变成，接着将数组排序（调亮次数小的排在前面）。
但是此时有一个问题，如果，则向左向右都为0，这样会影响结果，所以需要去除已经调整好的灯光。
接着再依次选择把调亮次数前小的调亮，剩余的调暗，这样需要调的次数就不会多余，调的次数就是第项的调亮次数与第项的调暗次数的和。
时间复杂度。
#include<bits/stdc++.h>
using namespace std;
long long t,n,m,a[200005],b[200005],cnt,minn;
struct d{
long long l,r;
}c[200005];
bool cmp(d x,d y){
return x.l<y.l;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
c[n+1].l=c[n+1].r=0,cnt=0,minn=0x3f3f3f3f;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
cin>>b[i];
if(a[i]!=b[i]){
c[++cnt].l=(a[i]+m-b[i])%m;
c[cnt].r=(b[i]+m-a[i])%m;
}
}
sort(c+1,c+cnt+1,cmp);
if(!cnt)minn=0;
for(int i=0;i<=cnt;i++){
minn=min(minn,c[i].l+c[i+1].r);
}
cout<<minn<<endl;
}
}
T5 午枫勇闯移动迷宫
这道题其实是在变向地求需修改几次才能到达出口，而修改次数也很好理解，就是不按照当前格子的颜色方向走，又因为要求最短路径，所以只需将广搜的队列改为优先队列即可。注意，这道题目的和的范围均为所以不能使用普通的二维数组来存储，可以将二维压缩成一维，可以将输入的若干个字符和迷宫的标记数组都用一维数组表示，而当前所在的格子因为可以存储到优先队列中，所以没有约束，可以用二维来表示。时间复杂度为（能过就对了）。
#include<bits/stdc++.h>
using namespace std;
long long t,n,m,k,b[128],dx[4]={0,1,0,-1},dy[4]={1,0,-1,0},vis[2000005],vv;
char c[2000005];
struct kk{
long long x,y,v;
bool operator<(const kk& g)const{
return v<g.v;
}
};
priority_queue<kk>pq;
int main(){
cin>>t;
b['G']=0,b['B']=1,b['Y']=2,b['O']=3;
while(t--){
cin>>n>>m>>k;
for(int i=1;i<=n*m;i++){
cin>>c[i];
vis[i]=0;
}
pq.push({1,1,k});
vv=0;
while(pq.size()){
kk f=pq.top();
pq.pop();
if(vis[(f.x-1)*m+f.y])continue;
vis[(f.x-1)*m+f.y]=1;
if(f.x==n&&f.y==m){
cout<<"YES\n";
vv=1;
break;
}
for(int i=0;i<4;i++){
int nx=f.x+dx[i],ny=f.y+dy[i];
if(nx<1||ny<1||nx>n||ny>m||vis[(nx-1)*m+ny])continue;
if(b[c[(f.x-1)*m+f.y]]==i){
pq.push({nx,ny,f.v});
}else if(f.v){
pq.push({nx,ny,f.v-1});
}
}
}
while(pq.size())pq.pop();
if(vv!=1)cout<<"NO\n";
}
}
T6 午枫的创造
因为只会有一串字符串与原字符串集不同。再动一动脑筋就会发现，如果想要更改字符串，那么只有前后字符串都拥有的字符能够使用，假如可用字符的数量为，那么我们可以做个表格来观察可用情况。
| x | 字符串1 | 字符串2 | 情况1 | 情况2 |
|---|---|---|---|---|
| 1:a | abc | def | 1种 | 1种 |
| 2:ab | ace | bdf | 3种 | 3种 |
| 3:abc | acgo | a | 7种 | 7种 |
| 4:wxyz | abcdefg | hijkxyz | 15种 | 15种 |
那么不难发现，假如可用字符的数量为，可用情况就为
时间复杂度
#include<bits/stdc++.h>
using namespace std;
long long t,n,m,vis[200005],num,a[30]={1};
string s;
int f(int x){
int ans=0;
while(x){
ans+=x%2;
x/=2;
}
return ans;
}
int main(){
cin>>t;
for(int i=1;i<=26;i++){
a[i]=a[i-1]*2;
}
while(t--){
cin>>n>>m;
num=0;
vis[0]=vis[n+1]=a[m]-1;
for(int i=1;i<=n;i++){
cin>>s;
vis[i]=0;
for(char c:s)vis[i]+=a[c-'a'];
}
for(int i=1;i<=n;i++){
int k=(vis[i-1]&vis[i+1]);
num+=a[f(k)]-1;
}
cout<<num<<endl;
}
}
@AC君给个置顶吧。[：求]
有帮助，赞一个