【sorting+并查集】代码源每日一题div2 psort

短命女 2024-03-16 18:43 62阅读 0赞

[pSort - 题目 - Daimayuan Online Judge][pSort - _ - Daimayuan Online Judge]

题意：

![1891c1dfb7284d6aa969e722d240012c.png][]

思路：

这是个很常见的套路

固定距离交换元素，用并查集即可

这道题中，用并查集染色，建完图之后，只需要去判一个连通块里的元素是不是恰好是那几个不同位置的元素即可

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=1e5+10;
    
    int N;
    int a[mxn],b[mxn],d[mxn];
    int F[mxn];
    
    int find(int x){
    	return F[x]=(x==F[x])?x:find(F[x]);
    }
    void join(int u,int v){
    	int f1=find(u),f2=find(v);
    	if(f1!=f2) F[f1]=f2;
    }
    void solve(){
    	cin>>N;
    	for(int i=1;i<=N;i++) F[i]=i;
    	for(int i=1;i<=N;i++) a[i]=i;
    	for(int i=1;i<=N;i++) cin>>b[i];
    	for(int i=1;i<=N;i++) cin>>d[i];
    	for(int i=1;i<=N;i++){
    		if(i+d[i]<=N) join(i,i+d[i]);
    		if(i-d[i]>=1) join(i,i-d[i]);
    	}
    	for(int i=1;i<=N;i++){
    		if(i+d[i]<=N){
                if(find(b[i])!=find(b[i+d[i]])){
                    cout<<"NO"<<'\n';
                    return;
                }
    		}
            if(i-d[i]>=1){
                if(find(b[i])!=find(b[i-d[i]])){
                    cout<<"NO"<<'\n';
                    return;
                }
            }
    	}
    	cout<<"YES"<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[pSort - _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/11/problem/876
[1891c1dfb7284d6aa969e722d240012c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b7a1f573c6694e5e893b7995994c815f.png