網頁

2014年2月28日 星期五

UVa 712 S-Trees

題意:
    第一個數字為樹的深度N,然後有N個xi表示從root到(N-1)每一層的變數xi(例如x3 x1 x2表示root層的變數為x3,第1層變數為x1,第二層變數為x2),接下來一串0和1的序列代表樹的最底層從左到右的値,然後有M個VVL,每個VVL依序表示變數xi的値(例如011表示x1=0,x2=1,x3=1),因此知道xi代表的値後,就能從root走到底層(每層有自己的變數xi,遇到0向左走,1向右走),一直走到底層看最底層是什麼數字。

想法:
    從root開始往下走,先將root編號n為0,往左下走就乘以2,往右下走就乘以2加1,直到最底層,看編號n是多少就輸出底層序列的第n個數字。
        0              root
    0       1          第1層
  0   1   2   3        第2層
 0 1 2 3 4 5 6 7       最底層