P11361 编辑字符串 题解

· · 题解

又是贪心......CSP-S T1贪心，NOIP T1还是贪心......还好是贪心......要不是贪心，估计我就挂了qwq

——LTTXiaochuan

Part.1 前言

打完以后去吃饭，看见你谷评蓝直接吓一大跳，点开一看确定做法不是 DP 以后放心（也不是很放心）地离去了。

但是不多时，放下的心又悬了起来。于是写篇题解证明一下，防止做法假掉导致的原地爆炸。

Part.2 思考过程

（不感兴趣的可以直接跳到 Part.3 证明）

刚拿到这题，我还兴致勃勃地以为是P4008 文本编辑器的变体，正准备掏出我刚打好的平衡树模板，突然发现这题和 BST 毫无关联......

随即发现了“最多”这个词，首先联想到贪心。

怎么贪呢？

既然它分为固定的和自由的两部分，则分为以下几种情况讨论：

1.固定 & 固定：

直接判断是否相同即可；

2.自由 & 固定：

由于自由的块可以随意调换顺序，我们需要一种方法记录每个块的 0/1 数量，方便我们操作。

这里我使用的是类似并查集的方法：把每个块的父亲设为每个块的第一个位置，把块内 0/1 的数量都整合到父亲那里统计。

然后只需要看固定数对应的自由块内是否还有 0/1 能调过来和它匹配就行，匹配成功要将块内0/1的数量 -1 。

3.自由 & 自由：

本来想着用和上面类似的方法，发现这么做需要模拟交换，不仅麻烦，时间复杂度还可能错误，于是另辟蹊径。

先得到两个自由块的交集位置的长度 len，然后先取两个块中 0 的数量 tmp_1 的最少值和 1 的数量的最少值 tmp_2，用 len 减去 tmp_1,tmp_2，直到 len 为 0 即可。

Part.3 证明

Part.2 中的第一种情况无需证明。

第二种情况：如果固定的数更多可用于匹配（意思就是等到自由的数能和固定的数匹配的都匹配了，仍然有剩余的固定数没有匹配到），那么自由块剩下的数一定是单一类（即全是 0 或全是 1 ，因为如果不是单一类，一定可以拿去和固定数再匹配）的，不用再考虑调换顺序的问题，一定最优；如果自由块的数更多可用于匹配，那么固定的数一定被匹配完了，则此时自由块多匹配一个，固定块就少匹配一个，所以令固定块失配不可能更优。

第三种情况也无需证明，不存在调换方式会使得某些数无法被用来匹配（就是说没有可用的自由数“躲在”固定块的后面），因为“固定 & 自由”型已经被处理完毕。

Part.4 Code

（赛时代码复现，过大样例和民间数据）

如果将代码的各个部分封装成函数，可以减少50%的码量。但是在赛时怕出篓子，没有这么做。


#include <bits/stdc++.h>
using namespace std;

const int N=1e5+10;

char s1[N],s2[N],t1[N],t2[N];
int fa1[N],fa2[N],one1[N],one2[N],zero1[N],zero2[N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    //freopen("edit2.in","r",stdin);
    //freopen("edit2.out","w",stdout);

    int T;
    cin>>T;
    while(T--)
    {
        int n,ans=0;
        cin>>n>>s1+1>>s2+1>>t1+1>>t2+1;
        //初始化
        for(int i=1; i<=n; i++)
        {
            fa1[i]=fa2[i]=i;
            one1[i]=zero1[i]=one2[i]=zero2[i]=0;
        }
        //获取0/1数量
        for(int i=1; i<=n; i++)
        {
            if(t1[i]=='0') continue;
            if(t1[i-1]=='0' || i==1) fa1[i]=i;
            else fa1[i]=fa1[i-1];

            if(s1[i]=='1') one1[fa1[i]]++;
            else zero1[fa1[i]]++;
        }
        for(int i=1; i<=n; i++)
        {
            if(t2[i]=='0') continue;
            if(t2[i-1]=='0' || i==1) fa2[i]=i;
            else fa2[i]=fa2[i-1];

            if(s2[i]=='1') one2[fa2[i]]++;
            else zero2[fa2[i]]++;
        }

        //固定&固定和固定&自由
        for(int i=1; i<=n; i++)
        {
            if(t1[i]=='0' && t2[i]=='0')
            {
                if(s1[i]==s2[i]) ans++;
                continue;
            }
            if(t1[i]=='0')
            {
                if(s1[i]=='0' && zero2[fa2[i]])
                {
                    ans++;
                    zero2[fa2[i]]--;
                }
                else if(s1[i]=='1' && one2[fa2[i]])
                {
                    ans++;
                    one2[fa2[i]]--;
                }
            }
            else if(t2[i]=='0')
            {
                if(s2[i]=='0' && zero1[fa1[i]])
                {
                    ans++;
                    zero1[fa1[i]]--;
                }
                else if(s2[i]=='1' && one1[fa1[i]])
                {
                    ans++;
                    one1[fa1[i]]--;
                }
            }
        }
        //自由&自由
        int len=0;
        for(int i=1; i<=n; i++)
        {
            if(t1[i]=='0' || t2[i]=='0') continue;
            len=0;
            while(t1[i]=='1' && t2[i]=='1') len++,i++;
            i--;
            int tmp;
            tmp=min(one1[fa1[i]],one2[fa2[i]]);
            if(len>=tmp)
            {
                len-=tmp;
                one1[fa1[i]]-=tmp,one2[fa2[i]]-=tmp;
                ans+=tmp;
            }
            else
            {
                one1[fa1[i]]-=len,one2[fa2[i]]-=len;
                ans+=len;
                len=0;
            }
            tmp=min(zero1[fa1[i]],zero2[fa2[i]]);
            if(len>=tmp)
            {
                len-=tmp;
                zero1[fa1[i]]-=tmp,zero2[fa2[i]]-=tmp;
                ans+=tmp;
            }
            else
            {
                zero1[fa1[i]]-=len,zero2[fa2[i]]-=len;
                ans+=len;
                len=0;
            }
        }
        cout<<ans<<"\n";
    }

    return 0;
}
//By LTTXC