构造、排序

题目链接

由于操作一的存在序列实际上是一个环，操作一就是旋转这个环。

首先使用序列 $b$ 对序列 $a$ 进行重标，然后对序列 $a$ 从小到大排序。

考虑操作二，其实就是把序列的后 $n-1$ 个元素看成一个环，然后旋转这个环。也就是说其实可以把 $a_1$ 隔离出来。

于是做法就有了：模拟插入排序，一开始有序区只有 $1$ 一个元素，每次如果 $a_1$ 不在有序区内就把 $a_1$ 插入到有序区。

分析操作次数：每个元素插入排序至多需要 $(n-2)$ 次操作二，操作一至多执行 $(n-1)$ 次插入待排序元素，整个环被旋转一次之后所有元素的插入操作结束，至多使用操作一 $n$ 次。可能需要至多 $n-1$ 次操作一复位这个环。

粗略分析得到的最坏操作次数为 $n(n-2)+(n-1)+n+(n-1) = n^2 + n -2$ 次，操作上限为 $n^2$ 次，由于次数卡不满能够通过。

时间复杂度 $O(n^2)$。

#include<bits/stdc++.h>
using namespace std;
int n,a[1'005],b[1'005],ex[1'005];
bool on[1'005];
list<int> s;
string ans;
void operation_1(){
    ans.push_back('1');
    s.push_back(s.front());
    s.pop_front();
}
void operation_2(){
    int fro=s.front();
    ans.push_back('2');
    s.pop_front();
    s.push_back(s.front());
    s.pop_front();
    s.push_front(fro);
}
void solution(){
    cin>>n,ans="",s.clear();
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i],ex[b[i]]=i;
    for(int i=1;i<=n;i++) s.push_back(ex[a[i]]);
    set<int> w;
    fill(on+1,on+n+1,0);
    on[1]=1,w.emplace(1);
    for(int i=1;i<=n-1;i++){
        while(on[s.front()]) operation_1();
        int nxt=s.front(),aim=*prev(w.upper_bound(nxt));
        while(s.back()!=aim) operation_2();
        on[nxt]=1,w.emplace(nxt);
        operation_1();
    }
    while(s.front()!=1) operation_1();
    cout<<ans<<'\n';
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}