AtCoder-ABC 450直播真题解析预告

四季读书网 2026-03-19 09:09:50 3 0

8点击上面微信号关注我关注我哟定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！有任何问题请联系小编！

清北名师坐镇！AtCoder Beginner Contest 450题解直播重磅来袭！

各位OIer们注意啦！本周日（3月22日）晚19:00，清北学堂OI金牌教研团的清华吴老师将空降B站，为大家带来AtCoder Beginner Contest 450的全程题解直播！

【名师加持，实力护航】
本次直播的主讲人吴老师，是清北学堂OI金牌教研团的核心成员，毕业于清华大学，更是斩获过NOI2021银牌的大神级选手。他不仅有着扎实的竞赛理论基础，更具备丰富的实战经验，擅长将复杂的算法问题拆解为通俗易懂的解题思路，帮助无数OIer在竞赛中突破瓶颈，斩获佳绩。
【聚焦AtCoder，直击竞赛核心】
AtCoder作为全球知名的编程竞赛平台，其题目风格灵活多变，涵盖算法、数据结构等多个核心考点，是检验选手编程能力和思维逻辑的绝佳舞台。本次直播中，吴老师将针对AtCoder Beginner Contest 450的所有题目进行逐题精讲：
思路拆解：从题目分析入手，带领大家梳理解题思路，挖掘题目背后隐藏的算法模型；
代码实现：现场编写代码，演示如何将思路转化为高效、简洁的可运行程序；
技巧点拨：分享竞赛中的实用技巧和避坑指南，帮助大家在有限时间内快速提升解题效率。

直播间地址（复制下方链接或直接扫描二维码，PC端建议使用chrome浏览器点击“阅读原文”也可查看）：

https://live.bilibili.com/21371611?live_from=84002

如不能显示请在哔站搜索栏查找“清北学堂信息学”账号（录播也发布在此）

欢迎加入ABC交流QQ群咨询、沟通、交流（群密码：AtCoder）

ABC449比赛真题讲解

题目列表：

题目地址：https://atcoder.jp/contests/abc448/tasks

题目讲解：识别下方二维码或点击文末“阅读原文”可查看视频直播解析题解)

ABC449题解及参考程序（文字版）

