以为是拓扑排序之类的东西，结果一看 tag 是构造，已老实。

思路

注意到当

b

有一段连续相同数的时候，对于最后一个经过这一段的操作必须覆盖整个这一段，因此考虑将一段相同的数缩成一个点，记作

c_1,\dots,c_k

。

有解的条件为：

c

序列是

a

序列的一个子序列。这个条件显然是充要的：

充分性：记 $c_i$ 在 $a$ 中对应 $a_{pos_i}$ ，在 $b$ 中对应 $b_{l_i \sim r_i}$ 。我们可以通过先顺序将 $pos_i$ 推到 $l_i$ ，再逆序将 $pos_i$ 推到 $r_i$ 的构造方式将 $a$ 序列变为 $b$ 序列。因为 $pos_i$ 是递增的，所以方案肯定能将 $a$ 变为 $b$ ；同时因为对于一个需要花两步的 $c_i$ ，长度必定 $\geq 3$ ，因此步数 $\leq n$ 。

必要性：反证法。若 $\exist i < j,pos_i > pos_j$ ，分讨 $l_i,r_j,pos_i,pos_j$ 的位置关系，容易发现无论什么情况都不能使将 $c_i,c_j$ 同时合法。

直接按照证明充分性的构造方式输出即可。

Code

CPP

#include <bits/stdc++.h>
#define re register
#define fst first
#define snd second

using namespace std;

typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int N = 3e5 + 10;
int n;
int arr[N],brr[N];
vector<pii> v;
vector<int> pos;
vector<pip> ans;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

int main(){
    n = read();
    for (re int i = 1;i <= n;i++) arr[i] = read();
    for (re int i = 1;i <= n;i++) brr[i] = read();
    for (re int i = 1,lst = 1;i <= n + 1;i++){
        if (brr[i] != brr[lst]){ v.push_back({lst,i - 1}); lst = i; }
    }
    for (re int i = 0,j = 1;i < v.size();i++){
        while (j <= n && arr[j] != brr[v[i].fst]) j++;
        if (j == n + 1) return puts("NO"),0;
        pos.push_back(j);
    }
    for (re int i = 0;i < v.size();i++){
        if (pos[i] > v[i].fst) ans.push_back({0,{v[i].fst,pos[i]}});
    }
    for (re int i = v.size() - 1;~i;i--){
        if (pos[i] < v[i].snd) ans.push_back({1,{pos[i],v[i].snd}});
    } printf("YES\n%d\n",ans.size());
    for (pip p:ans) printf("%c %d %d\n",p.fst ? 'R' : 'L',p.snd.fst - 1,p.snd.snd - 1);
    return 0;
}

[题解]P10297 [CCC 2024 S3] Swipe

文章操作

思路

Code

相关推荐

评论

[题解]P10297 [CCC 2024 S3] Swipe