UVa 11038 How many 0's?

題目連結
想法：
　　將問題簡化為求1~m 0的總數，以及1~n 0的總數，然後最後再相減。
　　求1~n 0的總數，要將n分別算每個位數0的個數，舉例如30324：

• 先從右邊第一位'4'開始，其左邊為3032，表示1~30320在"第一位"總共有3032*1=3032個0
• 換第二位數'2'，其左邊為303，表示總共有303*10(右邊有1位)=3030個0
• 再換第三位數也是一樣，30*100=3000個0，
• 注意第四位數為'0'，因此原本應該是3*1000，但第3個1000其實只到324而以，所以為2*1000+324+1=2325個0 (+1是因為別忘了0~324是325個)
• 最後一位'3'，它是最高位數，因此不會有0
• 所以總共為3032+3030+3000+2325=11387

因此，此演算法從最低位(i==1)開始到最高位(i==k)結束，如果第i位不為0，直接左邊數字x10^(i-1)，如果第i位為0，那麼(左邊數字-1)x10^(i-1)+右邊數字+1，最後把每位數的0總數加起來即可。

UVa 620 Cellular Structure

題意：給定O為一條細胞序列

• 若O僅僅為'A'，那麼是simple
• 若O為'OAB'的型態，則OAB的O需要符合O的3種型態的其中一種，如果符合則為Fully-Grown，否則為Mutant。
• 若O為'BOA'的型態，則BOA的O需要符合O的3種型態的其中一種，如果符合則為Mutagenic，否則為Mutant。

想法：

　　用遞迴式parsing來分析O為哪種型態，如果為第2種和第3種，則要繼續呼叫遞迴分析O的型態，只要分析過程中只要O不符合3種的其中一種，則不用再分析，直接回傳Mutant。

UVa 10101 Bangla Numbers

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

UVa 10696 f91

想法：
　　典型的DP題目，把需要遞迴計算的答案用陣列存起來即可。

UVa 136 & POJ 1338 Ugly Number

想法：
　　下一個數必定是從之前的某個數x2或x3或x5而來的，因此要找第n個數(N[n])，就把前n-1個數x2,x3,x5，找出大於(N[n-1])的最小值。
　　另外找第n個數的時候，乘以2不用每次都從第0個開始乘，每次紀錄2乘到哪個位置，以後就從這個位置往後找即可。例如12是從6這個數字乘以2而來，那麼要找12以後的number的時候，只要從6以後的數字乘以2開始找，因為6以前的數字乘以2不可能大於12，乘以3和乘以5也是同樣道理。

UVa 495 Fibonacci Freeze

想法：
　　本題單純求費柏那西數列，因為n值很大，所以要做大數加法，可以以1000為一個位數，提升效率。

UVa 10446 The Marriage Interview

本題連結
想法：
　　依照題意，將算過的答案記錄下來，在遞迴裡面如果已經算過，就直接回傳答案，避免重複計算。

UVa 10334 Ray Through Glasses

本題連結

想法：
 　　觀察圖，能造成下次數量變多的折線，其最右邊"尖點"都位在上面那條線或下面那條線，例如a2=3，有'2'個"尖點"位在上面那條線，因此能使得a3比a2多出'2'條摺線(a3=a2+2=5)，在觀察a3，有'3'個尖點，因此能使a4比a3多出3個折線(a4=a3+3=8)。那麼尖點的產生方式在於前一個的折線數量，例如a2的尖點來自於a1的箭頭與上面那條線的交點，所以a2尖點的數量=a1，因此我們可得a3=a2+(a2尖點)=a2+a1。
　　簡而言之，本題為費伯那西數列，a(n)=a(n-1)+a(n-2)，而另外由於n可到1000，因此要自己寫大數加法。

UVa 900 Brick Wall Pattern

本題連結

想法：
　　我們用－表示橫的磚塊，∣表示直的磚塊，而兩個直的∣∣可以換成兩個橫的＝，以長度為5舉例，一開始我們可以先假設都是直的∣∣∣∣∣，首先我們可以將兩塊直的換成橫的＝，注意現在兩塊橫的有２個空位，分別是左邊和右邊，然後我們剩下3個直的磚塊，因此把這３個直的放到２個空位的方式為Ｈ(2,3)=4。再將兩個直的換成兩塊橫的，變成＝＝，現在４塊橫的有３個空位，然後剩下１個直的，因此為H(3,1)=3，最後全部加起來就是答案了，1+H(2,3)+H(3,1)=8。
　　本題其實寫出排列組合的C函數就完成了，H(m,n)=C(m+n-1,n)，因此可以先去寫UVa 369是C的題目，而注意type要用long long int。

