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

· · 题解

题目传送门

题意理解：

思路：

已知 a[i] 与 b[i] 只有以下三种对应情况：

现在问题变成了可移动字符应该如何移动？

由于连续的可移动字符可以任意调换顺序，因此可以将连续的可移动字符看作一块。

因此原序列就变成了若干个可调换顺序的字符块与锁定字符的序列。在划分块的时需要记录在当前位置 i 的字符属于哪个可移动块，并且记录当前块有多少个 1 和 0。

接下来再考虑如何调换。

首先考虑 c[i]=0，d[i]=1 或 c[i]=1，d[i]=0 的情况。我们只需要考虑可移动的块内是否拥有当前不可移动的字符。如果有，则使当前可移动块的对应字符个数减 1，并使 ans++，相当于将这个字符填在了这个位置。

接着考虑 c[i]=d[i]=1 的情况，此时这个位置都在可移动块内，只需分别比对对应块的 1 的个数以及 0 的个数，如果都有 1 或者都有 0，就在这个位置填上 1 或者 0，并使 ans++，两个可移动块对应字符个数分别减 1。

至此，问题已经解决，请看代码实现：

#include<bits/stdc++.h>
using namespace std;
int t,n;
char a[1145140],b[1145140],c[1145140],d[1145140];
int loca[1145140],locb[1145140];//a[i]与b[i]当前位置为第几块
int blocka[1145140][3],blockb[1145140][3];//记录第某一块的字符0的总数与1的总数 
int main(){
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    cin>>t;
    while(t--){
        int ans=0;//记录答案 
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)cin>>b[i];
        for(int i=1;i<=n;i++)cin>>c[i];
        for(int i=1;i<=n;i++)cin>>d[i];
        //输入
        int cnta=1;//cnta记录当前为第几块 
        for(int i=1;i<=n;i++){
            if(c[i]=='1'){
                loca[i]=cnta;//记录当前位置属于哪个块 
                blocka[cnta][a[i]-'0']++;//块内对应字符个数+1 
            }
            if(c[i]=='0'&&c[i-1]=='1'){
                cnta++;//此块已经结束，开一个新块 
            }
        }
        int cntb=1;//b[i]与a[i]同理进行处理 
        for(int i=1;i<=n;i++){
            if(d[i]=='1'){
                locb[i]=cntb;
                blockb[cntb][b[i]-'0']++;
            }
            if(d[i]=='0'&&d[i-1]=='1'){
                cntb++;
            }
        }

        for(int i=1;i<=n;i++)if(c[i]=='0'&&d[i]=='0'&&a[i]==b[i])ans++;//当两位置锁定且相同时ans++

        for(int i=1;i<=n;i++){
            if(c[i]=='1'&&d[i]=='0'){
                if(blocka[loca[i]][b[i]-'0']!=0){//若当前块存在与锁定字符相同的字符时，将此字符填入 
                    blocka[loca[i]][b[i]-'0']--;
                    ans++;
                }
            }
            if(c[i]=='0'&&d[i]=='1'){
                if(blockb[locb[i]][a[i]-'0']!=0){//同理
                    blockb[locb[i]][a[i]-'0']--; 
                    ans++;
                }
            }
        }

        for(int i=1;i<=n;i++){
            if(c[i]=='1'&&d[i]=='1'){
                if(blocka[loca[i]][1]!=0&&blockb[locb[i]][1]!=0){
                    blocka[loca[i]][1]--;
                    blockb[locb[i]][1]--;
                    ans++;
                }
                else if(blocka[loca[i]][0]!=0&&blockb[locb[i]][0]!=0){
                    blocka[loca[i]][0]--;
                    blockb[locb[i]][0]--;
                    ans++;
                }
            }
        }
        cout<<ans<<endl;

        for(int i=1;i<=n;i++)loca[i]=0,locb[i]=0;
        //多测不清空，亲人两行泪 
        for(int i=1;i<=cnta;i++)blocka[i][0]=0,blocka[i][1]=0;
        //多测不清空，亲人两行泪 
        for(int i=1;i<=cntb;i++)blockb[i][0]=0,blockb[i][1]=0;
        //多测不清空，亲人两行泪
        //重要的事情说三遍 
    }
    return 0;
}

这可能是真正意义上的第一次场切蓝题，但这也可能是最后一场比赛了，珍惜和 OI 在一起的时光吧，继续走下去。