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;
}