題目鏈接

題目描述

有 $n$ 個小朋友，編號 $1～n$。

每個小朋友都拿著一個號碼牌，初始時，每個小朋友拿的號碼牌上的號碼都等于其編號。

每個小朋友都有一個幸運數(shù)字，第 $i$ 個小朋友的幸運數(shù)字為 $d_i$。

對于第 $i$ 個小朋友，他可以向第 $j$ 個小朋友發(fā)起交換號碼牌的請求，當且僅當 $|i?j|=d_i$ 成立。

注意，請求一旦發(fā)出，對方無法拒絕，只能立刻進行交換。

每個小朋友都可以在任意時刻發(fā)起任意多次交換請求。

給定一個 $1～n$ 的排列 $a1,a2,\dots ,an$。

請問，通過小朋友相互之間交換號碼牌，能否使得第 i 個小朋友拿的號碼牌上的號碼恰好為 $a_i$，對 $i\in [1,n]$ 均成立。

輸入格式

第一行包含整數(shù) n。

第二行包含 n 個整數(shù) $a1,a2,\dots ,an$。

第三行包含 n 個整數(shù) $d1,d2,\dots ,dn$。

輸出格式

共一行，如果能做到，則輸出 YES，否則輸出 NO。

數(shù)據(jù)范圍

所有測試點滿足 1≤n≤100，1≤di≤n，保證 a1～an 是一個 1～n 的排列。

樣例

輸入樣例1：

5 5 4 3 2 1 1 1 1 1 1

輸出樣例1：
YES

輸入樣例2：

7 4 3 5 1 2 7 6 4 6 6 1 6 6 1

輸出樣例2：
NO

分析：

聯(lián)通塊（并查集）

交換方式唯一，說白了就是一個可以互相交換的小團體翻來覆去的換，可以交換達到的任意兩點絕對可達

• 考慮以聯(lián)通塊編號為數(shù)組下標，構(gòu)建一個聯(lián)通塊內(nèi)可達點集
• 同樣以下邊所在聯(lián)通塊編號為下標，標注一個題目要求達的點集，比較集合相等即可

code

#include<bits/stdc++.h> using namespace std; const int N = 1e3+9; vector <int> A[N],B[N]; int fa[N], a[N] , d[N];int find (int x) {if(fa[x]==x) return x;else return fa[x]= find(fa[x]); }int main() {int n;scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d",&a[i]);for (int i = 1; i <= n; i ++ ) scanf("%d",&d[i]);for (int i = 1; i <= n; i ++ ) fa[i] =i;for (int i = 1; i <= n; i ++ ){if(i+d[i]<=n) fa[find (i+d[i])] =find (i);if(i-d[i]>=1) fa[find (i-d[i])] =find (i);}for (int i = 1; i <= n; i ++ ){A[find (i)].push_back (i);B[find (i)].push_back (a[i]);}for (int i = 1; i <=n; i ++ ){sort (B[i].begin(),B[i].end());if(A[i]!=B[i]){puts ("NO");return 0;}}puts("YES");return 0; }

總結(jié)

以上是生活随笔為你收集整理的错题本 （并查集） acwing 4084.号码牌的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。