题解：洛谷 P11361 [NOIP2024] 编辑字符串

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

【解题思路】

【算法标签】

#提高+# #贪心#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;// 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(){cin>>t;// 输入测试用例数量while(t--){// 初始化计数数组memset(n1,0,sizeof(n1));memset(n2,0,sizeof(n2));intn;intans=0;// 记录能够匹配的字符对数// 输入n和四个字符串（均从下标1开始存储）cin>>n>>s1+1>>s2+1>>s3+1>>s4+1;intid1=0;// 第一组的分段编号intid2=0;// 第二组的分段编号charlst='0';// 上一个分隔符字符// 处理第一组字符串 s1 和 s3for(inti=1;i<=n;i++){// 如果前一个分隔符是'0'或者当前分隔符是'0'，开启新的一段if(lst=='0'||s3[i]=='0'){id1++;}pos1[i]=id1;// 记录当前字符所属段号// 统计当前段的字符数量if(s1[i]=='0'){n1[id1][0]++;}else{n1[id1][1]++;}lst=s3[i];// 更新上一个分隔符}lst='0';// 重置分隔符// 处理第二组字符串 s2 和 s4for(inti=1;i<=n;i++){// 如果前一个分隔符是'0'或者当前分隔符是'0'，开启新的一段if(lst=='0'||s4[i]=='0'){id2++;}pos2[i]=id2;// 记录当前字符所属段号// 统计当前段的字符数量if(s2[i]=='0'){n2[id2][0]++;}else{n2[id2][1]++;}lst=s4[i];// 更新上一个分隔符}// 遍历每一个位置，进行匹配for(inti=1;i<=n;i++){// 尝试匹配 '0'if(n1[pos1[i]][0]&&n2[pos2[i]][0]){n1[pos1[i]][0]--;// 消耗一个'0'n2[pos2[i]][0]--;// 消耗一个'0'ans++;// 匹配对数加1}// 尝试匹配 '1'elseif(n1[pos1[i]][1]&&n2[pos2[i]][1]){n1[pos1[i]][1]--;// 消耗一个'1'n2[pos2[i]][1]--;// 消耗一个'1'ans++;// 匹配对数加1}}// 输出当前测试用例的结果cout<<ans<<endl;}return0;}

【运行结果】

1 6 011101 111010 111010 101101 4