P11361 [NOIP2024] 编辑字符串

· · 个人记录

考场20，多骗10有3=

60pts：

#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：

#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：

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;        
//}

注意我分段时的判断：

if(t1[i]!=t1[i-1])  cnt1++;

会有个小问题：当t是两个连续的不可交换数时会把它们算成一段

100pts：

#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;
}

搞定了！！！

回顾这道题，可行的贪心思路其实很好想，分段，能配就配。

我的问题的话就是码力不足了，就算是知道正解也不太行写出来，小问题多，细节上的处理没怎么注意，要关注。