本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P11361 [NOIP2024] 编辑字符串 - 洛谷【题目描述】小 M 有两个长度为n nn且字符集为{ 0 , 1 } \{0, 1\}{0,1}的字符串s 1 , s 2 s_1, s_2s1​,s2​。小 M 希望两个字符串中对应位置字符相同的出现次数尽可能多即满足s 1 , i s 2 , i s_{1,i} s_{2,i}s1,i​s2,i​的i ( 1 ≤ i ≤ n ) i(1 \leq i \leq n)i(1≤i≤n)尽可能多。为此小 M 有一个字符串编辑工具这个工具提供的基本操作是在一个字符串中交换两个相邻的字符。为了保持字符串的可辨识性规定两个字符串中的部分字符不能参与交换。小 M 可以用工具对s 1 s_1s1​或s 2 s_2s2​进行多次字符交换其中可以参与交换的字符能够交换任意多次。现在小 M 想知道在使用编辑工具后两个字符串中对应位置字符相同的出现次数最多能有多少。【输入】本题包含多组测试数据。输入的第一行包含一个整数T TT表示测试数据的组数。接下来包含T TT组数据每组数据的格式如下第一行包含一个整数n nn表示字符串长度。第二行包含一个长度为n nn且字符集为{ 0 , 1 } \{0, 1\}{0,1}的字符串s 1 s_1s1​。第三行包含一个长度为n nn且字符集为{ 0 , 1 } \{0, 1\}{0,1}的字符串s 2 s_2s2​。第四行包含一个长度为n nn且字符集为{ 0 , 1 } \{0, 1\}{0,1}的字符串t 1 t_1t1​其中t 1 , i t_{1,i}t1,i​为1 11表示s 1 , i s_{1,i}s1,i​可以参与交换t 1 , i t_{1,i}t1,i​为0 00表示s 1 , i s_{1,i}s1,i​不可以参与交换。第五行包含一个长度为n nn且字符集为{ 0 , 1 } \{0, 1\}{0,1}的字符串t 2 t_2t2​其中t 2 , i t_{2,i}t2,i​为1 11表示s 2 , i s_{2,i}s2,i​可以参与交换t 2 , i t_{2,i}t2,i​为0 00表示s 2 , i s_{2,i}s2,i​不可以参与交换。【输出】对于每组测试数据输出一行包含一个整数表示对应的答案。【输入样例】1 6 011101 111010 111010 101101【输出样例】4【解题思路】【算法标签】#提高# #贪心#【代码详解】#includebits/stdc.husingnamespacestd;constintN100005;// s1, s2: 原始字符串从下标1开始// s3, s4: 分隔符字符串用于判断是否属于同一组chars1[N],s2[N],s3[N],s4[N];// n1[i][0/1]: 第一组字符串中第i段的0和1的数量// n2[i][0/1]: 第二组字符串中第i段的0和1的数量intn1[N][2],n2[N][2];// pos1[i]: 原始字符串s1中第i个字符属于第一段中的哪一段// pos2[i]: 原始字符串s2中第i个字符属于第二段中的哪一段intpos1[N],pos2[N];intt;// 测试用例数量intmain(){cint;// 输入测试用例数量while(t--){// 初始化计数数组memset(n1,0,sizeof(n1));memset(n2,0,sizeof(n2));intn;intans0;// 记录能够匹配的字符对数// 输入n和四个字符串均从下标1开始存储cinns11s21s31s41;intid10;// 第一组的分段编号intid20;// 第二组的分段编号charlst0;// 上一个分隔符字符// 处理第一组字符串 s1 和 s3for(inti1;in;i){// 如果前一个分隔符是0或者当前分隔符是0开启新的一段if(lst0||s3[i]0){id1;}pos1[i]id1;// 记录当前字符所属段号// 统计当前段的字符数量if(s1[i]0){n1[id1][0];}else{n1[id1][1];}lsts3[i];// 更新上一个分隔符}lst0;// 重置分隔符// 处理第二组字符串 s2 和 s4for(inti1;in;i){// 如果前一个分隔符是0或者当前分隔符是0开启新的一段if(lst0||s4[i]0){id2;}pos2[i]id2;// 记录当前字符所属段号// 统计当前段的字符数量if(s2[i]0){n2[id2][0];}else{n2[id2][1];}lsts4[i];// 更新上一个分隔符}// 遍历每一个位置进行匹配for(inti1;in;i){// 尝试匹配 0if(n1[pos1[i]][0]n2[pos2[i]][0]){n1[pos1[i]][0]--;// 消耗一个0n2[pos2[i]][0]--;// 消耗一个0ans;// 匹配对数加1}// 尝试匹配 1elseif(n1[pos1[i]][1]n2[pos2[i]][1]){n1[pos1[i]][1]--;// 消耗一个1n2[pos2[i]][1]--;// 消耗一个1ans;// 匹配对数加1}}// 输出当前测试用例的结果coutansendl;}return0;}【运行结果】1 6 011101 111010 111010 101101 4