题解：CF1698F Equal Reversal

koukou · 2026-07-24 14:53:07 · 题解

首先 a_1,a_n 不会改变，b 同理，所以有解需要满足 a_1=b_1,a_n=b_n。

接着你发先一次操作不会改变相邻数对的集合，即 \{a_i,a_{i+1}\}。于是要求 a,b 这两个集合相同。

你从图论的角度考虑是一样的，这两个条件是充分且必要的。

考虑有解的情况，增量构造，假设现在 a,b 的前 i 个已经全都相等，需要使得 a_{i+1}=b_{i+1}。

因为有解，所以 a 数组中 i 后面必然存在一对数等于 (b_i,b_{i+1})，当然因为无序，也可以等于 (b_{i+1},b_i)。

分类讨论，如果存在 (b_{i+1},b_i) 这一对则直接操作整个区间，可以使得第 i+1 位相等。

否则一定会存在一个区间，包含 (b_i,b_{i+1}) 且可以被操作，操作一下再使用上面的方法即可。证明可以从图论角度证明。

然后这个东西的操作次数是一个 2\times n 的。

:::success[代码]{open}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e2 + 5;
int T, n, a[N], b[N];
vector<pair<int, int>> ans;
void rev(int l, int r)
{
    ans.push_back({l, r});
    reverse(a + l, a + r + 1);
    return;
}
bool work(int i)
{
    for(int j = i; j < n; j++)
    {
        if(a[j] == b[i] && a[j + 1] == b[i - 1])
        {
            rev(i - 1, j + 1);
            return 1;
        }
    }
    int p = -1;
    for(int j = i; j < n; j++)
    {
        if(a[j] == b[i - 1] && a[j + 1] == b[i])
        {
            p = j;
            break;
        }
    }
    if(p == -1) return 0;
    vector<int> pos(n + 1, -1);
    for(int j = i - 1; j <= p; j++) pos[a[j]] = j;
    int l = -1, r = -1;
    for(int j = p + 1; j <= n; j++)
    {
        if(pos[a[j]] != -1)
        {
            l = pos[a[j]], r = j;
            break;
        }
    }
    if(l == -1) return 0;
    rev(l, r);
    for(int j = i; j < n; j++)
    {
        if(a[j] == b[i] && a[j + 1] == b[i - 1])
        {
            rev(i - 1, j + 1);
            return 1;
        }
    }
    return 0;
}
void solve()
{
    cin >> n;
    ans.clear();
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];
    if(a[1] != b[1] || a[n] != b[n])
    {
        cout << "NO\n";
        return;
    }
    vector<pair<int, int>> pa, pb;
    for(int i = 1; i < n; i++)
    {
        int x = a[i], y = a[i + 1];
        if(x > y) swap(x, y);
        pa.push_back({x, y});
        x = b[i], y = b[i + 1];
        if(x > y) swap(x, y);
        pb.push_back({x, y});
    }
    sort(pa.begin(), pa.end());
    sort(pb.begin(), pb.end());
    if(pa != pb)
    {
        cout << "NO\n";
        return;
    }
    for(int i = 2; i < n; i++)
    {
        if(a[i] == b[i]) continue;
        if(!work(i))
        {
            cout << "NO\n";
            return;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(a[i] != b[i])
        {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n" << ans.size() << "\n";
    for(auto [l, r] : ans) cout << l << " " << r << "\n";
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    cin >> T;
    while(T--) solve();
    return 0;
}

:::