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;
}