起床才發現，Facebook Hacker Cup Round 2 比賽不是比 24 小時，翻譯機的小夥伴醒了嗎？在這樣的情況下，只好自主宣告放棄，看題一直失敗，整個心情都壞了。關於 Round 2，根本沒看懂題目，就這麼結束了。

［2015 Facebook Hacker Cup Round 1］

＊Homework (10 points)

數學老師給一份質數作業，要求找到 [A, B] 之間的正整數，有多少不同質因數個數恰好等於 K 個，例如 12 = 2^2 * 3，則 f(12) = 2。寫一個程式來快速完成它。

A, B 小於等於 1000 萬，而詢問組數不超過 100 組，預估就算 O(n) 窮舉，速度來說仍然可以在時間內完成。無聊可以使用線性篩法，快速得到某個數字 x 必含的其中一個質因數來加速，f(x) = f(y) + 1, x = y * z, z power of prime nubmer。而區間查找可以針對 K 分開成數組，進行二分搜索。這樣寫太拚，有六分鐘的時間，暴力一點也無仿。

＊Autocomplete (25 points)

手機輸入單詞，會自動補上正在輸入單字的後綴，現在要求依序輸入單字，至少要敲入幾個字母，才能將所有單字完成。這題有點奇怪，照理來說要給定一個字典，接著開始鍵入，但這題是根據之前輸入的單詞，如果前綴相同就不能自動完成，怎麼補完的一點都不科學。

這題用內建 set<string>，可以使用 iterator it = map.lower_bound(word), it--; 來找到最有可能的前綴單詞，一定得輸入最大共同前綴長 +1，如果不想用內建，可以帶入 Trie 來完成，保證單詞總長不超過 100 萬，在某些題目 Trie 的速度跟泛用性相當高。

＊Winning at Sports (25 points)

在比賽中，勝利情況分成有、無壓力兩種方案，無壓力的情況是過程中，最後獲勝者的分數恆大於另一方，有壓力的情況是過程中，在另一方達到終盤分數前，最後獲勝者的分數不得大於另一方。現在給定終盤分數，請問兩種方案的比賽過程分別有多少種。

Dynamic programming 狀態 dp[a][b] 表示分別得分 a, b 的方法數，每次轉移 dp[a+1][b] += dp[a][b], dp[a][b+1] += dp[a][b] 特別小心條件範圍，分別對兩種方案做一次迭代。

＊Corporate Gifting (40 points)

每名員工都有一位上司，保證是樹狀結構，每名員工將要買禮物送給上司，禮物的花費為 $1, $2, …, $n，每個人都不想送出 $x 後，又從下屬中得到 $x 的禮物，請問該公司買禮物的總花費最小值為何？

樹狀最小帶權著色問題，套入樹形 Dp 的思路，定義狀態 dp[u][2] 表示以節點 u 當作 subtree root 的最佳解，其中 u 買 $?1,$?2 的兩種花費最小方案。合併時，窮舉 root 購入的價格，結合子樹的最小花費，防止同色即可。根據官方題解，使用的是 dp[u][log n]，可想而知數學推導得到最大購入不超過 $(log n)，但實際運作，我並沒有這麼做，而是看子樹最大著色數為何，再根據最大著色數進行窮舉。

這一題看到 N=200000 就要有點警惕，一般電腦預設 stack 大小，遞迴深度最多撐到 10 萬，呈現鏈狀很容易造成 stackoverflow，其一解決方案是編譯器調參數，其二 bfs 後的拓墣排序。