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;
    //處理 s1
	for(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; 
}