解法 這題其實可以 Greedy + 二分搜，我使用的是 maxflow + 二分搜， 一不小心就想歪了。 先離散化每個區間，之後將每個時間的區間流量設為時間的長度，並將對應的菜餚上菜的時間， 加上對應的時間（流量）邊，將菜餚的節點容量上限設為我們假設的每道菜都必須吃的時間長度， 最後流到匯點，每道菜流到匯點的流量為我們假設要吃的時間長度，最後檢查最大流是否等於我們假設的時間 * 菜餚數量。 二分搜每個時間，得到吃每道菜的最長總時間。 傳送門 CF589F 程式碼 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 ... Read more 10 Jul 2017 - 3 minute read
Rolling Hash + 二分搜 題目要找到最長 （含開頭子字串 == 含結尾子字串 == 中間子字串（不含頭尾的）） 的子字串 可以使用 Rolling Hash 快速查詢區間的子字串是否相同。 先花費 的時間找到所有合法的（開頭字串 == 結尾字串）子字串， 之後利用這些子字串的長度，對中間子字串做二分搜，尋找使得中間子字串合法且長度最大的子字串。 總體複雜度約 現在還還弱弱的，字串題只會用 Hash 隨便做 傳送門 CF126B 程式碼 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... Read more 10 Jul 2017 - 1 minute read
最大流 牛要吃、要喝，現在有有限的食物、飲料種類， 每種食物、飲料只能供應一隻牛吃喝， 每隻牛必須要又吃又喝才算被餵養。 現在給定每隻牛接受的食物、飲料種類， 問最多能餵養幾隻牛？ 解法 使用最大流，將食物擺在源點，飲料擺在匯點，而牛擺中間， 將水流過去，得到最大的吃+喝飲料的牛的數量。 要注意，每隻牛最多只能吃喝一種飲料、食物，所以必須在牛的那層節點加上容量限制， 每隻牛限制流量為 1 ，多產生一條容量為 1 的邊，就可以達成目的。 傳送門 POJ3281 程式碼 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 3... Read more 10 Jul 2017 - 2 minute read
線段樹 先將題目給的區間們離散化， 並且將每個區間擁有的高度推進線段樹。 要維護的內容是每個區間擁有的最大高度， 有了每個區間的最大高度就可以得到總面積。 在 push 時更新最大高，在 pull 時也做相同的事。 建構完以後，詢問每個區間，乘上相對應的寬、高並加總，得到總面積。 總體複雜度大約 ，其中 為輸入的區間數量。 傳送門 POJ3277 程式碼 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 5... Read more 10 Jul 2017 - 3 minute read
線段樹，要維護的是區間內含有的顏色種類。 在 push 、更新時，新增顏色到區間內； 在 pull 時，更新左右子樹的區間到自己的節點上。 每個節點使用位元運算紀錄顏色種類。 傳送門 POJ2777 程式碼 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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82... Read more 10 Jul 2017 - 2 minute read