回文区间翻转——贪心与分类讨论

这是一道蓝题（我自己都没想到这题我能过），下面是我的解题思路：

首先读题，有 $2$ 个长度为 $n$ 的二进制字符串 $s,t$，每次选择 $s$ 的一个长度至少为 $2$ 的回文区间，将其按位翻转，直到 $s$ 和 $t$ 相等，需要求出最少的翻转次数。

乍一看题面，首先想到的是动态规划或者是用图论解法，但把所有状态枚举出来时间复杂度太大了，远远超出了 $O(n^2)$ 的上限。那就先不管那么多，直接上贪心，至少不会超时。

贪心算法：枚举 $1$ ~ $n-2$ 中的每一个 $i$，每次我们需要保证对于任意一个 $j\in[1,i]$，$s_j=t_j$ 成立，换句话说，就是让 $i$ 从 $1$ 走到 $n-2$，当发现 $s_i≠t_i$ 时，就通过回文翻转使得 $s_i=t_i$，这样我们就保证了 $s,t$ 在 $[1,i]$ 区间内的子串是相等的。

那么具体该如何翻转呢？根据贪心思路，我们首先找到一个最大的 $p$，满足对于任意一个 $j\in[i,p]$，$s_j≠t_j$ 成立，换句话说，就是我们想要找到一个最长的区间 $[i,p]$，使得 $s,t$ 在该区间内的每一个字符都不一样；然后再找一个最大的 $q$，满足 $i<q≤p$ 且 $s[i,q]$ 是个回文串，这样一来，翻转一遍 $s[i,q]$，我们就使得最开始的要求 $s_i=t_i$ 满足。

我们现在需要快速判断 $s$ 的一个子串是否是回文串，很容易想到预处理，定义一个二维数组 $z$，$z_{i,j}$ 的值表示 $t[i,j]$ 是否为回文串，这里只需要考虑字符串 $t$ 就行了，因为根据我们先前对 $q$ 的求法，如果 $t[i,q]$ 是回文串，那么 $s[i,q]$ 必然也是回文串，反之亦然；先令所有的 $z_{i,i}=1$ 以及满足 $t_i=t_{i+1}$ 的 $z_{i,i+1}=1$，然后从 $3$ 开始枚举长度，如果 $t_{i+1}=t_{j-1}$，那么就令 $z_{i,j}=z_{i+1,j-1}$，这样我们后续就能 $O(1)$ 判断 $s[i,q]$ 是否为回文串。

这里会涉及到一种特殊情况，如果说找不出满足条件的 $q$，那么就令 $q$ 为满足大于 $i$ 且 $s_i=s_q$ 的最小值，如此一来我们能够保证 $s[i,q]$ 一定是回文串，因为夹在 $i$ 和 $q$ 之间的字符都不等于 $s_i$，翻转 $s[i,q]$，又使得 $s_i=t_i$ 满足；但还可能，$i$ 后面的所有字符都不等于 $s_i$，这时我们可以确定 $s[i+1,n]$ 一定是回文串，翻转 $s[i+1,n]$，再回到最开始的找 $p,q$ 的步骤。

讲到这，我们终于完成了字符串 $s$ 前 $n-2$ 个字符的翻转，但是我们仍然需要处理 $s$ 的最后 $2$ 位字符；这里我用了 $132$ 行的分类讨论来处理，大家凑合着看吧，当时我写这段代码的时候，用了整整 $2$ 页草稿纸才把所有情况捋清楚，毕竟最后 $2$ 个字符的归位要涉及到最后 $4$ 个字符的值，像在玩烧脑的 $4$ 位翻转游戏一样，代码里全是 $if-else$ 分支。

