2022/10/23 石窟探險

2023.1.18 PM 09:00 by CBJ

來源 : https://zerojudge.tw/ShowProblem?problemid=j124
出題者 : 2022年10月APCS
標籤 : 遞迴、stack
難易度 : 3

解題想法 : 
此題亦可使用暴力遞迴，但筆者此題使用的是stack解法。

輸入是一個樹的前序遍歷，因此可以利用stack的特性來做讀取，方法是每讀取一個值，就將它推進child[stack.top()]中，且若遇到非0的數值就push進stack，蒐集完child以後就pop，要如何判斷是否蒐集完，可以利用取得child[stack.top()]的長度來判斷，若為偶數則長度為2就蒐集完，若為奇數則長度為3才收集完，判斷方式有很多種，筆者的方式可參考下面的code。

讀取完以後就很容易實作了，只要把每個節點(若child是0需跳過)分別和自己的child相減取絕對值並加總起來即可(節點可用另一個陣列存)，但C/C++記得要開long long。

//C++ language

#include<iostream>
#include<stack> //stack 
#include<vector> //vector 
#include<unordered_set> //unordered_set
using namespace std;
int main(){
    stack<int>stk;
    vector<int> child[int(1e5+1)]={};
    vector<int> v;
    int n; cin>>n;
    stk.push(n); v.push_back(n);
    while(cin>>n){
        child[stk.top()].push_back(n);
        if(child[stk.top()].size() == 2+(stk.top()%2)) stk.pop();
        if(n != 0) stk.push(n), v.push_back(n);
    }
    long long ans=0;
    for(int i: v){
        for(int j: child[i]){
            if(j==0) continue;
            ans+=abs(i-j);
        }
    }
    cout<<ans<<"\n";
    return 0;
}

## Python language

stk=[]
child=[[] for _ in range(100005)]  #勿使用[]*100005
a=[]
def stk_top(): return stk[-1]
def stk_push(x): stk.append(x)
def stk_pop(): stk.pop()
nodes=[int(x) for x in input().split()]
stk_push(nodes[0]); a.append(nodes[0])
for n in nodes[1:]:
    child[stk_top()].append(n)
    if len(child[stk_top()]) == 2+(stk_top()%2): stk_pop()
    if n!=0:
        stk_push(n)
        a.append(n)
ans=0
for i in a:
    for j in child[i]:
        if j==0: continue
        ans+=abs(i-j)
print(ans)

相關文章

分享此文：