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

· · 题解

前言

这个T1比T2难真是绷不住了

思路

这个题意大致就是两个串，每个串里都有若干连续段，这些连续段的内部元素排列顺序任意，之后排列一下使得两个串相同位置上相等的元素最多。（此处定义下文的“连续段”为那些在 t 串里值全部为 1 的连续段，段内元素顺序是任意的。）

我们可以考虑先预处理出来这些连续段，对于每一个连续段 (l,r) 可以优先让它尽量的和它对应区间里固定的元素（t_i=1 的那些）进行一个匹配并统计对答案贡献。显然，一个固定的元素最多只可能被一个连续段所覆盖。

下一步是统计那些相交的连续段通过重排序做出的贡献。比如说我们现在在 s_1 里枚举到第 i 个连续段，在 s_2 里枚举到第 j 个连续段，那么就直接贪心地让它们尽可能地做出贡献；具体来说就是统计现在两个连续段内分别有多少个还可以随意移动（没有匹配过）的 0 和 1 ，以及两个连续段的交的长度 ，之后就直接把这些 0 和 1 往这个交集里扔就行了。那么处理完之后显然这个交集会覆盖到其中至少一个连续段的右端点（如果交集为空就直接跳了），也就是说至少会处理完一个连续段，就把处理完成的段的指针挪一下。

这个可以看出来是有点贪心的意味的。值得说明的是像这样贪心的直接把 i 连续段中的一些数字和 j 匹配而不是留到后边试图和 j+1 进行匹配（这里当然只是举例，下标是瞎胡的），是对答案的影响是只增不减的。

最后我们要记得把那些固定的而且本来就相同的元素给加上。蒟蒻考场上调这玩意调了一个小时TAT

代码是考完之后根据考场思路进行复现的，为了保证正确性和可调/可读性写的比较长，但是相对会明晰一点。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n;
char sa[N],sb[N],ta[N],tb[N];
struct P{
    int l,r,num[2];
} qa[N],qb[N];
int suma[N][2],sumb[N][2];
int ans,res,ma,mb;

void pre(){

    memset(qa,0,sizeof(qa));
    memset(qb,0,sizeof(qb));
    memset(suma,0,sizeof(suma));
    memset(sumb,0,sizeof(sumb));
    ans=res=ma=mb=0;
    bool bg=0;
    for(int i=1;i<=n;++i){
        if(ta[i]=='1'&&!bg)
            bg=1,qa[++ma].l=i;
        if(ta[i]=='0') ++suma[i][sa[i]-'0'],bg=0;
        if(bg) qa[ma].r=i,qa[ma].num[sa[i]-'0']++;
        suma[i][0]+=suma[i-1][0],
        suma[i][1]+=suma[i-1][1];
    }
    bg=0;
    for(int i=1;i<=n;++i){
        if(tb[i]=='1'&&!bg)
            bg=1,qb[++mb].l=i;
        if(tb[i]=='0') ++sumb[i][sb[i]-'0'],bg=0;
        if(bg) qb[mb].r=i,qb[mb].num[sb[i]-'0']++;
        sumb[i][0]+=sumb[i-1][0],
        sumb[i][1]+=sumb[i-1][1];
    }

    for(int i=1;i<=n;++i)
        if(ta[i]=='0'&&tb[i]=='0'&&sa[i]==sb[i])
            ++res;
}

inline int gt(int i,int j){
    return min(qa[i].r,qb[j].r)-max(qa[i].l,qb[j].l)+1;
}

inline void con(int& i,int& j){
    int mr=min(qa[i].r,qb[j].r);
    if(mr==qa[i].r) ++i;
    if(mr==qb[j].r) ++j;
}

int main(){

    int T; cin>>T;
    while(T--){
        scanf("%d",&n);
        scanf("%s\n%s\n%s\n%s",sa+1,sb+1,ta+1,tb+1);
        pre();

        for(int i=1;i<=ma;++i){
            int l=qa[i].l,r=qa[i].r;
            int del0=sumb[r][0]-sumb[l-1][0],
                del1=sumb[r][1]-sumb[l-1][1];
            int del=min(qa[i].num[0],del0);
            ans+=del,qa[i].num[0]-=del;
            del=min(qa[i].num[1],del1);
            ans+=del,qa[i].num[1]-=del;
        }

        for(int i=1;i<=mb;++i){
            int l=qb[i].l,r=qb[i].r;
            int del0=suma[r][0]-suma[l-1][0],
                del1=suma[r][1]-suma[l-1][1];
            int del=min(qb[i].num[0],del0);
            ans+=del,qb[i].num[0]-=del;
            del=min(qb[i].num[1],del1);
            ans+=del,qb[i].num[1]-=del;
        }//处理连续段覆盖的固定元素所做的贡献

        for(int i=1,j=1;;){
            if(i>ma||j>mb) break;
            int del0=min(qa[i].num[0],qb[j].num[0]),
                del1=min(qa[i].num[1],qb[j].num[1]);
            int jiao=gt(i,j);
            if(jiao<=0){
                con(i,j); continue;
            }

            int del=min(del0,jiao);
            qa[i].num[0]-=del,qb[j].num[0]-=del;
            jiao-=del,ans+=del;
            del=min(del1,jiao);
            qa[i].num[1]-=del,qb[j].num[1]-=del;
            jiao-=del,ans+=del;
            con(i,j);
        }//处理连续段交集的贡献
        printf("%d\n",ans+res);//res就是固定且本来相同的元素数量
    }
    return 0;
}