j124. 3. 石窟探險 - 高中生程式解題系統

內容

有一組探險隊要去一個樹狀結構的石窟內探險，該石窟內有 $n$ 個石室，第 $i$ 個石室有一個編號 $a_i$，若 $a_i$ 為偶數則會有 $2$ 條分支(左分支和右分支)，若 $a_i$ 為奇數則有 $3$ 條分支(左分支、中分支和右分支)。

探險隊想要紀錄這個石窟的結構，每次只要第一次走到一個新的石室，就會將該石室的編號記錄在紙上，並由左到右依序走訪該石室的分支們，若走到一條死路則會在紙上紀錄一個數字 $0$，若該石室已經走完所有分支則退回到上一個石室，走訪完整個石窟後在紙上得到上一個數字序列。

探險隊回到基地後忘記計算了這個石窟內所有相鄰的石室編號相差取絕對值的總和，請幫助探險隊從紙上的序列推算出該數值。

輸入說明

輸入一個整數個數不超過 $10^6$ 的整數序列，石室的編號不超過 $10^5$，並保證造出來的樹深度不超過 $40$。

子題配分
(20%): 石室數量最多不超過 $20$ 個，編號均為偶數
(20%): 石室數量最多不超過 $10^3$ 個
(60%): 石室最大深度不超過40層，而且編號和石室編號不超過 $10^5$，答案可能會超過 $2^{31}$。

輸出說明

輸出一個整數代表這個石窟內所有相鄰的石室編號相差取絕對值的總和，答案大小有可能會超過 $2^{31}$。

範例輸入 #1

2 6 0 8 14 0 0 0 10 0 4 0 0

範例輸出 #1

範例輸入 #2

5 2 10 0 0 0 8 0 0 17 0 0 0

範例輸出 #2

測資資訊：

記憶體限制： 256 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 , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M

提示：

範例測資一

|2 - 6| + |6 - 8| + |8 - 14| + |2 - 10| + |10 - 4| = 26

範例測資二

|5 - 2| + |2 - 10| + |5 - 8| + |5 - 17| = 26

標籤:

APCS dfs 樹

出處:

2022年10月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
37577	ishinlo@gmai ... (駱怡心)	j124	石窟探險（遞迴解法）	718	2023-09-17 17:41
41050	glps1004@gma ... (Ian)	j124	APCS202210	151	2024-06-28 15:37
40861	076linqungyo ... (076)	j124	stack解	149	2024-06-16 14:45
38897	youtong826 (Youtong0826)	j124	不用自己寫一個樹的結構出來只要利用dfs模擬就行了	581	2024-01-01 21:30
37983	haochiwu (教授加博士先生)	j124	針對C malloc的部分	358	2023-10-21 23:50