本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】瑞学堂徐老师的二进制加法【题目描述】徐老师最近刚刚学习了二进制加法现在他希望自己出一些题目来锻炼一下自己。他先随便写了一个n nn位的二进制数字 x。接下来他会进行m mm次加法运算每次运算就是给x xx加上2 k 2^k2k对应的二进制数字。但是他突发奇想想知道每次运算后有多少位会变化并且最终x xx的值是多少。你能帮他完成这些计算吗【输入】输入第一行包含一个整数n nn表示二进制位数输入第二行一个长度为n nn的二进制数字x xx每位只有0 / 1 0/10/1接下来一个整数m mm表示徐老师要进行加法的次数接下来m mm行每行一个整数k kk表示这次加法要加的数字为2 k 2^k2k对应的二进制数字【输出】对于每次加法运算输出一行一个整数表示此次运算后发生变化的位数。所有运算结束后输出一行一个二进制字符串表示最终的x xx的值不含前导零。【输入样例】3 110 6 2 2 1 2 2 2【输出样例】2 1 4 1 2 1 11100【核心思想】问题分析给定一个n nn位二进制数x xx低位在前存储进行m mm次加法每次加2 k 2^k2k。要求输出每次运算后发生变化的位数以及最终x xx的值不含前导零。这是一个高精度二进制加法模拟问题关键在于利用二进制加2 k 2^k2k的特殊性只会影响从第k kk位开始连续的1 11段。算法选择高精度二进制存储用数组a aa倒序存储a [ 1 ] a[1]a[1]为最低位支持动态扩位进位链模拟加2 k 2^k2k时从第k 1 k1k1位开始连续的1 11变为0 00进位直到遇到第一个0 00变为1 11变化位数统计进位链中每个1 → 0 1 \to 01→0和最终的0 → 1 0 \to 10→1都计入变化关键步骤读入与初始化读入n nn和二进制字符串s ss将s ss倒序存入a [ 1.. n ] a[1..n]a[1..n]a [ 0 ] a[0]a[0]存位数处理每次加法读入k kk转换为下标x k 1 x k1xk1进位链遍历当a [ x ] 1 a[x] 1a[x]1时a[x] 0changex向高位进位终止进位a[x] 1change该位由0 00变1 11更新位数若x a [ 0 ] x a[0]xa[0]则a[0] x输出change去除前导零当a [ 0 ] 1 a[0] 1a[0]1且最高位a [ a [ 0 ] ] 0 a[a[0]] 0a[a[0]]0时--a[0]输出结果从a [ a [ 0 ] ] a[a[0]]a[a[0]]到a [ 1 ] a[1]a[1]倒序输出时间/空间复杂度时间复杂度O ( n m 总进位次数 ) O(n m \text{总进位次数})O(nm总进位次数)每次加法最坏O ( n ) O(n)O(n)但均摊接近O ( 1 ) O(1)O(1)每位从1 11变0 00后需再从0 00变1 11才能再次进位空间复杂度O ( n m ) O(n m)O(nm)高精度数组存储二进制加法模拟的核心思想加2 k 2^k2k的局部性与普通高精度加法不同加2 k 2^k2k只影响从第k kk位开始的高位低位完全不变利用此特性避免全数组遍历进位链的连续段处理二进制中1 1 0 110110并产生进位因此连续的1 11会形成全变0 00的链式反应直到遇到第一个0 00吸收进位变化位数的精确统计进位链中每个1 → 0 1 \to 01→0贡献1 11次变化最终的0 → 1 0 \to 10→1贡献1 11次变化总和为连续1 11的个数 1 11前导零的动态维护通过while循环在输出前去除最高位的0 00保证输出格式正确适用于高精度二进制数的单点增量操作核心在于利用二进制进位链的连续性实现高效模拟【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;constintN2000005;// 定义数组最大容量为2000005不能按照题意的1000005需要开大点intn,m;// n为二进制位数m为加法运算次数inta[N],b[N];// a数组存储高精度二进制数a[0]为位数a[i]为第i位的值b数组未使用chars[N];// s临时存储输入的二进制字符串intmain(){scanf(%d,n);// 读入二进制位数nscanf(%s,s);// 读入n位二进制数字x字符串形式memset(a,0,sizeof(a));// 将a数组清零a[0]n;// a[0]存储当前二进制数的位数// 将字符串s倒序存入a数组低位在前高位在后// s[0]是最高位对应a[n]s[n-1]是最低位对应a[1]for(inti1;in;i)a[i]s[n-i]-0;// 字符0/1转换为数字0/1scanf(%d,m);// 读入加法运算次数mwhile(m--)// 依次处理每次加法运算{intx;scanf(%d,x);// 读入k表示要加2^kx;// 将k转换为数组下标a[1]对应2^0所以k对应下标k1intchange0;// change记录此次运算发生变化的位数// 模拟二进制加法从第x位开始连续的1变为0进位直到遇到第一个0while(a[x]1)// 如果当前位为1加1后变为0继续向高位进位{a[x]0;// 该位由1变0change;// 变化位数加1x;// 向高位进位}// 遇到第一个0将其变为1进位结束a[x]1;change;// 该位由0变1变化位数加1// 如果进位超出了当前最高位更新位数if(xa[0])a[0]x;// 更新二进制数的总位数printf(%d\n,change);// 输出此次运算发生变化的位数}// 去除前导零当位数大于1且最高位为0时减少位数重要怀疑输入的数据就有前导零while(a[0]1!a[a[0]])--a[0];// 输出最终的二进制数从高位到低位for(intia[0];i1;i--)// 从最高位到最低位遍历{printf(%d,a[i]);// 输出每一位}printf(\n);// 输出结束后换行return0;}【运行结果】3 110 6 2 2 2 1 1 4 2 1 2 2 2 1 11100