AtCoder Beginner Contest 456真题解析预告
讲解赛事：AtCoder Beginner Contest 456 讲解嘉宾：清北学堂 OI 金牌教研团 吴老师（清华大学 NOI银牌） 直播时间：本周日（5 月 3 日）晚上 19:00 直播内容：完整赛题逐题解析、思路推导、代码实现、易错点总结
直播间地址（复制下方链接或直接扫描二维码，PC端建议使用chrome浏览器点击“阅读原文”也可查看）：
https://live.bilibili.com/21371611?live_from=84002
如不能显示请在哔站搜索栏查找“清北学堂信息学”账号（录播也发布在此）
PC 端建议使用Chrome 浏览器，观看更稳定、体验更佳。
本次直播聚焦AtCoder ABC命题特点，用竞赛金牌视角拆解题目，帮你建立规范解题流程，提升算法思维与实战得分能力。
欢迎加入ABC交流QQ群咨询、沟通、交流（群密码：AtCoder）
题目讲解：识别下方二维码或点击文末“阅读原文”可查看视频直播解析题解)
ABC455题解及参考程序（文字版）
题目地址：https://atcoder.jp/contests/abc455/tasks
题目讲解：识别下方二维码或点击文末“阅读原文”可查看视频直播解析题解)
参考代码
A
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;int a,b,c;intmain(){cin>>a>>b>>c;if(a!=b&&b==c) cout<<"Yes"<<endl;elsecout<<"No"<<endl;return0;}
B
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=15;int n,m;char s[N][N];intmain(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i)scanf("%s",&s[i][1]);int ans=0;for(int h1=1;h1<=n;++h1)for(int h2=h1;h2<=n;++h2)for(int w1=1;w1<=m;++w1)for(int w2=w1;w2<=m;++w2) {int ok=1;for(int i=h1;i<=h2;++i)for(int j=w1;j<=w2;++j)if(s[i][j]!=s[h1+h2-i][w1+w2-j]) {ok=0; break;}ans+=ok;}printf("%d\n",ans);return0;}
C
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=3e5+5;int n,k,a[N];vector<ll> tmp;intmain(){ios::sync_with_stdio(0);cin>>n>>k;ll ans=0;for(int i=1;i<=n;++i)cin>>a[i],ans+=a[i];sort(a+1,a+n+1);int lst=0;for(int i=1;i<=n;++i)if(i==n||a[i]!=a[i+1]) {tmp.push_back(1ll*(i-lst)*a[i]);lst=i;}sort(tmp.begin(),tmp.end(),greater<ll>());for(int i=0;i<min(k,int(tmp.size()));++i)ans-=tmp[i];cout<<ans<<endl;return0;}
D
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;constint N=3e5+5;int n,q;int nxt[N],cnt[N];intgetf(int x){if(!nxt[x]) return x;return nxt[x]=getf(nxt[x]);}intmain(){scanf("%d%d",&n,&q);while(q--) {int c,p;scanf("%d%d",&c,&p);nxt[c]=p;}for(int i=1;i<=n;++i)++cnt[getf(i)];for(int i=1;i<=n;++i)cout<<cnt[i]<<' ';cout<<endl;return0;}
E
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;typedefpair<int,int> pii;constint N=2e5+5;int n;char s[N];int cnt[3];int buc[3][N*2];map<pii,int> Buc;intmain(){scanf("%d%s",&n,s+1);ll ans=1ll*n*(n+1)/2;++buc[0][cnt[0]-cnt[1]+N];++buc[1][cnt[1]-cnt[2]+N];++buc[2][cnt[0]-cnt[2]+N];++Buc[pii(cnt[0]-cnt[1],cnt[0]-cnt[2])];for(int i=1;i<=n;++i) {cnt[s[i]-'A']++;ans-=buc[0][cnt[0]-cnt[1]+N];ans-=buc[1][cnt[1]-cnt[2]+N];ans-=buc[2][cnt[0]-cnt[2]+N];++buc[0][cnt[0]-cnt[1]+N];++buc[1][cnt[1]-cnt[2]+N];++buc[2][cnt[0]-cnt[2]+N];ans+=2*Buc[pii(cnt[0]-cnt[1],cnt[0]-cnt[2])];++Buc[pii(cnt[0]-cnt[1],cnt[0]-cnt[2])];}printf("%lld\n",ans);return0;}
F
#include<bits/stdc++.h>usingnamespacestd;typedeflonglong ll;typedefpair<ll,ll> pll;constint N=1e5+5,MOD=998244353,inv2=(MOD+1)/2;int n,q;ll sum[N<<2],sum2[N<<2],tag[N<<2];#define lc (k<<1)#define rc (lc|1)#define left lc,l,mid#define right rc,mid+1,rvoidpushup(int k){sum[k]=(sum[lc]+sum[rc])%MOD;sum2[k]=(sum2[lc]+sum2[rc])%MOD;}voidputtag(int k,int l,int r,ll v){(sum2[k]+=2ll*sum[k]*v%MOD+1ll*(r-l+1)*v%MOD*v%MOD)%=MOD;(sum[k]+=1ll*(r-l+1)*v)%=MOD;(tag[k]+=v)%=MOD;}voidpushdown(int k,int l,int r,int mid){if(tag[k]) {puttag(left,tag[k]);puttag(right,tag[k]);tag[k]=0;}}voidchange(int k,int l,int r,int x,int y,int v){if(x<=l&&r<=y) return puttag(k,l,r,v);int mid=l+r>>1; pushdown(k,l,r,mid);if(x<=mid) change(left,x,y,v);if(y>mid) change(right,x,y,v);pushup(k);}pll operator + (const pll &a,const pll &b) {return pll((a.first+b.first)%MOD, (a.second+b.second)%MOD);}pll query(int k,int l,int r,int x,int y){if(x<=l&&r<=y) return pll(sum[k],sum2[k]);int mid=l+r>>1; pushdown(k,l,r,mid);pll z(0ll,0ll);if(x<=mid) z=z+query(left,x,y);if(y>mid) z=z+query(right,x,y);return z;}intmain(){scanf("%d%d",&n,&q);while(q--) {int l,r,v;scanf("%d%d%d",&l,&r,&v);change(1,1,n,l,r,v);pll z=query(1,1,n,l,r);printf("%lld\n",((z.first*z.first-z.second)%MOD*inv2%MOD+MOD)%MOD);}return0;}
G
#include<bits/stdc++.h>usingnamespacestd;#define int long longtypedeflonglong ll;typedefunsignedlonglong ull;constint N=2e5+5;const ll MOD=1000019861ll*1000019767ll;int T,n,m,k,a[N];ll A[N],S[N],rndv[N];mt19937 _rnd(123456);ull rnd(){return (ull)(_rnd())<<32|(ull)(_rnd());}vector<int> occ[N];int cnt0[N]; map<ll,int> buc1;voidwork1(){for(int v=1;v<=n;++v) {if(occ[v].size()<k) {for(auto i:occ[v]) A[i]=rnd()%MOD;} else {rndv[k-1]=0;for(int i=0;i<k-1;++i) {rndv[i]=rnd()%MOD;(rndv[k-1]+=MOD-rndv[i])%=MOD;}for(int i=0;i<occ[v].size();++i)A[occ[v][i]]=rndv[i%k];}}for(int i=1;i<=n;++i)S[i]=(S[i-1]+A[i])%MOD;for(int i=1;i<=n;++i)cnt0[i]=0;buc1.clear();int pt=1; ll ans=0;for(int r=1;r<=n;++r) {++cnt0[a[r]];++buc1[S[r-1]];while(cnt0[a[r]]>k) {--buc1[S[pt-1]];--cnt0[a[pt]],++pt;}ans+=buc1[S[r]];}cout<<ans;}int cnt[2][N],dist[2];ll H;map<ll,int> buc2;voidadd(int o,int v){if((cnt[o][v]++)==0) {++dist[o];if(o==0) (H+=rndv[v])%=MOD;}}voiddel(int o,int v){if((--cnt[o][v])==0) {--dist[o];if(o==0) (H+=MOD-rndv[v])%=MOD;}}__int128 I=1;voidwork2(){for(int v=1;v<=n;++v)rndv[v]=rnd()%MOD;for(int i=1;i<=n;++i)S[i]=(S[i-1]+rndv[a[i]])%MOD;for(int i=1;i<=n;++i)cnt[0][i]=cnt[1][i]=0;dist[0]=dist[1]=0;H=0;buc2.clear();int pt1=1,pt2=1; ll ans=0;for(int r=1;r<=n;++r) {ll tmpH=H;add(0,a[r]); add(1,a[r]);while(pt2<=r&&dist[1]>k-1) {++buc2[(ll)((I*S[pt2-1]*k%MOD+MOD-I*tmpH*(pt2-1)%MOD)%MOD)];del(1,a[pt2++]);}while(pt1<=r&&dist[0]>k) {--buc2[(ll)((I*S[pt1-1]*k%MOD+MOD-I*tmpH*(pt1-1)%MOD)%MOD)];del(0,a[pt1++]);}if(H!=tmpH) {buc2.clear();for(int l=pt1;l<pt2;++l)++buc2[(ll)((I*S[l-1]*k%MOD+MOD-I*H*(l-1)%MOD)%MOD)];}ans+=buc2[(ll)((I*S[r]*k%MOD+MOD-I*H*r%MOD)%MOD)];}cout<<ans;}signedmain(){ios::sync_with_stdio(0);cin>>T;while(T--) {cin>>n>>m;for(int i=1;i<=n;++i)cin>>a[i],occ[a[i]].push_back(i);for(int i=1;i<=m;++i) {cin>>k;work1();cout<<' ';work2();cout<<'\n';}for(int i=1;i<=n;++i)occ[i].clear();/*memset(a,0,sizeof a);memset(A,0,sizeof A);memset(S,0,sizeof S);memset(rndv,0,sizeof rndv);memset(cnt0,0,sizeof cnt0);buc1.clear();buc2.clear();memset(cnt,0,sizeof cnt);memset(dist,0,sizeof dist);H=0;*/}return0;}
针对每周六20:00举办的ABC比赛，我们每周日都会对比赛真题进行直播讲解。
直播间地址（点击“阅读原文”也可查看）：https://live.bilibili.com/21371611?live_from=84002
AtCoder-OI初学者最佳题库推荐（附比赛参赛方式介绍）<<<点击查看
往期精选内容
2025年五大学科竞赛国家集训队正式公布，260人获清北保送资格
2026 NOI系列活动和认证日历发布，CSP-J/S等竞赛时间公布
信息学高手是怎么炼成的 | 入选信息学国家队，被清北保送两次！
详细盘点清华姚班 智班，北大 浙大图灵班等多所高校AI专业实力！
再见，OI-大牛HZW亲笔，分享OI生涯记录，不变的是坚持和热爱！
从搜狗CEO王小川（信息学金牌），看这二十几年中国奥赛金牌的去向
揭晓高薪专业排行榜，计算机专业薪资最高！哪些专业最具潜力？
计算机科学与技术专业全国大学排行榜！
关注「信息学竞赛」
看更多信息学趣闻与知识
↓↓↓
文章来源：
四季读书网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至23467321@qq.com举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！
