UVa 11069 A Graph Problem

題意：

1. 子集合內數字不能相鄰
2. 要盡可能填滿，比如n=6，那麼就不能有{3,6}而是要{1,3,6}，不能是{1,4}而是要{1,4,6}

想法：

　　一開始很直覺的使用遞迴一直往下尋找，但是使用遞迴會TLE，換個想法，很類似高中排列組合的階梯問題，本題是一次走2階或3階：

• n=1{1} : 1
• n=2{1,2} : 2
• n=3{1,2,3} : 2
• 當n=4{1,2,3,4}，有哪些情況會選到'4'? n=1({1,4})或n=2({2,4})的情況，所以n(4)=n(1)+n(2)=3
• 當n=5{1,2,3,4,5}，會選到'5'的情況有n=2({2,5})或n=3({1,3,5})，所以n(5)=n(2)+n(3)=4
• 以此類推..

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 10815 Andy's First Dictionary

想法：
　　用%s讀入temp(可略過空白和換行)=>判斷temp裡每個字放到dic[].word裡=>排序=>輸出

注意：

• 如A's 要分成A跟s
• 不用考慮最後一行換行的問題
• 陣列開很大時要放在global，避免Runtime Error(放在local會有大小限制，array開很大就會overflow)

POJ 3067 Japan

　　本題東邊有N個城市，西邊有M個城市，現在欲蓋多條高速公路連接東西邊，求路線的交點數。

ps.不會有三邊共點的情形

struct city{

     int e;  // 存東邊城市編號

     int w;  // 存西邊城市編號

}

想法1：每次讀入(e,w)時(設第k次)就檢查(k-1)次之前所有情況，若city[k-1].e<city[k].e，則city[k-1].w>city[k].w才會有交點，反之。此算法為O(n^2)會TLE。

想法2: 可依e由小到大(若e相等則依w小到大排)將city[K]排序，此時將只討論city[k-1].e<city[k].e的情況，只要檢察前(k-1)次的w值大於第k次的w值的總和就是解答，但如果又用兩個for loop來跑又變成O(n^2)的算法，本題可簡化為求city[K]的逆序數，使用mergesort求逆序數(可參考UVa 10810)，此算法為O(nlgn)會AC。

UVa 10810 Ultra-Quicksort

本題求數字陣列的逆序數

算法：使用mergesort

UVa 10026 Shoemaker's Problem

　　本題是指鞋匠一次只能選一個工作做，以Sample Input為例，如果先選第一件工作，它需要完成的時間為3天，那麼這3天就無法做其他工作，罰金就為3*(1000+2+5)元，本題要找出選擇工作的次序使得罰金最小。

想法：
　　兩相鄰事件a(Ta,Fa),b(Tb,Bb)無論排成ab或是ba，其他部分的罰金是固定的所以差異在於ab(Ta*Fb)還是ba(Tb*Fa)的損失較小

假如是ab較小，則

• (Ta*Fb)<(Tb*Fa) 
• => (Fa/Ta)>(Fb/Tb) 

a的(罰金/時間)比較大

因此本題解法是將每個工作(Fi/Ti)由大到小排序

UVa 10420 List of Conquests

前言寫很多，其實就只是找每個國家的重複個數而已
想法：
　　只存國家名稱=>按名稱排序=>找重複數量

UVa 156 Ananagrams

　　本題是輸入一堆單字，come, EoMc, emoc, ECMO這四個單字是一樣的，輸出的單字找不到其他字與其相同。輸出按ABC..abc..順序。

想法：

　　將字母皆視為小寫，而替每個字母產生一個亂數，單字將字母的值加起來存成一個value，如果兩個單字的value一樣則為相同。

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=>之後沒有數字必須沒有空格
• 每個問題後面都要有一個換行(包含最後一個問題)