UVa 10285 Longest Run on a Snowboard

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

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


    

UVa 10037 Bridge

本題連結

題意：
　　每個人的移動速度不一樣，兩個人走時間是以較慢那個人，一次只能兩個人走過去橋的對面，然後需要有一個人把手電筒送回來，求耗費時間最少的方法。

想法：
　　先將數列P排序好，時間由小到大，本題可以分為幾種情況：

1. 只有一個人：直接走過去，時間為P[0]。
2. 兩個人：直接走過去，時間為P[1]。
3. 三個人：P[0],P[1],P[2]，時間為P[1]+P[0]+P[2]
      P[0] P[1]
      P[0]
      P[0] P[2]
4. 三個人以上：如果是偶數個人(例如4個人)，可利用P[0],P[1]不斷將最後面兩個人送到橋的對面，這樣就回到第二點，如果是奇數個人，不斷將最後面兩個送過去就回到第三點。
   將最後面兩個送到橋的對面有兩種方式，設時間最少兩人為P[0],P[1]，最後面兩個人為P[X],P[Y]：
   
   方案A(如Example)： 時間為 P[1]+P[0]+P[Y]+P[1]
      P[0] P[1]
      P[0]
      P[X] P[Y]
      P[1]
   方按B：時間為 P[X]+P[0]+P[Y]+P[0]
      P[0] P[X]
      P[0]
      P[0] P[Y]
      P[0]
   
   因此每次送最後兩個人過去的時候，要比較兩種方式的時間，如果(方案A<方案B)就使用方案A，否則使用方案B。

UVa 642 Word Amalgamation

本題連結
想法：
　　給不同的單字不同的Hash值，在比對Hash值來找。


2014/2/23 更新： C++(11)寫法

UVa 11489 Integer Game

http://uva.onlinejudge.org/external/114/11489.html
題意：
　　由S先開始，每次拿掉一個數字都要使得剩下的"位數和"是3的倍數，如果找不到數字拿掉就輸了。

想法：
　　我們知道如果數字和為3的倍數，那麼接下來要拿掉的數字必須為3的倍數，才能繼續使得數字和為3的倍數。本題可將一連串的數字分成兩組：3的倍數和非3的倍數，然後有3種情況：

1. 如果非3倍數的數字和是3的倍數：那麼只要看3的倍數的數字個數是奇數個還偶數個就能決定贏家，因為當拿完3的倍數的數字後就無法再拿任何數字了。
2. 如果非3倍數的數字和不是3的倍數：
   那麼需要確認是否能從非3倍數的數字中找出使得數字和為3的倍數，
   ＊如果找的到，那麼就可以回到狀況1
   ＊如果找不到，代表是T獲勝，因為從一開始就無法拿掉任何數字。

UVa 10189 Minesweeper

題目連結

想法：
　　判斷如果輸入的字元為'*'，就將其八個方向都+1，最後輸出每個位置的數量。

註：本題只有Case與Case之間才有空行

UVa 10077 The Stern-Brocot Number System

題目連結

想法：
　　初始化三個數L=0/1, M=1/1, R=1/0，設輸入的分數為a：

• 如果a<M，那麼要往左邊走，
      R = M;
      M = (L分子+M分子)/(L分母+M分母);
• 如果a>M，往右邊走，
      L = M;
      M = (R分子+M分子)/(R分母+M分母);
• 如果a==M，停止。

這題和二分搜尋很類似。

UVa 10050 Hartals

本題題目連結

題意：
　　每個政黨都有發表演講的週期，只要星期日~星期四該天有任何一個政黨演講，hartal數目就+1，最後輸出hartal。
想法：
　　日數從1開始，每天對每個政黨的週期取餘數，若為0代表該日那個政黨有演講，hartal++。

UVa 12192 Grapevine

本題題目連結

題意：
　　N為該矩形範圍的高，M為長，並輸入該範圍內每個數字，Q代表要測試幾次，每次給定L,U，在範圍內求出最大正方形的邊長，該正方形內的數字都要符合L<=H[i][j]<=U，也就是介於L和U之間。

