q371. 6. 完滿二元搜尋樹 - 高中生程式解題系統

Content

　　有一 $K$ 層之完滿二元樹（Full Binary Tree），其中節點按中序遍歷（Inorder Traversal）順序編號 $1\sim 2^K-1$，以 $K=4$ 為例，如下圖：

　　有 $Q$ 筆詢問，詢問包含以下幾個種類：

輸出節點 $x$ 之父節點（Parent）編號。
輸出節點 $x$ 之左子節點（Left Child）編號。
輸出節點 $x$ 之右子節點（Right Child）編號。
輸出節點 $x$ 之左兄弟節點（Left Cousins）編號。
輸出節點 $x$ 之右兄弟節點（Right Cousins）編號。
輸出以節點 $x$ 作為根節點（Root）之子樹（Subtree）節點編號和。

Input

　　輸入的第一行有兩個正整數 $K, Q$（$1\le K\le 32$, $1\le Q\le 10^6$），代表完滿二元數樹的高度與詢問數量。
　　接下來有 $Q$ 行，每行包含兩個正整數 $o,x$（$1\le o\le 6$, $1\le x<2^K$），代表第 $o$ 種詢問與其詢問的節點 $x$。

Output

　　每筆詢問請單獨輸出於一行。
　　對於詢問 $1\sim 5$，請輸出目標節點，若該節點不存在，則輸出 $-1$；對於詢問 $6$，請輸出該子樹的所有節點編號總和（包含 $x$）。

Sample Input #1

Sample Output #1

Sample Input #2

Sample Output #2

-1
9
-1
-1
-1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1K
公開測資點#5 (5%): 1.0s , <1K
公開測資點#6 (5%): 1.0s , <1K
公開測資點#7 (5%): 1.0s , <1K
公開測資點#8 (5%): 1.0s , <1K
公開測資點#9 (5%): 1.0s , <1K
公開測資點#10 (5%): 1.0s , <50M
公開測資點#11 (5%): 1.0s , <50M
公開測資點#12 (5%): 1.0s , <50M
公開測資點#13 (5%): 1.0s , <50M
公開測資點#14 (5%): 1.0s , <50M
公開測資點#15 (5%): 1.0s , <50M
公開測資點#16 (5%): 1.0s , <50M
公開測資點#17 (5%): 1.0s , <50M
公開測資點#18 (5%): 1.0s , <50M
公開測資點#19 (5%): 1.0s , <50M

Hint ：

本題共有 $8$ 個子題，每個子題有多筆測資。
第一子題：　$K\le 10$、$Q\le 100$、$o=1$，全部解出可得 $10$ 分。
第二子題：　$K\le 10$、$Q\le 100$、$o=2,3$，全部解出可得 $10$ 分。
第三子題：　$K\le 10$、$Q\le 100$、$o=4,5$，全部解出可得 $10$ 分。
第四子題：　$K\le 10$、$Q\le 100$、$o=6$，全部解出可得 $20$ 分。
第五子題：　$K\le 32$、$o=1$，全部解出可得 $10$ 分。
第六子題：　$K\le 32$、$o=2,3$，全部解出可得 $10$ 分。
第七子題：　$K\le 32$、$o=4,5$，全部解出可得 $10$ 分。
第八子題：　$K\le 32$、$o=6$，全部解出可得 $20$ 分。

Tags:

二進位

出處:

113學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」