第一道完全自己想+做出来的一道绿题！！！！！！心情大好（ ，写篇题解记录一下qwq

接下来进入正题。

涉及的知识点：并查集

思路：

• 一些数组，变量的定义：
  $f_i$? 表示 位置 $i$ 的祖先。（注意这里说的是“位置”）
  $dis_i$ 表示可以移动的距离，也就是题目中的 $d$ 数组。
  $goal1_i$ 表示目标数列。

• 如何判断位置为 $i$ 的数可不可以移动到 $j$ 位置上：如果这两个位置的祖先相同就可以。也就是说 $f_i$? 和 $f_j$? 的祖先相同就可以。
  find(j) == find(i) <— 这个就是判断祖先相同的代码

• 什么时候，怎么将两个位置合并：如果位置 $i$ 可以移动到位置 $j$ 上（用 $dis$ 数组判断），就将 $f_i$? 和 $f_j$? 合并。（注意考虑出界问题）
  这一部分的代码↓

        int x,y;
        x = i+dis[i];
        y = i-dis[i];

        if(x <= n){
            f[find(x)] = find(i);
        }
        if(y >= 1){
            f[find(y)] = find(i);
        }

好了，思路差不多了，接下来就放一下代码qwq

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

int n;
int goal1[10009];//目标序列
int dis[10009];
int f[100009];//f[i] 表示位置 i 的祖先 

void init(){
    for(int i=0; i<1000; i++)f[i] = i;
}

int find(int k){//路径压缩
    if(f[k] == k)return k;
    return f[k] = find(f[k]);
}
int main(){

    init();//初始化 

    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> goal1[i];
    }
    for(int i=1; i<=n; i++){
        cin >> dis[i];
        int x,y;
        x = i+dis[i];
        y = i-dis[i];

        if(x <= n){//不出界再合并
            f[find(x)] = find(i);
        }
        if(y >= 1){//不出界再合并
            f[find(y)] = find(i);
        }

    }

    for(int i=1; i<=n; i++){
        int j = goal1[i];
        if(find(j) != find(i)){
            cout << "NO";
            return 0;//只要有一个不行（移动不到目标位置）就输出 "NO"
        }
    }   

   //成功运行到了最后，说明初始数列所有位置上的数都可以移动到目标位置，那就输出 "YES"
    cout << "YES";
    return 0;
} 

（自我感觉马蜂应该不错qwq 可读性比较高qwq）

最后，如果有什么问题欢迎指出！

【题解】CF28B pSort