ACGO挑战赛#24 题解

CuSn

2025-11-13 20:06:09

发布于：江苏

32阅读

0回复

0点赞

前言

因为作者期中考试在即，所以先发布一篇简易版题解，约15天后更新
$\color{white}_{隐形防窥线---隐形防窥线---隐形防窥线---隐形防窥线---隐形防窥线---隐形防窥线---隐形防窥线---隐形防窥线---隐形防窥线}$
11.13 ：考完了，回来更新了

个人难度：

题目	难度	知识点
T1：午枫喝水	$\color{red}红$	模拟
T2：午枫的排队	$\color{red}红$	-
T3：午枫坐公交	$\color{orange}橙$	贪心
T4：午枫的双向奔赴2	$\color{gold}黄$	广搜
T5：午枫的填数游戏	$\color{gold}黄$	模拟
T6：午枫的字符串反转	$\color{gold}黄$	树状数组

T1 午枫喝水

可以看到操作次数 $~k~$ 并不是太多，所以根据题意中模拟即可。

#include<bits/stdc++.h>
using namespace std;
int k,a,b,nowa,nowb;
int main(){
    cin>>k>>a>>b;
    nowa=a,nowb=b;
    while(k--){
        if(nowa==a)nowa=0;
        else if(nowb==0)nowb=b;
        else{
            int minn=min(a-nowa,nowb);
            nowa+=minn;
            nowb-=minn;
        }
    }
    cout<<nowa<<" "<<nowb;
}

时间复杂度 $~O(k)$

T2

此题用元素 $~a_i~$ 来表示第 $~i~$ 个人前面的人的编号，那不妨再设置一个数组 $~b~$ ，用 $~b_i~$ 来表示第 $~i~$ 个人后面的人的编号，再找到队首的人，紧接着依次往后找就行了。

#include<bits/stdc++.h>
using namespace std;
int n,a[300005],b[300005],f;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=-1)b[a[i]]=i;
        else f=i;
    }
    cout<<f<<" ";
    while(b[f]){
        cout<<b[f]<<" ";
        f=b[f];
    }
}

时间复杂度 $~O(n)$

T3

#include<bits/stdc++.h>
using namespace std;
long long n,a[200005];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
        if(a[i]<0)a[i]=0;
    }
    cout<<a[n];
}

T4

#include<bits/stdc++.h>
using namespace std;
int n,vis[65][65][65][65],a1,a2,a3,a4,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
char a[65][65];
struct k{
    int ax,ay,bx,by,k;
};
queue<k>q;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
            if(a[i][j]=='P'){
                if(!a1)a1=i,a2=j;
                else a3=i,a4=j;
            }
        }
    }
    q.push({a1,a2,a3,a4,0});
    vis[a1][a2][a3][a4]=1;
    while(q.size()){
        k f=q.front();
        q.pop();
        if(f.ax==f.bx&&f.ay==f.by){
            cout<<f.k;
            return 0;
        }
        for(int i=0;i<4;i++){
            int nax=f.ax+dx[i],nay=f.ay+dy[i];
            int nbx=f.bx+dx[i],nby=f.by+dy[i];
            if(a[nax][nay]=='#'||nax<1||nay<1||nax>n||nay>n)nax=f.ax,nay=f.ay;
            if(a[nbx][nby]=='#'||nbx<1||nby<1||nbx>n||nby>n)nbx=f.bx,nby=f.by;
            if(!vis[nax][nay][nbx][nby]){
                vis[nax][nay][nbx][nby]=1;
                q.push({nax,nay,nbx,nby,f.k+1});
            }
        }
    }
    cout<<-1;
}

T5

#include<bits/stdc++.h>
using namespace std;
long long n,q,p[5005],v[5005],l[5005],r[5005],mod=998244353,maxn,num=1;
vector<long long>a[5005];
int main(){
    cin>>n>>q;
    for(int i=1;i<=q;i++){
        l[i]=r[i]=1;
        cin>>p[i]>>v[i];
        maxn=0;
        for(long long i:a[p[i]])maxn=max(maxn,v[i]);
        for(int k=1;k<p[i];k++){
            for(int j:a[k])if(v[j]>v[i]){
                r[i]=0;
                l[j]=0;
            }
        }
        for(int k=p[i]+1;k<=n;k++){
            for(int j:a[k])if(v[j]>v[i]){
                l[i]=0;
                r[j]=0;
            }
        }
        if(maxn>v[i])num=0;
        a[p[i]].push_back(i);
    }
    for(int i=1;i<=q;i++){
        num*=(r[i]+l[i]);
        num%=mod;
    }
    cout<<num;
}

T6

#include<bits/stdc++.h>
using namespace std;
int n,q,v[500005],f[500005],x,y,z;
char c;
int lb(int x){
    return x&-x;
}
void add(int k,int x){
    while(k<=n){
        f[k]+=x;
        k+=lb(k);
    }
}
long long qu(int k){
    int ans=0;
    while(k){
        ans+=f[k];
        k-=lb(k);
    }
    return ans;
}
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>c;
		v[i]=c-'0';
        if(v[i]==v[i-1]&&i>1)add(i,1);
	}
	for(int i=1;i<=q;i++){
		cin>>x>>y>>z;
		if(x==1){
			if(qu(y)-qu(y-1))add(y,-1);
            else add(y,1);
            if(z<n&&qu(z+1)-qu(z))add(z+1,-1);
            else add(z+1,1);
		}else{
			if(qu(y)==qu(z))cout<<"Yes\n";
			else cout<<"No\n";
		}
	}
}