P11361 [NOIP2024] 编辑字符串 题解

· · 题解

思路

直接从小到大开始遍历，在 i 这个位置如果 s_{i,1}=s_{i,2} 就给答案加 1，否则当 t_{i,1},t_{i,2} 不都为 0，则再开一个循环往后遍历，找到在同一个块里第一个 s_i\neq s_j，给它 swap 回去。这个东西是 O(n^2) 的，有 60pts，正确性在其他题解里有证明。

对于第二个循环，保存之前跑到过的位置，之后直接从这个位置开始跑，就是 O(n) 的，可以通过民间数据。

这个做法的正确性，感性理解一下，之前跑到过的位置，因为它不能影响答案，所以是一串相等的，于是往后遍历时这一段也是不会影响答案，可以直接跳过。

代码比其他题解中的做法短不少。

代码

#include<bits/stdc++.h>
using namespace std;
int T,n,ans,l[2];
string s[2],t[2];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>s[0]>>s[1]>>t[0]>>t[1];
        ans=l[0]=l[1]=0;
        for(int i=0;i<n;i++){
            if(s[0][i]==s[1][i]){ans++;continue;}
            else if(t[0][i]=='0'&&t[1][i]=='0')continue;
            for(int j=0;j<2;j++){
                bool c1=0;
                if(t[j][i]=='1')
                    for(l[j]=max(l[j],i+1);t[j][l[j]]=='1';l[j]++)
                        if(s[j][i]!=s[j][l[j]]){
                            c1=1,ans++,swap(s[j][i],s[j][l[j]]);
                            break;
                        }
                if(c1)break;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}