AtCoder Beginner Contest 454真题解析报告
讲解赛事：AtCoder Beginner Contest 454 讲解嘉宾：清北学堂 OI 金牌教研团 吴老师（清华大学 NOI银牌） 直播时间：本周日（4 月 19 日）晚上 19:00 直播内容：完整赛题逐题解析、思路推导、代码实现、易错点总结
直播间地址（复制下方链接或直接扫描二维码，PC端建议使用chrome浏览器点击“阅读原文”也可查看）：
https://live.bilibili.com/21371611?live_from=84002
如不能显示请在哔站搜索栏查找“清北学堂信息学”账号（录播也发布在此）
PC 端建议使用Chrome 浏览器，观看更稳定、体验更佳。
本次直播聚焦AtCoder ABC命题特点，用竞赛金牌视角拆解题目，帮你建立规范解题流程，提升算法思维与实战得分能力。
欢迎加入ABC交流QQ群咨询、沟通、交流（群密码：AtCoder）
题目讲解：识别下方二维码或点击文末“阅读原文”可查看视频直播解析题解)
ABC454题解及参考程序（文字版）
题目地址：https://atcoder.jp/contests/abc454/tasks
题目讲解：识别下方二维码或点击文末“阅读原文”可查看视频直播解析题解)
参考代码
A
#include<bits/stdc++.h>usingnamespacestd;intmain(){int L,R;scanf("%d%d",&L,&R);printf("%d\n",R-L+1);return0;}
B
#include<bits/stdc++.h>usingnamespacestd;constint MAXN = 100 + 5;int n,m,cnt[MAXN];// cnt[i]: 衣服i有几个人穿intmain(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;++i){int f;scanf("%d",&f);cnt[f]++;}puts(*max_element(cnt+1,cnt+m+1) <= 1 ? "Yes" : "No");puts(*min_element(cnt+1,cnt+m+1) >= 1 ? "Yes" : "No");return0;}
C
#include<bits/stdc++.h>usingnamespacestd;constint MAXN = 3e5 + 5;vector<int> G[MAXN];int n,m;bool vis[MAXN];int ans;voiddfs(int v){vis[v] = true;++ans;for(auto x:G[v]){if(vis[x]) continue;dfs(x);}}intmain(){scanf("%d%d",&n,&m);for(int i = 1;i <= m;++i){int a,b;scanf("%d%d",&a,&b);G[a].push_back(b);}dfs(1);printf("%d\n",ans);return0;}
C-bfs
#include<bits/stdc++.h>usingnamespacestd;constint MAXN = 3e5 + 5;vector<int> G[MAXN];int n,m;bool vis[MAXN];int ans;voidbfs(int S){queue<int> q;q.push(S);vis[S] = true;while(!q.empty()){int v = q.front();q.pop();++ans;for(auto x:G[v]){if(vis[x]) continue;vis[x] = true;q.push(x);}}}intmain(){scanf("%d%d",&n,&m);for(int i = 1;i <= m;++i){int a,b;scanf("%d%d",&a,&b);G[a].push_back(b);}bfs(1);printf("%d\n",ans);return0;}
D
#include<bits/stdc++.h>usingnamespacestd;constint MAXN = 2e6 + 5;char A[MAXN], B[MAXN];char tA[MAXN], tB[MAXN];int tAl, tBl;bool del[MAXN];// 标记位置i是否已被删除voidsimplify(char *A, char *tA, int &tAl){int lA = strlen(A+1);for(int i = 1;i <= lA;++i) del[i] = false;for(int i = 1;i <= lA-1;++i){// A[i,i+1]=xxif(A[i] == 'x' && A[i+1] == 'x'){int k = 1;// A[i-k] == '(', A[i+1 + k] == ')'while(i-k >= 1 && i+1+k <= lA && A[i-k] == '(' && A[i+1+k] == ')'){del[i-k] = true;del[i+1+k] = true;++k;}}}tAl = 0;for(int i = 1;i <= lA;++i) if(!del[i]) tA[++tAl] = A[i];}inlinevoidsolve(){scanf("%s%s",A+1,B+1);int ltA = 0, ltB = 0;simplify(A, tA, ltA);simplify(B, tB, ltB);// printf("tA=%s\n",tA+1);// printf("tB=%s\n",tB+1);if(ltA == ltB){bool flag = true;for(int i = 1;i <= ltA;++i) flag &= (tA[i] == tB[i]);if(flag){puts("Yes");return;}}puts("No");}intmain(){int T;scanf("%d",&T);while(T--) solve();return0;}
E
#include<bits/stdc++.h>usingnamespacestd;voidgettrace(int N, int M,int A,int B){// 输出一条从 (1,1) 走到 (N,M) 不经过 (A,B) 和已经走过的格子if(N == 2 && M == 2){if(A == 1 && B == 2) printf("DR");elseprintf("RD");return;}if(A > 2){// RR...RR D LL....LL Dfor(int i = 1;i <= M-1;++i) putchar('R');putchar('D');for(int i = 1;i <= M-1;++i) putchar('L');putchar('D');gettrace(N-2,M,A-2,B);return;}if(B > 2){// DD..DD R UU...UU Rfor(int i = 1;i <= N-1;++i) putchar('D');putchar('R');for(int i = 1;i <= N-1;++i) putchar('U');putchar('R');gettrace(N,M-2,A,B-2);return;}if(A <= N-2){// (1,1) -> (N-2,M)gettrace(N-2,M,A,B);putchar('D'); // (N-1, M)for(int i = 1;i <= M-1;++i) putchar('L');// (N-1,1)putchar('D');// (N,1)for(int i = 1;i <= M-1;++i) putchar('R');// (N,M)return;}if(B <= M-2){// (1,1) -> (N,M-2)gettrace(N,M-2,A,B);putchar('R'); // (N, M-1)for(int i = 1;i <= N-1;++i) putchar('U');// (1,M-1)putchar('R');// (1,M)for(int i = 1;i <= N-1;++i) putchar('D');// (N,M)return;}}voidSolve(){int N, A, B;scanf("%d%d%d",&N,&A,&B);if(N%2==1){puts("No");return;}if((A+B)%2==0){puts("No");return;}puts("Yes");gettrace(N,N,A,B);puts("");}intmain(){int T;scanf("%d",&T);while(T--) Solve();return0;}
F
#include<bits/stdc++.h>usingnamespacestd;constint MAXN = 2e5 + 5;int n,m;int a[MAXN];longlong suf[MAXN];inlinevoidsolve(){scanf("%d%d",&n,&m);for(int i = 1;i <= n;++i) scanf("%d",a+i);vector<int> E;int las = 0;for(int i = 1;i <= n/2;++i){int v = (a[n-i+1] - a[i]+m)%m;E.push_back((v-las+m)%m);las = v;}E.push_back((m-las)%m);sort(E.begin(), E.end());suf[E.size()] = 0;for(int i = (int)E.size()-1;i >= 0;--i){suf[i] = (suf[i+1] + (m-E[i]));}longlong ans = suf[0], sm = 0;for(int p = 0;p < E.size();++p){sm += E[p];ans = min(ans, max(sm, suf[p+1]));}printf("%lld\n",ans);}intmain(){int T;scanf("%d",&T);while(T--) solve();return0;}
G
#include<bits/stdc++.h>usingnamespacestd;constint MAXN = 2500000+5;constint mod = 998244353;int p[MAXN], c[MAXN];int n, seed, m, F;int ans;int sz[MAXN], hson[MAXN];int f[MAXN], mx, mxcnt;vector<int> G[MAXN];voidadd(int c){f[c]++;if(f[c] > mx){mx = f[c];mxcnt = 1;}elseif(f[c] == mx){mxcnt++;}}voidadddfs(int v){add(c[v]);for(auto x:G[v]) adddfs(x);}voidclrdfs(int v){f[c[v]] = 0;for(auto x:G[v]) clrdfs(x);}voiddfs(int v,int clear){// clear=0 无需清空，1说明需要清空for(auto x:G[v]){if(x == hson[v]) continue;dfs(x, 1);}if(hson[v] != 0) dfs(hson[v], 0);// 轻儿子都加进去for(auto x:G[v]){if(x == hson[v]) continue;adddfs(x);}add(c[v]);(ans += 1ll*(mx ^ v) * (mxcnt ^ v) % mod) %= mod;if(clear){clrdfs(v);mx = 0;mxcnt = 0;}}intmain(){scanf("%d%d%d%d",&n,&seed,&m,&F);for(int i = 2;i <= m;++i) scanf("%d",p+i);for(int i = m+1;i <= n;++i){p[i] = (seed % (i-1)) + 1;seed = (seed * 1103515245ll + 12345) % (1LL<<31);}for(int i = 1;i <= m;++i) scanf("%d",c+i);for(int i = m+1;i <= n;++i){c[i] = (seed % F) + 1;seed = (seed * 1103515245ll + 12345) % (1LL<<31);}for(int i = n;i >= 1;--i){++sz[i];sz[p[i]] += sz[i];if(hson[p[i]] == 0 || sz[hson[p[i]]] < sz[i]){hson[p[i]] = i;}}for(int i = 2;i <= n;++i) G[p[i]].push_back(i);dfs(1, 0);printf("%d\n",ans);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举报，一经查实，本站将立刻删除;如已特别标注为本站原创文章的，转载时请以链接形式注明文章出处，谢谢！
