調和的靈感

終於AC了..這次最大的心得就是，腦袋不清楚的時候不要寫程式。如果沒辦法理清思路，找出邏輯上的漏洞，那麼debug也只是亂試一通而已，一點幫助都沒有(只有浪費時間)。寫到後來連錯誤的測資也在試，現在想起來真是笨阿 我用recursive的方法去追蹤整顆樹。測資是pre-order sequence 所以遞回順序是root ,left-child , right-child 很不清楚核心Algo: int traversal(int sum, int target){ 抓左括號 抓root lc = traversal(int sum+root, int target) //向left-child遞回 rc = traversal(int sum+root, int target) //向right-child遞回 抓右括號 如果是Leaf? 判斷總和相不相等？ 如果是Internal Node，將子樹的結果繼續往上回傳。 } 另外一提，這次我參考了某份AC Code，用non-recursive(Stack)作法，但是因為用了STL stack;，最後執行時間0.510s，慢了我五倍之多。我用Recursive反而執行時間只有0.100s(Ranking 90，再進百大XDDDD)有點意外。證明一件事：Recursive不一定慢，但是STL=慢。

解題策略 這題AC的關鍵是時間，用暴力法O(n 6 ) 六層迴圈去解鐵定超時。已知最佳的解法是 O(n 3 ) ，不過一般用O(n 4 ) 就可以通過了。 我也是用 O(n 4 ) 的解法，首先用四層迴圈窮舉子矩陣的左上角(x1,y1) 跟右下角 (x2,y2) 的位置，一旦給定了子矩陣後，就要 O(1) 時間得到子矩陣的和。 要達成這個目標可以透過 sum table 來達成，我說明一下我的方法， sum table ( i, j ) 每個位置儲存的值的是原矩陣 (1,1) ~ (i, j) 之間的元素總和。像下圖的 sum table ( 2, 3 ) 的值就是 原矩陣 (1, 1) ~ (2, 3) 之間的元素和。 一旦建好 sum table，那接下來就可以簡單透過這 D - B -C + A 這四個sum table的元素直接得到子矩陣的和了。 閒聊 最後執行時間0.052 過關....改天再將作法補完，我好睏....晚安。原本用暴力法去跑 100x100 的矩陣，竟然要253秒(大汗)。

解題策略 注意 修正了兩個問題，終於AC了 1. 雖然題目頁說只要印小數點後三位，但其實要印四位。 2. 各個output case"之間"，要隔一個blank line。 但只有case間要空行，最後一個case印完後不能有多餘的空行。 (很嚴格的的格式要求...) 新版的AC Code

這題說穿就是LIS，對於已經精通LIS的我自然是小菜一碟(咦？) 不過這題有個陷阱，如果沒仔細讀懂題目的話，會以為只要做一次轉換，其實上要做兩次轉換。 第一次把rank轉成真正的event sequence，(rank[] => seq[]) 第二次才轉成可以做LIS的形式。(seq[] => seq2[]) 剛開始送了兩個WA，後來看事有悉蹺，(sample output怪怪的)，改了一下就AC了。

題目講解 這題給你一堆多維的箱子，要找出最長的裝箱序列，這個最常裝箱序列就是像俄羅斯娃娃那樣，大箱子裡面放入小箱子，一層包一層，必須要可以裝最多層這樣。 這題的麻煩就是各個箱子之間不一定有的大小關係 (數學上打這叫偏序集 Partial Order Set ，不過這兒我們先不管 )，比方說有兩個三維箱子 BoxA(1,4,5) 、BoxB(2,4,6) ，B箱比較大，所以 BoxA 可以裝進 BoxB 裡，那麼我們說 BoxA < BoxB 。 但來看 BoxC(1,5,6) 跟 BoxD (2,4,5) 呢? 我們既不能說BoxC < BoxD ，也不能說 BoxC > BoxD，BoxC 與 BoxD 兩者之間就沒有大小關係。 一個簡單的表示法就是有向圖(Directed Graph) 比如說 A(1,2,3) B(2,4,6) C(2,3,7) D(50,50,50) E(10,10,100) 的有向圖表示法: 到此為止，本題的最長裝箱序列，已經有兩種解法，第一個方法就是找圖的最長路徑，稍微修改 Warsahll algorithm 來解，第二個方法是跑 LIS 。 我這裡用 LIS(最長上昇子串列) 解法。 //先定義一個box struct struct Box { int no; int edge[10]; }; Box box[30]; LIS 法的關鍵是要先對箱子排序，確保小箱子一定在大箱子前，至於沒有大小關係箱子的就隨便放沒關係。這個排序以圖的角度是拓樸排序，以字串的角度是字典排序，兩者都行。 sort(box[i].edge) for all i //先對箱子內部的邊長排序 int lexico_less(const Box& a, const Box& b) { for(int i=0;i<dimension;++i) if( !(a.edge[i]<=b.edge[i]) ) return false; return true; } sort(box) by lexico_less(); //再用字典序排箱子 一切都準備好後，就可以直接套用LIS解了。 // LIS int

看了兩次，可是每次都忘記，所以做個筆記 s: input string p: pattern Failure Function的值k，就是下次要從p(k)開始matching 舉例 Pattern A B C A B C D failure -1-1-1 0 1 2-1 Case I: Input string AB C D ADFGACEDAABBBB AB C A BCD 紅色 =not matching step1: 看最後一個matching字元 ( 綠色的字 ) 的failure function value= f step2: 將p(f)對齊綠色的位置 ( p(i)代表p的第i個字元 ) ex. f(C) = -1 ，所以p(-1)對齊上面那排的C AB C DADFGACEDAABB >>> ABCABCD Case II: ABCAB C E ACAADDBBBABCABC ABCAB C D f(C)=2 ，所以p(2)對齊上面那排的綠色C ABCAB C E ACAADDBBBABCABC >>> AB C ABCD 講的不是很有條理，不過我先給自己看懂就好= = 改天再來整理的清楚一些