ETH官方钱包

切換
舊版
前往
大廳
主題

ZeroJudge - d767: 血緣關係 解題心得

Not In My Back Yard | 2019-03-23 19:26:13 | 巴幣 0 | 人氣 393

題目連結:


題目大意:
給定兩正整數 N 、 Q (N ≦ 30, 000,Q ≦ N ^ 2),代表有 N 個人(編號 1 ~ N)、有 Q 筆詢問,並接著 N 列輸入。

每列輸入由先至後編號為 1 ~ N 。每列有不定量的數字(以數字「0」代表這列輸入的結尾),而第 i 列的代表編號 i 的人之兒女的編號(「0」不計,而兒女數目不會超過六個且兒女編號必大於父母編號)。

接著有 Q 列輸入,每列給定兩正整數 A 、 B (1 ≦ A 、 B ≦ N),代表要問編號 A 的人和編號 B 的人最近的共同祖先是誰?親等為多少?



範例輸入:
7 6
2 3 0
4 5 0
6 7 0
0
0
0
0
4 5
4 2
4 4
4 3
1 7
2 3


範例輸出:
2 2
2 1
4 0
1 3
1 2
1 2


解題思維:
先按照輸入的資訊將編號 1 ~ N 的人之子女全部存進陣列裡。

因為兒女的編號必大於父母,因此整棵血緣關係樹的根必定是編號 1 的人。因此我們從編號 1 開始,對這棵樹做深度優先搜尋(DFS)。

每當我們到達一個節點,根據我們現在到達的樹的深度,去賦予此節點相同的值(代表其在多深的地方)。並且一路上要記錄現在 DFS 走的路徑,然後去看當前節點往上 1 、 2 、 4 、 8 …… 個節點的節點編號為何,將其存放下來。

然後到詢問 A 、 B 的最近祖先跟親等時,先看 A 、 B 所在的深度是否相同。如果不同,就調整至相同(用上面有存的 1 、 2 、 4 、 8 …… 個節點的資訊去快速逼近);否則,就慢慢地往上一個節點直到 A 、 B 到達同一個節點。

由上面調整 A 、 B 的過程即可知最近祖先和親等。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
這題超好玩,可以達到一題三解
(1) RMQ轉LCA
(2) Tarjar 離線查詢算法
(3) 倍增法
(1)(2) 可以對應 Morris128大大 在 PCHome的文章 (1)=online (2)=offline
上述三種方法可以達到0.3s以內,你看到記憶體爆多的就是Tarjar,反而是RMQ方法比他小孩可以支援修改
(3)的倍增法是基於樓主的想法再進一步加速的方式,概念上類似 SparseTable 的建表概念
連結我就放這邊,裡面有註解( www.codepile.net/pile/VrRp360N )

2019-03-25 07:48:08

更多創作