想法：
　　題目給的範圍內的數字是有限制的，同列右邊比左邊大，同行下面比上面大，因此隨便框出一個正方形，其左上角必定為最小，右下角必定為最大，所以我們只要確認左上角>=L，和右下角<=U是否滿足即可。那麼首先從每列開始，在同一列使用二分搜尋找出左上角，然後沿著對角線二分搜尋找出右下角，最後把每列找出的正方形選出邊長最大的即可。

UVa 10520 Determine it

本題題目連結

想法：
　　本題就是按照題目規則下去做，從a(n,0),a(n,1)~a(n,n)，然後算a(n-1,0)~a(n-1,n)，一直到a(1,0)~a(1,n)，最後print a(1,n)。

　　另外原本想說就算輸入19,20的答案也還再int的範圍內，沒想到送出去是WA，後來改成long long int就AC了=  ="

UVa 834 Continued Fraction

本題題目連結

想法：
　　這題可以自己舉幾個例子算出分數，找出規則，解法如下，由題目Example，從(43,19)逆推回去

1. 首先2的話就是43/19=2,43%19=5，那麼現在[2;] & (5,19)
2. 19/5=3,19%5=4，得到[2;3] & (5,4)
3. 倒數的緣故，交換兩數，現在[2;3] & (4,5)
4. 重複2~3步驟，直到第一個數為1

UVa 494 Kindergarten Counting Game

想法：
　　檢查不是字母的下一個字元是不是字母，如果是數量就加一。對於這種input很多字串的情況，可以使用freopen("input.txt","rt",stdin)在debug時較為方便，但提交時記得刪除。

UVa 846 Steps

題意：
　　給定兩地的位置x,y，其距離為(x-y)，而第一步和最後一步的距離皆規定為1，每次踏下一步的距離只能比上一步的距離多1或少1或一樣，本題求最少走的步數，從Example來看x=45,y=50，距離為5，其最少步數為{1,2,2,1}。

想法：
　　因為本題只要求最少的步數即可，因此過程如何安排就不重要，只要符合規定即可，所以我們可以先一步從起點一步從終點開始往中間走，變成{1,1},{1,2,2,1},{1,2,3,3,2,1}...這樣，舉個例子如果兩地距離為14，那麼剛才的算法到{1,2,3,3,2,1}就會停止，因為已經12了，在+2*4就會超過14，這時候只要判斷12+4<14，再走一步就可以了，我們不管這步應該排在哪個位置，反正這步的距離一定<=4。還要考慮另外兩種情況，分別是兩地距離如果為17，那麼12+4<17，就要再兩步，而如果兩地距離為12，那麼就剛好。

UVa 10038 Jolly Jumpers

題意：
　　N個數的數列中，(1,2,3...,N-1)這些值都要被兩數字的差值涵蓋到，從Example來說，(1,4,2,3)的差值分別為(3,2,1)，所以有涵蓋(1~3)，因此為Jolly，(1,4,2,-1,6)的差值為(3,2,3,5)沒有涵蓋(1~5)所以不是Jolly

UVa 10340 All in All

如果陣列開很大的情況下，要放在global，不然會造成stack overflow，就會看到RuntimeError的出現。

UVa 714 Copying Books

本題題目連結
想法：
　　這題跟UVa 11413 Fill the Containers很類似，題目給定M本書及K個員工(1<=K<=M<=500)，每本書有不同的頁數，同本書只能分配給同個員工，我們用二分搜尋找出每個人的工作量(頁數)的上限，(題目要求工作量越少越好，但如果太少就需要>K個員工)。此外如果有多組解的情況，index越大的員工所分配的書要盡量的多，因此分配書的時候index從後面開始，但注意分配時每個人至少要有一本書，因此如果(剩下的書<=剩下的人)，就算那個人還沒分完，也要直接換下一個人。

UVa 10474 Where is the Marble

本題題目連結
想法：
　　將數列排序好後直接用二分搜尋即可。

UVa 10341 Solve It

本題題目連結
p*e^-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x² + u = 0
0<=p, r<=20 and -20<=q,s,t<=0

想法：
　　因為題目的係數有範圍限制，使得x越大，f(x)的值就越小，為遞減函數，因此可使用二分搜尋逼近答案。

UVa 11413 Fill the Containers