参考程序

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;intmain(){  int d;  scanf("%d",&d);  printf("%.9lf\n",acos(-1)*d*d/4);  return0;}

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;int h,w,q;intmain(){  ios::sync_with_stdio(0);  cin>>h>>w>>q;  while(q--) {    int op,x;    cin>>op>>x;    if(op==1) {      cout<<x*w<<endl;      h-=x;    } else {      cout<<x*h<<endl;      w-=x;    }  }  return0;}

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=5e5+5;int n,L,R;char s[N];int sum[N];intmain(){  scanf("%d%d%d%s",&n,&L,&R,s+1);  ll ans=0;  for(int c=0;c<26;++c) {    for(int i=1;i<=n;++i) {      sum[i]=sum[i-1]+(s[i]=='a'+c);      if(s[i]=='a'+c && i>L) {        if(i>R) ans+=sum[i-L]-sum[i-R-1];        else ans+=sum[i-L];      }    }  }  printf("%lld\n",ans);  return0;}

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;int L,R,D,U;ll work1(int l,int r,int x){  if(l>r||x%2==1) return0;  return (r-l+1);}ll work2(int l,int r){  if(r%2) --r;  if(l%2) ++l;  if(l>r) return0;  return (r-l)/2+1;}intmain(){  cin>>L>>R>>D>>U;  ll ans=0;  for(int x=L;x<=R;++x) {    int dx=abs(x);    ans+=work2(D,min(U,-dx-1)) //[D,U] and (-inf,-dx-1]      +work1(max(D,-dx),min(U,dx),dx) //[D,U] and [-dx,dx]      +work2(max(D,dx+1),U); //[D,U] and [dx+1,inf)  }  cout<<ans<<endl;  return0;}

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=5e5+5,M=N;int n,m,q,a[N],cnt[M],ans[N];vector<int> val[N];ll lim[N];structQuery {  ll x; int id;} t[N];int seg[M<<2];#define lc (k<<1)#define rc (lc|1)#define left lc,l,mid#define right rc,mid+1,rvoidchange(int k,int l,int r,int x){  seg[k]+=1;  if(l==r) return;  int mid=l+r>>1;  if(x<=mid) change(left,x);  else change(right,x);}intquery(int k,int l,int r,int kth){  if(l==r) return l;  int mid=l+r>>1;  if(kth<=seg[lc]) return query(left,kth);  return query(right,kth-seg[lc]);}intmain(){  ios::sync_with_stdio(0);  cin>>n>>m;  for(int i=1;i<=n;++i) {    cin>>a[i];    cnt[a[i]]++;  }  for(int i=1;i<=m;++i)    val[cnt[i]].push_back(i);  int tmp=m;  for(int i=1;i<=n;++i) {    tmp-=val[i-1].size();    lim[i]=lim[i-1]+(m-tmp);  }  cin>>q;  for(int i=1;i<=q;++i) {    cin>>t[i].x;    t[i].id=i;  }  sort(t+1,t+q+1,[](const Query &i,const Query &j) {    return i.x<j.x;  });  int pt=0;  for(auto v:val[0])    change(1,1,m,v);  for(int i=1;i<=q;++i) {    ll x=t[i].x;    if(x<=n) {      ans[t[i].id]=a[x];      continue;    }    x-=n;    while(pt<n&&x>lim[pt+1]) {      ++pt;      for(auto v:val[pt])        change(1,1,m,v);    }    x-=lim[pt];    if(pt==n) {      ans[t[i].id]=(x-1)%m+1;    } else {      ans[t[i].id]=query(1,1,m,x);    }  }  for(int i=1;i<=q;++i)    cout<<ans[i]<<endl;  return0;}

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=2e5+5;int H,W,h,w,n,rt;structLine {  int x,l,r,v;};vector<Line> lines;structNode {  int sum,tag,lc,rc;} t[N*30*2];int tot;voidpushup(int k,int l,int r){  if(t[k].tag) t[k].sum=r-l+1;  else t[k].sum=t[t[k].lc].sum+t[t[k].rc].sum;}voidchange(int &k,int l,int r,int x,int y,int v){  if(!k) k=++tot;  if(x<=l&&r<=y) {    t[k].tag+=v;    pushup(k,l,r);    return;  }  int mid=l+r>>1;  if(x<=mid) change(t[k].lc,l,mid,x,y,v);  if(y>mid) change(t[k].rc,mid+1,r,x,y,v);  pushup(k,l,r);}intmain(){  ios::sync_with_stdio(0);  cin>>H>>W>>h>>w>>n;  for(int i=1;i<=n;++i) {    int x,y;    cin>>x>>y;    lines.push_back(Line{max(1,x-h+1),max(1,y-w+1),min(y,W-w+1),1});    lines.push_back(Line{x+1,max(1,y-w+1),min(y,W-w+1),-1});  }  sort(lines.begin(),lines.end(),[](const Line &a,const Line &b) {    return a.x<b.x;  });  int lstx=1; ll ans=1ll*(H-h+1)*(W-w+1);  for(auto x:lines) {    if(x.x>H-h+1) {      ans-=1ll*t[rt].sum*((H-h+1)-lstx+1);      break;    }    ans-=1ll*t[rt].sum*(x.x-lstx);    change(rt,1,W-w+1,x.l,x.r,x.v);    lstx=x.x;  }  cout<<ans<<endl;  return0;}

#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=1e5+5,MOD=998244353;int n,m;ll F[N];ll qpow(ll a,int x){  ll z=1;  for(;x;x>>=1,a=a*a%MOD) if(x&1) z=z*a%MOD;  return z;}ll f(ll x){  ll ret=0;  for(int i=1;i<=m-1;++i) {    ret+=x%10;    x/=10;    if(x==0) break;  }  return ret+x;}intmain(){  cin>>n>>m;  ll C=1;  for(int i=0;i<=n/10;++i) {    F[i*10]=C*(i&1?-1:1); //C(m-1,i)    C=C*(m-1-i)%MOD*qpow(i+1,MOD-2)%MOD;  }  for(int i=9;i<=n;++i)    (F[i]+=F[i-9])%=MOD;  ll ans=0;  C=1;  for(int i=0;i<=n;++i) {    (ans+=C*F[n-i])%=MOD; //C(i+m-1,i)    C=C*(i+m)%MOD*qpow(i+1,MOD-2)%MOD;  }  for(int i=0;i<n;++i)    if((n-f(i))%9==0) --ans;  ans%=MOD;  cout<<(ans+MOD)%MOD<<endl;  return0;}