本文分享的必刷题目是从蓝桥云课、洛谷、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

【核心思想】

1. 问题分析：给定一个n nn位二进制数x xx（低位在前存储），进行m mm次加法，每次加2 k 2^k2k。要求输出每次运算后发生变化的位数，以及最终x xx的值（不含前导零）。这是一个高精度二进制加法模拟问题，关键在于利用二进制加2 k 2^k2k的特殊性：只会影响从第k kk位开始连续的1 11段。

2. 算法选择：

   • 高精度二进制存储：用数组a aa倒序存储（a [ 1 ] a[1]a[1]为最低位），支持动态扩位
   • 进位链模拟：加2 k 2^k2k时，从第k + 1 k+1k+1位开始，连续的1 11变为0 00（进位），直到遇到第一个0 00变为1 11
   • 变化位数统计：进位链中每个1 → 0 1 \to 01→0和最终的0 → 1 0 \to 10→1都计入变化

3. 关键步骤：

   • 读入与初始化：读入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 = k+1x=k+1）：
     • 进位链遍历：当a [ x ] = 1 a[x] = 1a[x]=1时，a[x] = 0，change++，x++（向高位进位）
     • 终止进位：a[x] = 1，change++（该位由0 00变1 11）
     • 更新位数：若x > a [ 0 ] x > a[0]x>a[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]倒序输出

4. 时间/空间复杂度：

   • 时间复杂度：O ( n + m + 总进位次数 ) O(n + m + \text{总进位次数})O(n+m+总进位次数)，每次加法最坏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(n+m)，高精度数组存储

5. 二进制加法模拟的核心思想：

   • 加2 k 2^k2k的局部性：与普通高精度加法不同，加2 k 2^k2k只影响从第k kk位开始的高位，低位完全不变，利用此特性避免全数组遍历
   • 进位链的连续段处理：二进制中1 + 1 = 0 1+1=01+1=0并产生进位，因此连续的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 + 1+1"
   • 前导零的动态维护：通过while循环在输出前去除最高位的0 00，保证输出格式正确
   • 适用于高精度二进制数的单点增量操作，核心在于利用二进制进位链的连续性实现高效模拟

【算法标签】

#模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=2000005;// 定义数组最大容量为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(inti=1;i<=n;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对应下标k+1）intchange=0;// 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(x>a[0])a[0]=x;// 更新二进制数的总位数printf("%d\n",change);// 输出此次运算发生变化的位数}// 去除前导零：当位数大于1且最高位为0时，减少位数（重要！怀疑输入的数据就有前导零）while(a[0]>1&&!a[a[0]])--a[0];// 输出最终的二进制数（从高位到低位）for(inti=a[0];i>=1;i--)// 从最高位到最低位遍历{printf("%d",a[i]);// 输出每一位}printf("\n");// 输出结束后换行return0;}

【运行结果】

3 110 6 2 2 2 1 1 4 2 1 2 2 2 1 11100