被这题干爆了
考虑把环压缩成块。这样一次操作就是,选择两个相邻的块,把左边块长度减 \(1\),右边块长度加 \(1\)。
特判 \(a, b\) 所有块长都是 \(1\) 的情况,这种情况不能操作。
排除掉上面的情况,我们断言:有解的充要条件是,存在某一种 \(a\) 的顺序,使得 \(b\) 是它的子序列。
充分性:因为存在长度 \(> 1\) 的块,所以块的位置可以随意移动,只要保持相对位置不变即可。
必要性:考虑证明它的逆否命题。如果不是子序列,那 \(a\) 不可能凭空中间冒出一个块使得有解,因为只能扩充或压缩块。
然后这个东西朴素 \(O(n^2)\) 判定即可。
code
// Problem: C - Roller
// Contest: AtCoder - AtCoder Regular Contest 154
// URL: https://atcoder.jp/contests/arc154/tasks/arc154_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;
const int maxn = 5050;
int n, m1, m2, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn];
bool vis[maxn];
inline bool check() {
int j = 1;
for (int i = 1; i <= m1; ++i) {
if (j <= m2 && e[i] == d[j]) {
++j;
}
}
return j > m2;
}
void solve() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &b[i]);
}
m1 = m2 = 0;
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && a[j + 1] == a[i]) {
++j;
}
c[++m1] = a[i];
}
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && b[j + 1] == b[i]) {
++j;
}
d[++m2] = b[i];
}
if (c[1] == c[m1] && m1 > 1) {
--m1;
}
if (d[1] == d[m2] && m2 > 1) {
--m2;
}
if (m1 == n && m2 == n) {
for (int i = 1; i <= n; ++i) {
if (a[i] != b[i]) {
puts("No");
return;
}
}
puts("Yes");
return;
}
for (int i = 1; i <= m1; ++i) {
int t = 0;
for (int j = i; j <= m1; ++j) {
e[++t] = c[j];
}
for (int j = 1; j < i; ++j) {
e[++t] = c[j];
}
if (check()) {
puts("Yes");
return;
}
}
puts("No");
}
int main() {
int T = 1;
scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}