回分類題庫
h111: D.小可魚兒向上游
關鍵字: NPSC 2012 高中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 17 Times / 16 Users | Submit : 37 Times / 19 Users | Accepted rate : 84%
題目加入時間 : 2013-11-07 13:27

Content: 简体中文

江江江江,有一條江耶!

經過長時間的觀察,老姜發現這條江有許多支流,且整個河系可以用一個以源頭為根的樹狀結構來表示。除此之外老姜還發現有許多小可魚循著某種規律在江河中悠游穿梭,每當一隻小可魚開始逆流而上時,牠會先在起點做個記號,之後開始奮發向上游阿游阿游,直到源頭或是遇到其他小可魚在牠開始前做的記號為止。

聰明的老姜已經先寫了一個程式來預測每隻小可魚最後會停在哪裡,但謹慎的他還是請你也寫一份來確認他寫的程式是否正確。但為了肉眼比對方便,聰明的老姜決定比較結果的雜湊值就好,也就是假設小可魚最後停留的位置依序為p1, p2, . . . , pk,則我們定義其雜湊值為(p1+1)⊕(p2+2)⊕...⊕(pk+k),其中⊕代表 XOR 運算。 

Input:

輸入檔的第一行有一個正整數 T (T<=514),表示接下來總共有幾條江的觀察記錄。

每個觀察記錄開始有兩個正整數 N, M (M<N<=105),代表這條江的樹狀結構有 N 個節點,M 隻小可魚。節點編號為 0, 1, ..., N−1,其中 0 為源頭。下一行有 N−1 個整數,代表每個節點(支流) 1, 2, ..., N−1 的上游編號。再下一行有 M 個相異整數,代表每隻小可魚的起點,輸入順序為小可魚們開始向上的順序。 

Output:

對於每筆觀察紀錄,請輸出其對應的雜湊值。雜湊值計算的程式碼如下:

int hash(int numbers[], int size){
    int value = 0, i;
    for(i = 0; i < size; i++){
        value ^= (numbers[i] + i + 1);
    }
    return value;

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
4 3
0 1 2
3 1 2
5 3
2 0 2 2
1 2 3

Sample Output :

7
6

Hint :

範例說明:

第一筆測試資料中的江系:0←1←2←3

  1. 一開始有隻小可魚在 3 號節點做記號並開始往上游,直到源頭為止,路線為 3→2→1→0,停在 0。
  2. 接下來有隻小可魚在 1 號節點做記號並開始往上游,直到源頭為止,路線為 1→0,停在 0。
  3. 接下來有隻小可魚在 2 號節點做記號並開始往上游,直到 1 號節點為止,路線為 2→1,停在 1。 

最後輸出的雜湊值為 (0+1)⊕(0+2)⊕(1+3)=7。

第二筆測試資料中的江系:0←2←1,3,4

  1. 一開始有隻小可魚在 1 號節點做記號並開始往上游,直到源頭為止,路線為 1→2→0,停在 0。
  2. 接下來有隻小可魚在 2 號節點做記號並開始往上游,直到源頭為止,路線為 2→0,停在 0。
  3. 接下來有隻小可魚在 3 號節點做記號並開始往上游,直到 2 號節點為止,路線為 3→2,停在 2。

最後輸出的雜湊值為 (0+1)⊕(0+2)⊕(2+3)=6。 

Author :

NPSC 2012 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum