| layout | title | date | tags | ||
|---|---|---|---|---|---|
post |
[GCJ] 2011 Qualification - B - Magicka |
2011-05-09 |
|
題目網址：B - Magicka
題目說這是一個基於名叫 Magicka™ 的遊戲，但沒聽過…。題目說我們可以「invoke」八種基本元素 {Q, W, E, R, A, S, D, F}。invoke 在這邊只是一個呼叫的意思，不要太去在意英文的本意。invoke 是呼叫一個元素列表 [E0, E1, ..., En]。
再來會提供結合列表，也就是當某兩個基本元素相鄰可以結合成另一個新的非基本元素。例如：Q 與 F 會結合為T（不限順序），所以當元素列表為 [Q, F, A]，則會因為結合的關係變成 [T, A]。
另外還有排斥列表，也就是某兩個元素不可同時存在於元素列表中，若同時存在於列表中，且無法結合為其他元素時，將把這兩個元素所包圍的區段內的元素移除（含這兩元素）。例如：Q 與 F 會排斥，所以當元素列表為 [Q, A, D, F, E]，則會因為排斥的關係變成 [E]。
此題目就是給你元素列表、結合列表以及排斥列表。將元素列表經過結合列表與排斥列表處理後的列表輸出。
注意，所有元素均由最左邊往最右邊讀取。
small case
- 測試資料的數量 T, 1 ≤ T ≤ 100
- 結合列表數量 C, 0 ≤ C ≤ 1
- 排斥列表數量 D, 0 ≤ D ≤ 1
- 初始元素列表長度 N, 1 ≤ N ≤ 10
large case
- 測試資料的數量 T, 1 ≤ T ≤ 100
- 結合列表數量 C, 0 ≤ C ≤ 36
- 排斥列表數量 D, 0 ≤ D ≤ 28
- 初始元素列表長度 N, 1 ≤ N ≤ 100
每一筆測試資料由一個整數 T 開始，表示接下來有 T 組測試資料。
每一組測試資料由一個整數 C 開始，表示接下來有 C 個字串。這些字串為結合列表，每個字串都包含三個字元，前兩個為基本元素，第三個為經過結合的新元素。接著一個整數 D，表示接下來有 D 個字串。這些字串為排斥列表，每個字串包含兩個字元，該兩字元都為基本元素。接著是一個整數 N，表示初始的元素列表長度。最後一個長度為 N 的字串，也就是初始元素列表。
對於每一筆測試資料，輸出只有一行，輸出測試資料編號與一個整數 Case #X: Y。X 為測試資料編號，由 1 開始；Y 為最後處理過的元素列表。
這題也花不少時間阿，剛開始以為排斥列表的排斥關係是像括號配對的方式一樣，以為會有套嵌的關係存在。
例如：
Q 與 E 互相排斥，而元素列表為 [Q, A, Q, Q, W, E, A, E]。
處理過程：[Q, A, Q, Q, W, E, A, E] → [Q, A, Q, A, E] → [Q, A]。
但其實不是，依照上面的例子應該變為 [A, E]。也就是假設出現了一個有在排斥列表內的元素，當接下來的元素中有任何一個與他排斥的元素，且這個元素無法經過結合產生新元素時，就將此區段內的元素全部移除。剛開始用 stack 搞半天，但現在想想如果真的是我想的那樣，題目應該會更難寫，我又再一次地把題目複雜化了。
作法是將排斥列表與結合列表存起來。**注意，一個元素可能與多個元素排斥，但兩個元素結合必定只能產生一種新的元素。**因此排斥列表我用連結串列儲存，紀錄每個元素與那些元素排斥。結合列表則用二維陣列儲存，記錄此兩個元素會產生的新元素。再來用一個陣列紀錄元素列表內的元素是否消失，初始為全都存在。
接著就從第一個元素開始往後尋訪，每次尋訪到一個元素時，先判斷其是否存在，若不存在則尋訪下一元素。若此元素存在，查看此元素的排斥列表，查看此先前尋訪過的元素是否存在與此元素排斥的元素，並找出位於最前面（index 最小）的元素。
若有找到排斥的元素，我們將此區間內的元素通通標記為已消失。若沒找到，則查看此元素以及其下一個元素是否可以結合為新的元素，若可以就直接將當前的元素轉變為新元素，並標記下一個元素已消失。否則記錄此元素的位置。無此在尋訪所有元素後，最後就可得到我們答案了。
<script src="https://gist.github.com/KuoE0/1619625.js"></script>Time Complexity: O(N×D)
Source code on gist.