CF-1079-B. Array and Permutation

题目大意

给定一个长度为 $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 就会停下来。

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

源代码

/**
 * 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……）