CF-1079-B. Array and Permutation · znzryb
## 题目大意
给定一个长度为 $n$ 的排列 $p$ 和一个长度为 $n$ 的数组 $a$。
你可以进行任意次操作，每次操作选择一个下标 $i$（$1 \le i < n$），然后执行以下两种之一：
- 把 $p_i$ 的值覆盖为 $p_{i+1}$（即 $p_i := p_{i+1}$）
- 把 $p_{i+1}$ 的值覆盖为 $p_i$（即 $p_{i+1} := p_i$）
也就是说，每次选两个相邻元素，把其中一个的值复制到另一个上。
判断是否能通过若干次操作，把排列 $p$ 变成数组 $a$。
**样例解释：**
第一组：$p = [1, 2, 3]$，$a = [1, 2, 2]$。选 $i = 2$，把 $p_2$ 的值复制到 $p_3$，得到 $[1, 2, 2]$，与 $a$ 相同，输出 `YES`。
第二组：$p = [3, 1, 2, 4]$，$a = [3, 4, 2, 2]$，无论如何操作都无法得到 $a$，输出 `NO`。
第三组：$p = [1, 3, 2, 5, 4]$，$a = [3, 3, 3, 5, 4]$。先选 $i = 1$，把 $p_2$ 的值复制到 $p_1$，得到 $[3, 3, 2, 5, 4]$；再选 $i = 2$，把 $p_2$ 的值复制到 $p_3$，得到 $[3, 3, 3, 5, 4]$，与 $a$ 相同，输出 `YES`。
## 思路讲解
使用类似于双指针的做法，判断这个 A 数组是去重以后是否是 P 数组 P 排列的子序列。具体来说，在实现当中，我们是使用 P 排列去对应 A 的这个数组，去对应 A 数组，就是你可以理解为我们用一个 PI 去消 AJ 去消 A 数组中的元素，那么这个 pi 当然是可以一直消一直消，可以消除连续的 aj 的元素，只要 aj 和 pi 相等，连续的相等就可以。但是 pi 一旦遇到了第一个和自己不相等的 aj 就会停下来。
```cpp
void Solve() {
ll N;
cin >> N;
vector<ll> P(N+2),A(N+2);
for (int i=1;i<=N;++i) {
cin>>P[i];
}
for (int i=1;i<=N;++i) {
cin>>A[i];
}
ll bp=1;
for (ll i=1;i<=N;++i) {
bool isbreak=false;
for (ll j=bp;j<=N;++j) {
if (P[i]!=A[j]) {
bp=j;
isbreak=true;
break;
}
}
if (!isbreak) {
bp=N+1;
}
}
if (bp==N+1) {
cout<<"YES\n";
}else {
cout<<"NO\n";
}
}
```
## AC代码
AC
[https://codeforces.com/contest/2197/submission/362443575](https://codeforces.com/contest/2197/submission/362443575)
::: 源代码
```cpp
/**
* Problem: B. Array and Permutation
* Contest: Codeforces Round 1079 (Div. 2)
* Judge: Codeforces
* URL: https://codeforces.com/contest/2197/problem/B#
* Created: 2026-02-11 23:03:41
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\n";
#define debug3d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " [\n"; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
{ \
cerr << " ["; \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k]; \
cerr << "]\n"; \
} \
cerr << " ]\n"; \
} \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N;
cin >> N;
vector<ll> P(N+2),A(N+2);
for (int i=1;i<=N;++i) {
cin>>P[i];
}
for (int i=1;i<=N;++i) {
cin>>A[i];
}
ll bp=1;
for (ll i=1;i<=N;++i) {
bool isbreak=false;
for (ll j=bp;j<=N;++j) {
if (P[i]!=A[j]) {
bp=j;
isbreak=true;
break;
}
}
if (!isbreak) {
bp=N+1;
}
}
if (bp==N+1) {
cout<<"YES\n";
}else {
cout<<"NO\n";
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2197/submission/362443575
*/
```
:::
## 心路历程（WA，TLE，MLE……）