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{L1}{2}2L1​-th character ofS SS, whereL LLis the length ofS SS.输出删除S SS的中间字符后得到的字符串。S SS的中间字符是第L 1 2 \frac{L1}{2}2L1​个字符其中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》 #模拟#【代码详解】#includebits/stdc.husingnamespacestd;string s;// 存储输入的字符串intmain(){// 输入字符串cins;// 获取字符串长度intns.size();// 在字符串前添加空格使索引从1开始便于处理s s;// 输出前半部分不包括中间字符// 从第1个字符到第n/2个字符for(inti1;in/2;i){couts[i];}// 输出后半部分不包括中间字符// 从中间字符的下一个位置到字符串末尾for(inti(n1)/21;in;i){couts[i];}coutendl;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)1236.对于正整数x xx定义f ( x ) f(x)f(x)为x xx的十进制表示中各位数字之和。例如f ( 123 ) 1 2 3 6 f(123) 123 6f(123)1236。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​1Fori ≥ 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​j0∑i−1​f(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》 #递推#【代码详解】#includebits/stdc.husingnamespacestd;constintN105;// 定义最大序列长度intn;// 序列长度inta[N];// 存储原始序列值intf[N];// 存储数字和序列值/** * 计算一个整数的各位数字之和 * param x 输入整数 * return 各位数字之和 */intcalc(intx){intres0;while(x){resx%10;// 取个位数并累加x/10;// 去掉个位数}returnres;}intmain(){// 输入序列长度cinn;// 初始化前两个元素a[0]1;// 第0项为1a[1]1;// 第1项为1f[0]calc(a[0]);// 计算第0项的数字和f[1]calc(a[1]);// 计算第1项的数字和// 计算序列的后续元素for(inti2;in;i){// 计算a[i]前i项f值的和for(intj0;ji;j){a[i]f[j];}// 计算f[i]a[i]的各位数字之和f[i]calc(a[i]);}// 输出第n项的值couta[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 _ iui​andv 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 _ iv _ iui​vi​) or multi-edges (pairs of edges whereu i u j u _ iu _ jui​uj​andv i v j v _ iv _ jvi​vj​).一个图是简单图当且仅当它没有自环u i u j u _ iu _ jui​uj​的边或重边满足u i u j u _ iu _ jui​uj​且v i v j v _ iv _ 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#【代码详解】#includebits/stdc.husingnamespacestd;typedefpairint,intPII;// 定义边对类型constintN15;// 定义最大节点数intn,m;// n:节点数, m:边数intcol[N];// 存储每个节点的颜色1或2intcnt;// 统计同色边的数量intcur;// 未使用的临时变量intans1e9;// 存储最小同色边数PII bian[N*N];// 未使用的边数组vectorintve[N];// 邻接表存储图结构boolvis[N];// DFS访问标记数组/** * 深度优先搜索进行二分图染色 * param u 当前节点 * param color 当前节点要染的颜色 */voiddfs(intu,intcolor){vis[u]1;// 标记当前节点已访问col[u]color;// 给当前节点染色// 遍历所有邻接节点for(inti0;ive[u].size();i){intvve[u][i];// 邻接节点// 如果邻接节点与当前节点颜色相同统计同色边if(col[v]col[u]){cnt;}// 如果邻接节点已访问跳过if(vis[v]){continue;}// 递归染色邻接节点使用相反颜色dfs(v,color1?2:1);}}intmain(){// 输入节点数和边数cinnm;// 输入图的边for(inti1;im;i){intu,v;cinuv;ve[u].push_back(v);ve[v].push_back(u);}// 尝试以每个节点为起点进行二分图染色for(inti1;in;i){// 重置访问标记和颜色数组memset(vis,0,sizeof(vis));memset(col,0,sizeof(col));cnt0;// 重置同色边计数器// 从当前节点开始DFS染色dfs(i,1);// 更新最小同色边数ansmin(ans,cnt);}// 输出结果同色边被统计了两次需要除以2coutans/2endl;return0;}【运行结果】5 8 1 2 1 3 1 4 2 3 2 5 3 4 3 5 4 5 2