P11361 [NOIP2024] 编辑字符串 题解
题目传送门
我的博客
前言
笔者在考场上的时候，心态完全崩了。
现在回过头来，才发觉其实静下心来，这道题也不是不能得分。
笔者补题时借鉴了题解，补完后为了方便自己理解于是作此篇题解。
思路
在一个字符串中交换两个相邻的字符
......
两个字符串中对应位置字符相同的出现次数最多能有多少？
显然，这个问题需要我们贪心求解。只要可以匹配，就尽量匹配。因为前面的匹配成功与否并不影响后面不相邻的字符。
于是我们可以预处理位置数组 \(p[i]\)，记录当前位置能否和前面匹配。如果可以匹配就把他们并到一个段里面。显然，当 \(t_{i} =0\) 的时候不能匹配，此时我们就可以单独给它开一段，表示它把前后两个字符分开。
再预处理每一段中 \(0,1\) 的个数。这一步可以通过判断当前 \(s_i\) 为 \(0\) 或者为 \(1\) 来更新。类似前缀和的思想，让对应数组 \(+1\) 即可。
最后从左到右，判断 \(s_1,s_2\) 是否有相同的未使用的字符。如果有，那么 ans++，同时让未使用的字符数量减 \(1\)。如果没有，那么直接让当前段中还有的字符数量减 \(1\)。
警示后人
-
数组名称不要混乱。
-
\(\color{red}{\text{注意字符串下标问题！}}\)
-
第一个字符要单独处理，位置也是！
-
多测记得清空！
代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
#define int long long
#define ___ __int128
#define INF 0x3f3f3f3f3f3f3f3f
inline int Read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=x*10+c-48;c=getchar();}return x*f;
}
inline void Write(int x){if(x<0) {putchar('-');x=-x;}if(x>9) Write(x/10);putchar(x%10+'0');
}
const int N=1e5+10;
string s1,s2,t1,t2;
int T,n,ans;
int f[N][10],p[N][5];
/*
f[i][1]：s1 中 1 的个数，f[i][2]: s1 中 0 的个数
f[i][3]：s2 中 1 的个数，f[i][4]: s2 中 0 的个数
p[i][1]: s1 中的 p[i]
p[i][2]: s2 中的 p[i]
*/
void solve(){ans=0;//清空！！for(int i=0;i<=n;i++){//清空for(int j=0;j<=4;j++) f[i][j]=0;for(int j=0;j<=2;j++) p[i][j]=0;}n=Read();cin>>s1>>s2>>t1>>t2;s1=" "+s1,s2=" "+s2,t1=" "+t1,t2=" "+t2;//笔者这里字符串习惯从下标 1 开始//第一个字符单独处理if(s1[1]=='1') f[1][1]++;else f[1][2]++;if(s2[1]=='1') f[1][3]++;else f[1][4]++;p[1][1]=p[1][2]=1;//处理 s1for(int i=2;i<=n;i++){//注意下标从第二个字符开始！笔者调了好久！！if(t1[i]=='1'&&t1[i-1]=='1') p[i][1]=p[i-1][1];//如果可以交换else p[i][1]=i;//否则自己单独开一段if(s1[i]=='1') f[p[i][1]][1]++;//1 的个数else f[p[i][1]][2]++;// 0 的个数}//处理 s2，同上for(int i=2;i<=n;i++){if(t2[i]=='1'&&t2[i-1]=='1') p[i][2]=p[i-1][2];else p[i][2]=i;if(s2[i]=='1') f[p[i][2]][3]++;else f[p[i][2]][4]++;}//从左到右贪心匹配for(int i=1;i<=n;i++){if(f[p[i][1]][2]&&f[p[i][2]][4]) ans++,f[p[i][1]][2]--,f[p[i][2]][4]--;else if(f[p[i][1]][1]&&f[p[i][2]][3]) ans++,f[p[i][1]][1]--,f[p[i][2]][3]--; else if(f[p[i][1]][2]) f[p[i][1]][2]--,f[p[i][2]][3]--;else f[p[i][1]][1]--,f[p[i][2]][4]--;}printf("%lld\n",ans);
}
signed main(){T=Read();while(T--){solve();//多测函数好！}return 0;
}