UVa 311 Packets

題意：
　　本題共有1x1,2x2,3x3,4x4,5x5,6x6共6種箱子數個(每行Input代表各個的數量)，而它們的高度均一樣，所以本題只考慮平面，而題目問的是，有一個大箱子的大小為6x6，如何使用最少數量的大箱子將上述的6種箱子包裝起來。

想法：

1. 6x6：1個6x6剛好裝滿一個大箱子
2. 5x5：一個5x5搭配11個1x1
3. 4x4：一個4x4搭配5個2x2，如果2x2不夠改用4個1x1代替
4. 3x3：要分別討論1~3個3x3 與2x2和1x1搭配的數量
5. 2x2與1x1：如果有剩下再放進大箱子

UVa 10282 & POJ 2503 Babelfish

想法：
　　本題可直接使用STL的map來做string與string的對應，用printf而不用cout可提升效率，因此使用c_str()將c++字串轉為c字串(POJ實測是985ms與766ms)。

UVa 120 Stacks of Flapjacks

　　題目的意思就是要將數字由小到大排序，但排序的方法稱為flip，比如{1,3,4,2}這些數字，如果flip(2) ('4'這個數字)的話，就要把'4'前面的數字做顛倒排序，變成{4,3,1,2}，那再flip(1) ('2'這個數字)的話，就會變成{2,1,3,4}，最後就是想辦法用最少步驟變成{1,2,3,4}

想法：
　　每次都將最大的數字移到最右邊，要移到最右邊，就先判斷

1. 本來就在最右邊：不動，換下一個最大值
2. 在最左邊：直接flip(1)將它換到最右
3. 在中間：先flip(自己的位置)換到最左邊後，再flip(1)換到最右邊

UVa 10245 The Closest Pair Problem

求任兩點的最短距離，如果全部枚舉的話，時間複雜度n^2，一定會TLE。

想法：

• 將所有點依x座標排序
• 從中間切開，將所有點分成左右兩個集合(設line為中線x座標)
• 左右兩邊各求出任兩點最小值a,b，設d為min(a,b)
• 那麼現在只要枚舉(line+-d)這範圍內的點有沒有比d還更小的值即可

遞迴定義：

• divide(point_type a[], low, high)  
• 求出a[low]~a[high]範圍內任兩點的最短距離
• combine(point_type a[], low, mid, high, min_left, min_right)
• d=min(min_left,min_right)
• line=(a[mid].x+a[mid+1].x)/2
• 合併左右兩個集合，並確認在(line+-d)的範圍內有沒有比d更小的值，最後回傳最小值

更詳細圖解可參考KuoE0:http://www.slideshare.net/KuoE0/acmicpc-uva10245

注意輸入輸出皆要用double

UVa 10666 The Eurocup is Here!

題意：

• Team 4贏過Team 6，而Team 6贏過Team 7，那麼表示Team 4確定贏過(優於)Team 7，也可說Team 7比Team 4差。
• Team 0同時贏過Team 4和Team 2，則Team 4和Team 2關係無法確定。
• 因為隊伍與隊伍之間關係有些確定有些不確定，本題要求出Team X可能最佳為第幾名，以及最差為第幾名

想法：

• 1.找最佳：只要找到贏過Team X的共有n隊，那麼n+1即是Team X的最佳名次。
• 1.做法：win(x)函數找到贏過Team X的隊伍(設為a)，再繼續win(a)找到贏過Team a的隊伍(設為b)，一直找到底(Team 0)為止，計算途中總共幾隊。
• 2.找最差：計算比Team X差的隊伍總共有幾隊，那麼Team X的最差名次就是全部隊伍數減掉比Team X還差的隊伍數
• 2.做法：Team X如果在Round r輸掉，那麼比Team X差的隊伍數為(2^(r-1)-1)，可多次觀察樹狀圖r=1,2,3,4...其結果為0,1.3,7...得知

POJ 1664 放蘋果

想法：

　　因為盤子皆一樣，例如(1,1,3)和(1,3,1)是同樣的，所以排的時候以遞增的方式排，只保留(1,1,3)這組，故左邊的數字不大於右邊的數字。在一開始(0,0,0)時，若最左邊的盤子要+1，則右邊兩個也要跟著+1才能使上面的條件成立，照此規則，當某個盤子要+1時，其右邊的盤子也要跟著+1，所以要注意此動作是否會造成蘋果不夠(if(m-i>=0))，而當蘋果剛好分完(m=0)或是只剩最右邊的盤子(n=1)時，遞迴結束。

POJ 1068 Parencodings

S (((()()())))

P-sequence    4 5 6666

W-sequence    1 1 1456

P_seq表示第i個')'前共有n個'('

W_seq表示第i個'( )'裡包含自己有幾個'( )'

想法：用一個parenthes陣列存每個括弧，找到第i個')'就往前找'('形成'( )'，已經配對的'('就跳過，看中間經過幾個已配對'('就是表示總共包含幾個'( )'

2014/2/17 更新：

用一個diff陣列存每個P値之間的差値，代表兩個')'之間有diff個'('，其他詳見程式碼。

POJ 3262 Protecting the Flowers

這題與UVa 10026 Shoemaker's Problem是一樣的

POJ 1007 DNA Sorting

想法：
　　 使用bubble sort時候每交換一次逆序數就+1，最後由逆序數小到大輸出。至於求逆序數更快的算法可參考UVa 10810 Ultra-Quicksort。

POJ 1035 Spell Checker

想法：

• dic[i],check字數相等的情況
• dic[i],check字數相差1的情況