D. Cyclic Rotation

D. Cyclic Rotation

题意：

给你两串数

你可以对第一串数多次操作： 选择l r满足a[l] == a[r] 将序列a[l]...a[r] 变成 a[l + 1] ... a[r] a[l] 判断最终a能否变成b （b是a的一个排列）

思路：

可以逆向思考 就相当于在b中有连续的 就可以取出一个放到前面任意一个位置

对于b串 k个连续的那么k-1个都可以由前面换位过来 

可以从后往前遍历b数组一一比对a数组  每次b数组遇到当前数与前面数相同时 储存当前数（用cnt数组记录储存的个数） 比对时如果两者相同 两指针都向前移动一位 当两者不相同时 那就判断 a[i]是否有储存的值 有的话直接对应掉 然后a数组指针前移 否则就输出no直到b数组都比对完 都符合就输出yes

#include
#define ll long long
#define ull unsigned long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-4;
const int N = 1e6 + 5;
const int M = 1e5 + 5;
const int mod = 1e9 + 7;
ll n, a[N], b[N], vis[N], cnt[N];
ll pos1[N], pos2[N];
struct node {
    ll num, pos;
}aa[N], bb[N];

bool comp(node a, node b) {
    return a.pos < b.pos;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    for (int i = n, j = n; j >= 1; ) {
        while (b[j] == b[j - 1]) {
            cnt[b[j]]++;
            j--;
            continue;
        }
        if (a[i] == b[j]) {
            i--;
            j--;
        }
        else if (cnt[a[i]]) {
            cnt[a[i]]--;
            i--;
        }
        else {
            cout << "NO\n";
            return;
        }
        
    }
    cout << "YES\n";
}

int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}
 

除了倒序遍历 其实也可以正序

正序方法：

开一个cnt数组 cnt[x] 存储需要从后面移过来多少个x

从前往后比对 如果ai == bj 两指针都往右移一位 如果没对上 分两种情况：

1.如果b[j] == b[j - 1] 说明b[j]可以移位到前面 判断一下前面是否需要该数 需要就直接cnt[b[j]]-1 然后j指针右移

2. b[j] != b[j - 1] 说明当前位置a[i] 需要一个数来对应 自动拿取一个数与ai对应掉 cnt[ai]就加1 i指针右移

当a数组已经遍历完而b数组还没遍历完时 说明前面需要置换过来的数 多于 后面能提供的数 那就不符合条件了 直接输出no

没有输出no 就输出yes即可

两种方法类似 理解了一种 另一种也很好理解 

第一种是倒序的 要先进行b[j] == b[j - 1]判断 是现将可以提供的数储存下来 后续需要时再判断该数是否有储存（重复的统一删除 需要的时候再取）
而第二种是正序 要先判断a[i] == b[j] 因为b数组只能从后面调取数与前面的数置换 前面能对应上的肯定是对应了的 （先拿取 再减重复的）