P11361 [NOIP2024] 编辑字符串 一种非常简单的解法

· · 题解

没去 NOIP，今天在学校里某同学告诉我今年 T1 非常难打，他打了 100 多行

所以回来打了一下，2024/12/3\ 18:09 开题，2024/12/3\ 18:27 AC

发篇题解炫耀一下

考虑贪心，从左到右每个字符能匹配就匹配。

显然是对的，因为匹配这一对字符至多会导致后面的一对字符不匹配。

但是很多题解到这一步开始就过于复杂了，各种分段模拟的方法码量都很大。

这里提供一种简单的方法。

考虑预处理两个数组，记录每个字符所在可以交换的连续段（后面简称段）的编号，只要从左往右判断每个字符和上一个字符是否可以交换，可以的就和上一个字符在同一段，否则作为一个新段。

再预处理每一段还有多少个没有使用的 0/1，同样从左到右把每个字符所在的段对应变量加 1 即可。

然后从左到右，每次判断对应的两个字符 s_{1,i},s_{2,i} 所在段是否有相同的未使用的字符，有的话按照贪心直接取并将使用的字符在对应段的变量 -1，否则将对应段还有的字符的变量分别 -1。

最后一个细节问题：如果一个字符不能被交换该怎么办？

大部分题解都选择分类讨论，但是这里不用，因为预处理的时候考虑的是和上一个字符是否可以交换，所以不能交换的字符在单独的一段中，满足要求。

现在就有一个 10 分钟以内能写完调完的解法了。

AC Code

#include<bits/stdc++.h>
using namespace std;
int t,n,ans,p[100009],q[100009],e[100009],f[100009],g[100009],h[100009];
string a,b,c,d;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>a>>b>>c>>d,p[0]=q[0]=0,(a[0]&1)?++f[0]:++e[0],(b[0]&1)?++h[0]:++g[0],ans=0;
        for(int i=1;i<n;++i) p[i]=((c[i]&1)&&(c[i-1]&1)?p[i-1]:i),(a[i]&1)?++f[p[i]]:++e[p[i]];
        for(int i=1;i<n;++i) q[i]=((d[i]&1)&&(d[i-1]&1)?q[i-1]:i),(b[i]&1)?++h[q[i]]:++g[q[i]];
        for(int i=0;i<n;++i){
            if(e[p[i]]&&g[q[i]]) ++ans,--e[p[i]],--g[q[i]];
            else if(f[p[i]]&&h[q[i]]) ++ans,--f[p[i]],--h[q[i]];
            else if(e[p[i]]) --e[p[i]],--h[q[i]];
            else --f[p[i]],--g[q[i]];
        }
        cout<<ans<<"\n";
    }
    return 0;
}

让我看看还有谁抱怨写不完