专栏文章

P11361 [NOIP2024] 编辑字符串

WWild_Of_The_World
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqo4zvw
此快照首次捕获于
2025/12/04 07:59
3 个月前
此快照最后确认于
2025/12/04 07:59
3 个月前
查看原文
考场20，多骗10有3=
60pts：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
string s1,s2,t1,t2;
int a[N],b[N];
int u1[N][2],u2[N][2],cnt1,cnt2;
int n,ans;
void work(){
	memset(u1,0,sizeof(u1));
	memset(u2,0,sizeof(u2));
	ans=cnt1=cnt2=0;
	cin>>n;
	cin>>s1>>s2>>t1>>t2;
	for(int i=0;i<n;i++){
		if(t1[i]!=t1[i-1]){
			cnt1++;
		}
		if(t1[i]=='1'){
			a[i]=cnt1;
			u1[cnt1][s1[i]-'0']++; 
		}
		if(t2[i]!=t2[i-1]){
			cnt2++;
		} 
		if(t2[i]=='1'){
			b[i]=cnt2;
			u2[cnt2][s2[i]-'0']++;
		}
	}
	for(int i=0;i<n;i++){
		if(t1[i]=='0'&&t2[i]=='0'){
			if(s1[i]==s2[i]) ans++;
			continue;
		}
		if(t1[i]=='0'){
			if(u2[b[i]][s1[i]-'0']!=0){
				u2[b[i]][s1[i]-'0']--;
				ans++;
			} 
		}
		if(t2[i]=='0'){
			if(u1[a[i]][s2[i]-'0']!=0){
				u1[a[i]][s2[i]-'0']--;
				ans++;
			} 
		}
	}
	int js;
	for(int i=0;i<n;i++){
		if(t1[i]!='0'&&t2[i]!='0'){
			if(u1[a[i]][0]!=0&&u2[b[i]][0]!=0){
				js=min(u1[a[i]][0],u2[b[i]][0]);
				u1[a[i]][0]-=js,u2[b[i]][0]-=js;
				ans+=js;		
			}
			if(u1[a[i]][1]!=0&&u2[b[i]][1]!=0){
				js=min(u1[a[i]][1],u2[b[i]][1]);
				u1[a[i]][1]-=js,u2[b[i]][1]-=js;
				ans+=js;		
			}
		}
	}
	cout<<ans<<endl;
	return ;
}
int main(){    
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}
如果一个字符不能被交换该怎么办？
因为预处理的时候考虑的是和上一个字符是否可以交换，所以不能交换的字符在单独的一段中，满足要求。
35pts：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
string s1,s2,t1,t2;
int a[N],b[N];
int u1[N][2],u2[N][2],cnt1,cnt2;
int n,ans;
void work(){
	memset(u1,0,sizeof(u1));
	memset(u2,0,sizeof(u2));
	ans=cnt1=cnt2=0;
	cin>>n;
	cin>>s1>>s2>>t1>>t2;
	for(int i=0;i<n;i++){
		if(t1[i]!=t1[i-1])	cnt1++;
		a[i]=cnt1;
		u1[cnt1][s1[i]-'0']++; 
		if(t2[i]!=t2[i-1])	cnt2++;
		b[i]=cnt2;
		u2[cnt2][s2[i]-'0']++;
	}
	int js;
	for(int i=0;i<n;i++){
			if(u1[a[i]][0]!=0&&u2[b[i]][0]!=0){
				js=min(u1[a[i]][0],u2[b[i]][0]);
				u1[a[i]][0]-=js,u2[b[i]][0]-=js;
				ans+=js;		
			}
			if(u1[a[i]][1]!=0&&u2[b[i]][1]!=0){
				js=min(u1[a[i]][1],u2[b[i]][1]);
				u1[a[i]][1]-=js,u2[b[i]][1]-=js;
				ans+=js;		
			}
	}
	cout<<ans<<endl;
	return ;
}
int main(){    
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}
注意到我计数时是直接取两个相交段的公共的数量，但其相交部分可能不足以支持其将相同部分完全配对
60pts：
CPP
if(u1[a[i]][0]!=0&&u2[b[i]][0]!=0){
	u1[a[i]][0]--,u2[b[i]][0]--;
	ans++;		
	}
if(u1[a[i]][1]!=0&&u2[b[i]][1]!=0){
	u1[a[i]][1]--,u2[b[i]][1]--;
	ans++;		
}

//if(u1[a[i]][0]!=0&&u2[b[i]][0]!=0){
//	js=min(u1[a[i]][0],u2[b[i]][0]);
//	u1[a[i]][0]-=js,u2[b[i]][0]-=js;
//	ans+=js;		
//}
//if(u1[a[i]][1]!=0&&u2[b[i]][1]!=0){
//	js=min(u1[a[i]][1],u2[b[i]][1]);
//	u1[a[i]][1]-=js,u2[b[i]][1]-=js;
//	ans+=js;		
//}
注意我分段时的判断：
CPP
if(t1[i]!=t1[i-1])	cnt1++;
会有个小问题：当t是两个连续的不可交换数时会把它们算成一段
100pts：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
string s1,s2,t1,t2;
int a[N],b[N];
int u1[N][2],u2[N][2],cnt1,cnt2;
int n,ans;
void work(){
	memset(u1,0,sizeof(u1));
	memset(u2,0,sizeof(u2));
	ans=cnt1=cnt2=0;
	cin>>n;
	cin>>s1>>s2>>t1>>t2;
	for(int i=0;i<n;i++){
		if(t1[i]!=t1[i-1]||t1[i-1]=='0')	cnt1++;
		a[i]=cnt1;
		u1[cnt1][s1[i]-'0']++; 
		if(t2[i]!=t2[i-1]||t2[i-1]=='0')	cnt2++;
		b[i]=cnt2;
		u2[cnt2][s2[i]-'0']++;
	}
	for(int i=0;i<n;i++){
		if(u1[a[i]][0]!=0&&u2[b[i]][0]!=0){
			u1[a[i]][0]--,u2[b[i]][0]--;
			ans++;		
		}
		if(u1[a[i]][1]!=0&&u2[b[i]][1]!=0){
			u1[a[i]][1]--,u2[b[i]][1]--;
			ans++;		
		}
	}
	cout<<ans<<endl;
	return ;
}
int main(){    
	int t;
	cin>>t;
	while(t--) work();
	return 0;
}
搞定了！！！
回顾这道题，可行的贪心思路其实很好想，分段，能配就配。
我的问题的话就是码力不足了，就算是知道正解也不太行写出来，小问题多，细节上的处理没怎么注意，要关注。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...