[NOIP2024] 编辑字符串

· · 题解

依次打开折叠框，提示由浅入深，希望对大家有用。提示框是提示，成功框是提示的答案。

没思路：

:::info 想想什么策略可以匹配的最多。 :::

:::success 显然能匹配尽量匹配。 :::

只有不成熟的想法（上面的内容）：

:::info 注意到有一些固定的位置。好像和不固定的位置形成某种关系？观察一下具体怎么处理。 :::

:::success 不能动的位置把可以移动的位置分成了若干段。 :::

:::info 不能移动的位置怎么当分割点？ :::

:::success 单独组成一段即可。 :::

成功分段的看这里：

:::info 考虑两个段怎么处理？ :::

:::success 你注意到能匹配尽量匹配，比如说这两个段 0,1 数量是 (5,3),(4,4)，尽量匹配之后能匹配 (4,3) 个。

证明：如果这里不匹配那到后面匹配贡献不变。

这里给一个参考代码。

#include<bits/stdc++.h>
using namespace std;
int T,n,ans;
string s1,s2,t1,t2;
vector<tuple<int,int,int,int> >seg1,seg2;
void Main(){
    seg1.clear(),seg2.clear();
    cin>>n>>s1>>s2>>t1>>t2;
    s1=" "+s1,s2=" "+s2,t1=" "+t1,t2=" "+t2;
    ans=0;
    for(int i=1,cnt10=0,cnt11=0,cnt20=0,cnt21=0,lst1=1,lst2=1;i<=n+1;i++){
        if(i==n+1){
            if(lst1!=n+1)
                seg1.push_back(make_tuple(lst1,n,cnt10,cnt11));
            if(lst2!=n+1)
                seg2.push_back(make_tuple(lst2,n,cnt20,cnt21));
            break;
        }
        if(t1[i]=='0'){
            if(lst1!=i)
                seg1.push_back(make_tuple(lst1,i-1,cnt10,cnt11));
            seg1.push_back(make_tuple(i,i,s1[i]=='0',s1[i]=='1'));
            cnt10=cnt11=0,lst1=i+1;
        }
        else
            cnt10+=(s1[i]=='0'),cnt11+=(s1[i]=='1');
        if(t2[i]=='0'){
            if(lst2!=i)
                seg2.push_back(make_tuple(lst2,i-1,cnt20,cnt21));
            seg2.push_back(make_tuple(i,i,s2[i]=='0',s2[i]=='1'));
            cnt20=cnt21=0,lst2=i+1;
        }
        else
            cnt20+=(s2[i]=='0'),cnt21+=(s2[i]=='1');
    }// 分段
    for(int i=0,j=0;i<seg1.size()&&j<seg2.size();){
        auto&[l1,r1,cnt10,cnt11]=seg1[i];
        auto&[l2,r2,cnt20,cnt21]=seg2[j];
        ans+=min(cnt10,cnt20)+min(cnt11,cnt21);//尽量匹配
        if(r1<=r2){
            cnt20-=min(cnt10,cnt20),cnt21-=min(cnt11,cnt21);
            i++;
        }
        if(r1>=r2){
            cnt10-=min(cnt10,cnt20),cnt11-=min(cnt11,cnt21);
            j++;
        }//后续更新剩余
    }
    cout<<ans<<'\n';
    return;
}
int main(){
    for(cin>>T;T;--T)
        Main();
    return 0;
}

:::

:::warning 有问题，只有 60 分，输出答案比正确答案大。

思考有什么问题。问题在下面一个框。 :::

:::error 注意到我们只考虑尽量匹配更多的数，但是对于位置区间出现 [1,5],[3,7]，这两个段只有 [3,5] 相交。如果两段公共的 0,1 超过长度限制怎么办？

答案在下面。 :::

::::success 我们进行观察，显然不能一个段包含另一个（不然公共部分长度短于短的段，短的段的长度就是公共部分），不相交更不用考虑贡献。显然是 l_1<l_2\le r_1<r_2（两个段反过来同理）。

:::info 考虑怎么匹配？匹配 0/1 还是分情况？ :::

:::success 其实你被诈骗了。

你注意到左边的段剩余的比公共部分长，说明前面有位置没匹配上。前面没匹配上有什么条件？至少 0,1 中有一种缺失。

证明：考虑反证法，如果这个段有 0,1，那之前没匹配的那一位无论是啥都可以匹配，矛盾！

所以不需要考虑到底匹配哪个，匹配 0 还是匹配 1，因为你压根没得选，这个段只会剩一种数，全都和后面尽量匹配即可。

这也是这篇题解在这种情况遇到没匹配的直接匹配就是正确的的原因。

我不知道我是不是讲复杂了，应该没有吧。 :::

::::

于是你切了，发现代码不长。正解代码稍微改改即可，不在给了。

存档，如果觉得有帮助可以在这个专栏点赞，不知道能不能全站推荐。