Lowest Common Ancestor 在 IOICamp2017 解過的題目，雖然名稱叫做「最低共同祖先」，但是並不真的要求出 LCA (?) 不提供傳送門 題目敘述 在一棵樹上有 n 個點 ，對每個點 ，找出有幾組有序點對的 LCA 是 。 輸入格式 第一行一個正整數 ，代表測資筆數。每筆測資兩行， 第一行整數 ，第二行 個整數 ，代表 的老爸是 。 限制 $$1 \leq T \leq 100$$ $$2 \leq n \leq 100000$$ $$1 \leq p_{i} < i$$ 輸出格式 輸出 個以空白分隔的整數 ，代表有 組有序點對的 LCA 是 。 解題想法 對於樹上一組點對的 LCA ，可以想成這一組點... Read more 12 Feb 2017 - 1 minute read
String matching 練習一下基本的字串比對 傳送門: POJ3461 程式碼: 主要練習了兩種方法，一種用 MP 算法、一種用 hash MP 改天再練習 KMP ，很怕 MP 算法會被 Hack 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include <iostream> #include <cstdio> #include <cstdlib> #in... Read more 12 Feb 2017 - 2 minute read