UVa 441 Lotto

想法：
    排列組合中的組合，因此每次挑選的時候只能比之前挑的數字還要大，用遞迴做Backtraking，詳細見底下code:

POJ 2255 Tree Recovery

想法：
　　原本的字串是整棵Tree，我們可先找到這個Tree的Root，再將其分為左右Sub Tree，一直遞迴下去直到Sub Tree只剩一個元素。
　　具體做法是：

1. 先用Preorder String找出Root(P_root)，再透過P_root找到Inorder String的Root(I_root)
2. 然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index：左子樹的左右界和右子樹的左右界)，再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
3. 依照Post Order的順序：
1. 先遞迴左子樹
2. 再遞迴右子樹
3. 輸出Root

底下有附詳細註解的Code：

UVa 10821 Constructing BST

想法：
    在最上層的時候，假設我們有數列{1,2,3,4,5,6,7}，要選出一個數字當作該層的root，例如選擇'4'，那麼{1,2,3}就被分配到左子樹，{4,5,6}到右子樹，到下一層我們一樣從{1,2,3}和{4,5,6}選出各自的root，然後繼續到下一層。
    但題目有說輸出要盡可能小，所以選擇root的時候，要盡可能選靠左邊的數字，所以要讓右子樹填滿，例如現在最上層數列為{1,2,3,4,5,6}，深度H=3，代表子樹深還有2，則左右子樹各別能提供(2^2-1=3)3個空間，因此我們選擇'3'當作root，分成{1,2}和{4,5,6}到左右子樹，讓右子樹3個空間被填滿，一直遞迴下去直到分配完全部數字。

UVa 10776 Determine The Combination

想法：

直接舉例子來講，假設字串aaabbc(編號012345)，取3個(n==3)，我們先假設ans這個容器來存放所選的字元。

首先進入第一層遞迴後，表示要選一個字元放到ans[0]，能選的字元為0~5，for loop 0~5，先放0('a')到ans。然後進入第二層遞迴，能選的字元變成1~5，for loop 1~5，放入1('a')到ans。再進入第三層遞迴，能選的字為2~5，for loop 2~5，放入2('a')到ans。進入第四層遞迴後發現ans.size()==n，因此輸出答案。

接下來退出第四層回到第三層，跳出ans的字(ans.pop_back())，找下一個字元，因為避免重複，所以用while loop找到下一個不一樣的字，放入3('b')到ans，以此類推...

把第三層for loop跑完後，回到第二層，一樣跳出第二層的字，找下一個字不一樣的字元，然後繼續進入第三層。....剩下以此類推。

UVa 10101 Bangla Numbers

想法：
　　透過遞迴求出答案。

UVa 10285 Longest Run on a Snowboard

本題連結
題意：
　　本題給予一個區域內的每個點的高度，滑雪只能由高的點往低的點滑，要求出在這個區域內最多能滑幾個點(滑最遠的方式)。

想法：
　　用一一枚舉的方式，也就是每個點都走走看。
我們定義遞迴式int find_longest (i,j,length) 是回傳area[i][j]這個點所能走的最遠長度。把所有點都算出其最遠長度，在從所有點中選出最大值輸出。


    

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

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)時，遞迴結束。

UVa 10098 Generating Fast

2014.2.13更新：
這題使用STL_next_permunation即可，不過效率較慢，1.035秒，底下自幹的方法0.119秒。




想法：

char str[]存原本所有的字元

char temp[]來存已選擇的字元

bool choosed[]來表示哪些字元已被選擇

int all表示總共幾個字元

int left表示剩下幾個字元還沒選到

舉例子解釋，本題比如是"abc"，那麼第一個位置可能放a或b或c

所以在遞迴第一層用for loop從i=0~i=2。

假設現在i=1 將'b'放入temp

同時將choosed[1]標記為1  

那麼進入下一層遞迴就不會選到'b'

進入下層遞迴後 一樣for loop從i=0~2

但是'b'因為choosed[1]=1就不會選到

以此類推，例如現在第二層遞迴i=0選'a'

就將'a'放入temp(此時temp[]="ba")，choosed[0]=1;

再進入第三層時因為其他choosed皆=1，

所以只剩'c'，將'c'放入temp，

最後進入第四層因為left==0(所有字元都被選到了)，就可以print結果

返回第三層，將'c'從temp剔除，choosed[2]=0，此時i值已經到底了(i==2)

然後返回第二層，將'a'剔除，choosed[0]=0，此時i++，

到i==2時，把'c'放入temp(此時temp[]="bc")，進入第三層

之後以此類推。

從以上可寫成遞迴式:

permu(all,left,str,choosed,temp)
{
   if(left==0) printf結果;
   else{
      for(int i=0;i<all;i++){
         if(choosed[i]==0){
            choosed[i]=1;
            temp.push_back(str[i]);

            permu(all,left-1,str,choosed,temp);

            temp.pop_back();
            chooses[i]=0;
         }
      }
   }
}


注意： "aab" 會重複排列字元的問題，加入一條判斷式避免
if(choosed[i]==0 && choosed[i+1]==1 && str[i]==str[i+1]) continue;

UVa 374 Big Mod

已知 (A^n)%M=(A%M)*(A%M)*(A%M)*......*(A%M)%M

可用遞迴 (A^n)%M = (A^(n/2))%M * (A^(n/2))%M %M

UVa 755 487-3279

UVa 10017 The Never Ending Towers of Honoi

想法：
　　河內塔問題可先簡化成只有一個，那麼只要將它從A移到C，而如果有兩個的話，那就把上面那個移到B，再把下面那個移到C，B再移到C即完成，因此如果有n個，先把上面(n-1)個從A移到B，再把下面那個移到C，最後把(n-1)個從B移到C。

• Honoi(n,a,b,c) 表示將"n"個從A移到C(從第二個參數移到第四個參數)
• Move(a,c) 表示將最下面一個從A移到C

因此可寫成遞迴式：

Hanoi(n,a,b,c)   //將"n"個從A移到C

{

    if(n==1) Move(a,c);  //只有一個，直接移到C

    else{

        Hanoi(n-1,a,c,b);  // 將"n-1"個從A移到B

        Move(a,c);  //將最底下那個從A移到C

        Hanoi(n-1,b,a,c); //最後將"n-1"個從B移到C

    }

}

注意本題output的要求：

• 如果A=>之後沒有數字必須沒有空格
• 每個問題後面都要有一個換行(包含最後一個問題)