最后判断 $ans$ 是否大于 $2n$，然后输出即可，参考代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pi pair<int,int>
const int N=110;
vector<pi> res;
bool fg[N][N];
void swp(string &s,int l,int r){
    for(int i=l;i<=r;i++)
        s[i]='1'-s[i]+'0';
}
void sve(){
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    s='.'+s+'.';
    t='.'+t+'.';
    for(int i=1;i<=n;i++){
        fg[i][i]=true;
        fg[i][i+1]=true;
        if(t[i]!=t[i+1])
            fg[i][i+1]=false;
    }
    for(int e=3;e<=n;e++){
        for(int i=1;i+e-1<=n;i++){
            int j=i+e-1;
            fg[i][j]=fg[i+1][j-1];
            if(t[i]!=t[j])
                fg[i][j]=false;
        }
    }
    int ans=0;
    res.clear();
    for(int i=1;i<=n-2;i++){
        if(s[i]==t[i])
            continue;
        int p=i,q;
        while(p<n&&s[p+1]!=t[p+1])
            p++;
        for(q=p;q>i;q--)
            if(fg[i][q])
                break;
        if(q>i){
            swp(s,i,q);
            ans++;
            res.push_back({i,q});
        }
        else{
            int w=i+1;
            while(w<n&&s[w]!=s[i])
                w++;
            if(s[w]==s[i]){
                swp(s,i,w);
                ans++;
                res.push_back({i,w});
            }
            else{
                swp(s,i+1,w);
                ans++;
                res.push_back({i+1,w});
                i--;
            }
        }
    }
    if(s[n-1]!=t[n-1]&&s[n]!=t[n]){
        if(s[n]==s[n-1]){
            ans++;
            res.push_back({n-1,n});
        }
        else{
            if(s[n-2]==s[n-1]&&s[n-2]==s[n-3]){
                ans+=4;
                res.push_back({n-3,n-1});
                res.push_back({n-2,n});
                res.push_back({n-2,n-1});
                res.push_back({n-3,n-2});
            }
            else if(s[n-2]==s[n-1]){
                ans+=5;
                res.push_back({n-2,n-1});
                res.push_back({n-3,n-1});
                res.push_back({n-2,n-1});
                res.push_back({n-1,n});
                res.push_back({n-3,n-1});
            }
            else if(s[n-2]==s[n]&&s[n-2]==s[n-3]){
                ans+=4;
                res.push_back({n-3,n-2});
                res.push_back({n-3,n-1});
                res.push_back({n-2,n});
                res.push_back({n-2,n-1});
            }
            else{
                ans+=5;
                res.push_back({n-3,n-1});
                res.push_back({n-1,n});
                res.push_back({n-2,n-1});
                res.push_back({n-3,n-1});
                res.push_back({n-2,n-1});
            }
        }
    }
    else{
        if(s[n-1]!=t[n-1]){
            if(s[n-3]==s[n-2]&&s[n-2]==s[n-1]){
                ans+=2;
                res.push_back({n-3,n-1});
                res.push_back({n-3,n-2});
            }
            else if(s[n-2]==s[n-1]){
                if(s[n-1]==s[n]){
                    ans+=5;
                	res.push_back({n-2,n});
                	res.push_back({n-3,n-1});
                	res.push_back({n-2,n-1});
                	res.push_back({n-1,n});
                	res.push_back({n-3,n-1});
                }
                else{
                    ans+=3;
                	res.push_back({n-2,n-1});
                	res.push_back({n-2,n});
                    res.push_back({n-1,n});
                }
            }
            else if(s[n-3]==s[n-1]){
                if(s[n-1]==s[n]){
                    ans+=3;
                	res.push_back({n-1,n});
                	res.push_back({n-2,n});
                	res.push_back({n-2,n-1});
                }
                else{
                    ans+=4;
                	res.push_back({n-2,n});
                	res.push_back({n-3,n-2});
                	res.push_back({n-3,n-1});
                	res.push_back({n-2,n});
                }
            }
            else{
                ans+=2;
                res.push_back({n-3,n-2});
                res.push_back({n-3,n-1});
            }
        }
        else{
            if(s[n]!=t[n]){
                if(s[n]!=s[n-1]){
                    if(s[n]!=s[n-2]){
                        ans+=2;
                        res.push_back({n-2,n-1});
                		res.push_back({n-2,n});
                    }
                    else{
                        if(s[n]!=s[n-3]){
                            ans+=5;
                			res.push_back({n-2,n});
                			res.push_back({n-3,n-2});
                			res.push_back({n-3,n-1});
                			res.push_back({n-2,n});
                			res.push_back({n-1,n});
                        }
                        else{
                            ans+=3;
                			res.push_back({n-3,n-2});
                			res.push_back({n-3,n-1});
                			res.push_back({n-1,n});
                        }
                    }
                }
                else{
                    if(s[n]!=s[n-2]){
                        if(s[n]!=s[n-3]){
                            ans+=3;
                			res.push_back({n-1,n});
                			res.push_back({n-3,n-1});
                			res.push_back({n-3,n-2});
                        }
                    	else{
                            ans+=5;
                			res.push_back({n-1,n});
                			res.push_back({n-2,n});
                			res.push_back({n-3,n-1});
                			res.push_back({n-3,n-2});
                			res.push_back({n-2,n});
                        }
                    }
                    else{
                        ans+=2;
                		res.push_back({n-2,n});
                		res.push_back({n-2,n-1});
                    }
                }
            }
        }
    }
    if(ans>n*2){
        cout<<-1<<endl;
        return;
    }
    cout<<ans<<endl;
    for(auto [x,y]:res)
        cout<<x<<' '<<y<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin>>T;
    while(T--)
        sve();
    return 0;
}