题解：P12353 「HCOI-R2」DataErr0r

· · 题解

upd：数据更新。

注意到 S 和 T 的长度分别为 N 和 N+1，所以删除操作有且仅有一次，并且操作 2 相当于选一个区间并将区间内的奇数/偶数位取反。

所以就可以把题意转化为把 T 的其中一个字符删去后，前后字符串拼接而成的新字符串和 S 相等的最少操作次数（操作 2 可以在删前执行也可以在删后执行）。

考虑预处理出 T 的前缀和后缀通过操作 2 使得两个字符串对应部分相同的最少操作次数 pre_i 和 ne_i。于是我们就能枚举删掉第 i 个字符，每次枚举计算一下操作次数 pre_{i-1}+ne_{i+1}+1，然后取最小值即可。

但是还需要注意：拼接成新字符串后，前后字符串的操作 2 有可能合并在一起使得操作次数更少，所以如果出现可合并的操作，要将答案减一。接下来考虑如何合并。

我们可以发现操作合并只对当前字符后的字符串的前两位即 i+1 和 i+2 有效。考虑计算出操作合并出现在删除前和删除后的操作次数（不能一次合并在删除前，一次合并在删除后，因为这样会使同一个字符两次取反），删除前第 i+1 位的操作可以和第 i-1 位合并，第 i+2 位的操作可以和第 i-2 位合并，删除后同理。

考虑一种特殊情况（讨论区大佬的 hack）：

1 7
00000000
1110001

当删除第 4 位时，可以通过删除字符前后下标奇偶性改变的性质将前缀字符串的操作延伸到前后操作 2 不相邻的后缀字符串，即
先将操作 2 延伸到要改变的后缀字符串，

00000000
->01010101

然后删除第 4 位字符，

->0100101

最后再次取反，将后缀字符串前不需要改变的字符变回来。

->1110001

那怎么判断这种情况呢？
当 i-1 位和 i-2 位都需要改变且存在后缀字符串需要改变时，就可以将后缀字符串中的一次操作合并到前缀（因为这种操作只能是两次前缀字符串的操作中一次操作恢复另一次操作的前缀）；同理，当 i+1 位和 i+2 位都需要改变且存在前缀字符串需要改变时也能这么做。

代码中怎么实现呢？
预处理出两个数组 ne\_id_i 和 pre\_id_i 分别表示第 i 位字符前后第一个需要改变的字符，按照上述思路判断即可。

注意数组 ne 要清零和数组 ne\_id 的边界处理。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,pre[N],ne[N],pre_id[N],ne_id[N];
char x[N],y[N];
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>n>>x+1>>y+1;
        int ans=1e9;
        bool flag[2]={0,0};
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1];
            pre_id[i]=pre_id[i-1];
            if(x[i]==y[i]) flag[i%2]=0;
            else{
                pre_id[i]=i;
                if(!flag[i%2]) pre[i]++;
                flag[i%2]=1;
            }
        }
        flag[1]=flag[0]=0;
        ne[n+2]=0;
        ne_id[n+2]=ne_id[n+3]=n+2;
        for(int i=n+1;i>=2;i--){
            ne[i]=ne[i+1];
            ne_id[i]=ne_id[i+1];
            if(x[i]==y[i-1]) flag[i%2]=0;
            else{
                ne_id[i]=i;
                if(!flag[i%2]) ne[i]++;
                flag[i%2]=1;
            }
        }
        for(int i=1;i<=n+1;i++){
            int res=pre[i-1]+ne[i+1]+1,p1=pre_id[i-1],p2=pre_id[i-2],n1=ne_id[i+1],n2=ne_id[i+2];
            //删前
            ans=min(ans,res-(i-1>=1&&x[i-1]!=y[i-1]&&i+1<=n+1&&x[i+1]!=y[i])-(i-2>=1&&x[i-2]!=y[i-2]&&i+2<=n+1&&x[i+2]!=y[i+1]));
            //删后
            ans=min(ans,res-(i-2>=1&&x[i-2]!=y[i-2]&&i+1<=n+1&&x[i+1]!=y[i])-(i-1>=1&&x[i-1]!=y[i-1]&&i+2<=n+1&&x[i+2]!=y[i+1]));
            //特殊情况
            if(i-2>=1&&p1==i-1&&p2==i-2){
                if(n1<=n+1) res--;
                else if(n2<=n+1) res--;
            }
            else if(i+2<=n+1&&n1==i+1&&n2==i+2){
                if(p1) res--;
                else if(p2) res--;
            }
            ans=min(ans,res);
        }
        cout<<ans<<endl;
    }
    return 0;
}