因數倍數相關、範圍小、詢問多，從這些特徵，不難猜到要「建表」。
找到質數，把這個質數的所有倍數（包含本身）+1。
因為這題測資很弱，而且傳Output比賽，時限不會精確卡到，所以建完表對每筆詢問算一遍就會過了。
更進一步，可以發現在\(B\leq10^7\)下，\(K>8\)就不用處理了，
所以可以把\(K=1,2,...,8\)再預處理，做到時間複雜度\(O(N log log N +T)\)。

題意比較難理解，其實就是在讀到字串\(S\)的時候，計算已經讀入的字串中，
跟\(S\)的最長共同前綴有多長，\(ans+=共同前綴長度+1;\)，如果等於\(S\)長度，\(ans--;\)。
顯然trie支援如此詢問共同前綴並增加資料。
就這樣做一做，時間複雜度\(O(L)\)，其中\(L\)為字串總長度。

兩種情況分開來做DP，狀態都是訂dp[自己得分][對手得分]。
我是用Top-down來做，基本上不難列轉移關係。
只要注意stressful的DP轉移過程與對手的最終的分有關，大可對每個\(T\)都重做一遍。
時間複雜度\(O(AB)\)，\(A,B\)分別為自己與對手的得分。

實際畫一下，會發現單一人的錢不會太大，實測不超過\(11\)。
不知道怎麼確切的卡上限，大可切個\(log_2N\)，取\(20\)，
理由：一個人的錢為\(x\)時，與其有關的人必定包含\(1,2,3,...,(x-1)\)的錢。
這樣卡得其實很寬，不過足夠了。
從沒有子節點的點開始，往上處理，記錄（這個點用\(x\)錢時，這個子樹的最小花費）。
（處理順序要確保：當一個點被處理時，其所有後輩都已處理完。）
依序往上就完成了！ 時間複雜度\(O(N log N)\)。

如果用到遞迴，要小心自己電腦上的stack overflow，可以用以下編譯參數處理：
g++ -Wl,--stack=0x2000000

連結：2015ioicampOJ6
邏輯不難理解，只是寫起來複雜、麻煩而已。
線段樹每個節點都保存「區間總和」、「區間最大左綴」、「區間最大右綴」、「區間最大連續和」，
（左綴、右綴定義仿照前綴、後綴，相信很好理解這種講法）
接著只要能轉移就好：
「區間總和」=左「區間總和」+右「區間總和」
「區間最大左綴」=\(max(\)左「區間最大左綴」\(,\)右「區間最大左綴」+左「區間總和」\()\)
「區間最大右綴」=\(max(\)右「區間最大右綴」\(,\)左「區間最大右綴」+右「區間總和」\()\)
「區間最大連續和」=\(max(\)左「區間最大連續和」\(,\)右「區間最大連續和」\(,\)左「區間最大右綴」+右「區間最大左綴」\()\)
有了以上關係之後，不管是build、query、modify，其實寫起來都一樣！

連結：TIOJ1137
參考資料：建中講義(p.8~p.9)
經典的Tarjan's Algorithm ，不過我也是第一次真正寫。
一開始還寫了個假解，也就是對於根節點（這題保證圖連通，只有一個根節點），
我竟然判斷子節點的low值有沒有大於根節點的深度，而且還AC了！
還好寫完之後找了資料讀一下，才發現這個錯誤！
因為只是找割點，所以可以把back-edge跟回到parent的tree-edge混在一起也無妨。

連結：TIOJ1092
不知道要打什麼...
很單純的博奕問題，只要注意博奕問題中的「先手」是有選擇權的主動方，
以這題來講，主動方應該是站在圈外的人！
接著就是把邊反過來存、拓樸排序、依序處理。
因為一個小小的bug，害我拖了好久才弄完。

連結：TIOJ1027
參考資料：直式開方法
其實這題沒什麼算法特點，比較接近給初學者練語法的題目。
（當然，屬於比較複雜的語法練習了）
我原本不會直式開方法，昨天亂戳題目戳到這題，突然覺得很好玩，就寫了。
最大的價值應該是這題逼我查資料認真的讀、學了直式開方法。
此外，如果會用比較傾向物件導向的寫法，例如開一個struct或class、寫建構子、重載運算子等，會比較好寫。

