CF1698 F

CF1698 F

不错的题目。

考虑必要条件，也就是不变量，发现操作不改变相邻二元组集合，且不能改变 \(a_1,a_n\)。那么必要条件就是 \(a,b\) 相邻二元组集合相等和 \(a_1=b_1,a_n=b_n\)。

通过构造证明充分性。

对于此类从 \(a\) 操作到 \(b\) 的问题，且操作可逆，不妨考虑中间状态 \(c\)，考虑如何操作使得 \(a\rightarrow c,b\rightarrow c\)。

设目前操作前 \(i\) 为 \(a,b\) 对应相等，\(a_i=x,a_{i+1}=y,b_{i+1}=z\)，首先分别考察 \(a_{i\dots n}\) 中有无 \(zx\) 和 \(b_{i\dots n}\) 中有无 \(yx\)，有的话直接换。

否则猜测必然存在 \(a\) 使得 \(ax\) 在 \(a,b\) 同时存在，考察在 \(a_{i\dots n}\) 和 \(b_{i\dots n}\)，对于任意字符 \(p\)，形如 \(px\) 和 \(xp\) 的个数，由于目前存在 \(xy\) 和 \(xz\)，那么它们在 \(a,b\) 中相差不超过 \(2\)。

目前已经出现 \(4\) 个 \(xp\) 的形式，且 \((p,x)\) 在 \(a,b\) 中出现次数相同，要使得 \(px\) 和 \(xp\) 在 \(a,b\) 中相差不超过 \(2\)，那么必然存在一组对应的 \(px\) 存在，那么总操作次数不超过 \(2n\)，每次暴力查找，复杂度 \(\mathcal{O}(n^2)\)。

或者考虑连边 \((a_i,a_{i+1})\)，用欧拉回路做即可，实现差不多，都很简单。

类似方法：CF1458 D

#include <bits/stdc++.h>
#define file_in(x) (freopen(#x".in", "r", stdin))
#define file_out(x) (freopen(#x".out", "w", stdout))
#define ll long long
#define vi vector
#define pb push_back
#define db double
#define pr pair <int, int>
#define mk make_pair
#define fi first
#define se second
#define lb(x) (x & (-x))

using namespace std;

char _c; bool _f; template <class T> void IN(T &x) {
  _f = x = 0; while (_c = getchar(), !isdigit(_c)) {if (_c == '-') _f = 1;}
  while (isdigit(_c)) {x = x * 10 + _c - '0', _c = getchar();} if (_f) x = -x;
}

template <class T> void _write(T x) {
  if (x < 0) return putchar('-'), _write(-x), void();
  if (x > 9) _write(x / 10);
  putchar('0' + x % 10);
}
template <class T> void write(T x) {_write(x), putchar('\n');}
template <class T> void write_s(T x) {_write(x), putchar(' ');}
template <class first, class... rest> void write(first fir, rest... res) {
  write_s(fir), write(res...);
}

#define debug(...) (_debug(#__VA_ARGS__, __VA_ARGS__))
template <class T> void _debug(const char *format, T x) {
  cerr << format << " = " << x << endl;
}
template <class first, class... rest>
void _debug(const char *format, first fir, rest... res) {
  while (*format != ',') cerr << *format++;
  cerr << " = " << fir << ',', _debug(format + 1, res...);
}

bool START;

const int N = 505;

int t_c, n, a[N], b[N], p[N];
vi <pr> va, vb;

bool END;

bool chk() {
  if (a[1] != b[1] || a[n] != b[n]) return 1;
  for (int i = 0; i < n - 1; ++i) if (va[i] != vb[i]) return 1;
  return 0;
}

void opa(int l, int r) {
  va.pb(mk(l, r));
  for (int i = 1; 2 * i <= r - l + 1; ++i) swap(a[l + i - 1], a[r - i + 1]);
}

void opb(int l, int r) {
  vb.pb(mk(l, r));
  for (int i = 1; 2 * i <= r - l + 1; ++i) swap(b[l + i - 1], b[r - i + 1]);
}

signed main() {
  IN(t_c);
  while (t_c--) {
    IN(n), va.clear(), vb.clear();
    for (int i = 1; i <= n; ++i) IN(a[i]);
    for (int i = 1; i <= n; ++i) IN(b[i]);
    for (int i = 1; i < n; ++i) {
      va.pb(mk(min(a[i], a[i + 1]), max(a[i], a[i + 1])));
      vb.pb(mk(min(b[i], b[i + 1]), max(b[i], b[i + 1])));
    }
    sort(va.begin(), va.end()), sort(vb.begin(), vb.end());
    if (chk()) {puts("NO"); continue;}
    va.clear(), vb.clear(), puts("YES");
    for (int i = 1; i < n; ++i) {
      int x = a[i], y = a[i + 1], z = b[i + 1];
      bool fl = 0;
      for (int j = i + 1; j < n; ++j) if (a[j] == z && a[j + 1] == x) {opa(i, j + 1), fl = 1; break;}
      if (fl) continue;
      for (int j = i + 1; j < n; ++j) if (b[j] == y && b[j + 1] == x) {opb(i, j + 1), fl = 1; break;}
      if (fl) continue;
      for (int j = 0; j <= n; ++j) p[j] = 0;
      for (int j = i + 1; j < n; ++j) if (a[j + 1] == x) p[a[j]] = j + 1;
      for (int j = i + 1; j < n; ++j) if (b[j + 1] == x && p[b[j]]) {opa(i, p[b[j]]), opb(i, j + 1); break;}
    }
    write((int)va.size() + vb.size());
    for (auto x : va) write(x.fi, x.se);
    reverse(vb.begin(), vb.end());
    for (auto x : vb) write(x.fi, x.se);
  }
  return 0;
}