CF28B pSort 题解
CF28B pSort
题意
给定一个含有\(n\)个元素的数列，第\(i\)号元素开始时数值为\(i\),元素\(i\)可以与距离为\(d[i]\)的元素进行交换。再给定一个\(1-n\)的全排列，问初始的数列可否交换成给定的样式。
输入
第一行一个整数\(n\)，第二行\(n\)个互不相同的整数表示目标数列，第三行\(n\)个整数表示\(d[i]\)。
输出
如果能交换到给定样式，输出"YES"，否则输出"NO"。
数据范围
\(1 <= n <= 100\)
题解
<1>.首先看到对于第\(i\)个数，是可以跟\(i-d[i]\)和\(i d[i]\)交换位置的。考虑对于一个序列\(a_1,a_2,a_3...a_n\)，任意打乱这个它的顺序使它成为\(b_1,b_2,b_3...b_n\)，通过若干次交换相邻的数是可以使\(a[\ ]\)变为\(b[\ ]\)的。
证明：类似冒泡排序，定义每一个数\(a_i\)的优先级是 \(它在a[\ ]中的位置与它在b[\ ]中的位置\ 的距离\)，那么通过冒泡排序，是可以在这种优先级下使\(a[\ ]\)变有序的，也就是让\(a[\ ]\)变为\(b[\ ]\)。
<2>:那么考虑在原数列中，如果第\(i\)个数可以与\(j\)交换位置，且\(j\)可以与\(k\)交换位置，那么\(i,j,k\)就可以交换为它们三个数的任意排列(1.中的结论)，当然这是对任意多个数都成立的。
所以我们把可以互相交换(间接或直接)的数的下标看成一个集合，记为\(U\)；那么对于\(U\)中的每一个元素\(i\)，如果\(a[i](原始序列)\)在目标序列的位置\(v\)也在\(U\)中，那原序列的第\(i\)位就是符合条件的
<3>如果所有的\(a[i](原始序列)\)都是符合要求的，就说明所有的数字都可以换到目标序列上的位置，输出“YES”；只要有一个数字不符合要求，那么原序列就不能变为目标序列，输出"NO"
那么事实上
设原序列为\(a[\ ]\)，目标序列为\(target[\ ]\)；将每一个\(a[i]\)看作节点，向\(a[i d[i]]\)和\(a[i-d[i]]\)连边，只需要判断\(a[i]\)和\(target[i]\)是否联通即可
可以用并查集，也可以用floyd
代码
#include<bits/stdc .h>using namespace std;const int maxn = 105;int n, a[maxn], target[maxn], d[maxn];int father[maxn];int get_fa(int x) {if(x == father[x]) return x;return father[x] = get_fa(father[x]);}inline void merge(int x, int y) {int fa_x = get_fa(x);int fa_y = get_fa(y);if(fa_x == fa_y) return ;father[fa_y] = fa_x;}int main(){ ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; for(int i = 1; i <= n; i) { cin >> target[i]; } for(int i = 1; i <= n; i) { cin >> d[i]; } for(int i = 1; i <= n; i) { a[i] = father[i] = i; } /*思路：判断a[i]与target[i]是否连通 */ for(int i = 1; i <= n; i) { int p1 = i - d[i]; int p2 = i d[i]; if(p1 >= 1) { merge(a[i], a[p1]); } if(p2 <= n) { merge(a[i], a[p2]); } } for(int i = 1; i <= n; i) { int fa1 = get_fa(a[i]); int fa2 = get_fa(target[i]); if(fa1 != fa2) { cout << "NO\n"; exit(0); } } cout << "YES"; return 0;}