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

chenxi2009 · 2024-11-30 16:15:24 · 题解

Upd 2024.12.7：更改 AC 代码

思路

我们不妨先假设所有的位置都能匹配上，再计算不能匹配到的位置。

转换一下题意：有几个不能移动的点阻碍了移动，相当于两个字符串各自被分割成了数个区间，每个区间内部的 01 字符可以互换位置，但区间之间不能交换字符（不能移动的点相当于长度为一的区间）。

从左往右扫，假设扫到某个位置时，有 A 区间包含 B 区间。

显然 A 区间的字符可以匹配上 B 区间的每个字符的话，就尽管匹配，反正每个字符最多贡献一次在这里贡献了肯定不劣；如果 A 区间缺少了一种字符，那只能用另外一种字符填补了。采用这样的策略扫一遍全部区间，就可以得到答案。时间复杂度 O(Tn)。

代码

非考场代码，思路过程相同，暂时无法通过此题，仅供参考。

#include<bits/stdc++.h>
using namespace std;
struct node{
    int num0,num1;
    int l,r;
}; 
int T,n,ans,l,cnt[2],it;
char s[3][200000],t[3][200000];
vector<node>v[3];
int main(){
    scanf("%d",&T);
    while(T --){
        it = cnt[0] = cnt[1] = ans = 0,l = 1;
        v[1].clear(),v[2].clear(); 
        scanf("%d%s%s%s%s",&n,s[1] + 1,s[2] + 1,t[1] + 1,t[2] + 1);
        for(int i = 1;i <= n;i ++){
            if(t[1][i] == '0'){
                if(l != i) v[1].push_back({cnt[0],cnt[1],l,i - 1});
                if(s[1][i] == '1') v[1].push_back({0,1,i,i});
                else v[1].push_back({1,0,i,i});
                l = i + 1;
                cnt[0] = cnt[1] = 0;
            }
            else cnt[s[1][i] - '0'] ++;
        }
        if(l <= n) v[1].push_back({cnt[0],cnt[1],l,n});
        cnt[0] = cnt[1] = 0,l = 1;
        for(int i = 1;i <= n;i ++){
            if(t[2][i] == '0'){
                if(l != i) v[2].push_back({cnt[0],cnt[1],l,i - 1});
                if(s[2][i] == '1') v[2].push_back({0,1,i,i});
                else v[2].push_back({1,0,i,i});
                l = i + 1;
                cnt[0] = cnt[1] = 0;
            }
            else cnt[s[2][i] - '0'] ++;
        }
        if(l <= n) v[2].push_back({cnt[0],cnt[1],l,n});
        //至此字符串转变为区间结构体的形式保存，{区间左端点,区间右端点,0 的数量,1 的数量} 
        for(int i = 0;i < v[1].size();i ++){
            node tmp = v[1][i];
            while(it < v[2].size() && v[2][it].l <= tmp.r){
                if(v[2][it].r <= tmp.r){ 
                    tmp.num0 -= v[2][it].num0;
                    tmp.num1 -= v[2][it].num1;
                    ans += v[2][it].num0 + v[2][it].num1; 
                    if(tmp.num0 < 0) ans += tmp.num0,tmp.num1 += tmp.num0,tmp.num0 = 0;
                    if(tmp.num1 < 0) ans += tmp.num1,tmp.num0 += tmp.num1,tmp.num1 = 0;
                    it ++;
                }
                else{
                    v[2][it].num0 -= tmp.num0;
                    v[2][it].num1 -= tmp.num1;
                    ans += tmp.num0 + tmp.num1; 
                    if(v[2][it].num0 < 0) ans += v[2][it].num0,v[2][it].num1 += v[2][it].num0,v[2][it].num0 = 0;
                    if(v[2][it].num1 < 0) ans += v[2][it].num1,v[2][it].num0 += v[2][it].num1,v[2][it].num1 = 0;
                    break; 
                }
            }
            v[1][i] = tmp;
        }

        printf("%d\n",ans);
    }
    return 0;
}