Trick : 排列映射技巧

Trick : 排列映射技巧

假设给你排列 $a$ 以及排列 $b$ ，现在需要把 $a$ 变成 $b$ 。

假设存在数组 $c_i$ ，令 $c_{b_i}=i$ ，令 $a_i=c_{a_i}$ ，即可完成映射，使得 $b$ 变为 $1,2,\cdots ,n$ ，相当于变成排序问题。

void mapping(){for(int i = 1; i <= n; i ++){cin >> a[i];}for(int i = 1; i <= n; i ++){cin >> x;b[x] = i;}for(int i = 1; i <= n; i ++){a[i] = b[a[i]];}
}

例题

oph is playing a card game. She has $n$ cards and each card has a unique number of $1,2\cdots n$. In this game, Toph can operate the deck of the cards. We may wish to assume that the cards from the top to the bottom of the deck are $p_1,p_2,\cdots p_n$ (a permutation), then each operation must be one of the following two cases:

1. Place the top card at the bottom of the deck, that is, change the order of the deck into $p_2,p_3\cdots p_n,p_1$.
2. Place the second card from the top at the bottom of the deck, that is, change the order of the deck into $p_1,p_3\cdots p_n,p_2$
   Now, you know that the initial order(from top to bottom) of Toph’s deck is $a_1,a_2,\cdots a_n$, and Toph wants to change the order of the deck into $b_1,b_2,\cdots b_n$ after some operations. Please construct the operation sequence to help Toph implement the change.
   Toph has no patience. So the number of operations should not exceed $n^2$.

将 $b$ 映射，相当于对 $a$ 排序了。

发现执行 $n$ 个 $1$ ，$a$ 数组不变。

在其中第 $i$ 执行一次 $2$ ，最后输出的 $a$ 相当于 $a_i$ 与 $a_{i+1}$ 交换了位置。

利用冒泡排序的思想，如果 $b_j<b_{j+1}$ ，输出 $1$ ; 否则输出 $2$ 。

这样最后一个位置一定最大。

每一轮输出 $n$ 个数字即可，可以选择出一个第 $i$ 大元素，共 $n-1$ 轮。

#include<bits/stdc++.h>
using namespace std;
#define int long longint const N = 1100;int n, x, a[N], b[N];void solve(){cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];}for(int i = 1; i <= n; i ++){cin >> x;b[x] = i;}for(int i = 1; i <= n; i ++){a[i] = b[a[i]];}for(int i = 1; i < n; i ++){for(int j = 1; j < n; j ++){if(a[j] > a[j + 1]){swap(a[j], a[j + 1]);cout << '2';}else cout << '1';}cout << '1';}cout << '\n';
}signed main(){ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int T = 1;cin >> T;while (T --){solve();}return 0;
}