連結：UVa1153, 2014TOI初選
這題多虧CBD讓我找到一樣的題目，原本初選那題遙遙無解的。
不過出現在UVa還蠻可恨的，傳完等上5分鐘只得到Submission Error，
重複超多遍，而且這題又用到了「測資間輸出一行空行」以及「"before"但是可以同時」這些容易誤解的陷阱，
何況範測又給那麼弱，還好最後有讓我看到AC！
去年TOI1!時，室友跟我講了一個greedy：把它時間軸反過來，然後從可以選的工作中選能夠最晚開始做的
不過，在下面這種case會爛掉(TOI的輸入格式)
2
5 1
8 7
其實我一直深信上面那個greedy是對的，直到不久前才發現有這種情況會壞掉。
後來在FB社團有人討論，CBD就給了UVa的那題。
UVa那題有充分明顯的提示，所以不難想到解法：
1.按照deadline由小到大排序所有工作
2.依序加入這些工作，如果有擺不下的，就看看已經加入的工作有沒有花費比較長的，把它換掉。
很簡潔的算法，顯然步驟2.需要priority queue輔助，同時有很多東西其實不用記錄的。
複雜度：\(O(n\ log\ n)\)

reference data: Stanford那個雖然是英文，但是寫得最好，另外兩個資料給的範例圖都太簡單、不夠複雜。
不過有些內容不交叉比對每個參考資料，可能會沒辦法理解。
SCC定義參考Stanford就好，這裡不贅述，重點是Kosaraju's Algorithm。
作法如下：
1.以類似於找拓樸順序的方法，對原圖\(G\)做DFS並記錄timestamp(差別在於，不要判環，所以反而會比較好做)。
2.將原圖的邊通通反向得到\(G^T\)。
3.按照步驟1.得到的偽拓樸順序(參考演算法筆記的說法)對\(G^T\)走訪，所有還未處理而被走訪到的點便屬於同一個SCC。

結束了!? 是的，算法內容看起來好精簡，而且每個步驟都是linear time，總時間複雜度\(O(|V|+|E|)\)
不過它的正確性實在讓人困惑，似乎不怎麼直觀。
在說明它的正確性時，先假設大家都知道對圖\(G\)以SCC做的縮圖會是DAG(縮圖定義參見Stanford)。
以下開始說明：
首先，因為縮圖會是DAG，所以縮圖必定存在拓樸順序。
假設我們已經知道每個SCC包含的點，將圖\(G\)的偽拓樸順序的每個點對應到所屬的SCC，
將重複出現的SCC中，偽拓樸順序較後面者刪除，如此便能得到縮圖中的一組拓樸順序。
這部份的理由也相對不易理解，再細說如下：
並且我們知道，由任意一個點\(v\)出發，在\(G\)中能到達的點，其所屬的SCC必為：
1.與\(v\)同一個SCC
2.為\(v\)所屬的SCC在縮圖中能到達的SCC
再者，顯然將圖\(G\)的邊反向後，不會影響SCC的狀況，但在縮圖中，
因為是DAG，所以圖上的「祖先-後輩關係」會相反（雖然不是真正用詞，但是應該不難了解其意思）
如此一來，縮圖中的拓樸順序反轉後，便會是\(G^T\)的縮圖中的一組拓樸順序。
因此若我們按照最開始的偽拓樸順序走訪圖\(G^T\)，是按照圖\(G^T\)縮圖中的拓樸順序的相反順序走訪，
使得點\(v\)能抵達的點，若為上述的第二種情況（為縮圖中後輩SCC的點），那麼必定早已處理過了，
（因為是按照拓樸順序的相反順序）
那麼所有能抵達且還未處理的點便是與\(v\)同一個SCC的點囉！
這個算法完成了，算是蠻巧妙的~

至於題目與應用...我也沒有找到。