AtCoder Beginner Contest竞赛题解 | AtCoder Beginner Contest 427
欢迎大家订阅我的专栏：算法题解：C++与Python实现！
本专栏旨在帮助大家从基础到进阶 ，逐步提升编程能力，助力信息学竞赛备战！
专栏特色
1.经典算法练习：根据信息学竞赛大纲，精心挑选经典算法题目，提供清晰的代码实现与详细指导，帮助您夯实算法基础。
2.系统化学习路径：按照算法类别和难度分级，从基础到进阶，循序渐进，帮助您全面提升编程能力与算法思维。
适合人群：
- 准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生
- 希望系统学习C++/Python编程的初学者
- 想要提升算法与编程能力的编程爱好者
附上汇总帖：AtCoder Beginner Contest竞赛题解 | 汇总
A - ABC -> AC
【题目来源】
洛谷：[AT_abc427_a ABC427A] ABC -> AC - 洛谷
【题目描述】
You are given a stringS SSconsisting of uppercase English letters. Here, the length ofS SSis odd.
给定一个由大写英文字母组成的字符串S SS。此处，S SS的长度为奇数。
Print the string obtained by deleting the middle character ofS SS. The middle character ofS SSis theL + 1 2 \frac{L+1}{2}2L+1-th character ofS SS, whereL LLis the length ofS SS.
输出删除S SS的中间字符后得到的字符串。S SS的中间字符是第L + 1 2 \frac{L+1}{2}2L+1个字符，其中L LL为S SS的长度。
【输入】
The input is given from Standard Input in the following format:
S【输出】
Print the string as instructed in the problem statement.
【输入样例】
ABCDE【输出样例】
ABDE【算法标签】
《洛谷 AT_abc427_a ABC->AC》 #模拟#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;string s;// 存储输入的字符串intmain(){// 输入字符串cin>>s;// 获取字符串长度intn=s.size();// 在字符串前添加空格，使索引从1开始（便于处理）s=" "+s;// 输出前半部分（不包括中间字符）// 从第1个字符到第n/2个字符for(inti=1;i<=n/2;i++){cout<<s[i];}// 输出后半部分（不包括中间字符）// 从中间字符的下一个位置到字符串末尾for(inti=(n+1)/2+1;i<=n;i++){cout<<s[i];}cout<<endl;return0;}【运行结果】
ABCDE ABDEB - Sum of Digits Sequence
【题目来源】
洛谷：[AT_abc427_b ABC427B] Sum of Digits Sequence - 洛谷
【题目描述】
For a positive integerx xx, definef ( x ) f(x)f(x)as the sum of the digits in the decimal representation ofx xx. For example,f ( 123 ) = 1 + 2 + 3 = 6 f(123) = 1 + 2 + 3 = 6f(123)=1+2+3=6.
对于正整数x xx，定义f ( x ) f(x)f(x)为x xx的十进制表示中各位数字之和。例如，f ( 123 ) = 1 + 2 + 3 = 6 f(123) = 1+2+3 = 6f(123)=1+2+3=6。
Define an infinite sequenceA = ( A 0 , A 1 , A 2 , … ) A = (A_0, A_1, A_2, \ldots)A=(A0,A1,A2,…)by the following formula:
通过以下公式定义一个无限序列A = ( A 0 , A 1 , A 2 , … ) A = (A_0, A_1, A_2, \ldots)A=(A0,A1,A2,…)：
- A 0 = 1 A_0 = 1A0=1
- Fori ≥ 1 i \geq 1i≥1,A i = ∑ j = 0 i − 1 f ( A j ) A_i = \displaystyle\sum_{j = 0}^{i - 1} f(A_j)Ai=j=0∑i−1f(Aj)
You are given a positive integerN NN. Find the value ofA N A_NAN.
给定一个正整数N NN。求A N A_NAN的值。
【输入】
The input is given from Standard Input in the following format:
N【输出】
Print the answer.
【输入样例】
6【输出样例】
23【算法标签】
《洛谷 AT_abc427_b Sum of Digits Sequence》 #递推#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;constintN=105;// 定义最大序列长度intn;// 序列长度inta[N];// 存储原始序列值intf[N];// 存储数字和序列值/** * 计算一个整数的各位数字之和 * @param x 输入整数 * @return 各位数字之和 */intcalc(intx){intres=0;while(x){res+=x%10;// 取个位数并累加x/=10;// 去掉个位数}returnres;}intmain(){// 输入序列长度cin>>n;// 初始化前两个元素a[0]=1;// 第0项为1a[1]=1;// 第1项为1f[0]=calc(a[0]);// 计算第0项的数字和f[1]=calc(a[1]);// 计算第1项的数字和// 计算序列的后续元素for(inti=2;i<=n;i++){// 计算a[i]：前i项f值的和for(intj=0;j<i;j++){a[i]+=f[j];}// 计算f[i]：a[i]的各位数字之和f[i]=calc(a[i]);}// 输出第n项的值cout<<a[n]<<endl;return0;}【运行结果】
6 23C - Bipartize
【题目来源】
洛谷：[AT_abc427_c ABC427C] Bipartize - 洛谷
【题目描述】
There is a simple undirected graph withN NNvertices andM MMedges. The graph consists of vertex1 , 1,1,vertex2 , … , 2,\ldots,2,…,vertexN NN, and thei ii-th edge( 1 ≤ i ≤ M ) (1\le i\le M)(1≤i≤M)connects verticesu i u _ iuiandv i v _ ivi.
有一个具有N NN个顶点和M MM条边的简单无向图。该图包含顶点1 11、顶点2 22、……、顶点N NN，第i ii条边（1 ≤ i ≤ M 1≤i≤M1≤i≤M）连接顶点u i u_iui和v i v_ivi。
You will perform the following operation zero or more times:
您将执行以下操作零次或多次：
- Choose one edge that has not been deleted yet, and delete it.
选择一条尚未被删除的边，并将其删除。
Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.
您的目标是通过操作使图变为二分图。求使操作后的图成为二分图所需的最小操作次数。
What it means for a graph to be simple?
简单图是指满足以下两个条件的图：
A graph is simple if and only if it has no self-loops (edges whereu i = v i u _ i=v _ iui=vi) or multi-edges (pairs of edges whereu i = u j u _ i=u _ jui=ujandv i = v j v _ i=v _ jvi=vj).
一个图是简单图，当且仅当它没有自环（u i = u j u _ i=u _ jui=uj的边）或重边（满足u i = u j u _ i=u _ jui=uj且v i = v j v _ i=v _ jvi=vj的边对）。
【输入】
The input is given from Standard Input in the following format:
N M u_1 v_1 u_2 v_2 . . . u_M v_M【输出】
Print the number of operations that need to be performed to make the graph bipartite.
【输入样例】
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5【输出样例】
2【算法标签】
《洛谷 AT_abc427_c Bipartize》 #DFS#
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;// 定义边对类型constintN=15;// 定义最大节点数intn,m;// n:节点数, m:边数intcol[N];// 存储每个节点的颜色（1或2）intcnt;// 统计同色边的数量intcur;// 未使用的临时变量intans=1e9;// 存储最小同色边数PII bian[N*N];// 未使用的边数组vector<int>ve[N];// 邻接表存储图结构boolvis[N];// DFS访问标记数组/** * 深度优先搜索进行二分图染色 * @param u 当前节点 * @param color 当前节点要染的颜色 */voiddfs(intu,intcolor){vis[u]=1;// 标记当前节点已访问col[u]=color;// 给当前节点染色// 遍历所有邻接节点for(inti=0;i<ve[u].size();i++){intv=ve[u][i];// 邻接节点// 如果邻接节点与当前节点颜色相同，统计同色边if(col[v]==col[u]){cnt++;}// 如果邻接节点已访问，跳过if(vis[v]){continue;}// 递归染色邻接节点（使用相反颜色）dfs(v,color==1?2:1);}}intmain(){// 输入节点数和边数cin>>n>>m;// 输入图的边for(inti=1;i<=m;i++){intu,v;cin>>u>>v;ve[u].push_back(v);ve[v].push_back(u);}// 尝试以每个节点为起点进行二分图染色for(inti=1;i<=n;i++){// 重置访问标记和颜色数组memset(vis,0,sizeof(vis));memset(col,0,sizeof(col));cnt=0;// 重置同色边计数器// 从当前节点开始DFS染色dfs(i,1);// 更新最小同色边数ans=min(ans,cnt);}// 输出结果（同色边被统计了两次，需要除以2）cout<<ans/2<<endl;return0;}【运行结果】
5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5 2