ACGO挑战赛#24 题解
2025-11-03 19:27:36
发布于:江苏
前言
作者第四篇挑战赛题解,代表着作者已经AK挑战赛了四次。
因为作者期中考试在即,所以先发布一篇简易版题解,约15天后更新
个人难度:
| 题目 | 难度 | 知识点 |
|---|---|---|
| T1:午枫喝水 | 模拟 | |
| T2:午枫的排队 | - | |
| T3:午枫坐公交 | 贪心 | |
| T4:午枫的双向奔赴2 | 广搜 | |
| T5:午枫的填数游戏 | 模拟 | |
| T6:午枫的字符串反转 | 树状数组 |
T1
#include<bits/stdc++.h>
using namespace std;
int k,a,b,na,nb,c;
int main(){
cin>>k>>a>>b;
na=a,nb=b;
while(k--){
if(na==a)na=0;
else if(nb==0)nb=b;
else{
c=min(a-na,nb);
na+=c;
nb-=c;
}
}
cout<<na<<" "<<nb;
}
T2
#include<bits/stdc++.h>
using namespace std;
int n,a[300005],x,b;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
if(x!=-1)a[x]=i;
else b=i;
}
cout<<b<<" ";
while(a[b]){
cout<<a[b]<<" ";
b=a[b];
}
}
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";
}
}
}
全部评论 1
ddd
6小时前 来自 江苏
0作者再次声明:此版本只提供代码,并不是最终版
6小时前 来自 江苏
0










有帮助,赞一个