j124. 3. 石窟探險
Tags : APCS dfs
Accepted rate : 465人/480人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-10-24 13:17

Content

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

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

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

Input

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

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

Output

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

Sample Input #1
2 6 0 8 14 0 0 0 10 0 4 0 0
Sample Output #1
26
Sample Input #2
5 2 10 0 0 0 8 0 0 17 0 0 0
Sample Output #2
26
測資資訊:
記憶體限制: 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
Hint :

範例測資一

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

範例測資二

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

Tags:
APCS dfs
出處:
2022年10月APCS [管理者: algo.seacow@...(演算法海牛) ]


ID User Problem Subject Hit Post Date
33793 yoshi950325@...(第四象限) j124
14 2023-02-03 15:20
33777 tttest(testunknown) j124
C++ 詳解
6 2023-02-02 11:48
33678 luray0601@gm...(QWERTYPIG) j124
C++題解
20 2023-01-20 17:45
33656 a110608@ctes...(鍾均) j124
25 2023-01-18 20:56
33128 e002933(徐MAN) j124
241 2022-12-03 12:29