題意： 　　
　　給定N個牛奶瓶子，以及M個容器，每個牛奶瓶子n[i]的容積不一樣(題目會給)，我們所要求的是一個"容器"的容積至少要"多少'才能使得只用'M'個就能把那N個牛奶瓶裝完，而裝的時候有幾個規則：第一個牛奶瓶倒入容器後才能換第二個，每個牛奶瓶只能到入同個容器(因此如果該容器還有空間但不夠裝完這個牛奶瓶的話，就只能換下個容器)。
　　從Example來看：5個牛奶瓶子要到入"3"個容器裡(沒錯，題目規定不多不少就是3個)，那麼至少每個容器的容積要6才能滿足該條件{(1,2,3),(4),(5)}。 

想法： 　　
　　使用binary search找出符合的條件，Left=(所有牛奶瓶容積最大的那個)，Right=(所有牛奶瓶的容積)。

UVa 10487 Closest Sums

想法：
　　先將數列n排序好，之後n[j]從j=0開始，搜尋(q-n[j])，如果存在，則代表本題得解，如果不存在，則從最接近(q-n[j])的數字中挑選一個n[k]使得(n[i]+n[k])最接近q，將答案放入ans，然後j=1繼續搜尋...，直到n[j]>(q/2)為止，輸出ans。

UVa 11057 Exact Sum

想法：
　　先將書本價錢排序，然後i=0開始，.搜尋(用binary search)確認(M-book[i])是否存在，如果存在就先將該組答案暫時保存，因為題目有說如果有多組答案要寫出差距最小的那組，因為我們已經排序，所以越後面的答案的差距越小。

UVa 11520 Fill the Square

題意：
　　如果它不是'.'，那麼該位置的字母已經是固定的了，剩下是'.'的位置就要由我們依照左到右，上到下的順序來分別填入該位置一個英文字母，而填入字母的方式是由'A'開始，如果其上下左右已經有'A'，那麼再換'B'，以此類推....，如果'A'能填就要填，舉個例子：
..B
.B.
...
的解答為
ACB
CBA
ACB
而不是底下這個
BAB
ABA
BAB

想法：
如果該點為'.'，則從'A'開始，檢查其上下左右來決定'A'可否填入，不然就換'B','C'....，一直到可以填入為止

UVa 11729 Commando War

想法：B的總合是固定的，那麼要使得答案最小，就要盡量讓J的時間範圍重疊，因此將J由大排到小

UVa 11292 Dragon of Loowater

想法：

1. 排序m[i]與n[i]由小到大
2. 一一找尋並累加money

UVa 11054 Wine trading in Gergovia

想法：
　　舉個例子，5 1 3 2 -11，先假設答案ans=0表示運送所需的單位，那麼

1. 可以看成將第一個人要買的酒移到第二個人，並將ans加上5，ans=5
2. 那麼現在變成6 3 2 -11，繼續將第二個人移到第三個人，ans=11
3. 變成9 2 -11，一樣移到第四個人，ans=20
4. 變成11 -11，移到最後一個人，ans=31，得解

　　再用example作為例子

1. 5 -4 1 -3 1 , ans=0
2. 1 1 -3 1 , ans=5(+5)
3. 2 -3 1 , ans=6(+5+1)
4. -1 1 , ans=8(+5+1+2)
5. 0 , ans=9(+5+1+2+1) //因為是運送的單位，記得加絕對值

UVa 10249 The Grand Dinner

題意：
　　有M個隊伍以及N張桌子，每個隊伍的人數與每張桌子的座位均不一樣，現在要將同個隊伍的隊員分配到不同的桌子(同隊的不能在同張桌子，否則輸出0)
想法：

1. 每個隊伍的隊員排的時候都先挑剩餘位子最多的桌子
2. 如果該隊隊伍人數大於桌子數量或是座位不足則跳出並print 0

UVa 10020 Minimal Converge

題意：
　　數線上有很多條線段，每條線段給左右兩端的座標(L,R)，題目問如何用最少的線段去覆蓋[0,M]這個範圍

想法：

1. 依照L值來排序
2. 第一次left=0，從a[0]開始找(a[i].L要小於0)，找到一個最大R值(Max)的線段a[Max_index]
3. left=Max_index：下次從這開始找
4. right=Max
5. 第二次一樣從left開始找(a[i].L要小於right)，找一個最大R值(Max)的線段a[Max_index]
6. 重複3~5，直到Max大於M

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的情況