被这题干爆了
考虑把环压缩成块。这样一次操作就是,选择两个相邻的块,把左边块长度减 \(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;
}
- AtCoder Regular Contest Roller 154atcoder regular contest roller atcoder regular contest 154 beginner atcoder contest 154 atcoder regular contest 165 minimization atcoder regular contest atcoder regular contest 166 atcoder regular contest degree atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest 164