题解：CF1698F Equal Reversal

· · 题解

好题。

通过对操作的观察和手玩，你感觉到这个操作貌似不会改变数代表的颜色之间的相邻关系，于是你可以把每个颜色建点，然后 a_i \to a_{i+1}，你发现操作形如将一个环上的边全部取反，于是你可以知道能把 a 变成 b 的一个必要条件是 a_1=b_1,a_n=b_n 并且将两个数组建图后，将边视作无向边后两个图相同。

考虑说明这个条件同时是充分的，我们直接来构造说明。

考虑假若现在 a_i=x,a_{i+1}=y 而 b_i=x,b_{i+1}=z，并且前 i-1 位上 a=b，假若后面存在一个 a_p=z,a_{p+1}=x 那直接操作 [i,p+1] 即可，否则后面一定存在若干 a_q=x,a_{q+1}=z，我们考虑操作一个 a_l=a_r=c 并且 [l,r] 包含了 [q,q+1]，假若这样的区间不存在则会产生矛盾，导出矛盾可以考虑这样一个事情，按照序列 a 建立出来的图一定包含了 x \to y \to x \to z 的路径，按照序列 b 建立出来的图一定包含 x \to z \to x \to y 的路径，由于两个图将边时为无向边后相同，所以这个无向图上一定存在包含了 x,y 的环与包含了 x,z 的环，考虑序列 a 在抵达点 z 之前经过的包含 x,z 的环上的边，发现只要没有访问完所有边（如果访问完了就会访问一次 z）环上一定存在一个点 w 满足经过的路径行如 x \to y \to s \to w \to x \to z，并且抵达 z 后一定还会经过没有经过的边 d \to w，也就是整个路径行如 x \to y \to s \to w \to x \to z \to d \to w，那么两个 w 之间包含了 x \to z。如果访问完了那么路径 x \to y \to z \to x \to z 也满足两个 z 之间包含了 x \to z，故导出了矛盾。

顺着这个证明思路，直接从前往后暴力构造即可做到 O(n^3)。

#include<bits/stdc++.h>
using namespace std;
vector< pair<int,int> > opt;
bool solve(int a[],int b[],int n,int pos){
    if(pos==n) return true;
    if(a[pos]==b[pos]) return solve(a,b,n,pos+1);
    else{
        if(pos==0) return false;
        for(int i=pos+1;i+1<n;i++){
            if(a[i]==b[pos]&&a[i+1]==b[pos-1]){
                reverse(a+pos,a+i+1);
                opt.push_back(make_pair(pos,i+2));
                return solve(a,b,n,pos+1);
            }
        }
        vector<int> vis;
        vis.resize(n);
        for(int i=pos;i+1<n;i++){
            if(a[i]==b[pos-1]&&a[i+1]==b[pos]) vis[i]=1;
        }
        for(int i=1;i<n;i++) vis[i]+=vis[i-1];
        for(int i=pos-1;i<n;i++){
            bool flag=false;
            for(int j=i+1;j<n;j++){
                if(a[i]==a[j]&&vis[i]!=vis[j-1]){
                    reverse(a+i,a+j+1);
                    opt.push_back(make_pair(i+1,j+1));
                    flag=true;
                    break;
                }
            }
            if(flag==true) break;
        }
        for(int i=pos+1;i+1<n;i++){
            if(a[i]==b[pos]&&a[i+1]==b[pos-1]){
                reverse(a+pos,a+i+1);
                opt.push_back(make_pair(pos,i+2));
                return solve(a,b,n,pos+1);
            }
        }
        return false;
    }
}
void work(){
    int n;
    cin>>n;
    opt.clear();
    int a[501],b[501];
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    if(solve(a,b,n,0)==true){
        cout<<"YES\n";
        cout<<opt.size()<<'\n';
        for(pair<int,int> now:opt) cout<<now.first<<" "<<now.second<<'\n';
    }else{
        cout<<"NO\n";
    }
    return ;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}
/*
1
9
3 3 3 3 3 4 1 3 3
3 3 3 3 4 1 3 3 3
*/