Flipping 傳送門 POJ3185 題目概述 給你 20 個水盆，剛開始每個水盆可能是上，可能是下。 我們必須用一次反轉三個相鄰水盆的方式（開頭和結尾位置可以只轉兩個），將所有水盆轉正，請問最少需要轉多少次？ 解題想法 因為反轉相同區間 偶數 次，都會轉回原先的狀態。[1] 並且反轉後的結果與選擇反轉位置的順序無關。（例如：照 1,2,3 順序轉和 2,1,3 順序轉是一樣的）。 所以我們可以由左做到右，左邊的水盆位置都會是已經確定的。 一個簡單的策略，對於位置 i 的水盆，如果位置 i-1 的水盆是反的，那們我們必須（一定）在位置 i 反轉一次。 判斷水盆正反的方式是： 令要判斷的水盆在位置 k ， 若 (k-1 不超過陣列範圍且 k-1 有被反轉?... Read more 12 May 2017 - 1 minute read
之前看到一篇文章， 現在還蠻贊同的。 StackOverflow – scope of using declaration within a namespace 裡面大概在講：最好不要在 namespace 裏使用 using foo::blah 。 因為萬一哪天在自訂 namespace 外面想要 using 該 namespace ，連裡面藏起來的妖魔鬼怪也一起跑出來了。 所以我天真的想說，寫一個 bash script ，讓它幫我把 using foo::blah 自動展開成 foo::blah ，然後我就崩潰了… 展開的時候匹配做得不好，還可能會改到一些不該動的東西。 （查一下資料， sed 似乎不好做 negative lookahead ，可能要改用 perl 比較... Read more 25 Mar 2017 - less than 1 minute read
Binary Search 傳送門 POJ3579 題目概述 給定一堆數字，會有 個差。 問在這些差之中，中位數的值是多少？ 解題想法 先將資料排序，並使用一個 deque ，以 的時間去檢查資料中相差 以內差的數量，是否可以達到不少於中位數的數量。在這裡定義上述結果為 。 之後對該 做二分搜，初始上界為 下界為 -1 ，尋找使得 為真的上界，該上界就是答案。 總體複雜度 。 注意：C++ STL 的 Deque 速度不是很理想，可以自己使用兩個指標實作。 程式碼: 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 ... Read more 25 Mar 2017 - 1 minute read
Binary Search 傳送門 POJ3273 解題想法 最大值最小化 => 二分搜尋 用二分搜去找到最低的最高花費。 check(d) 代表限制 fajomonth 最大的大小是 d ，是否能夠湊出數量 M 個 jajomonth 。 檢查的策略是，依序把每天的花費加起來，若有其中一天超過 d 則失敗，若發現 jajomonth 大小超過 d 則增加 jajomonth 數量，如果 jajomonth 的數量 > 題目的 M ，則失敗。 之後用二分搜找到 check(d) = true 的下界。 程式碼: 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... Read more 17 Mar 2017 - 1 minute read
Prefix sum and DP. 傳送門 Uva108 題目概述 給你一個矩陣，問你裡面最大的子矩陣總和是多少？ 解題想法 這題和一維的「找最大子陣列」很類似。 先將每一列，都算出該列的 prefix sum 備用。 之後窮舉每對欄的組合，這時已經固定了欄的範圍， 之後在這幾欄的範圍內，利用之前算到的 prefix sum ，用 時間算出每一列在該範圍內的總和。之後直接套用「一維找最大子陣列」問題，就可以問二維的最大子陣列問題了。 程式碼: 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 #include &l... Read more 12 Mar 2017 - less than 1 minute read