ACGO挑战赛#24 题解
2025-11-13 20:06:09
发布于：江苏
15阅读
0回复
0点赞
前言
因为作者期中考试在即，所以先发布一篇简易版题解，约15天后更新
11.13 ：考完了，回来更新了
个人难度：
| 题目 | 难度 | 知识点 |
|---|---|---|
| T1：午枫喝水 | 模拟 | |
| T2：午枫的排队 | - | |
| T3：午枫坐公交 | 贪心 | |
| T4：午枫的双向奔赴2 | 广搜 | |
| T5：午枫的填数游戏 | 模拟 | |
| T6：午枫的字符串反转 | 树状数组 |
T1 午枫喝水
可以看到操作次数并不是太多，所以根据题意中模拟即可。
#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;
}
时间复杂度
T2
此题用元素来表示第个人前面的人的编号，那不妨再设置一个数组，用来表示第个人后面的人的编号，再找到队首的人，紧接着依次往后找就行了。
#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];
}
}
时间复杂度
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";
}
}
}
这里空空如也
有帮助，赞一个