Programming學習筆記: 2014

2014年6月5日星期四

POJ 1226 Substrings

想法：
先將全部的字串依照length由小到大排序，把最短的那個字串拿來枚舉，由長到短枚舉該字串的所有substring，以sample input第二個case舉例，最短的字串為"rose"，枚舉substring "rose", "ros", "ose", "ro", "os"...。
每次枚舉到一個substring後，記得還有反轉sub_inverse，把substring和sub_inverse拿來和其他字串(除了最短的字串以外的字串)比較，這邊我是套KMP Algorithm，如果其他字串全部都找的到substring或sub_inverse的話，表示找到答案，輸出該substring的長度。

POJ 3461 Oulipo

題意：
找出W字串在T字串中出現幾次。例如W="AZA",T="AZAZAZA"，答案為3次。

想法：
套KMP演算法

2014年6月3日星期二

UVa 10806 Dijkstra, Dijkstra

題意：
給你一個無向圖，每條邊有cost，現在問如果不走已經走過的邊，則從S到T，然後再從T到S的最少cost是多少，如果無法達成則輸出"Back to jail"。

想法：
最小cost最大流，S到T再從T到S，也就是T當作源點，S當作匯點，從T流到S，看是否能流過去2條，如果能則輸出min_cost，否則輸出"Back to jail"。
因為同一條邊不能重複走，因此可以用一個二維矩陣used[][]，在SPFA找"正向邊"的時候檢查used[i][j]!=true，除了code 82行和96行之外，其他都和MCMF模板一樣。

UVa 10746 Crime Wave - The Sequel

想法：
銀行編號1~N，警察編號N+1~N+M，源點S=0以及匯點T=N+M+1。一開始先將S連到每間銀行，每個警察連到T，以及每間銀行連到每個警察，以上單向邊容量都為1。
接下來就是套模板做MCMF，注意輸出的時候因為是double，因為進位問題所以要把答案加上一個極小的數字，例如，如果printf("%.2f", 17.225);，結果是輸出17.22，因此要printf("%.2f", 17.225+0.000000001);才會是正確答案17.23。

2014年5月31日星期六

UVa 563 Crimewave

想法：
點與點之間的邊是雙向邊，但是走某一邊後另一邊就不能走了，所以我們把一個點i分成兩個點i和i'，i到i'容量為1，點i建圖的時候：

cap[i][i']=1
假設j在i的上方，cap[i'][j]=1，上下左右依此類推

然後我們還要有個super source(S)和super sink(T)，把最外面四個邊的點i'連到T，S連到輸入的座標i(也就是銀行的位置)。建完圖後，就是做最大流看結果是否等於銀行的數量即可。

一開始TLE了，後來用了個vector<int> edge[MAX]來存每個點i能連到哪些點，避免bfs的時候nxt要從0到最後(程式碼81行)，最後時間為1.8s。

2014年5月30日星期五

UVa 10594 Data Flow

題意：
給你一個無向圖，兩點之間的邊的容量是K，每條邊有不同的cost，現在有大小為D的資料，要從起點傳到終點，問把全部資料傳過去的最小cost是多少，如果不能全部傳過去則輸出Impossible.

第一行輸入N M：總共N個點，編號從1~N，然後底下有M行
有M行，每行u v c：表示點u和點v之間的cost為c(雙向圖)
最後一行D K：要傳的資料大小為D，每個邊的容量為K

想法：

最小cost最大流題型(MCMF)，基本上就是建圖，然後套MCMF演算法模板，但提交後發現時間根本是壓秒過@@，花了2.979s(時限3s)，但是這個秒數排名還在前一半以內...。

不過還是要壓一下秒數，看了同學的code後，發現這題可以最佳化的地方在於"每條邊的容量都是一樣的"，所以你可以把每條邊的容量當成1，然後再乘以K就好了。底下附上兩種code，第一個是差點TLE的模板code，第二個是最佳化的code，兩者的差別只差在MCMF()這個function的寫法。第二個的時間是0.135s，和原本差了20幾倍。

POJ 2411 Mondriaan's Dream

想法：

狀態壓縮DP，我們定義一列(橫的)一個狀態D：

第i位置為1表示這一列位置i和下一列位置i是由直長方形組成(|)
第i位置為0表示1以外的情況

注意以上的定義，以這題題目的圖來看，

第一列狀態D1=(00100001100)2
第二列狀態D2=(11010010000)2
第三列狀態D3=(00100001001)2
其他列依此類推，最後一列一定全部都是0。

接下來定義dp[i][d] = k，表示第i列在狀態d的情況下有k個方法數。如果能接受的話，那麼根據定義，如果第H列是圖的最後一列，本題答案就是dp[H][0]。

定義完成後，基本上的做法是從最上面那列開始往下更新，例如第i列狀態a如果能和第i+1列狀態b相鄰(注意任兩個狀態不一定相鄰..)，那麼dp[i+1][b]+=dp[i][a];，就這樣枚舉所有狀態，最後輸出答案dp[H][0]。

為了簡化code，不用初始化第一列每個狀態方法數是1(因為第一列所有狀態都是可以的)，因此我們直接初始化dp[0][0]=1，令這個假設的第0列狀態0方法數為1。

另外在做以上的for loop之前，先建個狀態是否可以相鄰的表，令adjacent[i][j] = true表示狀態i在這列而狀態j在下一列是可以相鄰的，如最上面題目example，adjacent[D1][D2]==true，adjacent[D2][D3]==true。

最後總結一下，為了加速，我們可以總是讓寬比較小高比較大，這樣可以減少每列的狀態數，另外也能用個ans[H][W]來紀錄答案，如果重複的題目就直接輸出即可。

2014年5月27日星期二

UVa 10364 Square

想法：

dfs加上各種減支：

如果所有stick的長度和(sum)不能被4整除直接輸出no
如果最長stick的長度已經大於(sum/4)直接輸出no
dfs的時候已經排完三個邊直接return true，因為第四個邊一定排得出來
先將stick由大排到小，每次dfs的時候stick不要從第一個開始挑選，而是要從上一層dfs選到的stick的下一個開始選。

基本上第四點是關鍵，有跟沒有就是0.0x秒和TLE的差別。

2014年5月26日星期一

UVa 11218 KTV

題意：
總共有9個人(編號1~9)要分成3組唱歌，每組3個人，每個人只能唱一次。第一行N表示底下有N種組合，每種組合a,b,c,s，前三個是人員編號，s是該組合的分數。從N種中任選三種組合使得1~9號都能唱到歌，並且使得分數的和最高，輸出該分數，如果找不到組合滿足大家都能唱到歌則輸出-1。

想法：
bitmask，(1<<9)-1表示所有人都唱的到歌的狀態，二進位來看就是(111111111)2，dp[i]=j表示在狀態i的情況下最高分數為j，因此dp[(1<<9)-1]就是所有人唱的到歌的最高分數。
用dfs來枚舉不同組合，當人員沒有重複的時候才能將兩個狀態合併在一起，例如(000000111)2和(000111000)2這兩個狀態可以合併變成(000111111)2，並去更新dp[(000111111)2]的分數，不斷更新所有可能的合併來枚舉所有情況。

UVa 10651 Pebble Solitaire

題意：
跳棋，例如"oo-"表示第一和第二個位置有棋子，第三個位置是空的，因此第一個位置的棋子可以跳過第二個位置的棋子並取走第二個位置的棋子，變成"--o"。題目給定一個12個位置的棋盤，問經過不斷跳棋後，剩下最少棋子的數量。

想法：
想到兩種方式：bitmask+bfs或是backtracking，兩種方法其實差不多，都是把所有的情況枚舉，找出最小値。第一種方法為0.009s，第二種為0.012s，時間相差不大，寫backtracking是較簡單的。

2014年5月22日星期四

POJ 1753 Flip Game

想法：
Bit運算，16位來表示棋盤的情況，16個0表示全白，16個1表示全黑。用BFS演算法，從一開始的情況開始出發，直到變成全白或全黑為止，或是無法變成全白或全黑。

POJ 2117 Electricity

題意：
這題是將graph中移除一個點，graph會變成D個獨立部分，求D的最大値。
第一行輸入P和C表示有P個點(0~P-1)和C條邊，每條邊都是雙向的。

想法：
分成兩個

如果C==0表示P個點沒有任何的邊，直接輸出P-1
本來的圖就分成N部分(N可能==1表示所有點都是連通的，但N也可能>1)，移除某個點i能將該部分再分成cut[i]部分，那麼其中一個候選答案為N+cut[i]-1，找到最大的候選答案。套Cut Vertex模板求cut[i]。

第二點舉個例子：

5 3

0 1

1 2

3 4

表示0,1,2和3,4不連通，所以N==2，N是固定的，然後例如移除點1，cut[1]==2(因為(0,1,2)這部分移除點1會將0,2分開變成2個部分)，因此候選答案就是2+2-1=3，也是這個測資的解答。

UVa 10199 Tourist Guide

題意：
LuckyCat中文翻譯，基本上就是求所有Cut Vertex。

想法：
Cut Vertex模板。

POJ 1523 SPF

題意：
基本上就是給你一個Network的Graph，然後求這graph的所有割點，以及如果去除掉該割點能將Network分成幾個部分。
本題都是雙向邊，且每個測資是以1個0分開，最後結束也是1個0。

想法：
Cut Vertex模板。

UVa 247 Calling Circles

題意：
LuckyCat中文翻譯
想法：
SCC Tarjan演算法模板，將每個SCC的朋友名字都存下來，然後一行一行輸出。

UVa 11838 Come and Go

題意：
題目求這個城市是否為一個強連通的城市(從任意點出發可以抵達每個點)，第一行會給N個點和M條路，底下M行每行有V,W,P，如果P==1表示該條路為單向V->W，P==2則是雙向V<->W。

想法：
SCC模板，檢查scc_cnt是否為1，因為scc_cnt==1表示整個graph都可連通。

UVa 315 & POJ 1144 Network

題意：
    critical point指的是在一個connected graph中，如果移除該點，會使得該graph不再connected，則該點為critical point(cut vertex，割點)，現在給你一個graph，求critical point的數量。
    給你一個N表示共有N個點，底下最多N行，以0表示本次case輸入完畢，每行有a,b1,b2,b3.....，表示(a,b1),(a,b2),(a,b3)為邊，記得建邊的時候為雙向。

想法：
   cut vertex模板題。

2014年5月8日星期四

UVa 10080 Gopher II

題意：
有N個地鼠和M個地鼠洞，每個點都有座標(x,y)，因此每隻地鼠和每個地鼠洞之間有不同的距離，每隻地鼠的移動速度都是v，現在有老鷹會在s秒後抓沒有跑進洞的地鼠，一個地鼠洞只能藏一隻地鼠，求沒有躲到洞裡被老鷹抓走的地鼠的最少數量為?

想法：
地鼠在左邊，地鼠洞在右邊，把每隻地鼠與能在時間內跑到的地鼠洞都建一條邊，然後做最大匹配，答案就是(地鼠數量-最大匹配數)。

UVa 1194 & POJ 1325 Machine Schedule

題意：
    有A,B兩台機器，A的mode從0~n-1，B的mode從0~m-1，現在有k個job，底下有k行，每行有三個數i,x,y表示第i個job，A機器需用mode(x)完成這項工作，B機器則是需用mode(y)，一向工作只需交給A或B其中一個即可。有個規則是A,B這兩台機器變換mode的時候需要restart一次，例如mode(1)變成mode(10)需要restart一次，一開始兩台機器都是從mode(0)開始，問如何分配工作給A或B使得總restart次數最小，並輸出restart次數。

想法：
    一件工作x,y如果選x則不用y，反之選y就不用x，但都是要restart一次，因此可以想到最大匹配數，如果x或y其中一個已經匹配好了，表示A或B其中之一已經restart一次，則這件job就可以跳過。
    具體做法是，將第i個工作x放到左邊那群，y放到右邊那群，並建立(x,y)這條邊，然後套模板求最大匹配數就是答案。注意讀入測資的時候如果x或y其中是0，則直接跳過不用建邊，因為機器從mode(0)開始。

UVa 663 & POJ 1486 Sorting Slides

想法：
做最大匹配，做完可從llink[i]=j得到每條匹配的邊(i,j)，也就是(i,j)是可能的答案，但要確認這條邊(i,j)的唯一性。
例如Sample Input的第二個測資，做完最大匹配可得到(A,1)(B,2)兩條邊，最大匹配數為2，要確認(A,1)是否唯一，就把(A,1)這條邊去掉並且禁止，然後再做一次最大匹配，會變成得到(A,2)(B,1)，最大匹配數還是2，與數量原來一樣並沒有減少，因此可知(A,1)這條邊不唯一。同理(B,2)也把它去掉並禁止，再做一次最大匹配，如果最大匹配數比原本小，這條邊就是答案可以輸出，反之如果最大匹配數和原本一樣，則這條邊不唯一不能輸出。
從底下code可以看到最大匹配的模板函數Bipartite(int n, int u, int v)多了兩個參數u, v，表示做最大匹配的時候禁止(u,v)這條邊的使用(line 65)。

UVa 10349 Antenna Placement

題意：
如題目的圖，一個圓圈最多能圈住兩個'*'，現在問一幅圖有n個'*'，最少用多少個圓圈就能把所有'*'圈住？

想法：
最大匹配問題，將圖上所有點分成兩群相間隔，例如
101010
010101
101010
在編號1的'*'建一條邊連到S(Super Source)，在編號'0'的'*'建一條邊連到T(Super Sink )，然後相鄰的'*'彼此也建一條邊，這些邊的容量都是1，建完邊後套一次最大流模板，就是最大匹配數。
做最大匹配得到的結果不是真正的答案，例如*****五個'*'的最大匹配是2，答案則是(5-3)，因此本題答案為(所有'*'數量-最大匹配數)。

2014年5月1日星期四

POJ 1742 Coins

題意：
有N種硬幣，每種硬幣價值A[i]元以及該種硬幣的數量為C[i]，問這些硬幣在最多總合為M元的限制下有幾種組合數?

想法：
01背包，dp[i]=true表示i元可以被組合出來，最後看dp[1]~dp[M]有幾個true就是答案。這題時間限制嚴格，因此用POJ 1276那篇的方法還是會TLE，因此在底下code22行，我們知道如果j是從M~0表示一次放一個物品，每種要做C[i]次，現在22行j從0開始~M，是用無限背包的方式，先把物品當作無限個，類似greedy的方式，然後用個num陣列來計數，這樣每種物品都只要跑1次就可以了。

2014年4月30日星期三

POJ 1384 Piggy-Bank

題意：
存錢桶重量E，裝滿硬幣的時候重量為F，現在有N種硬幣，每種硬幣的價值為P重量為W，問這個存錢桶至少為多少錢？

想法：
最小背包問題，先將dp[i]初始化成INF，將最大背包的max()改成min()就可以了。

POJ 2392 Space Elevator

題意：
K種不同的磚塊，每種磚塊的高度為h，能蓋的最大高度為a，數量為c，由於安全考量，所以當現在蓋的高度超過該種磚塊的a時，就不能再用該種磚塊，求最大能蓋的高度？
例如sample input，第二種磚塊的高度為23，所以如果現在建築物蓋到24以上，就只能用第一種和第三種磚塊繼續蓋。

想法：
這題要先將磚塊的a値由小到大排序，再做背包問題，算是一種greedy的方式，把a値小的磚塊盡可能放在底層，否則無法達到最大高度。
例如底下左邊這組，答案是4，如果不排序成右邊的話，算出的結果會<4。
2 2
1 4 3 2 2 1
2 2 1 1 4 3
且最後要枚舉一下dp的每個値找出最大値，因為最大値不一定位在dp的最後一個位置。

POJ 1276 Cash Machine

題意：
不同價值Dk元的鈔票有Nk張，現在要求用這些鈔票能湊出最接近cash是多少元？

想法：
背包問題，dp[i]=k表示i重量上限的背包最多能裝k價值的東西，題目給的Nk表示該物品的數量，而Dk是重量同時也是價值，這樣去求背包問題。因為這題時間限制，須採用和POJ 1024一樣的做法，將Nk件捆成1+2+4+8+16+32+....+left的形式，減低運算次數。

2014年4月29日星期二

UVa 10313 Pay the Price

題意：
LuckyCat中文翻譯

想法：
用dp[i][j]=k表示i元最多用j個硬幣有k種方法，詳細註解在底下code：

UVa 10465 Homer Simpson

題意：
有兩種漢堡A和B，吃一個A需要m分鐘，吃一個B需要n分鐘。現在給你t分鐘，問在"剛好用完"t分鐘的情況下最多能吃幾個漢堡k，輸出k；如果沒辦法剛好用完t分鐘，則找最接近t分鐘的k値，輸出k和差幾分鐘。

想法：
背包問題，重量和物品價值都是時間，Time[i]=k表示給你i分鐘最多能用到k分鐘，如果Time[t]==t表示剛好用完t分鐘，否則最多就是用到Time[t]分鐘，差t-Time[t]分鐘；另外用num[i]=k用來記錄i分鐘能吃k個漢堡。

UVa 10130 SuperSale

題意：
有一家超市有N種商品正在做特價，每種商品數量無限，但規定一個人每種只能買一個，P表示該種商品價值P元，W表示該種商品重W。現在有一家庭共G人，每個人都有不同的背包重量上限MW，問這一家人能買到最高商品價值為多少?

想法：
背包問題，dp[MW]=k表示重量上限MW的背包裝的物品最多價值k。

UVa 674 Coin Change

想法：
用method[i]=k表示i元有k種方法，枚舉所有錢幣，假設該錢幣為j元，則method[i+j] = method[i+j] + method[j]，表示method[i+j]的一部分方法數是由method[j]而來。

2014年4月24日星期四

POJ 1014 Dividing

題意：
每次有n1,n2,n3,n4,n5,n6六個數字代表價值1的大理石有n1個，價值2的大理石有n2個，....，價值6的大理石有n6個，現在要將這些大理石分成兩堆，問能否使得這兩堆價值一樣？

想法：
背包問題，一開始單純把價值i的大理石做了ni次，例如價值5有70個，for迴圈就跑70次，結果就TLE了。
後來學到其實可以將70 = 1+2+4+8+16+32+7，也就是ni=1+2+4+8+....+2^x+left，這樣可以大大減少for的次數，ni如果是70只要做6+7=13次。

2014年4月20日星期日

UVa 10944 Nuts for nuts..

想法：
狀態壓縮DP題目，假設Larry編號為0，堅果編號從1~N，一開始先將任兩點距離算好，因為移動是八個方向，所以dis[i][j] = max(|x[i]-x[j]|, |y[i]-y[j]|)。
接下來做dynamic programming，定義dp[i][j]這個矩陣用來存最短步數：

i為該狀態最後收集到的堅果編號
j表示該狀態

狀態的表示是用二進位，例如有5個堅果，若j=22則二進位為10110，表示編號2,3,5號的堅果已經被收集過了。那麼dp[3][22]就是在2,3,5號堅果已經收集且3號堅果是最後被收集的最短步數。
定義完成後，首先先將dp初始化成INF，然後對於dp[i][1<<(i-1)]初始化成dis[0][i]，因為dp[i][1<<(i-1)]就是從起點走到編號i堅果的最短步數。然後以上面例子繼續，5個堅果，從狀態0 (00000)開始，一直遞增枚舉到狀態((1<<N)-1) (11111)就算完成。
每次枚舉一個狀態i，例如10110，已經被收集的堅果編號j(也就是2,3,5)；沒有被收集的堅果編號k(也就是1,4)，然後再用迴圈跑這些已經被收集的編號j，每次就以這個編號j為最後被收集的編號(也就是dp[j][i])，加上j到k的距離去更新dp[k][i+ (1<<(k-1))]。整個式子
dp[k][1+ (1<<(k-1))] = min(dp[k][1 + (k-1))], dp[j][i] + dis[j][k]);

最後在檢查dp[1~5][11111]+dis[1~5][0](記得要走回原點)哪一個最小就是答案。

另外<<這個運算符的順序很低，所以括號要記得加。

2014年4月18日星期五

UVa 10779 Collectors Problem

題意：
有N個人(含Bob)以及M種貼紙(編號1~M)，每個人手上有不同種類的貼紙數張，Bob要透過和別人交換貼紙使得他擁有最多種類的貼紙。交換規則為，除了Bob以外的其他人只與Bob交換，且只有當手中該種類貼紙大於1張時才會交換沒有的種類，也就是Bob要用某甲手中沒有的貼紙種類與某甲交換，且某甲只當該種類他有大於1張時他才願意換出那張貼紙。
輸入第一行N M，接下來N行，每行第一個數字K表示那個人有K張貼紙，後面K個數字分別為每張貼紙的種類編號。N行中第一行為Bob。
輸出Bob最多能擁有幾種貼紙。

想法：
建圖做最大流，建圖方法為：

每個人i擁有j種類貼紙d張，則cap[i][j]=d，表示人與該種貼紙之間的容量為那個人擁有該種貼紙的張數。
"除了Bob以外"，每個人i如果擁有j種類貼紙(也就是cap[i][j]>=1)，則將cap[i][j]--，因為他要保留一張絕對不交換出去，如果cap[i][j]==0，表示那個人沒有j種類貼紙，所以他願意換入該種類貼紙1張，因此把cap[j][i]=1。
因為最後只要輸出Bob有幾種貼紙，建立每種貼紙到super sink(T)的容量為1。

POJ 2112 Optimal Milking

題意：

有K台機器以及C頭牛，每台機器能容納M頭牛，且點與點之間距離不一樣，現在要分配每頭牛到某台機器，某一隻牛走到機器路徑最遠，假設為D，現在要使得D値最小，並輸出D値。

輸入第一行為K C M，接下來有(K+C)*(K+C)矩陣，表示這(K+C)個點之間的距離(如果無法到達則為0)。

想法：

先用Floyd解出任兩點最短距離，然後用二分搜尋去找D値，每次二分就建立一個圖並做最大流，並判斷最後到達牛的數量是否為M，如果是則D値可以更小，如果不是則要把D値加大。

建圖方法為將每頭牛i和每台機器j之間的距離如果<=D，也就是dis[i][j]<=D，那麼把i,j兩個點之間容量設為1(cap[i][j]=1)
每頭牛與super source(S)相連，容量為1
每台機器與super sink(T)相連，容量為M

POJ 2455 Secret Milking Machine

題意：
有N個點(編號1~N)組成無向圖，總共有P條邊，要找出從編號1走到編號N共T條路徑(也就是有T條從1~N的路徑)，使得這T條路徑最長的那條為最小。假設T條中最長的那條路徑長為D，我們要找出D的最小値。
輸入第一行分別為N P T，接下來有P行，每行u v d表示有一條u到v距離為d的邊，注意u到v可能會有很多條邊，且這T條路徑不能重邊。

想法：
二分搜尋+最大流，用二分去找D値，每次二分時就重新建一個新的圖，建圖方法為假設dis[u][v]<=D，就把[u][v]容量+1，建完圖後做最大流並確認是否有T條路徑，如果有則D値可以再小，如果沒有則要把D値加大。

2014年4月16日星期三

UVa 825 Walking on the Safe Side

題意：
從左上角走到右下角，只能往右走或是往下走，有障礙的點不能走，問左上走到右下共有幾種方法？

想法：
高中排列組合題目，dp[i][j]的方法數一定是從dp[i-1][j]和dp[i][j-1]相加而來。

UVa 11389 The Bus Driver Problem

題意：
有n個司機，早班有n條路線，晚班也有n條路線，這2n條路線都有不同的距離，要安排每一個司機早班和晚班各一條路線，但是如果早班+晚班的路線距離超過d的話，超過每1單位就要加班費r元，求如何安排路線給每位司機使得全部加班費為最小，並輸出。

想法：
將早班n條路線由小到大排序，晚班也是，為了使得加班費總和最少，安排時就要盡量填滿d，因此早班最短配上晚班最長路線，然後早班第二短配上晚班第二長,.....依此類推。如果最短配上最短，會導致該路線和遠小於d，表示浪費了這位司機還剩下的距離，因此要盡量讓每位司機平均填滿d。

UVa 11833 Route Change

題意：
第一行有N M C K四個數字，N表示有N個地點(編號0~N-1)，M表示有M條路線，C-1為終點編號，K為出發點編號。
底下有M行，每行u v d三個數字，分別表示u到v和v到u這條路線需要花費d元。
本題特別的要求為，0~C-1為特殊地點，只要踏入0~C-1這C個地點內，例如i這個點<=C-1，之後的路徑就只能依照i, i+1, i+2, .....,C-1這樣走，只要不在特殊地點，就能前往任意其他地方，本題求K到C-1的最小花費。

想法：
依題目輸入將M條路線建好dis[u][v]=d，其他沒有連通的路線為INF。輸入完成後我們將編號小於C-1的點i，算出dis[i][C-1]，等等SPFA用到。
然後做K到C-1的SPFA最短路徑，注意如果踏入的點(nxt)為特殊地點(nxt<C)，不要丟入queue裡面，而是直接判斷cost[C-1]=min(cost[C-1], cost[nxt]+dis[nxt][C-1])，其他不是特殊地點的nxt，則依照一般SPFA把nxt丟入queue即可。

1459 Power Network

題意：
有發電站(只發電不耗電)，中繼站(不發電不耗電)，和用電站(只耗電不發電)三種node，題目求所有用電站耗電量總和的最大値。
輸入第一行有4個數字，n np nc m，n表示共有n站，np為發電站數量，nc為用電站數量，m為有m條電線。
接下來有m組(u,v)z，表示u到v該電線的容量為z。然後有np個(u)z表示編號u發電站發電量為z；再接下來有nc個u(z)表示編號u為用電站最大用電量為z。
想法：
最大流模板題，用super source串起所有發電站，super sink串起所有用電站。

POJ 2584 T-Shirt Gumbo

題意：
　　以sample input舉例
START 4 -> 4表示有4個人
SM ML LX XT -> 第一人能穿的衣服Size從S~M，第二人從M~L，...
0 1 1 1 0 -> 衣服S號有0件，M號有1件，L號有1件，X號有1件，T號有0件
END
求出是否能將衣服分配給所有人。
想法：
最大流題目，S表示super source，T表示super sink，S到每個人的容量為1，因為每個人只需要一件衣服；每種size的衣服到T的容量為該種size衣服的數量；然後做最大流，並判斷最後的數量是否與人數一樣。

2014年4月11日星期五

2014年4月7日星期一

POJ 2240 Arbitrage

題意：
所謂"套匯"指的是透過不斷兌換成別的貨幣，最後再換成原本的貨幣會比本來的錢多。
想法：
用R[i][j]表示i換成j的匯率，且初始化R[i][i]=1，做Floyd演算法後，去判斷R[i][i]是否大於1，如果大於1表示可以套匯。

POJ 2253 Frogger

題意：
有隻青蛙要從位置1跳到位置2，假設某路徑途中單次最大跳躍距離為D，求出D的最小値。
已sample input舉例，如果直接從(17,2)跳到(19,4)，D値為2，但如果從(17,4)跳到(18,5)再跳到(19,4)，D値為1.414。
3
17 4
19 4
18 5

2014年4月6日星期日

POJ 1860 Currency Exchange

題意：
假設有A，B兩種貨幣，要將A換成B，須透過匯率Rab和手續費Cab，因此實際得到B貨幣=(A-Cab)*Rab元。
第一行輸入N, M, S, V，N表示共有N種貨幣(1<=N<=100)，M表示底下有M行，每一行有六個數字A,B,Rab,Cab,Rba,Cab，Rab表示A換成B的匯率，Cab表示A換成B需要扣除的手續費，Rba和Cba同理。現在Nick有第S種貨幣V元，題目問Nick透過不斷交換貨幣，然後最後換回第S種貨幣的時候能否大於V元?

想法：
用SPFA演算法，初始除了Dis[S]=V以外Dis[i]都是0，然後不斷更新Dis的值使其盡可能大，最後判斷Dis[S]是否大於V。

POJ 1125 Stockbroker Grapevine

題意：
N表示共N個點，然後底下N行，第i行第一個數字t表示後面有t個pair，每個pair兩個數字分別代表x, w，i點到x點距離w，注意這是單向道路。題目求從哪個點當作起點可以使得該點走到距離該點最遠的距離為最短。假設i點作起點，走到距離i點最遠的那個點距離為Di，求所有Di中最小的那個值，輸出i及Di。另外題目要求這個i點需要能夠到達所有其他的點。
想法：
先做Floyd演算法，再去找每個點i的Di，在從Di中選出最小的那個去輸出i及Di即可，注意要判斷這個i是否能到達所有除了i以外的點。

2014年4月5日星期六

POJ 1724 ROADS

題目：
總共N個點，給定R條道路，每條共有S,D,L,T代表S點到D點這條路長度L且須花費T元，題目求從1為起點，N為終點，在花費<=K元的情況下走到終點的最短距離。
注意同一個S到D可能有多條道路。
想法：
用Dis[i][j]表示"從起點1走到i點花費j元的最短距離"，所以做SPFA的時候，每次就去更新Dis[i][0~K]的值，使其值盡可能的小，最後再去檢查Dis[N][0~K]的最小值是多少。
因為S到D可能有多條道路，所以用vector來存較為簡單。

UVa 10986 Sending email

這題就是簡單的Shortest path問題，用SPFA即可解決。

2014年4月3日星期四

UVa 10801 Lift Hopping

題意：
有n個電梯(1<=n<=5)，每個電梯移動一層樓的時間不一樣，第i個電梯每層樓的移動時間以T[i]表示，而每個電梯能到達的樓層也不一樣，如果兩個電梯都能到達x樓，則能在x樓換另一台電梯搭乘，但轉換的時間為60秒。今天起點在第0樓，給定第k樓為要前往的樓層，問最短的時間?
想法：
先以Weight[i][j]表示在'不轉換'電梯的情況下，i樓到j樓所需的最短時間，這個部份可以在輸入測資的過程中一起完成。然後再考慮轉換電梯的情況，以Dis[i]表示到達i樓的時間，用SPFA演算法，每次queue的時候就判斷 if (Dis[now] + Weight[now][nxt] + 60 < Dis[nxt]) 來不斷更新Dis[nxt]的值。

UVa 10557 XYZZY

題意：
總共有N個節點(1~N)，一開始起點在1且有100的能量，踏到每個節點都會有不同的能量變化(-100~+100)，目標是要走到終點N且過程中能量不能歸0。
想法：
用SPFA演算法，不過要注意過程中可能會碰到正環或是負環，且有正環也不一定能走到終點，因為題目給的是單向的所以有可能走到正環的路走不到終點。因此可以假設如果走了100萬次(數字不一定)還是走不到終點就判定為無法到達。

UVa 10278 Fire Station

題意：
有F個消防站分布在I個路口，假設每個路口i到離該路口最近的消防站距離為di，而D為這些di的最大值。今天要再增加'一個'消防站在某個路口，求要設在哪個路口使得D為最小。
想法：

先用Floyd演算法求出All pair shortest path
然後求各個路口i到離該路口最近的消防站的距離，用shortest_lenght[i]來存，並找出D值。
從1開始枚舉到I，找出能使得D值最小的路口的編號。

2014年3月29日星期六

UVa 10048 Audiophobia

題意：
點與點之間的weight代表聲音的分貝大小，要找一條路徑所遇到的分貝最小，假設a到d某條路徑所遇到的最大分貝為100，另一條路徑所遇到的最大分貝為80，則後者那條路徑較佳。

想法：
用Floyd演算法找All Pair Shortest Path。

UVa 10000 Longest Paths

這題是找最長的路徑，我們可以用BellmanFord演算法，與找最短路徑相同的寫法，差別在於我們可以把點到點之間的路徑長變"負"的，最後找負最多的那個點就是最遠的點。

UVa 341 Non-Stop Travel

題意：
Ruby兔中文翻譯
想法：
用BellmanFord演算法找出最短路徑，並在找的過程中用Pre[i]紀錄什麼點走到i，最後在從終點利用Pre走回起點，並依題目輸出答案。

POJ 3259 Wormholes

題意：
FJ要找出是否能從某個起點出發，然後回到該起點但可以遇見出發時的自己，也就是時間和要<0。

題目N表示有幾個點
M表示有M行，每行S,E,T三個數字表示S點到E點或E點到S點所需要的時間是T
W表示有W行，每行S,E,T三個數字表示S點到E點所減少的時間T，也就是S到E你的時間總和會-T，注意這個是單向的，只有S點到E點

想法：

本題換句話說就是找出是否有負環(negative cycle)，確認在所有路徑中是否存在一個cycle，使得一直走那個cycle時間總合會越來越小。

POJ 2387 Til the Cows Come Home

這題其實就是要求終點走到起點的最短路徑，因此用個簡單的BellmanFord演算法即可解決這題。

2014年3月21日星期五

UVa 10534 Wavio Sequence

Longest Increased/Decreased Subsequence
想法：
替數列建LIS和LDS表，然後在從表中找出共同最大的數字。例如：
數列： 1 2 3 4 5 3 2
LIS： 0 1 2 3 4 0 0
LDS： 0 0 0 0 2 1 0
因此數字'5'的LIS為4,LDS為2，所以'5'為中心組成Wavio Sequence的長度就是min(4,2)*2+1=5。因此本題就從LIS和LDS表中找出最長的Wavio Seq長度。
至於求LDS我是由後面往前作LIS，因此這題就是做兩次LIS，另外要注意如果用O(n^2)演算法可能會TLE。

2014年3月20日星期四

UVa 437 The Tower of Babylon

題目：
LuckyCat中文翻譯
想法：
Longest Increased Subsequence題型，每種Block都有6種組合，所以每次讀入一組L,W,H，就存6種組合，等到全部讀完，就將全部的組合進行排序。因為我是打算將Block由小疊到大(做LIS，與題目相反)，所以排序方式就依L由小到大排，如果L一樣在依W排，然後就做LIS演算法。

UVa 836 Largest Submatrix

想法：
這題是2維MSS(minimum subarray sum)，基本上第一個for loop先選出submatrix的垂直邊長，第二個for loop選定這條邊起始位置，然後向右做MMS。

UVa 507 Jill Rides Again

Minimum Subarray Sum
想法：
這題求最大MSS值的區間，注意output說明，如果MSS一樣的話，要選擇最大的區間長度(j-i盡可能大)，如果區間長度又一樣長的話，那麼要選擇先出現的那個。

區間長度盡可能大：第18行要用">="
選擇最大區間長度：第24行的判斷式

UVa 231 Testing the CATCHER

Longest Decreased Subsequence
題意：
Ruby兔中文翻譯
想法：
由後往前用LIS。

UVa 111 History Sorting

題意：
Luckycat中文翻譯。
想法：
這題有個陷阱，以Sample input舉例：
10
3 1 2 4 9 5 10 6 8 7
4 7 2 3 10 6 9 1 5 8

由這行來看：3 1 2 4 9 5 10 6 8 7
"事件1在位置3"，"事件2在位置1"，"事件3在位置2"......"事件10在位置7"。

因此事件真正的排序是
10
2 3 1 4 6 8 10 9 5 7
8 3 4 1 9 6 2 10 7 5
然後再用LCS找出最大的長度。

2014年3月19日星期三

UVa 10684 The jackpot

Maximum Sub-array Sum
想法：
用DP做，設MSS為累加到目前的値，如果MSS是負的，那麼MSS=num，否則MSS+=num。

UVa 531 Compromise

Longest Common Subsequence題型
想法：
用pre[i][j]來記錄LCS[i][j]是從哪個方向來的，再從pre[N-1][M-1]開始逆向走回並保存答案。

POJ 2421 Constructing Roads

想法：
與POJ 1751是一樣的，先依題目將已連結的點連起來，剩下的再用Kruskal做最小生成樹，並累積最小生成樹的邊長和。

POJ 2395 Out of Way

想法：
這題與POJ 1861一模一樣，求最小生成樹的最大邊長而已。

POJ 1861 Network

題意&想法：
要找出最小生成樹MST，先輸出MST最長的邊長，再輸出MST有幾條邊(就是N-1)，然後在一一輸出這些邊的點。用Kruskal演算法找出MST，並依題輸出答案。
ps.這題Sample Output有誤，4個點只需要3條邊就可以產生MST。

POJ 2533 Longest Orderded Subsequence

Longest Increasing Sub-sequence(LIS)題目
想法：
這裡提供兩種方法：

把已經讀入的數字存起來，每次讀一個新的數字i的時候，就把LIS[i]設成1，然後把現在這個新數字i與以前已經讀入的數字j做比較，如果i比j大且LIS[i]<LIS[j]+1，就把LIS[i]=LIS[j]+1。最後輸出最大的LIS值即可。
與上面不同，LIS[]是存讀入的數字，一開始LIS[]是空的，慢慢放數字，每次讀入一個新的數字，從i=0，如果該數字>LIS[i]，就讓i++，直到在LIS表裡上不去為止，然後看該數字是否比LIS[i]小，如果是則更新LIS[i]的値。

POJ 1751 Highways

題意：
依序給你N個城市的座標，然後接下M行說明哪些城市已經相連，題目要求盡可能用最短的距離把所有的城市連起來。
想法：
先把兩兩城市的距離算出來，共有C(N,2)條邊長，將這些邊由小大到排序，然後做Kruskal演算法，將所有城市連起來。
原本49~53行原本我是打算如果總共已經做了(N-1)條邊就跳出for loop，但是WA，後來想想應該是測資給的已經存在的邊會形成一個環(cycle)，所以就不可能為最小生成樹，邊長總數會大於(N-1)條。

2014年3月17日星期一

POJ 1703 Find them, Catch them

想法：
Disjoint Set題目，開兩倍陣列Set[2*N]，然後Set[i]表示與i是同Set，Set[i+N]表示與i為敵人，初始化先將Set[i]=i, Set[i+N]=0，其他詳細看底下Code。

2014年3月16日星期日

UVa 11747 Heavy Cycle Edges

題意&想法：
本題就是要把多餘的邊去除掉使得該graph變成最小生成樹，因此我們可以用Kruskal直接做出最小生成樹，然後把沒有用到的邊由小到大輸出即可。

UVa 10369 Arctic Network

題意：
有S個衛星，以及P個城市，如果兩個城市都有衛星的話，那麼不管距離多遠都能通訊，否則就只能靠radio通訊，而靠radio通訊的最遠的兩個城市距離為D，現在求如果每個城市都要通訊的話，那麼D最小為多少?
以Sample Input舉例：
(0,300)~(0,600)=300之間，各使用一個satellite，透過satellite來溝通，(0,100)~(0,300)=200和(0,600)~(150,750)=212.13則使用radio，因此D至少要212.13

想法：
P個城市代表有(P-1)條邊，而用Kruskal演算法做出最小生成樹，做Kruskal的過程中將邊長記錄下來，共有(P-1)條，然後把其中最長的(S-1)條邊分配給衛星，剩下的邊的最大値就是D。

UVa 10034 Freckles

題意：
給你N個二維點座標，要找出把這N個點連在一起成一個Set的最短路徑
想法：
先將點與點兩兩之間的邊長先算出來並排序，然後用Kruskal演算法，找出最小生成樹，並在找的時候同時將邊長累加起來最後即是答案。

2014年3月11日星期二

淺談Backtracking演算法與其應用

一般遞迴是把所有可能的路徑走過，也就是一一把答案枚舉(列舉)出來，然後再檢查答案的是否正確，但一一枚舉會非常耗時，而且常常枚舉出來的數量遠多於所需要的答案，原因在於在遞迴進行到一半的時候，如果該路徑是錯的，還是會不斷往下繼續遞迴，但其實我們可以在發現這條路徑不可能為答案的時候，就不要再往下遞迴下去，這就是Backtracking演算法。

2014年3月10日星期一

POJ 1094 Sorting It All Out

題意：
給定N表示有N個點，M表示底下有M行關係式，然後一行一行讀取關係式：

如果在第i行發現已經能明確將所有點排出順序(也就是只有一種答案)，輸出Sorted sequence determined after i relations: ...(順序)
如果在第i行發現和之前的關係式有衝突(形成一個環，例如A>B>C>A)，則輸出Inconsistency found after i relations.
如果讀取到最後關係都沒有衝突但也找不到唯一答案，則輸出Sorted sequence cannot be determined.

想法：

每次讀取關係式的時候就檢查是否有衝突(形成一個環)，如果沒有再去找topological sort，topological sort這function裡面要判斷是否為唯一解，因此只能選一條路徑往下遞迴，最後判斷答案優先順序為1.先看有沒有衝突2.看有沒有解，再依題目敘述輸出即可，詳細看底下code。

POJ 2367 Genealogical tree

題意：
第一行N表示有N個數(編號1~N)，接下來N行每行有幾個數字，第i行表示數字i需要在第i行那些數前面，例如Sample Input的4 5 1 0表示數字2需要在4,5,1的前面，以數字0代表該行的終止。

想法：
建立graph，從起點(沒有其他點連入)開始用DFS走遍整個graph，並記下走過的順序，最後再逆向輸出就是一個topological sort。

UVa 872 Ordering

想法：
這題是backtracking內融合了topological sort，基本上就是第一格, 第二格, ....依序填入，每次填的時後判斷哪些node可以填(表示需要在該node前出現的node已經出現過了)，詳細見底下code。

2014年3月9日星期日

UVa 604 The Boggle Game

題意：
在一個4x4 board裡找出所有符合的4個字元的單字，該單字須符合剛好只有2個母音('Y'也算母音)，每次Case有兩個board，找出這兩個board交集的所有單字。

想法：
用DFS+backtracking先分別找出一個board的所有符合的單字，然後再將兩個board找出來的單字作交集：

UVa 193 Graph Coloring

題意：
黑色不能相鄰，白色則不限制，如果編號最大的點是黑色的，則稱這個填入方法為optimal。題目給定一個graph，求填入最多黑色的方法，如果有多個答案，則盡可能選擇optimal的那種。

想法：
MaxNum為填入最多黑色的點的數量，透過backtracking找出多種填入的方式，並不斷刷新MaxNum，並將該填法記錄下來，最後輸出最大MaxNum的填入方式，詳細見底下code。

UVa 10503 The dominoes solotarie

題意：

給定N表示起點和終點之間要填入N個骨牌，給定M表示除了起點和終點外還有M個骨牌，每個骨牌兩端高度不一樣，因此一個骨牌用(p,q)來表示其兩端的高度。在放骨牌的時候，其相鄰的骨牌連接的那端高度需一致(例如一段骨牌放置如(a,b),(b,c),(c,d),(d,e))。起點(i1,i2)和終點(d1,d2)這兩個骨牌的兩端是不能交換的(不能變成(i2,i1))，而其它M個骨牌在放入的時候兩端是能交換的，因此這題要確認是否能在(i1,i2)和(d1,d2)之間放入N個骨牌。

想法：

用backtracking確認是否能在起點和終點間放入N個骨牌。

	#include <cstdio>
	using namespace std;

	int N, M;
	int i1, i2, d1, d2, p[20], q[20];
	int choosed[20];

	bool backtracking(int Len, int num)
	{
	if (Len == N) {
	if (num == d1) return true;
	return false;
	}
	for (int i = 0; i < M; ++i) {
	if (choosed[i]) continue;
	if (p[i] == num \|\| q[i] == num) {
	choosed[i] = 1;

	bool ok;
	if (p[i] == num) ok = backtracking(Len + 1, q[i]);
	else ok = backtracking(Len + 1, p[i]);
	if (ok) return true;

	choosed[i] = 0;
	}
	}
	return false;
	}
	int main()
	{
	while (scanf("%d %d", &N, &M) && N) {
	scanf("%d %d %d %d", &i1, &i2, &d1, &d2);
	for (int i = 0; i < M; ++i) {
	scanf("%d %d", &p[i], &q[i]);
	choosed[i] = 0;
	}

	if (backtracking(0, i2)) puts("YES");
	else puts("NO");
	}
	return 0;
	}

view raw [UVa] 10503 The dominoes solitaire.cpp hosted with ❤ by GitHub

UVa 291 The House Of Santa Claus

想法：
這題的答案只從'1'當做起點，並將答案做遞增排序，用backtracking依序將答案找出。

	#include <cstdio>
	#include <vector>
	using namespace std;

	vector<int> toNxt[6] = {{}, {2,3,5}, {1,3,5}, {1,2,4,5}, {3,5}, {1,2,3,4}};
	bool choosed[6][6] = {0};
	int ans[9];

	void func(int n, int Len)
	{
	if (Len == 9) {
	for (int &a : ans)
	printf("%d", a);
	putchar('\n');
	}
	for (int nxt : toNxt[n]) {
	if (choosed[n][nxt] == 0 && choosed[nxt][n] == 0) {
	choosed[n][nxt] = 1, choosed[nxt][n] = 1;
	ans[Len] = nxt;

	func(nxt, Len + 1);

	choosed[n][nxt] = 0, choosed[nxt][n] = 0;
	}
	}
	}
	int main()
	{
	ans[0] = 1;
	func(1,1);
	}

	// Ans
	/*
	123153452
	123154352
	123451352
	123453152
	123513452
	123543152
	125134532
	125135432
	125315432
	125345132
	125431532
	125435132
	132153452
	132154352
	132534512
	132543512
	134512352
	134512532
	134521532
	134523512
	134532152
	134532512
	135123452
	135125432
	135215432
	135234512
	135432152
	135432512
	152134532
	152135432
	152345312
	152354312
	153123452
	153125432
	153213452
	153254312
	153452132
	153452312
	154312352
	154312532
	154321352
	154325312
	154352132
	154352312
	*/

view raw [UVa] 291 The House of Santa Claus.cpp hosted with ❤ by GitHub

UVa 598 Bundling Newspapers

題意：
參考Lucky Cat。
想法：
這題比較麻煩的部分在於輸入，輸入完成後就用backtracking把每個Size的答案找出來，詳細看底下code。

	#include <cstdio>
	#include <string>
	#include <map>
	#include <vector>
	using namespace std;

	int N;
	char News[15][40];
	int ans[20];
	bool choosed[20] = {0};

	int Input1(int &, int &);
	int Input2();
	void Combination(int &Size, int Len, int pos);

	int main()
	{
	int Case;
	scanf("%d ", &Case);

	while (Case--) {
	int a = 0, b = 0;
	int Mode = Input1(a, b);
	N = Input2();

	if (Mode == 1) b = a;
	else if (Mode == 3) a = 1, b = N;

	for (int i = a; i <= b; ++i) {
	printf("Size %d\n", i);
	Combination(i, 0, 0);
	putchar('\n');
	}
	if (Case) putchar('\n');
	}
	}
	int Input1(int &a, int &b)
	{
	char line[20];
	int Mode = 1;

	gets(line);

	if (line[0] == '*') Mode = 3;
	else {
	int i = 0;
	while (line[i] != '\0' && line[i] != ' ')
	a = a * 10 + (line[i++] - '0');
	if (line[i] == ' ') {
	Mode = 2, ++i;
	while (line[i])
	b = b * 10 + (line[i++] - '0');
	}
	}
	return Mode;
	}
	int Input2()
	{
	int n = 0;
	while (gets(News[n]) && News[n][0] != '\0') ++n;
	return n;
	}
	void Combination(int &Size, int Len, int pos)
	{
	if (Len == Size) {
	printf("%s", News[ans[0]]);
	for (int i = 1; i < Size; ++i)
	printf(", %s", News[ans[i]]);
	putchar('\n');
	return;
	}
	for (int i = pos; i < N; ++i) {
	ans[Len] = i;
	Combination(Size, Len + 1, i + 1);
	}
	}

view raw [UVa] 598 Bumdling Newspapers.cpp hosted with ❤ by GitHub

UVa 574 Sum It Up

想法：
用Backtracking找出所有答案(包括這些答案可能重複)，之後在將這些答案依照遞減排序，再輸出，輸出時要確定這個答案之前是否已經存在了。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;

	int T, N, List[20];
	vector<int> ans[10000];
	int nOfans;

	void backtracking(int pos, int sum)
	{
	if (sum == T) {
	ans[nOfans+1] = ans[nOfans];
	++nOfans;
	return;
	}
	for (int i = pos; i < N; ++i) {
	if (sum + List[i] <= T) {
	sum += List[i];
	ans[nOfans].push_back(List[i]);

	backtracking(i + 1, sum);

	sum -= List[i];
	ans[nOfans].pop_back();
	}
	}
	}
	bool cmp(vector<int> a, vector<int> b)
	{
	for (int i = 0; i < a.size(); ++i) {
	if (a[i] == b[i]) continue;
	return a[i] > b[i];
	}
	return a.size() > b.size();
	}
	void PrintOut(vector<int> &V)
	{
	printf("%d", V[0]);
	for (int i = 1; i < V.size(); ++i)
	printf("+%d", V[i]);
	printf("\n");
	}
	int main()
	{
	while (scanf("%d %d", &T, &N) && N) {
	for (int i = 0; i < N; ++i) {
	scanf("%d", &List[i]);
	}
	for (auto &v : ans) v.clear();
	nOfans = 0;

	backtracking(0, 0);

	printf("Sums of %d:\n", T);
	if (nOfans == 0)
	puts("NONE");
	else {
	sort(ans, ans + nOfans, cmp);
	PrintOut(ans[0]);
	for (int i = 1;i < nOfans; ++i)
	if (ans[i] != ans[i-1]) // 確認答案是否已經存在
	PrintOut(ans[i]);
	}
	}
	}

view raw [UVa] 574 Sum It Up.cpp hosted with ❤ by GitHub

UVa 524 Prime Ring Problem

想法：
用backtracking找出各種可能的組合方式，詳細看底下code：

	#include <cstdio>
	using namespace std;
	int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41};
	int N, Case = 0, ans[20] = {1};
	bool isPrime(int a)
	{
	for (int n : prime)
	if (n == a) return true;
	return false;
	}
	void backtracking(int L, bool visit[])
	{
	if (L == N) {
	if (!isPrime(ans[N-1] + 1)) // 確認頭+尾是否為質數
	return;
	printf("1");
	for (int i = 1; i < N; ++i)
	printf(" %d", ans[i]);
	printf("\n");
	return;
	}
	for (int i = 2; i <= N; ++i) {
	if (visit[i]) continue;
	if (isPrime(i + ans[L - 1])) {
	visit[i] = 1;
	ans[L] = i;

	backtracking(L + 1, visit);

	visit[i] = 0;
	}
	}
	}
	int main()
	{
	while (scanf("%d", &N) != EOF) {
	if (Case++) putchar('\n');
	printf("Case %d:\n", Case);
	bool visit[20] = {0};
	backtracking(1, visit);
	}
	}

view raw [UVa] 524 Prime Ring Problem.cpp hosted with ❤ by GitHub

UVa 11085 Back to the 8-Queens

想法：
先建表，把可能的位置存下來(共92種)，然後再看哪種位置所需要的Move數量最低。話說原本不知道Queen原來像象棋的車，移動一步可以任意距離，害我吃了WA@_@

	#include <cstdio>
	#include <vector>
	using namespace std;

	int Container[8];
	int Queens_row[100][8];
	int nOfQueens = 0;
	// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
	bool row[8] = {0}, left[15] = {0}, right[15] = {0};
	// 底下 r表示row c表示colum
	void Eight_Queens(int c)
	{
	if (c == 8) {
	for (int i = 0; i < 8; ++i)
	Queens_row[nOfQueens][i] = Container[i] + 1; //+1是因為題目的row是從1開始
	++nOfQueens;
	return;
	}
	for (int r = 0; r < 8; ++r) {
	int ld = c - r + 7;
	int rd = c + r;
	if (!row[r] && !left[ld] && !right[rd]) {
	row[r] = 1, left[ld] = 1, right[rd] = 1;
	Container[c] = r;

	Eight_Queens(c + 1);

	row[r] = 0, left[ld] = 0, right[rd] = 0;
	}
	}
	}
	int main()
	{
	Eight_Queens(0);

	int row_position[8], Case = 1;

	while (scanf("%d", &row_position[0]) != EOF) {
	for (int i = 1; i < 8; ++i)
	scanf("%d", &row_position[i]);

	int Min = 99999;

	for (int i = 0; i < nOfQueens; ++i) {
	int Move = 0;
	for (int c = 0; c < 8; ++c)
	if (Queens_row[i][c] != row_position[c])
	++Move;
	if (Move < Min) Min = Move;
	}
	printf("Case %d: %d\n", Case++, Min);
	}
	}

view raw [UVa] 11085 Back to the 8-Queens.cpp hosted with ❤ by GitHub

UVa 624 CD

想法：
在小於等於限制的情況下一直遞迴找能放入的數字，並不斷刷新Maxsum(最接近限制的和)，詳細看底下。

	#include <cstdio>
	#include <vector>
	using namespace std;

	int track[21];
	int N, T; // T is number of tracks
	vector<int> Container; // 遞迴時暫存track
	vector<int> Ans;
	int Maxsum;
	void combination(int pos, int sum);

	int main()
	{
	while (scanf("%d %d", &N, &T) != EOF) {
	for (int i = 0; i < T; ++i)
	scanf("%d", &track[i]);
	Container.clear();

	Maxsum = 0;
	combination(0, 0);

	int sum = 0;
	for (int n : Ans) {
	printf("%d ", n);
	sum += n;
	}
	printf("sum:%d\n", sum);
	}
	}
	void combination(int pos, int sum)
	{
	if (sum > Maxsum) { // 不斷刷新Maxsum,使得Maxsum更接近N
	Ans = Container;
	Maxsum = sum;
	}

	for (int i = pos; i < T; ++i) {
	if (track[i] + sum <= N) {
	sum += track[i];
	Container.push_back(track[i]);

	combination(i + 1, sum);

	sum -= track[i];
	Container.pop_back();
	}
	}
	}

view raw [UVa] 624 CD.cpp hosted with ❤ by GitHub

UVa 989 Su Doku

想法：

每次要填入一個數字時，確認該行與該列和該九宮格(box)裡面是否已經有這個數字，如果能填入，則繼續遞迴下去填下一格。

	#include <cstdio>
	using namespace std;

	int board[9][9];
	int n, N; // n是較小的邊長, N = n * n
	bool backtracking(int r, int c);

	int main()
	{
	int Case = 0;
	while (scanf("%d", &n) != EOF) {
	if (Case++) putchar('\n');
	N = n * n;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	scanf("%d", &board[i][j]);
	if (backtracking(0, 0)) {
	for (int i = 0; i < N; ++i) {
	for (int j = 0; j < N - 1; ++j)
	printf("%d ", board[i][j]);
	printf("%d\n", board[i][N-1]);
	}
	}
	else puts("NO SOLUTION");
	}
	}
	bool backtracking(int r, int c)
	{
	if (r >= N)
	return true;

	if (board[r][c] == 0) {
	bool col[10] = {0};
	bool row[10] = {0};
	bool box[10] = {0};
	//找出該欄與該列已經填過哪些數字
	for (int i = 0; i < N; ++i) {
	if (board[r][i]) row[board[r][i]] = 1;
	if (board[i][c]) col[board[i][c]] = 1;
	}
	//找出所在位置的九宮格裡已經填過哪些數字
	int rr = r - (r % n);
	int cc = c - (c % n);
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (board[rr+i][cc+j]) box[board[rr+i][cc+j]] = 1;
	//確認1~9哪些數字能填在這格,如果能填則繼續遞迴
	for (int num = 1; num <= 9; ++num) {
	if (!col[num] && !row[num] && !box[num]) {
	board[r][c] = num;

	int nxt_r = r, nxt_c = c + 1;
	if (nxt_c == N) ++nxt_r, nxt_c = 0; //換行
	bool hasAns = backtracking(nxt_r, nxt_c);
	if (hasAns) return true;

	board[r][c] = 0;
	}
	}
	}
	else { // board[r][c] != 0
	int nxt_r = r, nxt_c = c + 1;
	if (nxt_c == N) ++nxt_r, nxt_c = 0;
	bool hasAns = backtracking(nxt_r, nxt_c);
	if (hasAns) return true;
	}
	return false;
	}

view raw [UVa] 989 Su Doku.cpp hosted with ❤ by GitHub

2014年3月7日星期五

UVa 441 Lotto

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N, S[100], choosed[100], ans[100];
	void func(int len, int pos)
	{
	if (len == 6){
	for (int i = 0; i < 5; ++i)
	printf("%d ", ans[i]);
	printf("%d\n", ans[5]);
	return;
	}
	for (int i = pos; i < N; ++i) {
	if (!choosed[i]) {
	choosed[i] = 1;
	ans[len] = S[i];
	func(len+1, i + 1);
	choosed[i] = 0;
	}
	}
	}
	int main()
	{
	int Case = 0;
	while (scanf("%d", &N) && N) {
	if (Case++) printf("\n");
	for (int i = 0; i < N; ++i){
	scanf("%d", &S[i]);
	choosed[i] = 0;
	}
	func(0,0);
	}
	}

view raw [UVa] 441 Lotto.cpp hosted with ❤ by GitHub

UVa 167 The Sultan's Successors

想法：
這是一個八皇后問題，可以先將所有可能方式先記下來(共92種)，之後再輸入測資檢查這92種哪一種最大即可，如果還想更快的話，直接把這92種先輸出，然後直接寫在code裡XD。

	#include <cstdio>
	#include <vector>
	using namespace std;

	int P[1000][9];
	int tmp[8];
	int n = 0;
	// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
	bool col[8] = {0}, left[15] = {0}, right[15] = {0};
	// 底下 r表示row c表示colum
	void func(int r)
	{
	if (r == 8) {
	for (int i = 0; i < 8; ++i)
	P[n][i] = tmp[i];
	++n;
	return;
	}
	for (int c = 0; c < 8; ++c) {
	int ld = (c - r) + 7;
	int rd = c + r;
	if (!col[c] && !left[ld] && !right[rd]) {
	col[c] = 1, left[ld] = 1, right[rd] = 1;
	tmp[r] = c;

	func(r + 1);

	col[c] = 0, left[ld] = 0, right[rd] = 0;
	}
	}
	}
	int main()
	{
	func(0);

	int Case;
	int board[8][8];
	scanf("%d", &Case);
	while (Case--) {
	for (int i = 0; i < 8; ++i)
	for (int j = 0; j < 8; ++j)
	scanf("%d", &board[i][j]);

	int ans = 0;

	for (int i = 0; i < n; ++i) {
	int sum = 0;
	for (int j = 0; j < 8; ++j)
	sum += board[j][P[i][j]];
	if (sum > ans) ans = sum;
	}
	printf("%5d\n", ans);
	}
	}

view raw UVa 167 The Sultan's Successors.cpp hosted with ❤ by GitHub

UVa 10305 Ordering Tasks

想法：
輸出只要符合是一個topological sort即可，因此可以從起點(沒有被任何點連入的點)用DFS走遍，並同時記錄走遍的點，最後再逆向輸出這些點就是一個topological sort。

	#include <cstdio>
	#include <vector>
	using namespace std;
	void DFS(int n, int visit[], vector<int> toNode[], vector<int> &ans);
	int main()
	{
	int N, M, a, b;
	while (scanf("%d %d", &N, &M) && (N \|\| M)) {
	vector<int> toNode[101];
	vector<int> ans;
	bool connect[101] = {0};
	int visit[101] = {0};
	while (M--) {
	scanf("%d %d", &a, &b);
	toNode[a].push_back(b);
	connect[b] = 1;
	}
	for (int i = 1; i <= N; ++i) {
	if (!connect[i])
	DFS(i ,visit, toNode, ans);
	}
	for (auto iter = ans.end() - 1; iter != ans.begin(); --iter)
	printf("%d ", *iter);
	printf("%d\n", *ans.begin());
	}
	}
	void DFS(int n, int visit[],vector<int> toNode[], vector<int> &ans)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (int nxt : toNode[n]) {
	if (visit[nxt] != 2)
	DFS(nxt, visit, toNode, ans);
	}
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 10305 Ordering Tasks.cpp hosted with ❤ by GitHub

UVa 11606 Pick up sticks

想法：

把放在最上面(也就是這個點沒有其他點連入)的stick當做起點，用DFS走遍，並將走遍的經過的點記錄下來，最後逆向輸出這些記錄的點就是一個topological sort。

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;

	vector<char> ans;
	vector<char> toPoint[100];
	int visit[100] = {0};
	int deg[100] = {0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入
	void DFS(char n);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	string a, b;
	cin >> a;
	while (cin >> b && b != "#") {
	int L = (a.size() > b.size()) ? b.size() : a.size();
	for (int i = 0; i < L; ++i) {
	if (deg[a[i]] == 0) deg[a[i]] = 1;
	if (deg[b[i]] == 0) deg[b[i]] = 1;
	if (b[i] != a[i]) {
	toPoint[a[i]].push_back(b[i]);
	deg[b[i]] = 2;
	break;
	}
	}
	a = b;
	}
	for (char i = 'A'; i <= 'Z'; ++i)
	if (deg[i] == 1)
	DFS(i);

	for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
	cout << *iter;
	cout << endl;
	}
	void DFS(char n)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (char nxt : toPoint[n])
	if (visit[nxt] != 2)
	DFS(nxt);
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 200 Rare Order.cpp hosted with ❤ by GitHub

UVa 200 Rare Order

題意：
　　Input給的那些字串是每個index的名稱，而這些Index是照"某個字典序"由小到大排好的(就像一般的目錄是從A~Z排好)，我們要從Input裡面判斷這些字的字典序。例如Sample Input：
XWY
ZX
ZXY
ZXW
YWWX
我們可以從XWY和ZX判斷X<Z，ZXY和ZXW判斷Y<W，ZXW和YWWX判斷Z<Y，所以可以得到X<Z<Y<W。

**本題測資只有一個**

想法：
　　一次兩行判斷，找出誰<誰，記錄完之後，從沒有被連入的點當做起點，使用DFS走遍並記下走遍的點，將記下的點逆向輸出就是一個topological sort。

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;

	vector<char> ans;
	vector<char> toPoint[100];
	int visit[100] = {0};
	int deg[100] = {0}; // deg[i]=1:沒有被其他點連入 deg[i]=2:被其他點連入
	void DFS(char n);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	string a, b;
	cin >> a;
	while (cin >> b && b != "#") {
	int L = (a.size() > b.size()) ? b.size() : a.size();
	for (int i = 0; i < L; ++i) {
	if (deg[a[i]] == 0) deg[a[i]] = 1;
	if (deg[b[i]] == 0) deg[b[i]] = 1;
	if (b[i] != a[i]) {
	toPoint[a[i]].push_back(b[i]);
	deg[b[i]] = 2;
	break;
	}
	}
	a = b;
	}
	for (char i = 'A'; i <= 'Z'; ++i)
	if (deg[i] == 1)
	DFS(i);

	for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter)
	cout << *iter;
	cout << endl;
	}
	void DFS(char n)
	{
	if (visit[n] == 1) return;
	visit[n] = 1;

	for (char nxt : toPoint[n])
	if (visit[nxt] != 2)
	DFS(nxt);
	visit[n] = 2;
	ans.push_back(n);
	}

view raw [UVa] 200 Rare Order.cpp hosted with ❤ by GitHub

UVa 11060 Becerages

想法：
　　記錄每個點被其他點連入的數量(Ex: A->B, C->B，則beConnected[B]=2)，和記錄各個點連到哪些點。

每次從頭找beConnected[i]==0(表示沒有點連到i)的Node
將這個Node輸出
同時將beConnected[i]改成-1表示這Node已經輸出過了
然後其他每個被Node i連入的Node j，把beConnected[j]--
執行1~4 N次，把每個Node都輸出過

	#include <iostream>
	#include <string>
	#include <map>
	#include <vector>
	using namespace std;

	map<string, int> Map;
	string Name[105];
	vector<int> toNxt[105];
	int beConnected[105]; //該node被其他點連入的數量

	void Initial(int N)
	{
	Map.clear();
	for (int i = 0; i < N; ++i) {
	toNxt[i].clear();
	beConnected[i] = 0;
	}
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, M, Case = 1;
	string s1, s2;
	while (cin >> N) {
	Initial(N);
	for (int i = 0; i < N; ++i)
	cin >> s1, Map[s1] = i, Name[i] = s1;

	cin >> M;
	for (int i = 0; i < M; ++i) {
	cin >> s1 >> s2;
	toNxt[Map[s1]].push_back(Map[s2]);
	++beConnected[Map[s2]];
	}
	cout << "Case #" << Case++ << ": Dilbert should drink beverages in this order:";
	for (int i = 0; i < N; ++i) {
	int pos = 0;
	while (beConnected[pos] != 0) ++pos;

	beConnected[pos] = -1;
	cout << ' ' << Name[pos];

	for (int nxt : toNxt[pos])
	--beConnected[nxt];
	}
	cout << '.' << endl << endl;
	}
	}

view raw [UVa] 11060 Beverages.cpp hosted with ❤ by GitHub

POJ 2442 Sequence

想法：
　　這題與UVa 11997一樣，差別只在於UVa那題是K行K個數字，這題是M行N個數字，詳細過程我寫在UVa 11997 K Smallest Sums。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct custom_type {
	int val;
	int pos;

	bool operator < (const custom_type &B) const {
	return val > B.val; // min heap
	}
	};
	int main()
	{
	int T ,M, N, L1[2001], L2[2001];
	scanf("%d", &T);
	while (T--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; ++i) scanf("%d", &L1[i]);
	sort(L1, L1 + N);

	for (int k = 1; k < M; ++k) {
	for (int i = 0; i < N; ++i) scanf("%d", &L2[i]);
	sort(L2, L2 + N);

	priority_queue<custom_type> PQ;
	for (int i = 0; i < N; ++i)
	PQ.push({L1[i] + L2[0], 0});

	for (int i = 0; i < N; ++i) {
	custom_type tmp = PQ.top();
	PQ.pop();
	L1[i] = tmp.val;
	if (tmp.pos+1 < N)
	PQ.push({tmp.val - L2[tmp.pos] + L2[tmp.pos+1], tmp.pos + 1});
	}
	}
	for (int i = 0; i < N - 1; ++i)
	printf("%d ", L1[i]);
	printf("%d\n", L1[N-1]);
	}
	}

view raw [POJ] 2442 Sequence.cpp hosted with ❤ by GitHub

UVa 11997 K Smallest Sums

題意：
有K行，每行有K個數字，從每行裡面各選出1個數字並加起來共有K^K種組合的和，輸出最小的K個和。

想法：
我們可以先將第一行和第二行求出前K小的和，因此兩行數字就變成了一行數字，這一行數字再和第三行求出前K小的和，兩行又合併成一行，一直重複將兩行合併成一行，最後就是答案。
因此現在關鍵是如何有效率求出兩行的數字前K個最小的和，如果暴力解的話為O(K^2)，很可能會TLE，用priority queue來解這題只要O(K)，過程如下：
*假設第一行數字陣列為L1，第二行數字陣列為L2，
*要丟進priority queue(底下簡稱PQ)裡的structure裡面含有兩個元素，第一個為val: 表示L1某個數+L2某個數的和，第二個為pos: 表示L2某個數在L2的位置(index)。

將L1遞增排序
將L2遞增排序。
然後把L1裡面每個數字和L2[0]加起來，val=L1[i]+L2[0]和pos=0放到PQ裡面。
L1的數字就不會用到了
之後每次從PQ裡面拿出第一個(最小的val)，將這個val放入L1(覆蓋以重複利用L1)，然後將這個val=(val-L2[pos]+L2[pos+1])和pos=pos+1丟回PQ裡
重複步驟5 K次，L1裡面就有K個數字，表示這兩行已經合併成功
讀入下一個L2，並重複步驟2~7，直到將K行合併成一行
輸出L1

用這方法將兩行合併成一行的時候，只要做K次即可，因為我們已經將L1都丟進PQ裡面，然後每次都選最小和出來，並同時把可能的答案丟入PQ。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct custom_type {
	int val;
	int pos;

	bool operator < (const custom_type &B) const {
	return val > B.val; // min heap
	}
	};
	int main()
	{
	int K, L1[800], L2[800];
	while (scanf("%d", &K) != EOF) {
	for (int i = 0; i < K; ++i) scanf("%d", &L1[i]);
	sort(L1, L1 + K);

	for (int k = 1; k < K; ++k) {
	for (int i = 0; i < K; ++i) scanf("%d", &L2[i]);
	sort(L2, L2 + K);

	priority_queue<custom_type> PQ;
	for (int i = 0; i < K; ++i)
	PQ.push({L1[i] + L2[0], 0});

	for (int i = 0; i < K; ++i) {
	custom_type tmp = PQ.top();
	PQ.pop();
	L1[i] = tmp.val;
	if (tmp.pos+1 < K)
	PQ.push({tmp.val - L2[tmp.pos] + L2[tmp.pos+1], tmp.pos + 1});
	}
	}
	for (int i = 0; i < K - 1; ++i)
	printf("%d ", L1[i]);
	printf("%d\n", L1[K-1]);
	}
	}

view raw [UVa] 11997 K Smallest Sums.cpp hosted with ❤ by GitHub

2014年3月5日星期三

POJ 2255 Tree Recovery

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

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

先遞迴左子樹
再遞迴右子樹
輸出Root

底下有附詳細註解的Code：

	#include <cstdio>
	#include <cstring>
	using namespace std;

	char Preorder[30], Inorder[30];

	void Postorder(int PL, int PR, int IL, int IR);
	int FindInorderRoot(char c, int L, int R);

	int main()
	{
	while (scanf("%s %s", Preorder, Inorder) == 2) {
	Postorder(0, strlen(Preorder)-1, 0, strlen(Inorder)-1);
	putchar('\n');
	}
	return 0;
	}
	void Postorder(int PL, int PR, int IL, int IR) // PL, PR: Preorder的左右界 IL, IR: Inorder的左右界
	{
	if (PL == PR) { // 左界等於右界,
	printf("%c", Preorder[PL]);
	return;
	}
	// P_root, I_root: 目前這個Tree的root的index
	int P_root = PL;
	int I_root = FindInorderRoot(Preorder[P_root], IL, IR);

	// 要分成左右子樹, P_Lsub_L, P_Lsub_R: 為左子樹在Preorder的左右界,反之另外兩個為右子樹左右界
	int P_Lsub_L, P_Lsub_R, P_Rsub_L, P_Rsub_R;

	// I_Lsub_L, I_Lsub_R: 為左子樹在Inorder的左右界,另外兩個為右子樹的左右界
	int I_Lsub_L, I_Lsub_R, I_Rsub_L, I_Rsub_R;

	bool hasLsub = 1, hasRsub = 1; //確認左右子樹是否存在

	I_Lsub_L = IL;
	I_Lsub_R = I_root - 1;
	if (I_Lsub_L > I_Lsub_R) hasLsub = 0;

	I_Rsub_L = I_root + 1;
	I_Rsub_R = IR;
	if (I_Rsub_L > I_Rsub_R) hasRsub = 0;

	if (hasLsub) {
	P_Lsub_L = P_root + 1;
	P_Lsub_R = P_Lsub_L + (I_Lsub_R - I_Lsub_L);
	}
	if (hasRsub) {
	P_Rsub_L = (hasLsub) ? P_Lsub_R + 1 : P_root + 1;
	P_Rsub_R = PR;
	}

	//若左(右)子樹存在,則繼續遞迴分割,直到元素剩下一個
	//底下三行code的順序為Postorder(Left, Right, Root)
	if (hasLsub) Postorder(P_Lsub_L, P_Lsub_R, I_Lsub_L, I_Lsub_R);
	if (hasRsub) Postorder(P_Rsub_L, P_Rsub_R, I_Rsub_L, I_Rsub_R);
	printf("%c", Preorder[P_root]);
	}
	int FindInorderRoot(char c, int L, int R)
	{
	while (Inorder[L] != c && L <= R) L++;
	return L;
	}

view raw [POJ] 2255 Tree Recovery.cpp hosted with ❤ by GitHub

2014年3月4日星期二

UVa 11987 Almost Union-Find

想法：

int Root[] : 表示i這個點存放在哪個Set(也就是Set[Root[i]]裡面可以找到i這個數字)
vector<int> Set[] : 每個Set裡面可以存放很多數字

分成三個操作：

Union：如果x和y不在同個Set，那就把元素個數較少的那個Set裡面的每個元素移動到另一個Set，並同時將Root[]重新指向。例如Set[Root[y]]元素較少，就把Set[Root[y]]內的元素加入到Set[Root[x]]，並且把Set[Root[y]]的元素n，使得Root[n]=Root[x]。
Move：如果x和y不在同個Set，就把Set[Root[x]]這個Set內的元素x刪除，並在Set[Root[y]]加入x，記得將Root[x] = Root[y]。
Output：輸出Set[Root[x]].size()和該Set內每個元素的和。

	#include <cstdio>
	#include <vector>
	using namespace std;

	int Root[100010];
	vector<int> Set[100010];

	void Set_Initial(int N);
	void Union(int x, int y);

	int main()
	{
	int N, M, Command;
	int x , y;
	while (scanf("%d %d", &N, &M) != EOF) {
	Set_Initial(N);
	while (M--) {
	scanf("%d", &Command);
	if (Command == 1) {
	scanf("%d %d", &x, &y);
	Union(x, y);
	}
	else if (Command == 2) {
	scanf("%d %d", &x, &y);
	if (Root[x] == Root[y]) continue;

	auto iter = Set[Root[x]].begin();
	while (*iter != x) ++iter;
	Set[Root[x]].erase(iter);

	Set[Root[y]].push_back(x);
	Root[x] = Root[y];
	}
	else if (Command == 3) {
	scanf("%d", &x);
	int Sum = 0;
	for (int &n : Set[Root[x]])
	Sum += n;
	printf("%d %d\n", Set[Root[x]].size(), Sum);
	}
	}
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i) {
	Root[i] = i;
	Set[i].clear();
	Set[i].push_back(i);
	}
	}
	void Union(int x, int y)
	{
	x = Root[x];
	y = Root[y];
	if (x == y) return;

	if (Set[x].size() >= Set[y].size()) {
	for (int &n : Set[y]) {
	Set[x].push_back(n);
	Root[n] = x;
	}
	Set[y].clear();
	}
	else {
	for (int &n : Set[x]) {
	Set[y].push_back(n);
	Root[n] = y;
	}
	Set[x].clear();
	}
	}

view raw [UVa] 11987 Almost Union-Find.cpp hosted with ❤ by GitHub

UVa 11503 Virtual Friends

想法：
　　架構與UVa 10685 Nature一樣，差別在於這題每輸入一組測資就要把該組測資所在的Set的大小輸出。

	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;

	int Set[200010];
	int Num[200010];

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);

	int main()
	{
	ios::sync_with_stdio(false);
	int Case, F;
	cin >> Case;
	while (Case--) {
	cin >> F;
	map<string, int> Map;
	Set_Initial(2 * F);

	string A, B;
	for (int i = 0, j = 1; i < F; ++i) {
	cin >> A >> B;
	if (!Map[A]) Map[A] = j++;
	if (!Map[B]) Map[B] = j++;
	Union(Map[A], Map[B]);
	}
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 0; i <= N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	cout << Num[y] << endl;
	}

view raw [UVa] 11503 Virtual Friends.cpp hosted with ❤ by GitHub

UVa 10685 Nature

想法：

Set[i]表示i這個node的father node(上面一層node的編號)，Root這個node的father node還是自己。
Num[i]表示以i這個node為root的set，有幾個元素

這題與UVa 10608 Friends是一樣的，差別在於這題給的input為字串，因此我們先用map將它轉成數字編號。

	#include <iostream>
	#include <map>
	#include <string>
	using namespace std;

	map<string, int> Map;
	int Set[5010];
	int Num[5010];

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int FindLargest(int N);

	int main()
	{
	ios::sync_with_stdio(false);
	int C, R;
	while (cin >> C >> R) {
	if (!C && !R) break;

	Set_Initial(C);

	string A, B;
	for (int i = 0; i < C; ++i) {
	cin >> A;
	Map[A] = i;
	}
	while (R--) {
	cin >> A >> B;
	Union(Map[A], Map[B]);
	}
	cout << FindLargest(C) << endl;
	}
	}
	void Set_Initial(int N)
	{
	Map.clear();
	for (int i = 0; i < N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	}
	int FindLargest(int N)
	{
	int Max = 0;
	for (int i = 0; i < N; ++i)
	if (Num[i] > Max) Max = Num[i];
	return Max;
	}

view raw [UVa] 10685 Nature.cpp hosted with ❤ by GitHub

UVa 10608 Friends

想法：
　　做Disjoint Set，詳細看底下Code~。

	#include <cstdio>
	using namespace std;

	int Set[30010]; // Set[i]為i這node的father node,Set最上層的Set[root]=root
	int Num[30010]; // 以N[i]為root的Set有幾個element

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);
	int FindLargest(int N);

	int main()
	{
	int Case, N, M, A, B;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &N, &M);
	Set_Initial(N);
	while (M--) {
	scanf("%d %d", &A, &B);
	Union(A, B);
	}
	printf("%d\n", FindLargest(N));
	}
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i) {
	Set[i] = i;
	Num[i] = 1;
	}
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	Num[y] += Num[x];
	}
	}
	int FindLargest(int N)
	{
	int Max = 0;
	for (int i = 1; i <= N; ++i)
	if (Num[i] > Max)
	Max = Num[i];
	return Max;
	}

view raw [UVa] 10608 Friends.cpp hosted with ❤ by GitHub

UVa 10583 Ubiquitous Religions

做disjoint set，架構與UVa 793 Network Connections一樣。

	#include <cstdio>
	#include <set>
	using namespace std;

	int Set[50010];
	int nOfReligion;

	void Set_Initial(int N);
	int FindRoot(int x);
	void Union(int x, int y);

	int main()
	{
	int N, M, Case = 1;
	while (scanf("%d %d", &N, &M) && (N \|\| M)) {

	Set_Initial(N);
	int x, y;
	nOfReligion = N;

	while (M--) {
	scanf("%d%d", &x, &y);
	Union(x, y);
	}
	printf("Case %d: %d\n", Case++, nOfReligion);
	}
	return 0;
	}
	void Set_Initial(int N)
	{
	for (int i = 1; i <= N; ++i)
	Set[i] = i;
	}
	int FindRoot(int x)
	{
	if (x == Set[x])
	return x;
	return Set[x] = FindRoot(Set[x]);
	}
	void Union(int x, int y)
	{
	x = FindRoot(x);
	y = FindRoot(y);

	if (x != y) {
	Set[x] = y;
	--nOfReligion;
	}
	}

view raw [UVa] 10583 Ubiquitous Religions.cpp hosted with ❤ by GitHub

2014年3月3日星期一

UVa 879 Circuit Nets

想法：
　　與UVa 793 Network Connections一樣，依題意做disjoint set，排名拿到Rank 2，可能這題做的人少吧XD

	#include <cstdio>
	using namespace std;
	int Set[100001];
	int nOfNets;

	int getNum(char line[], int &i);
	void MakeSet(int n);
	int FindSetRoot(int x);
	void Union(int x, int y);

	int main()
	{
	int Case, N;
	char line[1000];
	scanf("%d", &Case);

	while (Case--) {
	scanf("%d ", &N);

	MakeSet(N);
	nOfNets = N;

	while (gets(line)) {
	if (line[0] == '\0') break;

	for (int i = 0; line[i];) {
	int X = getNum(line, i);
	int Y = getNum(line, i);
	Union(X, Y);
	}
	}
	printf("%d\n", nOfNets);
	if (Case) putchar('\n');
	}
	}
	int getNum(char line[], int &i)
	{
	int n = 0;
	while (line[i] != ' ' && line[i] != '\0') {
	n = n * 10 + (line[i] - '0');
	++i;
	}
	while (line[i] == ' ' && line[i] != '\0') ++i;
	return n;
	}
	void MakeSet(int n)
	{
	for (int i = 1; i <= n; ++i)
	Set[i] = i;
	}
	int FindSetRoot(int x)
	{
	if (Set[x] == x)
	return x;
	return Set[x] = FindSetRoot(Set[x]);
	}
	void Union(int X, int Y)
	{
	X = FindSetRoot(X);
	Y = FindSetRoot(Y);
	if (X != Y){
	Set[X] = Y;
	--nOfNets;
	}
	}

view raw [UVa] 879 Circuit Nets.cpp hosted with ❤ by GitHub

UVa 793 Network Connections

想法：
　　建disjoint set，把連在一起的電腦放在同一個Set，在判斷兩台電腦是否在同一個Set。具體做法是，

一開始每台電腦都是一個Set(同時該Set的root就是該台電腦編號)
然後要合併兩個Set就先各別找到它們的Root，再從一邊的Root連到另一邊的Root合併成一個Set
要判斷兩台電腦是否在同一個Set也是分別找Root，如果Root一樣表示這兩台電腦在同一個Set。

	#include <cstdio>
	using namespace std;

	int Set[1000001]; // Set[i]= x, x表示i的father, 最上層root的father還是自己

	void MakeSet(int n);
	int FindSetRoot(int x);
	void Union(int x, int y);

	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case, C;
	char line[100];
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d ", &C);

	MakeSet(C);

	char Type;
	int A, B;
	int nOfSuccess = 0, nOfUnSuccess = 0;

	while (gets(line)) {
	if (line[0] == '\0') break;
	sscanf(line, "%c %d %d", &Type, &A, &B);

	if (Type == 'c') {
	Union(A,B);
	}
	else {
	if (FindSetRoot(A) == FindSetRoot(B)) //如果同一個root表示在同一個Set
	++nOfSuccess;
	else
	++nOfUnSuccess;
	}
	}
	printf("%d,%d\n", nOfSuccess, nOfUnSuccess);
	if (Case) putchar('\n');
	}
	return 0;
	}
	void MakeSet(int n) // 一開始每個數字都是一個set,自己就是root
	{
	for (int i = 0; i <= n; ++i)
	Set[i] = i;
	}
	int FindSetRoot(int x) // 一直往上找到root
	{
	if (Set[x] == x)
	return x;
	return Set[x] = FindSetRoot(Set[x]); // 前面等號賦値的用意是讓Set深度不要太深
	} // 加速之後尋找速度
	void Union(int x, int y) //將x所屬的Set和y所屬的Set合併成一個Set
	{
	x = FindSetRoot(x);
	y = FindSetRoot(y);

	if (x != y) {
	Set[y] = x;
	}
	}

view raw [UVa] 793 Network Connections.cpp hosted with ❤ by GitHub

POJ 3253 Fence Repair

想法：
　　題目雖然說是砍斷，但其實可以想成一塊一塊拼回來，兩塊兩塊拼成的長度就是收取的費用，這題跟 UVa 10954 Add All 做法一樣，用priority_queue。

	#include <cstdio>
	#include <queue>
	using namespace std;
	typedef long long int llt;
	int main()
	{
	llt N, L;
	while (scanf("%lld", &N) != EOF) {
	priority_queue<llt, vector<llt>, greater<llt> > PQ;
	for (llt i = 0; i < N; ++i) {
	scanf("%lld", &L);
	PQ.push(L);
	}
	llt sum = 0;
	while (PQ.size() > 1) {
	llt tmp = PQ.top();
	PQ.pop();
	tmp += PQ.top();
	PQ.pop();

	sum += tmp;
	PQ.push(tmp);
	}
	printf("%lld\n", sum);
	}
	return 0;
	}

view raw [POJ] 3253 Fence Repair.cpp hosted with ❤ by GitHub

2014年3月2日星期日

POJ 2431 Expedition

題意：
　　一群牛從起點要出發到城鎮(目的地)距離共L單位，每走一單位同時消耗一單位的油，一開始油箱有P單位的油量，路途中會經過幾個加油站，每個加油站會給兩個數字，1.距離城鎮多少單位，2.這個加油站能加多少油，本題問到目的最少要到幾個加油站加油，如果不可能到達目的地則輸出-1。

想法：
　　因為所有地點都在同一直線上，所以都會經過每個加油站，只是看要不要停下來加油而已。所以我們就盡可能往前走，把每個路過加油站的該站的加油量放到priority queue裡面，然後直到走到途中沒油了，就從priority queue裡面拿出第一個(最大的加油量)加到自己的油箱，因為既然要加油，就要一次加最多的油，一直反覆這個動作直到終點。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct fuel_stop{
	int pos;
	int amount;
	}stop[10010];
	bool cmp(fuel_stop a, fuel_stop b)
	{
	return a.pos > b.pos;
	}
	int main()
	{
	int N, L, P;
	while (scanf("%d", &N) != EOF) {
	for (int i = 0; i < N; ++i)
	scanf("%d %d", &stop[i].pos, &stop[i].amount);
	scanf("%d %d", &L, &P);

	sort(stop, stop + N, cmp);

	stop[N] = {0,0}; // 終點也當一個stop
	priority_queue<int> PQ; // PQ用來裝每個stop的油量

	int dis = L - stop[0].pos; // 起點~第一站
	int sum_dis = dis; // 總共已經走了多遠
	P -= dis;

	int i = 0; // i用來當index
	int ans = 0;
	bool OK = 1;
	while (sum_dis < L && OK) {
	while (P >= 0) { //當身上油還>=0時繼續前進
	dis = stop[i].pos - stop[i+1].pos;
	P -= dis;
	sum_dis += dis;
	PQ.push(stop[i].amount);
	++i;
	if (i == N) break;
	}
	while (P < 0 && OK) { // PQ裡面從最多油量開始挑,加入油箱
	if (PQ.empty()) OK = 0;
	else{
	P += PQ.top();
	PQ.pop();
	++ans;
	}
	}
	}
	if (OK) printf("%d\n", ans);
	else puts("-1");
	}
	}

view raw [POJ] 2431 Expedition.cpp hosted with ❤ by GitHub

UVa 12347 Binary Search Tree

想法：
真的直接造出一棵樹來~

	#include <cstdio>
	using namespace std;
	struct Tree{
	int val = 0;
	Tree *L = nullptr;
	Tree *R = nullptr;
	};
	Tree Insert(Tree H, int node)
	{
	Tree *N = new Tree;
	N->val = node;

	if (H == nullptr) return N;

	Tree T = H, nxt = H;
	while (nxt != nullptr) {
	T = nxt;
	if (node > nxt->val) nxt = nxt->R;
	else nxt = nxt->L;
	}
	if (node > T->val) T->R = N;
	else T->L = N;
	return H;
	}
	void Post_Order(Tree *Root)
	{
	if (Root == nullptr) return;
	Post_Order(Root->L);
	Post_Order(Root->R);
	printf("%d\n", Root->val);
	}
	int main()
	{
	Tree *head = nullptr;
	int node;
	while (scanf("%d", &node) != EOF)
	head = Insert(head,node);
	Post_Order(head);
	return 0;
	}

view raw [UVa] 12347 Binary Search Tree.cpp hosted with ❤ by GitHub

2014年3月1日星期六

UVa 11995 I Can Guess the Data Structure

想法：

既然C++提供STL了，那就直接拿來用，模擬實際情況，但取値或pop()的時候要注意該Container是否為empty，否則會Runtime Error。

	#include <cstdio>
	#include <stack>
	#include <queue>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N, Command, num;
	while (scanf("%d", &N) != EOF) {
	stack<int> S;
	queue<int> Q;
	priority_queue<int> PQ;
	bool isStack = 1, isQueue = 1, isPriQueue = 1;

	while (N--) {
	scanf("%d%d", &Command, &num);
	if (Command == 1) {
	S.push(num);
	Q.push(num);
	PQ.push(num);
	}
	else {
	if (S.empty() \|\| S.top() != num) isStack = 0;
	if (Q.empty() \|\| Q.front() != num) isQueue = 0;
	if (PQ.empty() \|\| PQ.top() != num) isPriQueue = 0;
	if (!S.empty()) S.pop();
	if (!Q.empty()) Q.pop();
	if (!PQ.empty()) PQ.pop();
	}
	}
	if (isStack + isQueue + isPriQueue > 1)
	puts("not sure");
	else if (isStack) puts("stack");
	else if (isQueue) puts("queue");
	else if (isPriQueue) puts("priority queue");
	else puts("impossible");
	}
	return 0;
	}

view raw [UVa] 11995 I Can Guess the Data Structure.cpp hosted with ❤ by GitHub

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個空間被填滿，一直遞迴下去直到分配完全部數字。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	void BST(int Left, int Right, int H);
	int main()
	{
	int Case = 1;
	int N, H;
	while (scanf("%d %d", &N, &H) && (N \|\| H)) {
	printf("Case %d:", Case++);
	if (pow(2,H) - 1 < N) {
	puts(" Impossible.");
	continue;
	}
	if (H > N) H = N; // 深度如果大於總數就讓H=N
	BST(1, N, H);
	putchar('\n');
	}
	}
	void BST(int Left, int Right, int H)
	{
	if (H == 0 \|\| Left > Right) return;
	//下一個root應盡可能靠左,所以把右子樹填滿
	int right_space = pow(2, H - 1) - 1; //右子樹空間
	int root = Right - right_space;
	if (root < Left) root = Left;

	printf(" %d", root);

	BST(Left, root - 1, H - 1);
	BST(root + 1, Right, H - 1);
	}

view raw [UVa] 10821 Constructing BST.cpp hosted with ❤ by GitHub

UVa 10954 Add All

想法：
這題不是單純由小加到大，考慮 4 5 5 6 7 這數列，4+5+5=14之後，應該要做6+7=13，之後再做13+14=27。
因此每次都選擇兩個最小的數字相加，然後變成一個數字，然後丟回數列裡面，重複至數列只剩一個數字。
借這題順便練習一下priority_queue，它有三個參數priority_queue<type, container, function>，container有兩種，可以用vector<>和deque<>，function也有兩個，less<>將最大的元素放在top，greater<>將最小的元素放在top。

	#include <cstdio>
	#include <queue>
	using namespace std;
	int main()
	{
	int N, x;
	while (scanf("%d", &N) && N) {
	priority_queue<int, vector<int>, greater<int>> PQ;
	for (int i = 0; i < N; ++i) {
	scanf("%d", &x);
	PQ.push(x);
	}
	int cost = 0;
	while (PQ.size() != 1) {
	x = PQ.top(); PQ.pop();
	x += PQ.top(); PQ.pop();
	cost += x;
	PQ.push(x);
	}
	printf("%d\n", cost);
	}
	return 0;
	}

view raw [UVa] 10954 Add All.cpp hosted with ❤ by GitHub

2014年2月28日星期五

UVa 712 S-Trees

題意：
第一個數字為樹的深度N，然後有N個xi表示從root到(N-1)每一層的變數xi(例如x3 x1 x2表示root層的變數為x3，第1層變數為x1，第二層變數為x2)，接下來一串0和1的序列代表樹的最底層從左到右的値，然後有M個VVL，每個VVL依序表示變數xi的値(例如011表示x1=0，x2=1，x3=1)，因此知道xi代表的値後，就能從root走到底層(每層有自己的變數xi，遇到0向左走，1向右走)，一直走到底層看最底層是什麼數字。

想法：
從root開始往下走，先將root編號n為0，往左下走就乘以2，往右下走就乘以2加1，直到最底層，看編號n是多少就輸出底層序列的第n個數字。
0 root
0 1 第1層
0 1 2 3 第2層
0 1 2 3 4 5 6 7 最底層

	#include <iostream>
	#include <cstdio>
	#include <string>
	#include <vector>
	using namespace std;

	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, M, Case = 1;
	while (cin >> N && N) {
	cout << "S-Tree #" << Case++ << ':' << endl;
	string tmp;
	vector<int> order;
	string terminal_node;
	for (int i = 0; i < N; ++i) {
	cin >> tmp;
	order.push_back(tmp[1]-'0');
	}
	cin >> terminal_node >> M;
	string VVA;
	while (M--) {
	cin >> VVA;
	int node_num = 0;
	for (int i = 0; i < N; ++i) {
	int direction = VVA[order[i]-1] - '0';
	node_num = node_num * 2 + direction;
	}
	cout << terminal_node[node_num];
	}
	cout << endl << endl;
	}
	return 0;
	}

view raw [UVa] 712 S-Trees.cpp hosted with ❤ by GitHub

UVa 501 Black Box

想法：
原本是用multiset來存每個數字，因為multiset為紅黑樹，想說從第一個元素iterate i次來GET第i個數字，但一個一個iterate效率太慢就TLE了。
後來改用vector來存數字，每新增一個數字，就用binary search找到它該放的位置，然後用vector的insert來插入該數字，要GET第i個元素因為是vector就可以直接存取了，效率還不錯，UVa花了0.495秒。

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int A[30010];
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case, M, N, tmp;
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; ++i)
	scanf("%d", &A[i]);

	vector<int> Box;
	int U, a = 0, i = 0; // a is index of A
	while (N--) {
	scanf("%d", &U);
	while (a < U) { // lower_bound回傳一個iterator指向Box裡面第一個>=A[a]的元素
	auto iter = lower_bound(Box.begin(), Box.end(), A[a]);
	Box.insert(iter, A[a++]);
	}
	printf("%d\n", Box[i++]);
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 501-2 Black Box.cpp hosted with ❤ by GitHub

這是用set的版本：

	#include <cstdio>
	#include <set>
	using namespace std;
	int Case, M, N;
	int A[30010], U[30010];
	int main()
	{
	freopen("input.txt","rt",stdin);
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < M; ++i)
	scanf("%d", &A[i]);
	for (int i = 0; i < N; ++i)
	scanf("%d", &U[i]);

	multiset<int> Box;
	for (int i = 0, u = 0, a = 0; u < N; ++u, ++i)
	{
	while (a < U[u] && a < N)
	Box.insert(A[a++]);

	auto iter = Box.cbegin();
	for (int j = 0; j < i; ++j)
	++iter;
	printf("%d\n", *iter);
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 501-1 Black Box.cpp hosted with ❤ by GitHub

2014年2月27日星期四

UVa 902 Password Search

題意：
N為一個substring的長度，找出題目string裡面哪個substring重複最多次數。

想法：
用map[substring] = 次數來記錄每個substring出現的次數，然後再找出最大的次數並輸出該substring。

	#include <iostream>
	#include <string>
	#include <map>
	using namespace std;
	int main()
	{
	ios::sync_with_stdio(false);
	int N;
	string str;
	while (cin >> N) {
	cin.get();
	getline(cin, str);
	map<string, int> Map;
	for (int i = 0; i <= str.size()-N; ++i) {
	string tmp = str.substr(i, N); // 從第i個位置擷取str N個字元
	if (!Map[tmp]) Map[tmp] = 1;
	else Map[tmp]++;
	}
	int Max = 0;
	for (auto &m : Map) { // m為pair structure
	if (m.second > Max) {
	Max = m.second;
	str = m.first;
	}
	}
	cout << str << endl;
	}
	return 0;
	}

view raw [UVa] 902 Password Search.cpp hosted with ❤ by GitHub

POJ 3481 Double Queue

想法：
　　用STL_map可以完成這題，map<int, int>Map，然後對應方式為Map[優先權] = 人員編號，因為Map為自動平衡的tree，所以優先權最大的會在tree的最右下方，也就是Map這個container的最後一個，而優先權最小的反之，在Map的第一個位置。另外map這container是用pair來存資料，因此要輸出人員編號要用->second。

	#include <cstdio>
	#include <map>
	using namespace std;
	int main()
	{
	map<int,int> Map;
	int instruction, priority, number;
	while (scanf("%d", &instruction)) {
	switch (instruction) {
	case 1:
	scanf("%d%d", &number, &priority);
	Map[priority] = number;
	break;
	case 2:
	if (Map.empty()) puts("0");
	else {
	printf("%d\n", (--Map.end())->second);
	Map.erase(--Map.end());
	}
	break;
	case 3:
	if (Map.empty()) puts("0");
	else {
	printf("%d\n", Map.begin()->second);
	Map.erase(Map.begin());
	}
	break;
	case 0:
	return 0;
	}
	}
	}

view raw [POJ] 3481 Double Queue.cpp hosted with ❤ by GitHub

UVa 10308 Roads in the North

題意：
　　計算該graph最遠的距離。
想法：
　　DFS function 定義為"回傳該點能走的最遠深度"，例如DFS(p點)，則在DFS裡面我們對p點能前往的那些點做DFS，記下該路徑(route)的長度，並一直刷新route_max的大小，最後回傳route_max。
　　在刷新route_max"之前"，我們先把(route+route_max)與ans比較，刷新ans，(route+route_max)表示p點往兩個不同方向的路徑的和，不斷刷新ans，就能產生最遠的距離。

	#include <cstdio>
	#include <vector>
	using namespace std;
	struct point_type{
	int nxt;
	int len;
	};
	vector<point_type> toPoint[10005];
	int ans;
	int DFS(int point, int prev_point) // DFS回傳該點能走的最深路徑的距離
	{
	int route_max = 0;
	for (auto &p : toPoint[point]) {
	if (p.nxt == prev_point) continue;

	int route = DFS(p.nxt, point) + p.len;

	if (route + route_max > ans) // 現在走的路徑+已經儲存的最大路徑如果大於ans就更新ans
	ans = route + route_max;

	if (route > route_max)
	route_max = route;
	}
	return route_max;
	}
	void input(char line[])
	{
	int p1, p2, L;
	sscanf(line, "%d%d%d", &p1, &p2, &L);
	toPoint[p1].push_back({p2,L});
	toPoint[p2].push_back({p1,L});
	}
	int main()
	{
	freopen("input.txt","rt",stdin);
	char line[100];
	while (gets(line)) {
	if (line[0] == '\0') {
	puts("0");
	continue;
	}
	for (auto &v : toPoint) v.clear();
	input(line);

	while (gets(line)) {
	if (line[0] == '\0') break;
	input(line);
	}

	ans = 0;
	DFS(1,-1);
	printf("%d\n", ans);
	}
	return 0;
	}

view raw [UVa] 10308 Roads in the North.cpp hosted with ❤ by GitHub

UVa 11624 Fire

題意：

　　J在一個迷宮裡，迷宮有"不只一個"起火點F，J一分鐘移動一步，而火焰一分鐘也會向上下左右蔓延一步，J只要碰到迷宮的邊緣即可逃走，確認J是否能逃走，如果可以，輸出要走的最短步數。

想法：

　　將每個起火點用vector(或array)存下來，然後同時用兩個BFS，先讓所有起火點先動一步，再讓J動一步，確認J是否能碰到迷宮的邊緣。

　　用int Maze[1001][1001]來描述該迷宮的情況，我用-2代表起火點，-1代表牆壁('#')，0代表可以走的路，用BFS時，每次為了確認火焰都只動一步，因此勢必要記錄火焰走的步數，每次火焰走下一步時Maze[nxt_i][nxt_j] = Maze[cur_i][cur_j] - 1，用負數記錄火焰步數，而正數用來記錄Joe的步數。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;

	int R, C;
	int Maze[1001][1001]; // -2:'F', 0:'.', -1:'#'
	struct point_type{
	int x;
	int y;
	};
	vector<queue<point_type>> QF; // 存每個起火點
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	int BFS(point_type J)
	{
	queue<point_type> QJ; QJ.push(J); // 存Joe
	point_type cur, nxt;
	int minute;
	while(!QJ.empty()) {
	for (int i = 0; i < QF.size(); ++i) { // 多個火焰都要各動一步
	if (!QF[i].empty()){
	cur = QF[i].front();
	minute = Maze[cur.x][cur.y]; // 讓該火焰只動完目前這一分鐘後
	}
	while (!QF[i].empty()){
	cur = QF[i].front();
	if (Maze[cur.x][cur.y] != minute) break; // 就跳出queue 換成 J 移動
	QF[i].pop();
	for (int x = 0; x < 4; ++x) {
	nxt.x = cur.x + direction[x][0];
	nxt.y = cur.y + direction[x][1];
	if (nxt.x < 0 \|\| nxt.x >= R \|\| nxt.y < 0 \|\| nxt.y >= C) continue;

	if (Maze[nxt.x][nxt.y] == 0) {
	Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] - 1;
	QF[i].push(nxt);
	}
	}
	}
	}
	cur = QJ.front();
	minute = Maze[cur.x][cur.y];
	while (!QJ.empty()) {
	cur = QJ.front();
	if (Maze[cur.x][cur.y] != minute) break; //只動完一步後就換火焰移動

	QJ.pop();
	for (int x = 0; x < 4; ++x) {
	nxt.x = cur.x + direction[x][0];
	nxt.y = cur.y + direction[x][1];
	if (nxt.x < 0 \|\| nxt.x >= R \|\| nxt.y < 0 \|\| nxt.y >= C)
	return Maze[cur.x][cur.y];
	if (Maze[nxt.x][nxt.y] == 0) {
	Maze[nxt.x][nxt.y] = Maze[cur.x][cur.y] + 1;
	QJ.push(nxt);
	}
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case;
	char line[1005];
	scanf("%d", &Case);
	while (Case--) {
	scanf("%d %d", &R, &C);
	point_type J;
	QF.clear();
	for (int i = 0; i < R; ++i) {
	scanf("%s", line);
	for (int j = 0; j < C; ++j) {
	if (line[j] == '.')
	Maze[i][j] = 0;
	else if (line[j] == '#')
	Maze[i][j] = -1;
	else if (line[j] == 'J') {
	J = {i,j};
	Maze[i][j] = 1;
	}
	else if (line[j] == 'F') {
	queue<point_type> tmp;
	tmp.push({i,j});
	QF.push_back(tmp);
	Maze[i][j] = -2;
	}
	}
	}
	int minute = BFS(J);
	if (minute == -1) puts("IMPOSSIBLE");
	else printf("%d\n", minute);
	}
	return 0;
	}

view raw [UVa] 11624 Fire!.cpp hosted with ❤ by GitHub

UVa 10946 You want what filled

題意：
　　計算給定的區域不同種類的坑洞的面積，輸出時依照坑洞面積的大小排序，如果一樣則按照字母順序。

想法：
　　碰到不是'.'的字元就用BFS去算該坑洞的面積，最後再sort輸出即可。

	#include <cstdio>
	#include <queue>
	#include <algorithm>
	using namespace std;

	int X, Y;
	char grid[55][55];
	struct hole_type {
	char ch;
	int num;
	}hole[2550];
	struct point_type {
	int i;
	int j;
	};
	hole_type BFS(char c, int i, int j);
	bool cmp(hole_type a, hole_type b);
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d", &X, &Y) && (X \|\| Y)) {
	for (int i = 0; i < X; ++i)
	scanf("%s", grid[i]);

	int numOfhole = 0;
	for (int i = 0; i < X; ++i)
	for (int j = 0; j < Y; ++j)
	if (grid[i][j] != '.')
	hole[numOfhole++] = BFS(grid[i][j], i, j);

	sort(hole, hole + numOfhole, cmp);

	printf("Problem %d:\n", Case++);
	for (int i = 0; i < numOfhole; ++i)
	printf("%c %d\n", hole[i].ch, hole[i].num);
	}
	}
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	hole_type BFS(char c, int i, int j)
	{
	queue<point_type> Q;
	Q.push({i,j});
	grid[i][j] = '.';
	int num = 1;

	point_type cur, nxt;
	while (!Q.empty()) {
	cur = Q.front();
	Q.pop();
	for (int k = 0; k < 4; ++k) {
	nxt.i = cur.i + direction[k][0];
	nxt.j = cur.j + direction[k][1];
	if (nxt.i < 0 \|\| nxt.i >= X \|\| nxt.j < 0 \|\| nxt.j >= Y) continue;

	if (grid[nxt.i][nxt.j] == c) {
	grid[nxt.i][nxt.j] = '.';
	Q.push(nxt);
	++num;
	}
	}
	}
	return {c, num};
	}
	bool cmp(hole_type a, hole_type b)
	{
	return (a.num == b.num) ? (a.ch < b.ch) : (a.num > b.num);
	}

view raw [UVa] 10946 You want what filled.cpp hosted with ❤ by GitHub

UVa 10592 Freedom FIghter

題意：

　　'B'為fighter，'P'為enemy，'*'圍起來的範圍內為一個sector，sector的編號由左至右由上至下，要計算每個sector裡面有幾組fighter和幾組enemy，如果fighter和enemy面對面的話，表示有2個group在fighting position。

面對面的情況只會各有一組，

BBB

不會有底下這種情況

BBB

想法：

　　用DFS_1來走遍該sector，如果碰到'B'或'P'則用DFS_2走遍該group，並確認有沒有碰到另一個group。

	#include <cstdio>
	using namespace std;

	int n;
	int fighter, enemy, fighting_group;
	char grid[51][51];
	const int direction[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

	bool DFS_2(char, int ,int);
	void DFS_1(int i, int j, int &fighter, int &enemy) // DFS_1用來走遍'*',如果遇到'B'或'P'則進入DFS_2
	{
	grid[i][j] = '.';
	for (int x = 0; x < 4; ++x) {
	int nxt_i = i + direction[x][0];
	int nxt_j = j + direction[x][1];
	if (nxt_i < 0 \|\| nxt_i >= n \|\| nxt_j < 0 \|\| nxt_j >= n) continue;

	if (grid[nxt_i][nxt_j] == 'B') {
	++fighter;
	if (DFS_2('B', nxt_i, nxt_j)) fighting_group += 2;
	}
	if (grid[nxt_i][nxt_j] == 'P') {
	++enemy;
	if (DFS_2('P', nxt_i, nxt_j)) fighting_group += 2;
	}
	if (grid[nxt_i][nxt_j] == '*')
	DFS_1(nxt_i, nxt_j, fighter, enemy);
	}
	}
	bool DFS_2(char C, int i, int j) //用來走遍'B'或'P'並確認是否有碰到另一個group(面對面)
	{
	grid[i][j] = '*';
	bool another_group = 0;
	bool touch_another = 0;
	for (int x = 0; x < 4; ++x) {
	int nxt_i = i + direction[x][0];
	int nxt_j = j + direction[x][1];
	if (nxt_i < 0 \|\| nxt_i >= n \|\| nxt_j < 0 \|\| nxt_j >= n) continue;

	if (C == 'B' && grid[nxt_i][nxt_j] == 'P' \|\|
	C == 'P' && grid[nxt_i][nxt_j] == 'B') another_group = 1;

	if (grid[nxt_i][nxt_j] == C)
	another_group = DFS_2(C, nxt_i, nxt_j);
	if (another_group == 1) touch_another = 1;
	}
	return touch_another;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	while (scanf("%d", &n) && n) {
	for (int i = 0; i < n; ++i)
	scanf("%s", grid[i]);
	int sector = 1;
	fighting_group = 0;
	for (int i = 0; i < n; ++i) {
	for (int j = 0; j < n; ++j) {
	if (grid[i][j] != '.') {
	fighter = 0;
	enemy = 0;
	if (grid[i][j] == 'B') {++fighter; if (DFS_2('B', i, j)) fighting_group += 2;}
	if (grid[i][j] == 'P') {++enemy; if (DFS_2('P', i, j)) fighting_group += 2;}
	DFS_1(i, j, fighter, enemy);
	printf("Sector #%d: contain %d freedom fighter group(s) & %d enemy group(s)\n",
	sector++, fighter, enemy);
	}
	}
	}
	printf("Total %d group(s) are in fighting position.\n\n", fighting_group);
	}
	return 0;
	}

view raw [UVa] 10592 Freedom Fighter.cpp hosted with ❤ by GitHub

2014年2月24日星期一

UVa 705 Slash Maze

想法：
　　把長和寬延伸3倍，使得迷宮地圖大9倍，並將'/'和'\'變成底下的形式：
001 100
010 010
100 001
　　延伸3倍的目的是為了讓我們在使用BFS的時候，能夠直接上下左右的走，不需要斜著走，所以只要依照'/'將地圖先做出來，再使用BFS走遍，並要判斷走遍的時候會不會走出界，如果會走出界代表它不是一個Cycle，而因為延伸3倍的關係，走的路徑長度最後要除以3。

	#include <cstdio>
	#include <cstring>
	#include <queue>
	using namespace std;
	int W, H;
	int Maze[300][300];
	struct point_type{
	int i;
	int j;
	};
	void Write_Maze(char line[], int i)
	{
	for (int j = 0; line[j]; ++j) {
	int ii = i * 3, jj = j * 3;
	for (int x = 0; x < 3; ++x)
	for (int y = 0; y < 3; ++y)
	Maze[ii+x][jj+y] = 0;
	if (line[j] == '\\') {
	Maze[ii][jj] = 1;
	Maze[ii+1][jj+1] = 1;
	Maze[ii+2][jj+2] = 1;
	}
	else {
	Maze[ii][jj+2] = 1;
	Maze[ii+1][jj+1] = 1;
	Maze[ii+2][jj] = 1;
	}
	}
	}
	const int direction[][2] = {{-1,0},{1,0},{0,-1},{0,1}};
	bool Run_Maze(int i, int j, int &longest)
	{
	queue<point_type> Q;
	Q.push({i,j});
	int length = 1;
	bool isCycle = 1;
	point_type cur, nxt;
	while (!Q.empty()) {
	length++;
	cur = Q.front();
	Q.pop();

	for (int x = 0; x < 4; ++x) {
	nxt.i = cur.i + direction[x][0];
	nxt.j = cur.j + direction[x][1];
	if (nxt.i < 0 \|\| nxt.j < 0 \|\| nxt.i >= H \|\| nxt.j >= W) {
	isCycle = 0;
	continue;
	}
	if (Maze[nxt.i][nxt.j] == 0) {
	Maze[nxt.i][nxt.j] = 1;
	Q.push(nxt);
	}
	}
	}
	if (isCycle == 0) return 0;
	length /= 3;
	if (longest < length) longest = length;
	return 1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	char line[100];
	while (scanf("%d %d", &W, &H) && (W \|\| H)) {
	for (int i = 0; i < H; ++i){
	scanf("%s", line);
	Write_Maze(line, i);
	}
	H *= 3;
	W *= 3;
	int numOfCycles = 0;
	int longest = 0;
	for (int i = 0; i < H; ++i)
	for (int j = 0; j < W; ++j)
	if (Maze[i][j] == 0)
	if (Run_Maze(i, j, longest))
	numOfCycles++;
	printf("Maze #%d:\n", Case++);
	if (numOfCycles)
	printf("%d Cycles; the longest has length %d.\n\n", numOfCycles, longest);
	else printf("There are no cycles.\n\n");
	}
	}

view raw [UVa] 705 Slash Maze.cpp hosted with ❤ by GitHub

2014年2月22日星期六

UVa 10009 All Roads Lead Where?

想法：
將讀進來的字串用map轉成數字，並建立兩個點的連線。
用BFS演算法來搜索目的地，並在過程中用visit[]記錄每次的步數，最後抵達終點時BFS演算法結束，然後我們再利用visit從終點逆向走回起點，記下這條路徑走過的點，最後輸出結果。

	#include <cstdio>
	#include <iostream>
	#include <queue>
	#include <vector>
	#include <map>
	using namespace std;

	map<string, int> Map;
	vector<string> toPoint[10001];

	void BFS (string Start, string End)
	{
	queue<string> Q;
	Q.push(Start);
	int visit[10001] = {0};
	visit[Map[Start]] = 1;
	// 標準BFS演算法
	string cur;
	bool FindedEnd = 0;
	while (!Q.empty() && !FindedEnd) {
	cur = Q.front();
	Q.pop();

	for (const auto &nxt : toPoint[Map[cur]]) {
	if (visit[Map[nxt]] == 0) {
	// 將走過的步數存下來，等等逆向的時候會用到
	visit[Map[nxt]] = visit[Map[cur]] + 1;
	if (nxt == End) {
	FindedEnd = 1;
	break;
	}
	Q.push(nxt);
	}
	}
	}
	// 逆向走回起點並將該路徑存在Ans
	int step_count = visit[Map[End]];
	vector<char> Ans = {End[0]};
	cur = End;
	while (step_count != 1) {
	for (const auto &nxt : toPoint[Map[cur]]) {
	if (visit[Map[nxt]] == step_count - 1) {
	Ans.push_back(nxt[0]);
	--step_count;
	cur = nxt;
	break;
	}
	}
	}
	for (auto i = Ans.end() - 1; i != Ans.begin(); --i)
	cout << *i;
	cout << Ans[0] << endl;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int Case, M, N;
	cin >> Case;
	while (Case--) {
	Map.clear();
	for (auto &v : toPoint) v.clear();
	string s1, s2;

	cin >> M >> N;
	for (int i = 0, j = 1; i < M; ++i) {
	cin >> s1 >> s2;
	if (!Map[s1]) Map[s1] = j++;
	if (!Map[s2]) Map[s2] = j++;
	toPoint[Map[s1]].push_back(s2);
	toPoint[Map[s2]].push_back(s1);
	}
	for (int i = 0; i < N; ++i) {
	cin >> s1 >> s2;
	BFS (s1, s2);
	}
	if (Case) cout << endl;
	}
	return 0;
	}

view raw [UVa] 10009 All Roads Lead Where?.cpp hosted with ❤ by GitHub

UVa 10004 Bicoloring

題意：
只有兩種顏色，兩個相鄰的點必須顏色不同，給定一個graph，判斷該graph是否能符合上述條件。

想法：
用BFS走遍所有的點，走過的點將它編號為1或2，如果下一個點還沒走過，將它標上和現在這個點不一樣的編號，如果下一個已經走過，而編號和現在這個點一樣，回傳false，否則當BFS搜索完，回傳true。

	#include <cstdio>
	#include <queue>
	#include <vector>
	using namespace std;

	int N,I;
	vector<int> toPoint[205];

	bool BFS(int Start)
	{
	queue<int> Q;
	Q.push(Start);
	int visit[205] = {0};

	while (!Q.empty()) {
	int cur = Q.front();
	Q.pop();

	for (int &nxt : toPoint[cur]) {
	if (visit[nxt] == 0) {
	Q.push(nxt);
	if (visit[cur] == 1) visit[nxt] = 2;
	else visit[nxt] = 1;
	}
	else if (visit[nxt] == visit[cur])
	return false;
	}
	}
	return true;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d", &N)) {
	if (!N) break;
	for (auto &v : toPoint) v.clear();
	scanf("%d", &I);
	int p1, p2;
	for (int i=0; i<I; ++i) {
	scanf("%d %d", &p1, &p2);
	toPoint[p1].push_back(p2);
	toPoint[p2].push_back(p1);
	}
	printf("%s\n", BFS(p1) ? "BICOLORABLE." : "NOT BICOLORABLE.");
	}
	}

view raw [UVa] 10004 Bicoloring.cpp hosted with ❤ by GitHub

UVa 762 We Ship Cheap

想法：
用BFS從起點搜尋終點，並用visit[]儲存步數，然後再從終點依據visit走回起點，並將過程走過的點儲存起來，最後輸出。

	#include <bits/stdc++.h>
	using namespace std;

	map<string, int> Map; //將每個點從字串換成編號
	vector<string> toPoint[10001]; // 用來存每個點能連到哪些點

	void BFS(string Start, string End)
	{
	queue<string> Q;
	Q.push(Start);
	int visit[10001] = {0};
	visit[Map[Start]] = 1;

	string cur;
	bool findedEnd = 0;
	while (!Q.empty() && !findedEnd) { // BFS演算法
	cur = Q.front();
	Q.pop();

	for (string &nxt : toPoint[Map[cur]]) {
	if (visit[Map[nxt]] == 0) {
	visit[Map[nxt]] = visit[Map[cur]] + 1;
	if (nxt == End){
	findedEnd = 1;
	break;
	}
	Q.push(nxt);
	}
	}
	}
	// 從終點逆向走回起點，並將過程存在ans裡
	int step_count = visit[Map[End]];
	cur = End;
	vector<string> ans;
	ans.push_back(End);
	bool stop = 0;
	while (!stop) {
	bool finded_nxt_point = 0;
	for (string &nxt : toPoint[Map[cur]]) {
	if (nxt == Start) {
	ans.push_back(Start);
	stop = 1;
	break;
	}
	if (visit[Map[nxt]] == step_count - 1) {
	--step_count;
	ans.push_back(nxt);
	cur = nxt;
	finded_nxt_point = 1;
	break;
	}
	}
	if (!finded_nxt_point) stop = 1;
	}
	if (visit[Map[End]] == 0) cout << "No route" << endl;
	else {
	for (int i = ans.size() - 1; i > 0; --i)
	cout << ans[i] << ' ' << ans[i-1] << endl;
	}
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	ios::sync_with_stdio(false);
	int N, blank_line = 0;
	while (cin >> N) {
	if (blank_line) cout << endl;
	blank_line = 1;
	Map.clear();
	for (auto &v : toPoint) v.clear();

	string p1, p2;
	for (int i = 0, j = 1; i < N; ++i) {
	cin >> p1 >> p2;
	if (!Map[p1]) Map[p1] = j++;
	if (!Map[p2]) Map[p2] = j++;
	toPoint[Map[p1]].push_back(p2);
	toPoint[Map[p2]].push_back(p1);
	}
	cin >> p1 >> p2;
	//p1,p2不管是否為前面儲存的點，如果p1==p2就輸出p1 p2
	if (p1 == p2) cout << p1 << ' ' << p2 << endl;
	else if (!Map[p1] \|\| !Map[p2]) cout << "No route" << endl;
	else BFS (p1, p2);
	}
	}

view raw [UVa] 762 We Ship Cheap.cpp hosted with ❤ by GitHub

2014年2月20日星期四

UVa 567 Risk

題意:
　　1~19行，每行第一個數字表示後面會輸入幾個數字，而第i行表示第i個點能連到哪些點，第20行只有一個數字表示之後有幾個測試資料，每個測試資料有兩個數字：起點和終點，求出最短距離。

想法：
　　BFS題目，將每個點依序建立連結後，使用BFS並依題目要求輸出即可。

	#include <cstdio>
	#include <vector>
	#include <queue>
	using namespace std;

	int BFS(int Start, int End, vector<int> toPoint[])
	{
	int visit[21] = {0};
	queue<int> Q;
	Q.push(Start);

	while (!Q.empty()) {
	int cur = Q.front();
	Q.pop();

	for (int nxt : toPoint[cur]) {
	if (visit[nxt] == 0) {
	visit[nxt] = visit[cur] + 1;
	if (nxt == End) return visit[nxt];
	Q.push(nxt);
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N, i, j, point, Case = 1;
	while (scanf("%d", &N) != EOF) {
	vector<int> toPoint[21];
	for (j=0; j<N; ++j){ // 輸入第1個點
	scanf("%d", &point);
	toPoint[1].push_back(point);
	toPoint[point].push_back(1);
	}
	for (i=2; i<=19; ++i) { // 輸入第2~19個點
	scanf("%d", &N);
	for (j=0; j<N; ++j) {
	scanf("%d", &point);
	toPoint[i].push_back(point);
	toPoint[point].push_back(i);
	}
	}
	scanf("%d", &N);
	printf("Test Set #%d\n", Case++);
	while (N--) {
	int start_point, end_point;
	scanf("%d%d", &start_point, &end_point);
	printf("%2d to %2d: %d\n", start_point, end_point,
	BFS(start_point, end_point, toPoint));
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 567 Risk.cpp hosted with ❤ by GitHub

2014年2月19日星期三

UVa 539 The Settlers of Catan

題目連結
想法：
　　將每個點能連到哪些點存起來，然後對每個點使用DFS看該點最遠能走多深。

	#include <cstdio>
	#include <vector>
	using namespace std;
	int DFS (int node, vector<int> toNode[30], int dis, bool visit[][30])
	{
	int longest_length = 0; // 當前node能走的最遠距離
	for (int nxt_node : toNode[node]){
	if (!visit[node][nxt_node]) { // 該條線還沒走過
	visit[node][nxt_node] = 1;
	visit[nxt_node][node] = 1; // 雙向關閉

	int length = DFS (nxt_node, toNode, dis+1, visit);
	if (length > longest_length) longest_length = length;

	visit[node][nxt_node] = 0;
	visit[nxt_node][node] = 0; // 雙向開啟
	}
	}
	if (longest_length == 0) return dis; //如果走到底回傳當前距離
	else return longest_length; //否則回傳該點能走的最長距離
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int n, m;
	while (scanf("%d%d", &n, &m)) {
	if (!n && !m) break;
	vector<int> toNode[30]; // toNode[i]儲存i_node能走向哪幾個點
	for (int i=0, n1, n2; i<m; ++i) {
	scanf("%d%d", &n1, &n2);
	toNode[n1].push_back(n2);
	toNode[n2].push_back(n1);
	}
	bool visit[30][30] = {0}; //visit[i][j]=1 表示i_j這條線已經走過
	int longest = 0;
	for (int i=0; i<n; ++i){
	int length = DFS(i, toNode, 0, visit);
	if (length > longest)
	longest = length;
	}
	printf("%d\n", longest);
	}
	}

view raw [UAa] 539 The Settlers of Catan.cpp hosted with ❤ by GitHub

UVa 439 Knight Moves

想法：
　　西洋棋Knight的走法與中國象棋'馬'的走法一樣，所以在8x8方格中用BFS即可。注意index轉換的問題。

	#include <cstdio>
	#include <queue>
	using namespace std;
	struct point_type{
	int i;
	int j;
	};
	const int direction[][2] = {{-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
	int BFS(point_type Start, point_type End)
	{
	int step[9][9] = {0};
	queue<point_type> Q;
	Q.push(Start);

	point_type cur, nxt;
	while (!Q.empty()) {
	cur = Q.front();
	Q.pop();

	if (cur.i == End.i && cur.j == End.j)
	return step[cur.i][cur.j];

	for (int i = 0; i < 8; ++i) {
	nxt.i = cur.i + direction[i][0];
	nxt.j = cur.j + direction[i][1];
	if (nxt.i < 1 \|\| nxt.i > 8 \|\| nxt.j < 1 \|\| nxt.j > 8) continue;

	if (step[nxt.i][nxt.j] == 0) {
	step[nxt.i][nxt.j] = step[cur.i][cur.j] + 1;
	Q.push(nxt);
	}
	}
	}
	return step[cur.i][cur.j];
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char s1[3], s2[3];
	while (scanf("%s%s", s1, s2) != EOF) {
	point_type Start, End;
	Start.i = s1[0] - 'a' + 1;
	Start.j = s1[1] - '0';
	End.i = s2[0] - 'a' + 1;
	End.j = s2[1] - '0';
	int moves = BFS(Start, End);
	printf("To get from %s to %s takes %d knight moves.\n", s1, s2, moves);
	}
	return 0;
	}

view raw [UVa] 439 Knight Moves.cpp hosted with ❤ by GitHub

UVa 571 Jugs

想法：
　　題目沒說要最少步數(先輸出10次fill A empty A也可)，所以直接用DFS求解即可。

	#include <cstdio>
	#include <vector>
	#include <string>
	using namespace std;
	int A, B, N;
	vector<string> process;
	int visit[1005][1005];

	bool DFS(int a, int b)
	{
	visit[a][b] = 1;
	if (b == N) return 1;

	if (visit[A][b] == 0) {process.push_back("fill A"); if (DFS(A,b)) return 1; process.pop_back();}
	if (visit[a][B] == 0) {process.push_back("fill B"); if (DFS(a,B)) return 1; process.pop_back();}
	if (visit[0][b] == 0) {process.push_back("empty A"); if (DFS(0,b)) return 1; process.pop_back();}
	if (visit[a][0] == 0) {process.push_back("empty B"); if (DFS(a,0)) return 1; process.pop_back();}

	int pour_A, pour_B;

	if (b > (A-a)) {pour_A = A; pour_B = B - (A-a);}
	else {pour_A = a + b; pour_B = 0;}
	if (visit[pour_A][pour_B] == 0) {
	process.push_back("pour B A");
	if (DFS(pour_A,pour_B)) return 1;
	process.pop_back();
	}

	if (a > (B-b)) {pour_A = A - (B-b); pour_B = B;}
	else {pour_A = 0; pour_B = b + a;}
	if (visit[pour_A][pour_B] == 0) {
	process.push_back("pour A B");
	if (DFS(pour_A,pour_B)) return 1;
	process.pop_back();
	}
	return 0;
	}
	int main()
	{
	while (scanf("%d%d%d", &A, &B, &N) != EOF) {
	process.clear();
	for (int i = 0; i<1005; ++i)
	for (int j = 0; j<1005; ++j)
	visit[i][j] = 0;
	DFS(0,0);
	for (string &a : process)
	printf("%s\n", a.c_str());
	printf("success\n");
	}
	return 0;
	}

view raw [UVa] 571 Jugs.cpp hosted with ❤ by GitHub

UVa 336 A Node Too Far

想法：
　　先記錄某個點與哪些點有相連，然後對起點和TTL用BFS即可。

	#include <cstdio>
	#include <queue>
	#include <map>
	#include <vector>
	using namespace std;
	map<int, int> mapping;
	struct node_type{
	vector<int> connceted_node;
	};
	int NC;
	int numOfnode;
	int BFS(int start_node, int TTL, node_type node[]);
	int main()
	{
	//freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d", &NC)) {
	if (!NC) break;

	node_type node[100];
	mapping.clear();

	int node1, node2, i, j;
	for (i=0, j=0; i<NC; ++i) {
	scanf("%d%d", &node1, &node2);
	if (mapping.find(node1) == mapping.end())
	mapping[node1] = j++;
	if (mapping.find(node2) == mapping.end())
	mapping[node2] = j++;
	node[mapping[node1]].connceted_node.push_back(mapping[node2]);
	node[mapping[node2]].connceted_node.push_back(mapping[node1]);
	}
	numOfnode = j;
	int TTL;
	while (scanf("%d%d", &node1, &TTL)) {
	if (!node1 && !TTL) break;
	int numOfNotReach = BFS(node1, TTL, node);
	printf("Case %d: %d nodes not reachable from node %d with TTL = %d.\n",
	Case++, numOfNotReach, node1, TTL);
	}
	}
	return 0;
	}
	int BFS(int start_node, int TTL, node_type node[])
	{
	queue<int> Q;
	Q.push(mapping[start_node]);
	int visit[100] = {0};
	visit[mapping[start_node]] = 1;

	int nOfReach = 1;
	while (!Q.empty()) {
	int cur = Q.front();
	if (visit[cur] > TTL) return numOfnode - nOfReach;
	Q.pop();
	for (int nxt : node[cur].connceted_node) {
	if(visit[nxt] == 0){
	visit[nxt] = visit[cur] + 1;
	Q.push(nxt);
	++nOfReach;
	}
	}
	}
	return numOfnode - nOfReach;
	}

view raw [UVa] 336 A Node Too Far.cpp hosted with ❤ by GitHub

2014年2月18日星期二

UVa 383 Shipping Routes

想法：
　　用BFS來做，前M個先將輸入的字串用map對應成整數，然後接下來N行每行讀兩個字串，將彼此加入可到達的路徑裡，最後P行每行用BFS搜尋路徑。

注意輸出DATA SET" "1 有兩個空格

	#include <iostream>
	#include <string>
	#include <map>
	#include <vector>
	#include <queue>
	#include <cstdio>
	using namespace std;
	struct route_type{
	vector<string> route;
	};
	int BFS(string Start, string End, map<string,int> &mapping, route_type A[])
	{
	int step[1001] = {0};
	queue<string> Q;
	Q.push(Start);

	while (!Q.empty()) {
	string cur = Q.front();
	Q.pop();
	for (string nxt : A[mapping[cur]].route){
	if (step[mapping[nxt]] == 0) {
	step[mapping[nxt]] = step[mapping[cur]] + 1;
	if (nxt == End) return step[mapping[nxt]];
	Q.push(nxt);
	}
	}
	}
	return 0;
	}
	int main()
	{
	//freopen("input","rt",stdin);
	ios::sync_with_stdio(false);
	int T,Case = 1;
	int M, N, P;
	cin >> T;
	cout << "SHIPPING ROUTES OUTPUT" << endl << endl;
	while (T--) {
	cin >> M >> N >> P;
	map<string,int> mapping;
	string s1,s2;
	for (int i=0; i<M; ++i){
	cin >> s1;
	mapping[s1] = i;
	}
	route_type A[1000];
	for (int i=0; i<N; ++i){
	cin >> s1 >> s2;
	A[mapping[s1]].route.push_back(s2);
	A[mapping[s2]].route.push_back(s1);
	}
	cout << "DATA SET " << Case++ << endl << endl;
	int Size;
	for (int i=0; i<P; ++i){
	cin >> Size >> s1 >> s2;
	int legs = BFS(s1,s2,mapping,A);
	if (!legs) cout << "NO SHIPMENT POSSIBLE" << endl;
	else cout << '$' << Size * legs * 100 << endl;
	}
	cout << endl;
	}
	cout << "END OF OUTPUT" << endl;
	return 0;
	}

view raw [UV] 383 Shipping Routes.cpp hosted with ❤ by GitHub

2014年2月17日星期一

UVa 260 Il Gioco dell'X

想法：
　　因為題目說一定有人獲勝，獲勝條件為黑色是由上走到下，白色是要由左走到右，因此就用DFS確認即可。

	#include <cstdio>
	using namespace std;
	int N;
	char board[201][201];
	const int direction[][2] = {{-1,-1},{-1,0},{0,-1},{0,1},{1,0},{1,1}};
	void DFS(int i, int j, char c,int &win)
	{
	board[i][j] = '.';
	if (c == 'b' && i == N-1) win = 1;
	if (c == 'w' && j == N-1) win = 2;
	for (int x=0; x<6; ++x){
	int i_next = i+direction[x][0];
	int j_next = j+direction[x][1];
	if (i_next<0 \|\| i_next>=N \|\| j_next<0 \|\| j_next>=N) continue;
	if (board[i_next][j_next] == c)
	DFS(i_next, j_next, c, win);
	}
	}
	int main()
	{
	//reopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; ++i)
	scanf("%s",board[i]);
	int win = 0; // win=1:Black win=2:White
	for (int i=0; i<N; ++i)
	if (board[i][0] == 'w')
	DFS(i, 0, 'w', win);
	for (int j=0; j<N; ++j)
	if (board[0][j] == 'b')
	DFS(0, j, 'b', win);
	if (win == 1) printf("%d B\n",Case++);
	else printf("%d W\n",Case++);
	}
	return 0;
	}

view raw UVa 260 Il Gioco dell'X.cpp hosted with ❤ by GitHub

UVa 113 Power of Cryptography

想法：
　　在題目條件下，k^n與(k+1)^n的差異double的精度可以分辨的出來，因此直接對p開根號在四捨五入即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	double n,p;
	while (scanf("%lf %lf", &n, &p) != EOF)
	printf("%.0f\n",pow(p,1.0/n));
	return 0;
	}

view raw [UVa] 113 Power of Cryptography.cpp hosted with ❤ by GitHub

UVa 11538 Chess Queen

題意：
　　兩個Chess Queen在同一欄，或同一行，或同一對角線上表示為attacking position，給定a*b棋盤，問為attacking position的情況有幾種?

想法：
　　分成位在同一欄(直)，同一行(橫)，和同一對角線三種情況分開算，假設a為寬(橫的)，b為長(直的)，a必須<=b：

兩個棋子位在同一直線共有 a*C(b,2)*2!
位在同一橫線共有 b*C(a,2)*2!
位在對角線上可以自己畫圖觀察得到，對角線最長為a，且最長的共有(b-a+1)條，其他比a還短的對角線(長度2~a-1)都各有2條，記得對角線有左斜和右斜兩個方向。
....
.... 4x5的棋盤對角線最長為4，共2條
....
....
....
因此可得 2(左斜右斜)*[(b-a+1)*C(a,2) + 2*(C(2,2)+C(3,2)+C(4,2)+...+C(a-1,2))]
= 2*[(b-a+1)*C(a,2) + 2*C(a,3)]
把以上三式加起來即是答案

	#include <cstdio>
	#include <iostream>
	using namespace std;
	int main()
	{
	long long a,b;
	while (scanf("%lld%lld",&a,&b)){
	if (!a && !b) break;
	if (a > b) swap(a,b); // a:寬 b:長
	long long ans = ab(a-1) + ab(b-1); //寬 + 長
	ans += 4* (2(a(a-1)(a-2)/6) + (b-a+1)a*(a-1)/2); // 對角線
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [UVa] 11538 Chess Queen..cpp hosted with ❤ by GitHub

UVa 10763 Foreign Exchange

想法：
　　先對出發地排序一次，再對目的地排序一次，兩兩比較是否一樣即可。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N;
	int origin[500001], target[500001];
	int main()
	{
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; i++)
	scanf("%d %d",&origin[i],&target[i]);
	if (N % 2) {
	printf("NO\n");
	continue;
	}
	sort(origin, origin+N, cmp);
	sort(target, target+N, cmp);

	bool yes = 1;
	for (int i=0; i<N; i++)
	if (origin[i] != target[i])
	yes = 0;
	printf("%s\n", yes ? "YES" : "NO");
	}
	return 0;
	}

view raw [UVa] 10763 Foreign Exchange.cpp hosted with ❤ by GitHub

UVa 10222 Decode the Mad man

想法：
　　先建立一個鍵盤keyboard，然後輸入一個字元c之後就找在keyboard裡的index，並輸出keyboard[i-2]。

	#include <cstdio>
	#include <cctype>
	using namespace std;
	const char keyboard[] = "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
	int main()
	{
	char c;
	while (scanf("%c",&c) != EOF){
	c = tolower(c); //換成小寫字母
	if (isspace(c)) printf("%c",c); //如果為' '或'\n'直接輸出
	else{
	for (int i=0; keyboard[i]; ++i)
	if (c == keyboard[i]){
	printf("%c",keyboard[i-2]);
	break;
	}
	}
	}
	return 0;
	}

view raw [UVa] 10222 Decode the Mad man.cpp hosted with ❤ by GitHub

UVa 579 ClockHands

想法：
　　題目很長但只是時針和分針夾角幾度，先將時針指的地方換成分鐘表示，然後時針分針相減後換成角度表示即可。

	#include <cstdio>
	using namespace std;
	double Abs(double a) { return a<0 ? -a : a; }
	int main()
	{
	int H,M;
	while (scanf("%d:%d",&H,&M) != EOF){
	if (!H && !M) break;
	double H_minute = (double(H) + double(M)/60) * 5; // 將時針換成分鐘表示
	double M_minute = double(M);
	double diff = Abs(H_minute - M_minute);
	while (diff >= 60) diff -= 60;
	if (diff > 30) diff = 60 - diff;
	printf("%.3f\n", diff * 6); // 一分鐘6度
	}
	return 0;
	}

view raw [UVa] 579 ClockHands.cpp hosted with ❤ by GitHub

UVa 10905 Children's Game

想法：
　　對每個數字做排序，排序用STL_sort，cmp函數裡面就比較a和b兩個數字是(ab)比較大還是(ba)比較大決定排序方式，最後依序輸出即可。

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <string>
	using namespace std;
	bool cmp(string a, string b)
	{
	return (a+b) > (b+a);
	}
	int main()
	{
	ios::sync_with_stdio(false);
	int n;
	while (cin >> n){
	if (!n) break;
	vector<string> num;
	string temp;
	for (int i=0; i<n; ++i){
	cin >> temp;
	num.push_back(temp);
	}
	sort(num.begin(),num.end(),cmp);
	for (int i=0; i<n; ++i)
	cout << num[i];
	cout << endl;
	}
	return 0;
	}

view raw [UVa] 10905 Children's Game.cpp hosted with ❤ by GitHub

UVa 12079 Pie

題意：
　　有N塊半徑Ri的pie要分給F+1(包含作者)個人，要把N塊pie平分成F+1片，每片大小需一樣，而且須完整，表示不能從兩塊pie切下來合併成一片，問一片最大的面積為多少。

想法：
　　使用binary search搜出答案。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	const double pi = 2 * asin(1);
	int Case,N, F;
	int R[10001];
	scanf("%d",&Case);
	while (Case--){
	scanf("%d%d", &N, &F);
	F++;
	int UP = 0; // BS上界
	for (int i=0; i<N; i++){
	scanf("%d",&R[i]);
	R[i] *= R[i];
	if (R[i] > UP) UP = R[i];
	}
	double left = 0, right = UP;
	while (right-left > 0.00000001){
	double mid = (left+right)/2;
	int piece = 0;
	for (int i=0; i<N; i++)
	piece += R[i]/mid;
	if (piece >= F) left = mid; //片數大於人數因此往上逼近
	else right = mid;
	}
	printf("%.3f\n",pi * left);
	}
	return 0;
	}

view raw [UVa] 12079 Pie.cpp hosted with ❤ by GitHub

2014年2月16日星期日

UVa 352 The Seasonal War

題意：
　　要確認畫面中有幾隻Eagles，每個pixel如果是'1'代表為一隻Eagles，但上下左右(包含斜角共8個方向)相連的'1'只能算是同一隻。

想法：
　　使用DFS找'1'有幾個區域。

	#include <cstdio>
	using namespace std;

	char image[30][30];

	void DFS(int &n, int i, int j)
	{
	image[i][j] = '0';
	if (i-1 >= 0 && image[i-1][j] == '1') DFS(n, i-1, j);
	if (i+1 < n && image[i+1][j] == '1') DFS(n, i+1, j);
	if (j-1 >= 0 && image[i][j-1] == '1') DFS(n, i, j-1);
	if (j+1 < n && image[i][j+1] == '1') DFS(n, i, j+1);
	if (i-1 >= 0 && j-1 >= 0 && image[i-1][j-1] == '1') DFS(n, i-1, j-1);
	if (i-1 >= 0 && j+1 < n && image[i-1][j+1] == '1') DFS(n, i-1, j+1);
	if (i+1 < n && j-1 >= 0 && image[i+1][j-1] == '1') DFS(n, i+1, j-1);
	if (i+1 < n && j+1 < n && image[i+1][j+1] == '1') DFS(n, i+1, j+1);
	}

	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int n,Case = 1;
	while (scanf("%d", &n) != EOF){
	getchar();
	for (int i = 0; i < n; ++i)
	gets(image[i]);
	int num = 0;
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (image[i][j] == '1'){
	DFS(n, i, j);
	++num;
	}
	printf("Image number %d contains %d war eagles.\n", Case++, num);
	}
	return 0;
	}

view raw [UVa] 352 The Seasonal War.cpp hosted with ❤ by GitHub

UVa 532 Dungeon Master

想法：
　　走迷宮使用BFS演算法，使用BFS時要注意把該位置排入queue時就要同時把該位置關閉，避免該位置被排入queue裡面很多次，導致TLE。

	#include <cstdio>
	#include <queue>
	using namespace std;

	char dungeon[32][32][32];
	int Distance[32][32][32];
	int L, R, C;
	const int direction[6][3] = {{-1,0,0},{1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}};
	struct point_type{
	int x;
	int y;
	int z;
	};
	int BFS(int i, int j, int k)
	{
	Distance[i][j][k] = 0;
	queue<point_type> q;
	q.push(point_type{i,j,k});
	dungeon[i][j][k] = '#';

	point_type cur, nxt;
	while (!q.empty()){
	cur = q.front();
	q.pop();

	for (int i = 0; i < 6; ++i){
	nxt.x = cur.x + direction[i][0];
	nxt.y = cur.y + direction[i][1];
	nxt.z = cur.z + direction[i][2];

	if (nxt.x<0 \|\| nxt.x >= L \|\| nxt.y<0 \|\| nxt.y >= R \|\| nxt.z<0 \|\| nxt.z>=C) continue;

	if (dungeon[nxt.x][nxt.y][nxt.z] != '#'){
	Distance[nxt.x][nxt.y][nxt.z] = Distance[cur.x][cur.y][cur.z] + 1;
	if (dungeon[nxt.x][nxt.y][nxt.z] == 'E')
	return Distance[nxt.x][nxt.y][nxt.z];
	dungeon[nxt.x][nxt.y][nxt.z] = '#';
	q.push(nxt);
	}
	}
	}
	return -1;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d%d%d", &L, &R, &C)){
	if (!L && !R && !C) break;
	int start_i, start_j, start_k;

	for (int i = 0; i < L; ++i){
	for (int j = 0; j < R; ++j){
	scanf("%s",dungeon[i][j]);
	for (int k = 0; k < C; ++k)
	if (dungeon[i][j][k] == 'S'){
	start_i = i;
	start_j = j;
	start_k = k;
	}
	}
	}
	int minute = BFS(start_i, start_j, start_k);

	if (minute != -1) printf("Escaped in %d minute(s).\n", minute);
	else printf("Trapped!\n");
	}
	return 0;
	}

view raw [UVa] 532 Dungeon Master.cpp hosted with ❤ by GitHub

2014年2月13日星期四

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跑完後，回到第二層，一樣跳出第二層的字，找下一個字不一樣的字元，然後繼續進入第三層。....剩下以此類推。

	#include <iostream>
	//#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;

	string str;
	int n;

	void choose_ch (vector<char> &ans,int start)
	{
	if (ans.size() == n) {
	for (char &c : ans)
	cout << c;
	cout << endl;
	return;
	}
	for (int i = start; i < str.size(); ){
	char c = str[i];
	ans.push_back(c);
	choose_ch (ans, i+1);
	ans.pop_back();
	while (str[i] == c) i++;
	}
	}
	int main()
	{
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);
	while (cin >> str >> n){
	sort(str.begin(), str.end());
	vector<char> ans;
	choose_ch(ans, 0);
	}
	return 0;
	}

view raw [UVa] 10776 Determine The Combination.cpp hosted with ❤ by GitHub

UVa 12337 Bob's Beautiful Balls

題目連結
想法：
　　枚舉各種方式，每次都依照題意依順時針方向填入，再檢查是否符合每個colum都是同種顏色，把長+寬最小的値儲存起來，最後輸出。

	#include <iostream>
	#include <string>
	//#include <cstdio>
	using namespace std;

	void Fill(int w, int h, string &str, char grid[][51])
	{
	int i = 0, j = 0;
	int move_i = 0, move_j = 1;
	int L = -1, U = -1, R = w, D = h;
	for (int n = 0; n < str.size(); n++){
	grid[i][j] = str[n];
	if (j + move_j == R) {
	move_i = 1;
	move_j = 0;
	U++;
	}
	else if (i + move_i == D){
	move_i = 0;
	move_j = -1;
	R--;
	}
	else if (j + move_j == L) {
	move_i = -1;
	move_j = 0;
	D--;
	}
	else if (i + move_i == U) {
	move_i = 0;
	move_j = 1;
	L++;
	}
	i += move_i;
	j += move_j;
	}
	}
	bool analysis (int w, int h, char grid[][51])
	{
	bool ok = 1;
	for (int i = 0; i < w && ok; i++){
	char c = grid[0][i];
	for (int j = 1; j < h; j++){
	if (grid[j][i] != c)
	ok = 0;
	}
	}
	return ok;
	}
	int main()
	{
	ios::sync_with_stdio(false);
	// freopen("input.txt","rt",stdin);
	int T, Case = 1;
	string str;
	cin >> T;
	while (T--){
	cin >> str;
	int ans = 1000001;
	char grid[51][51];
	for (int i = 2; i < str.size(); i++){
	if (str.size() % i != 0) continue;

	int w = i, h = str.size()/i;

	Fill(w, h, str, grid);

	if (analysis(w, h, grid)){
	if (w+h < ans)
	ans = w+h;
	}
	}
	cout << "Case " << Case++ << ": ";
	if (ans == 1000001) cout << -1 <<endl;
	else cout << ans <<endl;
	}
	return 0;
	}

view raw [UVa] 12337 Bob's Beautiful Balls.cpp hosted with ❤ by GitHub

UVa 12667 Last Blood

想法：

輸入
如果WA->回到1.
如果已經AC->回到1.
更新problem[]資料

	#include <iostream>
	#include <string>
	//#include <cstdio>
	using namespace std;

	struct team_type{
	bool problem_AC[13] = {0};
	}team[101];

	struct problem_type{
	int time;
	int team_ID = 0;
	}problem[15];

	int main()
	{
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);

	int n, t, m;
	cin >> n >> t >> m;

	int time, ID;
	string problem_name, state;

	for (int i = 0; i < m; i++){
	cin >> time >> ID >> problem_name >> state;
	if (state != "Yes") continue;

	int index = problem_name[0]-'A';
	if (team[ID].problem_AC[index] == false){
	team[ID].problem_AC[index] = true;
	problem[index].time = time;
	problem[index].team_ID = ID;
	}
	}
	for (int i = 0; i < n; i++){
	if (problem[i].team_ID != 0)
	cout << char(i+'A') << ' ' << problem[i].time << ' '
	<< problem[i].team_ID << endl;
	else
	cout << char(i+'A') << " - -" << endl;
	}
	return 0;
	}

view raw [UVa] 12667 Last Blood.cpp hosted with ❤ by GitHub

2014年2月12日星期三

UVa 657 The die is cast

題意：
　　定義上下左右如果有一樣的符號，這些符號為connected。
　　分辨骰子某一面的點數，以'*'圍起來的面積代表那是骰子的某一面，在那裡面要計算有幾個點數，而且如果有多個'X'是connected，只能算作一個點數，例如sample input裡面左上為2，右上為1(因為'X'是connected)，左下為2，右下為4。

想法：
　　當碰到'*'的時候，代表有一塊區域，進入DFS_pixel走遍該區域，每走到一個點就將'*'變成'.'避免重複走過，如果碰到'X'，一樣代表有一塊X區域，計數器+1，並進入DFS_X走遍該區域，並將走到的點從'X'轉為'*'。

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	char pic[51][51];
	int w, h;
	void DFS_X(int, int);
	void DFS_pixel (int i, int j, int &dots)
	{
	if (pic[i][j] == 'X') {
	dots++;
	DFS_X(i, j);
	}
	pic[i][j] = '.';
	if (i+1 < h && pic[i+1][j] != '.') DFS_pixel(i+1, j, dots);
	if (i-1 >=0 && pic[i-1][j] != '.') DFS_pixel(i-1, j, dots);
	if (j+1 < w && pic[i][j+1] != '.') DFS_pixel(i, j+1, dots);
	if (j-1 >=0 && pic[i][j-1] != '.') DFS_pixel(i, j-1, dots);
	}
	void DFS_X (int i, int j)
	{
	pic[i][j] = '*';
	if (i+1 < h && pic[i+1][j] == 'X') DFS_X(i+1, j);
	if (i-1 >=0 && pic[i-1][j] == 'X') DFS_X(i-1, j);
	if (j+1 < w && pic[i][j+1] == 'X') DFS_X(i, j+1);
	if (j-1 >=0 && pic[i][j-1] == 'X') DFS_X(i, j-1);
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d", &w, &h)){
	if (!w && !h) break;

	getchar();
	for (int i = 0; i < h; i++)
	gets(pic[i]);

	int ans[100] = {0}, nOfans = 0;

	for (int i = 0; i < h; i++)
	for (int j = 0; j < w; j++)
	if (pic[i][j] == '*'){
	DFS_pixel(i, j, ans[nOfans]);
	nOfans++;
	}

	sort(ans, ans + nOfans);

	printf("Throw %d\n", Case++);
	for (int i = 0; i < nOfans; i++){
	if (i) printf(" ");
	printf("%d", ans[i]);
	}
	printf("\n\n");
	}
	return 0;
	}

view raw [UVa] 657 The die is cast.cpp hosted with ❤ by GitHub

2014年2月10日星期一

UVa 375 Inscribed Circles and Isosceles Triangles

題意：
　　求內切圓的圓周長總合，由於內切圓有無限多個，只要求到半徑0.000001為止。

想法：
　　先求斜邊T，在透過三角型面積 T*R*2 + B*R = B*H 算得內切圓半徑R。一開始我Pi値直接使用3.14159265359，想說已經夠了，沒想到還不夠精確@_@，因此pi要使用2*arcsin(1)。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	double B, H;
	const double pi = 2 * asin(1);
	int Case;
	scanf("%d", &Case);
	while (Case--){
	scanf("%lf %lf", &B, &H);
	double C = 0;
	while (1){
	double T = hypot(B/2, H);
	double R = (BH)/(2T+B); // 2TR+BR = BH
	if (R < 0.000001) break;
	C += (2 * pi * R);

	double H_tmp = H - 2*R;
	B = B * (H_tmp / H);
	H = H_tmp;
	}
	printf("%13.6f\n", C);
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 375 Inscribed Circles and Isosceles Triangles.cpp hosted with ❤ by GitHub

UVa 10014 Simple calculations

題目連結
想法：
a[i] = (a[i-1]+a[i+1])/2-c[i]，代入i値，左右兩式從1加到n，消除多餘項目後可得到：

a[1]+a[n] = a[0]+a[n+1] - 2*(c[1]+...+c[n])

再從這個等式代入n値，左右兩式從1加到n，可得到

(n+1)*a[1] = n*a[0] + a[n+1] - 2*[n*c[1] + (n-1)*c[2] + ... + 1*c[n]]

此時只剩下a[1]為未知數。

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	double a0,an1,c[3010];
	int Case, N;

	double sum_c()
	{
	double sum = 0;
	for (int i = 1, j = N; i <= N; i++, j--)
	sum += (c[i] * j);
	return sum;
	}
	int main()
	{
	scanf("%d", &Case);
	while (Case--){
	scanf("%d", &N);
	scanf("%lf %lf", &a0, &an1);
	for (int i = 1; i <= N; i++)
	scanf("%lf",&c[i]);
	printf("%.2f\n", (N * a0 + an1 - 2 * sum_c()) / (N+1));
	if (Case) printf("\n");
	}
	return 0;
	}

view raw UVa 10014 Simple calculations.cpp hosted with ❤ by GitHub

2014年2月9日星期日

UVa 107 The Cat in the Hat

題目連結
題意：
　　一隻高度H的貓可以呼叫N個小貓幫手(N是我們要算的)，其每個小貓高度為 H*(1/(N+1))，每隻小貓可以在呼叫它的幫手N隻，身高為H*(1/(N+1))^2，一直下去，直到呼叫的小貓高度為1後，就不能再呼叫幫手了，因此這些高度為1的最矮的貓(worker cats)要把工作作完。
　　
　　現在題目給定兩個數：

第一個數為最高的貓(一開始只有一隻最高的貓)的高度H
第二個數為高度為1的貓(worker cats)的數量W，
求出沒有工作的貓的數量(全部-W)以及這些貓的身高總合。

想法：
　　首先最高的貓呼叫幫手後，產生N隻，高度為H*(1/(N+1))，我們假設呼叫k次直到身高為1後停止，可得出兩個等式：

H * (1/(N+1))^k = 1
N^k = W

因此解出N以及k後即可知道每次呼叫多少貓以及身高變為多少，將等式移項取log：

k * log(N+1) = log(H)
k * log(N) = log(W)

我們將第一式除以第二式消除k，然後使用binary search找出N値，接下來就能求出答案了。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int H,W;
	while (scanf("%d%d",&H,&W) != EOF){
	if (!H && !W) break;
	// klog(N+1) = logH
	// klogN = logW
	// 第一式除以第二式
	double C = log(H) / log(W);

	int L = 1, R = 2147483645, mid = (L + R)/2;
	while (L != R){
	if (log(mid+1) / log(mid) - C > 0.000000000001) L = mid+1;
	else if (log(mid+1) / log(mid) - C < -0.000000000001) R = mid;
	else break;
	mid = (L + R) / 2;
	}
	int N = mid;
	int k = round (log(H) / log(N+1));
	// 不要用logW/logN避免N=1的情況，使用round四捨五入

	// N和k已經有了，剩下只是統計數量和高度
	llt notWorking = 0;
	llt totalHeight = 0;
	W = 1;
	for (int i = 0; i < k; i++){
	notWorking += W;
	totalHeight += (H * W);
	W *= N;
	H /= (N+1);
	}
	printf("%lld %lld\n",notWorking, totalHeight+(H * W));
	}
	return 0;
	}

view raw [UVa] 107 The Cat in the Hat.cpp hosted with ❤ by GitHub

UVa 10025 The ? 1 ? 2 ?....? n = k problem

想法：
　　可以先將k取絕對值，只考慮正數k，然後假設?都是+，也就是sum = +1+2+3+....+n，然後當sum > k時，將某些'+'變成'-'湊成k，可以發現把'+'變成'-'時，sum都是減掉偶數，例如Example，sum = +1+2+..+5 = 15，要湊成12，這時候把任一個數變號都是減掉偶數，因此奇數(15)減掉偶數不可能變成偶數(12)，所以要把sum往上加，直到sum為偶數為止(因為偶數-偶數=偶數)。
　　總結：sum = 1+2+3+..+n，如果k為偶數，sum為>=k的最小偶數(偶=偶-偶)；如果k為奇數，sum為>=k的最小奇數(奇=奇-偶)。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int Case, k;
	scanf("%d",&Case);
	while (Case--){
	scanf("%d",&k);
	k = abs(k);

	int n = 0;
	int sum = 0;
	while (sum < k) sum += (++n);

	if (k % 2)
	while (sum % 2 != 1) sum += (++n);
	else
	while (sum % 2 != 0) sum += (++n);

	if (k == 0) printf("3\n");
	else printf("%d\n",n);

	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10025 The ?1?2?...?n=k problem.cpp hosted with ❤ by GitHub

2014年2月8日星期六

UVa 550 Mutiplying by Rotation

題意：
　　給定3個數(假設B,A,S)，B表示B進位，A表示被乘數的最低位數字，S表示乘數，也就是現在是xxxxxA * S，問符合 xxxxxA * S = Axxxxx則Axxxxx是幾位數?

想法：
　　可以解出xxxxx是多少，以題目example(179487)為例，B=10, A=7, S=4，可以從等式
abcde7 * 4 =
7abcde
發現，7*4=28，所以e=8，進位2，然後知道e以後，8*4+2=34，d=4，進位3，4*4+3=19，c=9，進位1，依此類推...。因此我們可以將每個位數算出來，迴圈終止條件為該位數==A且進位為0。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int B, A, S;
	while (scanf("%d%d%d", &B, &A, &S) != EOF){
	int carry = 0, len = 0, x = A;
	while (1){
	int tmp = x * S + carry;
	carry = tmp / B;
	x = tmp % B;
	len++;
	if (carry == 0 && x == A) break;
	}
	printf("%d\n", len);
	}
	return 0;
	}

view raw [UVa] 550 Mutiplying by Rotation.cpp hosted with ❤ by GitHub

UVa 10392 Factoring Large Number

題意：質因數分解

想法：
　　因為題目說1000000以上的質因數最多只有1個，因此我們質數表只要建到1000000即可，建表時可以跳過2和3的倍數比較快速。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int prime[80000];
	int nOfprime = 2;
	prime[0] = 2;
	prime[1] = 3;
	for (int i = 5, gap = 2; i <= 1000000; i += gap, gap = 6-gap){
	int sqrt_i = sqrt(i);
	bool isPrime = 1;
	for (int j = 1; prime[j] < sqrt_i; j++){
	if (i % prime[j] == 0){
	isPrime = 0;
	break;
	}
	}
	if (isPrime)
	prime[nOfprime++] = i;
	}

	long long int N;
	while (scanf("%lld",&N)){
	if (N < 0) break;

	for (int i = 0; i < nOfprime; i++){
	while (N % prime[i] == 0){
	printf(" %d\n",prime[i]);
	N /= prime[i];
	}
	if (N == 1) break;
	}
	if (N != 1) printf(" %lld\n",N);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10392 Factoring Large Numbers.cpp hosted with ❤ by GitHub

UVa 10061 How many zero's and how many digits

題意：
　　以B進位計算N!尾數有幾個0以及有幾個位數。

想法：

位數部分比較簡單，如果要知道n有幾位數，直接log(10,n)+1，那如果n要換成B進位的話就取log(B,n)+1，而log的計算規則，log(B,N!) = log(B,1)+log(B,2)+......+log(B,N)。
計算尾數有幾個0，對(N!)質因數分解，計算每個因數的數量，然後再看這些因數能夠湊成幾個B，例如B=20，那麼有2和5這兩個質因數能組成20，計算能夠湊成幾個，本題時間限制夠長，因此算因數的時候直接2~B枚舉即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int N,B;
	while (scanf("%d%d",&N,&B) != EOF){
	double digit = 0;
	int factor[801] = {0};

	double log10_B = log10(B);

	// N!
	for (int i = 2; i <= N; i++){
	//計算位數
	digit += (log10(i) / log10_B); // 換底公式log(B,i)

	//計算i的質因數
	for (int temp = i, j = 2; j <= B; j++){
	while (temp % j == 0){
	factor[j]++;
	temp /= j;
	}
	}
	}

	// 計算有幾個0
	int nOf0 = 0;
	while (1){
	int temp = B;
	// 將因數從2~B跑過看能不能使temp==1
	for (int i = 2; i <= B; i++){
	while (factor[i] && temp % i == 0){
	factor[i]--;
	temp /= i;
	}
	}
	if (temp == 1) nOf0++;
	else break;
	}

	printf("%d %d\n",nOf0,(int)digit+1);
	}
	return 0;
	}

view raw [UVa] 10061 How many zero's and how many digits.cpp hosted with ❤ by GitHub

UVa 408 Uniform Generator

想法：
　　本題要確定Step與Mod的最大公因數是否為1，如果不是互質，那麼一定會存在空隙，比如(10,12)，其產生為10,8,6,4,2,0,..，空隙為gcd(10,12)=2。

	#include <cstdio>
	using namespace std;
	int gcd(int a, int b)
	{
	while (b){
	int temp = a % b;
	a = b;
	b = temp;
	}
	return a;
	}
	int main()
	{
	int step, mod;
	while (scanf("%d%d",&step,&mod) != EOF){
	printf("%10d%10d %s\n\n",step,mod,
	gcd(step,mod) == 1 ? "Good Choice":"Bad Choice");
	}
	return 0;
	}

view raw [UVa] 408 Uniform Generator.cpp hosted with ❤ by GitHub

UVa 10110 Light, more light

本題連結
題意：
　　有個人管理一條走廊的燈泡，當走廊有'n'個燈泡，編號1~n，預設是關閉的，他會來回走n趟，第i趟他把編號能被i整除的燈泡開關切換，本題問編號n的燈泡最後是亮還是暗。

想法：
　　n只有在其因數的時候被切換，因此如果因數個數為偶數，那麼最後是暗的，反之如果為基數則為亮的，而只有能被開平方根的時候因數個數才會為奇數。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef unsigned int uint;
	int main()
	{
	uint n;
	while (scanf("%u",&n)){
	if (!n) break;
	uint a = sqrt(n);
	if (a * a == n) printf("yes\n");
	else printf("no\n");
	}
	return 0;
	}

view raw [UVa] 10110 Light, more light.cpp hosted with ❤ by GitHub

2014年2月7日星期五

UVa 668 Parliament

本題連結
題意：
　　議會中有N位代表，依照規定須分成好幾個group，每個group的人數不能一樣，然後每個group每天要派出1個人出席會議，每次的會議人員組成必須與以前不同，否則會議無法開始(意即每次組合不能與以前重複)，求如何分配group人數使得能開會議的天數最久。
　　本題簡而言之，即為給定整數N，把N分成a,b,c....不同數字，求乘積最大的方式。

想法：
　　把數字分配的越小(試想如果每個group人數能一樣，那每組分成2或3乘積為最大)和越鄰近越好(如2,3,4,5..)。因此就從2開始，2,3,4,5,.....k，直到剩下的數left(=N-(1+2+3+...+k)) < (k+1)為止，那麼將left從k,k-1....往下分配，把每個數+1，如果分配到2如果left還有剩，再從k+1開始分配，使得每個數盡量靠近。

	#include <cstdio>
	using namespace std;
	int main()
	{
	int M,N;
	scanf("%d", &M);
	while (M--) {
	scanf("%d", &N);
	int ans[1001],nOfans = 0, sum = 0;
	for (int i = 2; sum + i <= N; i++){
	sum += i;
	ans[nOfans++] = i;
	}
	int left = N - sum;
	for (int i = nOfans-1; left > 0; i--, left--){
	if (i < 0) i = nOfans-1;
	ans[i]++;
	}

	printf("%d", ans[0]);
	for (int i = 1; i < nOfans; i++)
	printf(" %d", ans[i]);
	printf("\n");
	if (M) printf("\n");
	}
	return 0;
	}

view raw [UVa] 668 Parliament.cpp hosted with ❤ by GitHub

UVa 424 Integer Inquiry

本題連結
想法：
　　先不考慮進位與不夠減的情況，把每個位數都加起來，最後再處理進位或借位。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	int main()
	{
	char num[101][1001];
	int ans[1001]={0};

	for (int i = 0; scanf("%s",num[i]); i++){
	if (num[i][0] == '0') break;

	if (num[i][0] != '-'){ // 正數輸入
	for (int j = strlen(num[i])-1, k = 0; j >= 0; j--, k++)
	ans[k] += (num[i][j] - '0');
	}
	else { // 負數輸入
	for (int j = strlen(num[i])-1, k = 0; j >= 1; j--, k++)
	ans[k] -= (num[i][j] - '0');
	}
	}
	bool negative = 0;
	int i = 1000;
	while (ans[i] == 0) i--; // 找答案的最高位數
	if (ans[i] < 0) negative = 1;

	if (negative) // 如果答案為負數，先將每個數字變號，確保最高位數為正
	for (int j = 0; j <= i; j++) ans[j] *= (-1);

	for (int j = 0; j <= i; j++){
	int k = j;
	while (ans[k] > 9){ // 一直往高位數進位，直到不能進位為止
	ans[k+1]++;
	ans[k] -= 10;
	if (ans[k] <= 9) k++; // 確保該位數<=9
	}
	while (ans[k] < 0){ // 一直向高位數拿10，來使該位數>=0
	ans[k+1]--;
	ans[k] += 10;
	if (ans[k] >= 0) k++; // 確保該位數>=0
	}
	}
	if (negative) printf("-");
	for (i = 1000; ans[i] == 0; i--); // 因為進位的關係，重新找最高位數
	for (; i >= 0; i--)
	printf("%d", ans[i]);
	printf("\n");

	return 0;
	}

view raw [UVa] 424 Integer Inquiry.cpp hosted with ❤ by GitHub

UVa 10494 If We Were a Child Again

本題連結
想法：
　　與直式除法一樣，一邊作商數，一邊作餘數，直到被除數的個位數為止。

	#include <cstdio>
	using namespace std;

	char num[10001];
	long long int b,R;
	char oper[2];

	int main()
	{
	//freopen ("input.txt","rt",stdin);
	while (scanf("%s%s%lld",num,oper,&b) != EOF){
	int Q[10001],pos = 0;
	int i;
	for (i = 0, R = 0; num[i]; i++){
	R = R * 10 + (num[i] - '0');
	Q[pos++] = R / b; // ans前面幾個數字可能為0，等等輸出要從非0開始
	R = R % b;
	}
	if (oper[0] == '/'){
	for (i = 0; i < pos && Q[i] == 0; i++)
	;
	if (i == pos) printf("0"); // 如果被除數比除數小的情況
	else
	for (; i < pos; i++) printf ("%d",Q[i]);
	printf("\n");
	}
	else
	printf("%lld\n",R);
	}
	return 0;
	}

view raw [UVa] 10494 If We Were a Child Again.cpp hosted with ❤ by GitHub

2014年2月5日星期三

UVa 10878 Decode the tape

本題連結
想法：
　　觀察a,b,c,d..字母後發現：

a=|oo__.__o|
b=|oo__._o_|
c=|oo__._oo|
d=|oo__.o__|
e=|oo__.o_o|

　　可以知道它是以二進位的方式表示，在把'a'的値(2^0+2^5+2^6=97)加起來後與ASCII表比較，剛好就是表上'a'的値，因此這題把每個字元的値加起來輸出即可(換行符號它也已經在input裡囉，不用自己換行)。

	#include <cstdio>
	using namespace std;
	int main()
	{
	freopen ("input.txt","rt",stdin);
	char line[50];
	while (gets(line)){
	if (line[0] != '\|') continue;
	char c = 0;
	for (int i=0; line[i]; i++){
	if (line[i]==' ' \|\| line[i]=='o')
	c <<= 1;
	if (line[i]=='o')
	c++;
	}
	printf("%c",c);
	}
	return 0;
	}

view raw [UVa] 10878 Decode the tape.cpp hosted with ❤ by GitHub

2014年2月4日星期二

UVa 409 Excuses, Excuses!

題意：
　　給定K個關鍵字，和E個句字，分析每個句字含有多少個關鍵字，將關鍵字最多的句字輸出，如果有多個數量相同的句字，則全部都要輸出。

想法：
　　將句子不是英文字母的字去掉，一個單字一個單字比對。本題輸出的時候包含最後一個Case都要有個空行。

	#include <cstdio>
	using namespace std;

	int K,E;
	char keyword[20][100],line[20][1000];

	int analysis (int x)
	{
	int num = 0, p = 0;
	char word[100];
	while (1){
	while (line[x][p]<'A' \|\| line[x][p]>'Z' && line[x][p]<'a' \|\| line[x][p]>'z') {
	if (line[x][p] == '\0') break;
	p++;
	}
	if (line[x][p] == '\0') break;
	int i;
	for (i=0; line[x][p]>='A'&&line[x][p]<='Z'\|\|line[x][p]>='a'&&line[x][p]<='z'; i++)
	word[i] = line[x][p++];
	word[i] = '\0';

	for (int i=0; i<K; i++){
	int j=0,k=0;
	for (; word[j] && keyword[i][k]; j++){
	if (word[j]==keyword[i][k] \|\| word[j]==keyword[i][k]-32) k++;
	}
	if (keyword[i][k]=='\0' && word[j]=='\0') num++;
	}
	}
	return num;
	}

	int main()
	{
	freopen ("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d%d",&K,&E)!=EOF)
	{
	for (int i=0; i<K; i++) scanf("%s",keyword[i]);
	getchar();
	int num[20],Max = 0;
	for (int i=0; i<E; i++){
	gets(line[i]);
	num[i] = analysis(i);
	if (num[i] > Max) Max = num[i];
	}
	printf("Excuse Set #%d\n",Case++);
	for (int i=0; i<E; i++)
	if (num[i] == Max)
	puts(line[i]);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 409 Excuses, Excuses!.cpp hosted with ❤ by GitHub

UVa 537 Artificial Intelligence?

題意：
　　找出關鍵字U=???V或P=???W或I=???A的其中兩個，並從等式P=I*U算出另一個值。

想法：
　　函數分析時依序從整數，小數，以及指數的順序，在回傳兩個值後計算另一個即可。

	#include <cstdio>
	using namespace std;

	double num (char line[],int i)
	{
	double a = 0;
	while (line[i]>='0' && line[i]<='9'){
	a *= 10;
	a += (line[i]-'0');
	i++;
	}
	if (line[i] == '.'){
	i++;
	int j = 10;
	while (line[i]>='0' && line[i]<='9'){
	a += ((double)(line[i]-'0')/j);
	j *= 10;
	i++;
	}
	}
	if (line[i] == 'm') a /= 1000;
	else if (line[i] == 'k') a *= 1000;
	else if (line[i] == 'M') a *= 1000000;
	return a;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int Case;
	char line[1000];
	scanf("%d",&Case);
	getchar();
	for (int k=1; k<=Case; k++){
	gets(line);
	double P=0,U=0,I=0;
	for (int i=0; line[i+1]; i++){
	if (line[i]=='U' && line[i+1]=='=') U = num (line,i+2);
	if (line[i]=='P' && line[i+1]=='=') P = num (line,i+2);
	if (line[i]=='I' && line[i+1]=='=') I = num (line,i+2);
	}

	printf ("Problem #%d\n",k);
	if (U && I) printf("P=%.2fW\n",U*I);
	else if (P && U) printf ("I=%.2fA\n",P/U);
	else printf("U=%.2fV\n",P/I);
	printf("\n"); // 這題連最後一個problem都要空行
	}
	return 0;
	}

view raw [UVa] 537 Artificial Intelligence?.cpp hosted with ❤ by GitHub

UVa 10361 Automatic Poetry

題意：
　　給定n對詩句，每對詩句的第一句為s1<s2>s3<s4>s5的形式(si表示那是個字串，可包含空格)，我們所要做的就是把第一句<>去掉，然後第二句的"..."換成"s4s3s2s5"即可。

想法：
　　讀取每個si的時候一定要以'<'或'>'作為分隔點，因為測資不一定是以空格隔開。

	#include <cstdio>
	using namespace std;

	void l1 (char line[], char s[][1000])
	{
	int i,j;
	for (i=0; line[i]!='<'; i++) printf("%c",line[i]);
	for (i++,j=0; line[i]!='>'; i++,j++) s[2][j] = line[i];
	s[2][j] = '\0';
	for (i++,j=0; line[i]!='<'; i++,j++) s[3][j] = line[i];
	s[3][j] = '\0';
	for (i++,j=0; line[i]!='>'; i++,j++) s[4][j] = line[i];
	s[4][j] = '\0';
	for (i++,j=0; line[i]; i++,j++) s[5][j] = line[i];
	s[5][j] = '\0';
	printf("%s%s%s%s\n",s[2],s[3],s[4],s[5]);
	}
	void l2 (char line[], char s[][1000])
	{
	int i,j;
	for (i=0; line[i]!='.'; i++) printf("%c",line[i]);
	printf("%s%s%s%s\n",s[4],s[3],s[2],s[5]);
	}

	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	char line[10000],s[6][1000];
	scanf("%d",&N);
	getchar();
	while (N--){
	gets(line);
	l1 (line, s);
	gets(line);
	l2 (line, s);
	}
	return 0;
	}

view raw [UVa[ 10361 Automatic Poetry.cpp hosted with ❤ by GitHub

UVa 10010 Where's Waldorf?

想法：
　　先把字都換成小寫，然後由左往右，由上往下，每個位置往八個方向找確認是否符合。

	#include <cstdio>
	using namespace std;

	char grid[51][51],word[51];
	int Case,m,n,k;

	void upper_to_lower (char a[])
	{
	for (int i=0; a[i]; i++)
	if (a[i]>='A' && a[i]<='Z')
	a[i] += 32;
	}
	bool Locate (int i, int j)
	{
	int x;
	for (x=1; i-x>=0 && word[x]==grid[i-x][j];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i+x<m && word[x]==grid[i+x][j];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; j-x>=0 && word[x]==grid[i][j-x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; j+x<n && word[x]==grid[i][j+x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i-x>=0 && j-x>=0 && word[x]==grid[i-x][j-x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i+x<m && j-x>=0 && word[x]==grid[i+x][j-x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i-x>=0 && j+x<n && word[x]==grid[i-x][j+x];) {x++; if (word[x]=='\0') return 1;}
	for (x=1; i+x<m && j+x<n && word[x]==grid[i+x][j+x];) {x++; if (word[x]=='\0') return 1;}
	return 0;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	scanf("%d",&Case);
	while (Case--){
	scanf("%d%d",&m,&n);
	for (int i=0; i<m; i++){
	scanf("%s",grid[i]);
	upper_to_lower(grid[i]);
	}

	scanf("%d",&k);
	while (k--){
	scanf("%s",word);
	upper_to_lower(word);

	int i,j,ok=0;
	for (i=0; i<m && !ok; i++)
	for (j=0; j<n && !ok; j++)
	if (grid[i][j] == word[0] && Locate (i,j)){
	printf("%d %d\n",i+1,j+1);
	ok = 1;
	}
	}
	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10010 Where's Waldorf.cpp hosted with ❤ by GitHub

2014年2月3日星期一

UVa 401 Palindromes

本題連結
想法：
　　處理鏡像的部份我是把它存成陣列，Mir[]="AAE3HHIIJLLJ...."，比對兩個字元是否為鏡像，則看Mir[i]和Mir[i+1]是否符合，另外要注意本題每個輸出之間還要空一行。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	char Mir[]="AAE3HHIIJLLJMMOOS2TTUUVVWWXXYYZ500112S3E5Z88";
	bool isMirrored (char a, char b){
	for (int i=0; Mir[i+1]; i++)
	if (Mir[i]==a && Mir[i+1]==b) return 1;
	return 0;
	}
	bool isPalindrome (char a,char b){
	return a == b;
	}
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char c[100];
	while (gets(c)){
	bool palindrome = 1,mirrored = 1;
	for (int i = 0, j = strlen(c)-1; i <= j; i++, j--){
	if (!isMirrored(c[i],c[j])) mirrored = 0;
	if (!isPalindrome(c[i],c[j])) palindrome = 0;
	}
	if (palindrome && mirrored) printf("%s -- is a mirrored palindrome.\n\n",c);
	else if (palindrome) printf("%s -- is a regular palindrome.\n\n",c);
	else if (mirrored) printf("%s -- is a mirrored string.\n\n",c);
	else printf("%s -- is not a palindrome.\n\n",c);
	}
	return 0;
	}

view raw [UVa] 401 Palindromes.cpp hosted with ❤ by GitHub

UVa 445 Marvelous Mazes

題意：
　　遇到每個數字是"加起來"，如23X，則輸出5個X，2X12*，則輸出XX***，b表示空格，!則要換行。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	char c;
	int num=0;
	while (c=getchar()){
	if (c == EOF) break;
	if (c == '\n' \|\| c == '!')
	printf("\n");
	else if (c >= '0' && c <= '9')
	num += (c - '0');
	else{
	if (c == 'b'){
	for (int i=0; i<num; i++)
	printf(" ");
	}
	else {
	for (int i=0; i<num; i++)
	printf("%c",c);
	}
	num = 0;
	}
	}
	return 0;
	}

view raw [UVa] 445 Marvelous Mazes.cpp hosted with ❤ by GitHub

UVa 490 Rotating Sentences

題意：
　　將每一行的句子轉成直的，順序由下到上。
想法：
　　將每個句字保存後，依題意順序將句子每個字輸出，如果該列句子已經結束，則輸出空格。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	char sentence[101][101];
	int N=0,length[101];
	int Max_length=0;
	while (gets(sentence[N])) {
	length[N] = strlen(sentence[N]);
	if (length[N] > Max_length) Max_length = length[N];
	N++;
	}
	for (int i=0; i<Max_length; i++){
	for (int j=N-1; j>=0; j--){
	if (i < length[j])
	printf("%c",sentence[j][i]);
	else
	printf(" ");
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 490 Rotating Senteneces.cpp hosted with ❤ by GitHub

UVa 414 Machined Surfaces

題意：
　　固定左右兩邊形狀，合併後會有多少個空格
想法：
　　計算每一列有多少個X，並找出哪一列有最多個X，值為Max，則該列空格就是(Max-該列有幾個X)

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	while (scanf("%d",&N)){
	if (!N) break;
	int nOfX[20]={0},Max = 0;
	char line[30];
	gets(line);
	for (int i=0; i<N; i++){
	gets(line);
	for (int j=0; line[j]; j++)
	if (line[j]=='X') nOfX[i]++;
	if (nOfX[i]>Max)
	Max = nOfX[i];
	}
	int ans = 0;
	for (int i=0; i<N; i++)
	ans += (Max-nOfX[i]);
	printf("%d\n",ans);
	}
	return 0;
	}

view raw [UVa] 414 Machined Surfaces.cpp hosted with ❤ by GitHub

2014年2月1日星期六

UVa 10082 WERTYU

想法：
　　用一個陣列代表鍵盤按鍵：char keyboard[]="QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./"，然後找出輸入字元的i值，再輸出keyboard[i-1]。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	char keyboard[] = "`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
	char line[1000];
	while (gets(line)){
	for (int i=0; line[i]; i++){
	if (line[i] == ' ') printf(" ");
	else{
	int j = 0;
	while (line[i] != keyboard[j+1]) j++;
	printf("%c",keyboard[j]);
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10082 WERTYU.cpp hosted with ❤ by GitHub

UVa 12537 Radiation

題意：
　　在核能廠半徑範圍內的住家可以得到protective equipments，a和c區域可以得到一組，而b區域因為在重疊範圍內，所以有2組，但在範圍外的d區域沒有equipment，但因為equipments只要1組就夠用了，因此b區域的住家可以分給d區域的住家，題目求d區域在b區域給了equipments之後還有幾戶住家沒有equipments，即為(d-b)。
　　給定一堆點座標和兩個圓心座標，每次兩個圓都有不同的半徑，題目所求為在圓外面點的數量減掉在左圓且在右圓內點的數量，為(d-b)。

想法：

找出在左圓範圍內點的數量(a+b)
找出在右圓範圍內點的數量(c+b)
所有點的總數N=a+b+c+d
所求即為N-(a+b)-(c+b) = d-b

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;

	int N,x[200001],y[200001];
	double a_dis[200001],b_dis[200001];
	int ax,ay,bx,by,Q,R1,R2;

	int BS (int R,double dis[])
	{
	int left = 0, right = N-1;
	while (left != right){
	int mid = (left+right+1)/2;
	if (dis[mid] > R) right = mid-1;
	else left = mid;
	}
	return left+1; //回傳為數量，因此是index+1
	}

	int main()
	{
	freopen ("input.txt","rt",stdin);
	int Case = 1;
	while (scanf("%d",&N)){
	if (!N) break;
	for (int i=0; i<N; i++) scanf("%d %d",&x[i],&y[i]);
	scanf("%d %d %d %d %d",&ax,&ay,&bx,&by,&Q);
	for (int i=0; i<N; i++) {
	a_dis[i] = sqrt (pow(x[i]-ax,2) + pow(y[i]-ay,2));
	b_dis[i] = sqrt (pow(x[i]-bx,2) + pow(y[i]-by,2));
	}
	sort (a_dis,a_dis+N);
	sort (b_dis,b_dis+N);

	printf("Case %d:\n",Case++);

	while (Q--){
	scanf("%d %d",&R1,&R2);
	int ans = N - BS(R1,a_dis) - BS(R2,b_dis);
	if (ans >= 0) printf("%d\n",ans);
	else printf("0\n");
	}
	}
	return 0;
	}

view raw UVa 12537 Radiation.cpp hosted with ❤ by GitHub

2014年1月29日星期三

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總數加起來即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;

	llt sum0 (llt n)
	{
	llt N = n,sum = 0;
	int left=1,mid,right=1;
	while (N >= 10){
	mid = N%10;
	N /= 10;
	if (mid) sum += (N * left);
	else sum += ((N-1)*left + n%right +1);
	left *= 10;
	right *= 10;
	}
	return sum;
	}
	int main()
	{
	llt m,n;
	while (scanf("%lld%lld",&m,&n)){
	if (m < 0) break;
	llt ans = sum0(n) - sum0(m-1);
	if (m == 0) ans++; // 函數是從1~m，如果m==0會少算
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw UVa 11038 How many 0's.cpp hosted with ❤ by GitHub

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。

	#include <cstdio>
	#include <cstring>
	using namespace std;
	char APU[1000];

	int parsing (int front, int back)
	{
	// 0:Mutant
	// 1:Simple
	// 2:Fully-Grown
	// 3:Mutagenic

	if (front==back && APU[front]=='A') return 1;

	if (APU[back]=='B' && APU[back-1]=='A'){ // 判斷是否為Fully Grown
	if (front == back-1) return 0; // 如果為"AB"，那麼是Mutant
	else if (parsing (front,back-2) != 0) return 2;
	}
	if (APU[front]=='B' && APU[back]=='A'){ // 判斷是否為Mutagenic
	if (front+1 == back) return 0; // 如果為"BA"，那麼是Mutant
	else if (parsing (front+1,back-1) != 0) return 3;
	}
	return 0; // O不符合上面3種任一種型態，回傳0
	}
	int main()
	{
	int Case;
	scanf("%d",&Case);
	while (Case--){
	scanf("%s",APU);
	int t = parsing (0,strlen(APU)-1);
	switch (t){
	case 0: printf("MUTANT\n"); break;
	case 1: printf("SIMPLE\n"); break;
	case 2: printf("FULLY-GROWN\n"); break;
	case 3: printf("MUTAGENIC\n"); break;
	}
	}
	return 0;
	}

view raw [UVa] 620 Cellular Structure.cpp hosted with ❤ by GitHub

UVa 10101 Bangla Numbers

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

	#include <cstdio>
	using namespace std;

	void bangla(long long int n)
	{
	if (n >= 10000000){
	bangla (n / 10000000);
	printf (" kuti");
	n %= 10000000;
	}
	if (n >= 100000){
	bangla (n / 100000);
	printf (" lakh");
	n %= 100000;
	}
	if (n >= 1000){
	bangla (n / 1000);
	printf (" hajar");
	n %= 1000;
	}
	if (n >= 100){
	bangla (n / 100);
	printf (" shata");
	n %= 100;
	}
	if (n)
	printf (" %d",n);
	}
	int main()
	{
	long long int n;
	int Case=1;
	while (scanf("%lld",&n)!=EOF){
	printf ("%4d.",Case++);
	if (n==0) printf(" 0");
	bangla (n);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10101 Bangla Numbers.cpp hosted with ❤ by GitHub

UVa 10696 f91

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

	#include <cstdio>
	using namespace std;
	int fn[101]={0};

	int f91 (int N){
	if (N > 100) return N-10;
	if (fn[N] != 0) return fn[N];
	fn[N] = f91(f91(N+11));
	return fn[N];
	}

	int main()
	{
	int n;
	while (scanf("%d",&n)){
	if (!n) break;
	printf("f91(%d) = %d\n",n,f91(n));
	}
	return 0;
	}

view raw [UVa] 10696 f91.cpp hosted with ❤ by GitHub

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也是同樣道理。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	unsigned long long int N[1501];
	N[1]=1;
	int p2=1,p3=1,p5=1;
	for (int n=2; n<=1500; n++){
	while (N[p2]*2 <= N[n-1]) p2++;
	while (N[p3]*3 <= N[n-1]) p3++;
	while (N[p5]*5 <= N[n-1]) p5++;
	N[n] = min (N[p2]2, min (N[p3]3, N[p5]*5));
	}
	printf("The 1500'th ugly number is %llu.\n",N[1500]);
	}

view raw [UVa] 136 Ugly Number.cpp hosted with ❤ by GitHub

2014年1月28日星期二

UVa 495 Fibonacci Freeze

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

	#include <cstdio>
	using namespace std;

	int Fib[5001][500]={0};

	int main()
	{
	Fib[1][0]=1;
	for (int i=2; i<=5000; i++){
	for (int j=0; j<500; j++){
	Fib[i][j] += Fib[i-1][j]+Fib[i-2][j];
	if (Fib[i][j]>=1000){
	Fib[i][j] -= 1000;
	Fib[i][j+1]++;
	}
	}
	}
	int n;
	while (scanf("%d",&n)!=EOF){
	printf("The Fibonacci number for %d is ",n);
	if (!n) printf("0\n");
	else {
	int i=500;
	while (Fib[n][--i]==0);
	printf("%d",Fib[n][i--]);
	for (; i>=0; i--) printf("%.3d",Fib[n][i]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [UVa] 495 Fibonacci Freeze.cpp hosted with ❤ by GitHub

UVa 10446 The Marriage Interview

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

	#include <cstdio>
	using namespace std;
	typedef unsigned long long int ullt;

	ullt C[61][61]={0};
	ullt trib (int n, int back)
	{
	if (n <= 1) return 1;
	if (C[n][back] != 0) return C[n][back];

	C[n][back] = 1;
	for (int i=1; i<=back; i++)
	C[n][back] += trib(n-i,back);
	return C[n][back];
	}
	int main()
	{
	int n, back, Case=1;
	while (scanf("%d%d",&n,&back)){
	if (n > 60) break;
	printf("Case %d: %llu\n",Case++,trib(n,back));
	}
	return 0;
	}

view raw [UVa] 10446 The Marriage Interview.cpp hosted with ❤ by GitHub

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，因此要自己寫大數加法。

	#include <cstdio>
	using namespace std;
	int fib[1001][501]={0};

	int main()
	{
	fib[0][0]=1;
	fib[1][0]=2;
	for (int i=2; i<=1000; i++){
	for (int j=0; j<500; j++){
	fib[i][j] += fib[i-2][j]+fib[i-1][j];
	if (fib[i][j]>9){
	fib[i][j] -= 10;
	fib[i][j+1]++;
	}
	}
	}
	int n;
	while (scanf("%d",&n)!=EOF) {
	int i = 500;
	while (fib[n][--i] == 0);
	for (; i>=0; i--)
	printf("%d",fib[n][i]);
	printf("\n");
	}
	return 0;
	}

view raw [UVa] 10334 Ray Through Glasses.cpp hosted with ❤ by GitHub

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。

	#include <cstdio>
	using namespace std;
	typedef long long int llt;

	llt H (int m,int n){
	m = (m+n-1);
	if (n > m/2) n = (m-n);
	int M[100],N[100],i,j;
	for (i=0; i<n; i++){
	M[i] = m - i;
	N[i] = i + 1;
	}
	for (i=0; i<n; i++)
	for (j=0; j<n; j++)
	if (N[j]!=1 && M[i]%N[j] == 0){
	M[i] = M[i]/N[j];
	N[j] = 1;
	break;
	}
	llt a=1, b=1;
	for (i=0; i<n; i++) {
	a *= M[i];
	b *= N[i];
	}
	return a/b;
	}

	int main()
	{
	int L;
	llt patterns;
	while (scanf("%d",&L))
	{
	if (!L) break;
	patterns = 1;
	for (int i=1; L-2*i >= 0; i++)
	patterns += H(i+1,L-2*i);
	printf ("%lld\n",patterns);
	}
	return 0;
	}

view raw [UVa] 900 Brick Wall Pattern.cpp hosted with ❤ by GitHub

2014年1月27日星期一

UVa 10285 Longest Run on a Snowboard

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

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int N,R,C,area[101][101];
	char name[100];

	// 定義find_longest函數為回傳該點(area[i][j])盡可能走的最遠長度
	int find_longest (int i,int j,int length) // length為目前已經走的長度
	{
	int a=0, b=0, c=0, d=0;
	if (i-1>=0 && area[i-1][j]<area[i][j]) a = find_longest (i-1,j,length+1); //往上走
	if (i+1<R && area[i+1][j]<area[i][j]) b = find_longest (i+1,j,length+1); //往下走
	if (j-1>=0 && area[i][j-1]<area[i][j]) c = find_longest (i,j-1,length+1); //往左走
	if (j+1<C && area[i][j+1]<area[i][j]) d = find_longest (i,j+1,length+1); //往右走

	if (a \|\| b \|\| c \|\| d) { //表示至少還有一個方向能走，回傳最遠的長度
	a = max(a,b); a = max(a,c); a = max(a,d);
	return a;
	}
	else return length; //四個方向都不能在往下走了，表示走到死路，回傳當前長度
	}

	int main()
	{
	// freopen ("input.txt","rt",stdin);
	scanf("%d",&N);
	while (N--)
	{
	scanf("%s%d%d",name,&R,&C);
	for (int i=0; i<R; i++)
	for (int j=0; j<C; j++)
	scanf("%d",&area[i][j]);

	int Max=0;
	for (int i=0; i<R; i++) // 一一枚舉每個點，選出最遠的長度
	for (int j=0; j<C; j++){
	int t = find_longest(i,j,1); // 一開始長度為1(自己也算)
	if (t > Max) Max = t;
	}
	printf("%s: %d\n",name,Max);
	}
	return 0;
	}

view raw [UVa] 10285 Longest Run on a Snowboard.cpp hosted with ❤ by GitHub

2014年1月26日星期日

UVa 10037 Bridge

本題連結

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

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

只有一個人：直接走過去，時間為P[0]。
兩個人：直接走過去，時間為P[1]。
三個人：P[0],P[1],P[2]，時間為P[1]+P[0]+P[2]
P[0] P[1]
P[0]
P[0] P[2]
三個人以上：如果是偶數個人(例如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。

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int Case,N,P[1001],i;
	scanf("%d",&Case);
	while (Case--)
	{
	scanf("%d",&N);
	for (i=0; i<N; i++) scanf("%d",&P[i]);
	sort (P,P+N);

	int sum=0;

	for (i=N-1; i>=3; i-=2){ //三個人以上
	int A = P[1]+P[0]+P[i]+P[1];
	int B = P[i]+P[0]+P[i-1]+P[0];
	if (A<B) sum += A;
	else sum += B;
	}
	if (i == 2) sum += (P[1]+P[0]+P[2]); //三個人
	else if (i == 1) sum += P[1]; //兩個人
	else if (i == 0) sum += P[0]; //一個人

	printf("%d\n",sum);

	for (i=N-1; i>=3; i-=2){
	int A = P[1]+P[0]+P[i]+P[1];
	int B = P[i]+P[0]+P[i-1]+P[0];
	if (A<B) printf("%d %d\n%d\n%d %d\n%d\n",P[0],P[1],P[0],P[i-1],P[i],P[1]);
	else printf("%d %d\n%d\n%d %d\n%d\n",P[0],P[i-1],P[0],P[0],P[i],P[0]);
	}
	if (i == 2) printf("%d %d\n%d\n%d %d\n",P[0],P[1],P[0],P[0],P[2]);
	else if (i == 1) printf("%d %d\n",P[0],P[1]);
	else if (i == 0) printf("%d\n",P[0]);

	if (Case) printf("\n");
	}
	return 0;
	}

view raw [UVa] 10037 Bridge.cpp hosted with ❤ by GitHub

2014年1月25日星期六

UVa 642 Word Amalgamation

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

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

	#include <cstdio>
	#include <iostream>
	#include <string>
	#include <algorithm>
	using namespace std;
	struct dictionary{
	string Word;
	int Hash;
	}dic[102];
	bool cmp (dictionary a, dictionary b)
	{
	return a.Word <= b.Word;
	}
	int main(){
	ios::sync_with_stdio(false);
	// freopen ("input.txt","rt",stdin);
	int nOfdic=0,i;
	string str;
	for (i = 0; cin >> str && str != "XXXXXX"; ++i){
	dic[i].Word = str;
	dic[i].Hash = 0;
	for (char c : dic[i].Word)
	dic[i].Hash += (3.56ccc + 2c*c + 337);
	}
	nOfdic = i;
	sort (dic, dic+nOfdic, cmp);
	while (cin >> str && str != "XXXXXX"){
	int Hash = 0;
	for (char c : str)
	Hash += (3.56ccc + 2c*c + 337);
	bool valid=0;
	for (i=0; i<nOfdic; i++){
	if (Hash == dic[i].Hash){
	valid = 1;
	cout << dic[i].Word << endl;
	}
	}
	if (!valid) cout << "NOT A VALID WORD" << endl;
	cout << "******" << endl;
	}
	}

view raw [UVa] 642-2 Word Amalgation.cpp hosted with ❤ by GitHub

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct dictionary{
	char w[10];
	int map;
	}dic[102];
	bool cmp (dictionary a,dictionary b){
	for (int i=0; ; i++)
	if (a.w[i] != b.w[i]) return a.w[i] < b.w[i];
	}
	int main(){
	freopen ("input.txt","rt",stdin);
	int nOfdic=0,i;
	for (i=0;;i++){
	gets(dic[i].w);
	if (dic[i].w[0]=='X' && dic[i].w[1]=='X' && dic[i].w[2]=='X' &&
	dic[i].w[3]=='X' && dic[i].w[4]=='X' && dic[i].w[5]=='X') break;
	dic[i].map = 0;
	for (int j=0; dic[i].w[j]; j++){
	int t = dic[i].w[j];
	dic[i].map += (3.56ttt+2t*t+337);
	}
	}
	nOfdic = i;
	sort (dic,dic+nOfdic,cmp);

	char line[10];
	while (gets(line)){
	if (line[0]=='X' && line[1]=='X' && line[2]=='X' &&
	line[3]=='X' && line[3]=='X' && line[5]=='X') break;
	int n = 0;
	for (i=0; line[i]; i++){
	int t = line[i];
	n += (3.56ttt+2t*t+337);
	}
	bool valid=0;
	for (i=0; i<nOfdic; i++){
	if (n == dic[i].map){
	valid = 1;
	printf("%s\n",dic[i].w);
	}
	}
	if (!valid) printf("NOT A VALID WORD\n");
	printf("******\n");
	}
	}

view raw [UVa] 642 Word Amalgamation.cpp hosted with ❤ by GitHub

UVa 11489 Integer Game

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

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

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

	#include <cstdio>
	using namespace std;
	int main()
	{
	int T,Case=1;
	scanf("%d",&T);
	getchar();
	while (T--){
	int N[1001],nOfN=0; //用來存非3的倍數的數字
	int nOf3x = 0; //該位數為3的倍數的個數
	int sum = 0; //非3倍數的和
	while (1){
	char c = getchar();
	if (c == '\n') break;
	else if ((c-'0')%3 == 0) nOf3x++;
	else {
	N[nOfN++] = (c-'0');
	sum += (c-'0');
	}
	}
	int who; //who為偶數代表S,奇數代表T
	if (nOf3x % 2) who = 0;
	else who = 1;

	if (sum%3 !=0) {
	int i;
	for (i=0; i<nOfN; i++)
	if ((sum-N[i])%3 == 0) break;
	if (i==nOfN) who=1;
	else who++;
	}
	printf("Case %d: ",Case++);
	if (who % 2) printf("T\n");
	else printf("S\n");

	}
	return 0;
	}

view raw [UVa] 11489 Integer Game.cpp hosted with ❤ by GitHub

UVa 10189 Minesweeper

題目連結

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

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

	#include <cstdio>
	using namespace std;

	int n,m;
	char field[105][105];

	void Fill (int x,int y)
	{
	for (int i=-1; i<=1; i++)
	for (int j=-1; j<=1; j++)
	if (field[x+i][y+j]!='*')
	field[x+i][y+j]++;
	}

	int main()
	{
	// freopen("input.txt","rt",stdin);
	int T = 1;
	while (scanf("%d %d",&n,&m))
	{
	if (!n && !m) break;
	if (T!=1) printf("\n");

	//初始化數量為0
	for(int i=1; i<=n; i++)
	for (int j=1; j<=m; j++)
	field[i][j]='0';

	//輸入，如果為'*'，則呼叫Fill將其八個方向數量+1
	for(int i=1; i<=n; i++){
	for(int j=1; j<=m; j++){
	char c;
	c = getchar();
	while (c=='\n') c = getchar();

	if (c == '*'){
	field[i][j]='*';
	Fill(i,j);
	}
	}
	}

	//輸出結果
	printf("Field #%d:\n",T++);
	for (int i=1; i<=n; i++){
	for (int j=1; j<=m; j++)
	printf("%c",field[i][j]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [UVa] 10189 Minesweeper.cpp hosted with ❤ by GitHub

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，停止。

這題和二分搜尋很類似。

	#include <cstdio>
	using namespace std;
	struct fraction{
	int M; //Molecular 分子
	int D; //Denominator 分母
	};
	int main()
	{
	int m,n;
	while (scanf("%d%d",&m,&n))
	{
	if (m==1 && n==1) break;
	fraction L={0,1},M={1,1},R={1,0};

	while (1){
	long double t1 = (long double)m/n, t2 = (long double)M.M/M.D;
	if (t1 < t2){
	printf("L");
	R = M;
	M.M += L.M;
	M.D += L.D;
	}
	else if (t1 > t2){
	printf("R");
	L = M;
	M.M += R.M;
	M.D += R.D;
	}
	else{
	printf("\n");
	break;
	}
	}
	}
	return 0;
	}

view raw [UVa] 10077 The Stern-Brocot Number System.cpp hosted with ❤ by GitHub

UVa 10050 Hartals

本題題目連結

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

	#include <cstdio>
	using namespace std;

	int main()
	{
	int T,N,P,h[101]; // T: number of cases, N: number of days
	// P: number of parties, h[i]: hartal parameter for party i
	scanf("%d",&T);
	while (T--)
	{
	scanf("%d%d",&N,&P);
	for (int i=0; i<P; i++) scanf("%d",&h[i]);
	int hartal=0;
	for (int i=1; i<=N; i++){
	if (i%7 == 6) { // 跳過星期五和星期六
	i++; continue;
	}
	for (int j=0; j<P; j++){
	if (i%h[j] == 0) {
	hartal++;
	break;
	}
	}
	}
	printf("%d\n",hartal);
	}
	return 0;
	}

view raw [UVa] 10050 Hartals.cpp hosted with ❤ by GitHub

UVa 12192 Grapevine

本題題目連結

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

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

	#include <cstdio>
	using namespace std;

	int N,M,Q,L,U;
	int H[501][501];

	int BS_1 (int i) // 二分搜尋找出每列的符合>=L的最小值
	{
	int left = 0, right = M-1, mid;
	while (left != right){
	mid = (left+right)/2;
	if (H[i][mid] >= L) right = mid;
	else left = mid+1;
	}
	return left;
	}
	int BS_2 (int l_y,int l_x) // 二分搜尋找出右下斜角符合<=U的最大值
	{
	int r_x = l_x+(N-1-l_y); // r_x代表右下角的列index(橫), r_y為行index(直)
	if (r_x >= M) r_x = M-1; // 避免越界
	int r_y = l_y+(r_x-l_x);
	int mid_x,mid_y;

	while (l_x != r_x){
	mid_x = (l_x+r_x+1)/2;
	mid_y = (l_y+r_y+1)/2;
	if (H[mid_y][mid_x] <= U){
	l_x = mid_x;
	l_y = mid_y;
	}
	else {
	r_x = mid_x-1;
	r_y = mid_y-1;
	}
	}
	return l_x;
	}

	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%d%d",&N,&M))
	{
	if (!N && !M) break;
	for (int i=0; i<N; i++)
	for (int j=0; j<M; j++)
	scanf("%d",&H[i][j]);
	scanf("%d",&Q);
	while (Q--)
	{
	scanf("%d%d",&L,&U);
	int Max_len=0;
	for (int i=0; i<N; i++){ //每次找一列
	int left = BS_1(i); //找出該正方形的左上角
	if (H[i][left] < L) continue; //解答檢查
	int right = BS_2(i,left); //找出該正方形的右下角
	if (H[i+(right-left)][right] > U) continue; //解答檢查
	int length = right-left+1;
	if (length > Max_len) Max_len = length;
	}
	printf ("%d\n",Max_len);
	}
	printf("-\n");
	}
	}

view raw [UVa] 12192 Grapevine.cpp hosted with ❤ by GitHub

2014年1月24日星期五

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了= ="

	#include <cstdio>
	using namespace std;
	typedef long long int llt;

	llt a[21][21];

	void max_1(llt &A,llt n,llt i,llt j)
	{
	llt Max = 0;
	for (llt k=i+1; k<=n; k++)
	if (a[k][1]+a[k][j] > Max) Max = a[k][1]+a[k][j];
	A += Max;
	}
	void max_2(llt &A,llt n,llt i,llt j)
	{
	llt Max = 0;
	for (llt k=1; k<j; k++)
	if (a[i][k]+a[n][k]) Max = a[i][k]+a[n][k];
	A += Max;
	}
	void max_3(llt &A,llt i,llt j)
	{
	llt Max = 0;
	for (llt k=i; i<j; i++)
	if (a[i][k]+a[k+1][j] > Max) Max = a[i][k]+a[k+1][j];
	A += Max;
	}

	void func(llt &A,llt n,llt i,llt j)
	{
	A = 0;
	if (i >= j){
	if (i < n) max_1(A,n,i,j);
	if (j>0) max_2(A,n,i,j);
	}
	else
	max_3(A,i,j);
	}

	int main()
	{
	llt n,an1;
	while (scanf("%lld%lld",&n,&an1)!=EOF){
	a[n][0] = 0;
	a[n][1] = an1;
	for (llt j=2; j<=n; j++)
	func(a[n][j],n,n,j);
	for (llt i=n-1; i>0; i--)
	for (llt j=0; j<=n; j++)
	func(a[i][j],n,i,j);
	printf("%lld\n",a[1][n]);
	}

	return 0;
	}

view raw [UVa] 10520 Determine it.cpp hosted with ❤ by GitHub

UVa 834 Continued Fraction

本題題目連結

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

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	int a,b;
	while (scanf("%d%d",&a,&b)!=EOF){ // 43,19
	printf("[%d;",a/b); // [2;
	a %= b; // 5,19
	while(a!=1){
	printf("%d,",b/a); // [2;3, / [2;3,1,
	b %= a; // 5,4 / 4,1
	swap (a,b); // 4,5 / 1,4
	}
	printf("%d]\n",b); // [2;3,4,1]
	}
	return 0;
	}

view raw [UVa] 834 Continued Fraction.cpp hosted with ❤ by GitHub

2014年1月21日星期二

UVa 494 Kindergarten Counting Game

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

	#include <cstdio>
	using namespace std;
	char line[100000];
	bool is_word (char a){
	if (a<='z' && a>='a' \|\| a<='Z' && a>='A')
	return 1;
	return 0;
	}
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (gets(line)){
	int num;
	num = is_word(line[0]);
	for(int i=0; line[i+1]; i++){
	if (!is_word(line[i])) num += is_word(line[i+1]);
	}
	printf("%d\n",num);
	}
	return 0;
	}

view raw [UVa] 494 Kindergarten Counting Game.cpp hosted with ❤ by GitHub

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，那麼就剛好。

	#include <cstdio>
	using namespace std;
	int main()
	{
	// freopen ("input.txt","rt",stdin);
	int N;
	int x,y;
	scanf("%d",&N);
	while (N--){
	scanf("%d%d",&x,&y);
	int steps = 0, length;
	long long int sum = 0, distance = y-x;
	for (length=0;;) {
	length++;
	if (sum + 2*length > distance) break;
	sum += 2*length;
	steps += 2;
	}
	if (sum + length < distance) steps += 2;
	else if (sum != distance) steps += 1;
	printf("%d\n",steps);
	}
	return 0;
	}

view raw [UV] 846 Steps.cpp hosted with ❤ by GitHub

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

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	// freopen("input.txt","rt",stdin);
	int N;
	while (scanf("%d",&N)!=EOF){
	int s[3001],check[3001]={0};
	bool ok=1;

	scanf("%d",&s[0]);
	for (int i=1; i<N; i++) {
	scanf("%d",&s[i]);
	int temp = abs(s[i]-s[i-1]);
	if (temp<=3000) check[temp]++;
	}

	for (int i=1;i<N;i++)
	if (check[i]==0) { ok = 0; break; }

	if (ok) printf("Jolly\n");
	else printf("Not jolly\n");
	}
	return 0;
	}

view raw [UVa] 10038 Jolly Jumpers.cpp hosted with ❤ by GitHub

UVa 10340 All in All

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

	#include <cstdio>
	using namespace std;

	char s[100000],t[100000];

	int main()
	{
	// freopen ("input.txt","rt",stdin);
	while (scanf("%s%s",s,t)!=EOF){
	int i=0,j=0;
	for (;t[i];i++){
	if (t[i] == s[j]) j++;
	}
	if (!s[j]) printf("Yes\n");
	else printf("No\n");
	}
	return 0;
	}

view raw [UVa] 10340 All in All.cpp hosted with ❤ by GitHub

UVa 714 Copying Books

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	int M, K;
	int p[501];
	int ans[501][501],n[501]; // n is the index of ans[i];

	int main()
	{
	int N;
	scanf("%d",&N);
	while (N--){
	scanf ("%d%d",&M,&K);
	long long int Min=0,Max=0,mid;
	for (int i=0;i<M;i++) {
	scanf("%d",&p[i]);
	if (p[i] > Min) Min=p[i];
	Max += p[i];
	}

	while (Min < Max){
	int amount=1;
	long long int sum=0;
	mid = (Min+Max)/2;
	for (int i=0;i<M;i++){
	if (sum+p[i] > mid){
	amount++;
	sum = 0;
	}
	sum += p[i];
	}
	if (amount > K) Min = mid+1;
	else Max = mid;
	}

	fill (n,n+501,0);
	long long sum = 0;
	// 因為如果有多組解，後面的人要分配多一點書，因此i,j從後面開始
	for (int i=M-1, j=K-1; i>=0; i--){ // i: book index, j: scriber index
	if (sum+p[i] > Max \|\| j>i){ // j>i: 因為每個人都至少要有一本書
	j--;
	sum = 0;
	}
	sum += p[i];
	ans[j][n[j]++] = p[i];
	}

	for (int i=0; i<K; i++){
	for (int j=n[i]-1; j>=0; j--){
	if (i!=0 \|\| j!=n[0]-1) printf(" ");
	printf("%d",ans[i][j]);
	}
	if (i != K-1) printf(" /");
	}
	printf("\n");
	}

	return 0;
	}

view raw [UVa] 714 Copying Books.cpp hosted with ❤ by GitHub

UVa 10474 Where is the Marble

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	int N,Q,Case=1;
	int n[10001],q[10001];

	int Search (int q)
	{
	int L=0, R=N-1, mid;
	while (L!=R){
	mid = (L+R)/2;
	if (n[mid] >= q) R = mid;
	else L = mid+1;
	}
	if (n[L] == q) return L+1;
	else return -1;
	}

	int main()
	{
	//freopen ("input.txt","rt",stdin);
	while (scanf("%d%d",&N,&Q)){
	if (!N && !Q) break;
	for (int i=0;i<N;i++) scanf("%d",&n[i]);
	for (int i=0;i<Q;i++) scanf("%d",&q[i]);
	sort (n,n+N);

	printf("CASE# %d:\n",Case++);
	for (int i=0; i<Q; i++){ // q loop
	int position = Search(q[i]);
	if (position == -1) printf("%d not found\n",q[i]);
	else printf("%d found at %d\n",q[i],position);
	}
	}
	return 0;
	}

view raw [UVa] 10474 Where is the Marble.cpp hosted with ❤ by GitHub

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)的值就越小，為遞減函數，因此可使用二分搜尋逼近答案。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	#define F(x) (pexp(-x) + qsin(x) + rcos(x) + stan(x) + t*pow(x,2) + u)

	int main()
	{
	int p, q, r, s, t, u;
	while (scanf("%d %d %d %d %d %d",&p, &q, &r, &s, &t, &u)!=EOF)
	{
	double Min=0.0, Max=1.0, mid;
	for (int i=0; i<100; i++){
	mid = (Min+Max)/2;
	if (F(mid)>0) Min = mid;
	else Max = mid;
	}
	if (fabs(F(mid)-0) > 1e-10) printf ("No solution\n");
	else printf("%.4lf\n",mid);
	}
	return 0;
	}

view raw [UVa] 10341 Solve It.cpp hosted with ❤ by GitHub

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=(所有牛奶瓶的容積)。

	#include<cstdio>
	using namespace std;

	int N,M; // N:牛奶瓶數量 M:容器數量
	int n[1000001]; // 牛奶瓶的個別容積

	int main()
	{
	while (scanf("%d%d",&N,&M)!=EOF){
	int left=0,right=0,mid;
	for (int i=0; i<N; i++) {
	scanf("%d",&n[i]);
	if (n[i]>left) left = n[i];
	right += n[i];
	}

	while (left < right){ //使用二元搜尋找出最小容器的容積能使amount==M
	mid = (left+right)/2;
	int sum=0; // 用來累積每瓶牛奶的容量
	int amount=0; // 用來計數用了多少容器
	for (int i=0; i<N; i++){
	sum += n[i];
	if (sum > mid) {
	amount++;
	sum = n[i];
	}
	else if (sum == mid){
	amount++;
	sum = 0;
	}
	}
	if (sum>0) amount++;

	if (amount > M) left = mid+1; //如果大於題目規定代表我們的容積太小，導致容器太多
	else right = mid;
	}
	printf("%d\n",left);
	}
	return 0;
	}

view raw [UVa] 11413 Fill the Containers.cpp hosted with ❤ by GitHub

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。

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;

	int N,M;
	int n[1001],q[26];

	int Search(int a,int start){
	int L = start;
	int R = N-1;
	int mid;
	while (L<=R){
	mid = (L+R)/2;
	if (a==n[mid]) return mid;
	if (a>n[mid]) L = mid+1;
	else R = mid-1;
	}
	return mid;
	}
	int Closest(int q,int a,int b){
	if (abs(a-q) <= abs(b-q)) return a;
	else return b;
	}
	int main()
	{
	int Case=1,i,j;
	while (scanf("%d",&N)){
	if (N==0) break;
	for (i=0;i<N;i++) scanf("%d",&n[i]);
	sort (n,n+N);
	scanf("%d",&M);
	for (i=0;i<M;i++) scanf("%d",&q[i]);
	printf("Case %d:\n",Case++);

	for (i=0;i<M;i++){ // q loop
	int ans=n[0]+n[1];
	for (j=0;n[j]<=(q[i]/2) && j+1<N;j++){ // n loop
	int k = Search(q[i]-n[j],j+1);
	if ((n[j]+n[k])==q[i]) { ans = q[i]; break; }
	else {
	if (k-1!=j) ans = Closest(q[i],ans,n[j]+n[k-1]);
	ans = Closest(q[i],ans,n[j]+n[k]);
	if (k+1<N) ans = Closest(q[i],ans,n[j]+n[k+1]);
	}
	}
	printf("Closest sum to %d is %d.\n",q[i],ans);
	}
	}

	return 0;
	}

view raw [UVa] 10487 Closest Sums.cpp hosted with ❤ by GitHub

UVa 11057 Exact Sum

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	int N,M,i; // N: number of books, M: money Peter has
	int book[10001]; // price of each book

	int Search (int n,int start){ //使用binary search
	int left=start;
	int right=N;
	int mid;
	while (left<=right){
	mid = (left+right)/2;
	if (n==book[mid]) return mid;
	if (n>book[mid]) left=mid+1;
	else right=mid-1;
	}
	return -1;
	}

	int main()
	{
	while (scanf("%d",&N)!=EOF){
	for (i=0;i<N;i++) scanf("%d",&book[i]);
	scanf("%d",&M);
	sort (book,book+N);

	int ans[10000],a=0;
	for (i=0;book[i]<(M/2);i++){
	if (Search(M-book[i],i+1)!=-1) {
	ans[a++]=book[i];
	}
	}
	printf("Peter should buy books whose prices are %d and %d.\n\n",ans[a-1],M-ans[a-1]);
	}

	return 0;
	}

view raw [UVa] 11057 Exact Sum.cpp hosted with ❤ by GitHub

2014年1月19日星期日

UVa 11520 Fill the Square

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

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

	#include <cstdio>
	using namespace std;

	char square[12][12];

	void Fill (int n,int i,int j){
	char filled = 'A';
	bool up,left,right,down;
	while (filled <= 'Z'){
	if (i-1<0 \|\| square[i-1][j]!=filled) up=1; else up=0;
	if (i+1>=n \|\| square[i+1][j]!=filled) down=1; else down=0;
	if (j-1<0 \|\| square[i][j-1]!=filled) left=1; else left=0;
	if (j+1>=n \|\| square[i][j+1]!=filled) right=1;else right=0;

	if (up && down && left && right){
	square[i][j] = filled;
	printf("%c",filled);
	break;
	}
	else filled += 1;
	}
	}

	int main()
	{
	int t,n,Case=1;
	scanf("%d",&t);
	while (t--)
	{
	scanf("%d",&n);
	gets(square[0]);
	for(int i=0;i<n;i++) gets(square[i]);

	printf("Case %d:\n",Case++);

	for(int i=0;i<n;i++){
	for(int j=0;j<n;j++){
	if (square[i][j]!='.')
	printf("%c",square[i][j]);
	else Fill(n,i,j);
	}
	printf("\n");
	}
	}

	return 0;
	}

view raw [UVa] 11520 Fill the Square.cpp hosted with ❤ by GitHub

UVa 11729 Commando War

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct soldier{
	int B;
	int J;
	}a[10001];
	bool cmp(soldier a,soldier b){
	return a.J > b.J;
	}
	int main()
	{
	int N,Case=1;
	while (scanf("%d",&N)){
	if (N == 0) break;

	for(int i=0;i<N;i++) scanf("%d%d",&a[i].B,&a[i].J);
	sort (a,a+N,cmp);

	int time=0;
	int ans=0;
	for (int i=0;i<N;i++) {
	time += a[i].B;
	ans = max(ans,time+a[i].J);
	}

	printf("Case %d: ",Case++);
	printf("%d\n",ans);
	}
	return 0;
	}

view raw [Uva] 11729 Commando War.cpp hosted with ❤ by GitHub

UVa 11292 Dragon of Loowater

想法：

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	int main()
	{
	int M,N,i,j; // M: number of heads, N: number of knights
	int m[20010],n[20010]; // m[i]: diameter of head, n[i]: height of knight
	while (scanf("%d %d",&M,&N)){
	if (!M && !N) break;
	for(i=0;i<M;i++) scanf("%d",&m[i]);
	for(i=0;i<N;i++) scanf("%d",&n[i]);

	sort(m,m+M);
	sort(n,n+N);

	long long int paid=0;

	for(i=0,j=0;i<N;i++){
	if(n[i] >= m[j]){
	paid += n[i];
	if(++j == M) break;
	}
	}

	if(j == M) printf("%lld\n",paid);
	else printf("Loowater is doomed!\n");
	}

	return 0;
	}

view raw [UVa] 11292 Dragon of Loowater.cpp hosted with ❤ by GitHub

2014年1月18日星期六

UVa 11054 Wine trading in Gergovia

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

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

　　再用example作為例子

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

	#include <cstdio>
	#include <cmath>
	using namespace std;

	int a[100001];

	int main()
	{
	int n;
	while(scanf("%d",&n)){
	if (n==0) break;
	for(int i=0;i<n;i++)
	scanf("%d",&a[i]);

	long long int ans=0;
	for(int i=0;i<n-1;i++){
	ans += abs(a[i]);
	a[i+1] += a[i];
	}

	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [UVa] 11054 Wine trading in Gergovia.cpp hosted with ❤ by GitHub

UVa 10249 The Grand Dinner

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

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	struct temp_type{
	int *t;
	int index;
	}temp[51];
	bool cmp(temp_type a,temp_type b){
	return (a.t)>(b.t);
	}
	int main()
	{
	int M,N; //M:number of teams, N:number of tables
	int m[71],n[51]; //m:number of members of a team, n:seating capacity of a table
	while (scanf("%d %d",&M,&N)){
	if (!M && !N) break;
	int i,j,ans[71][100];
	for(i=0;i<M;i++) scanf("%d",&m[i]);
	for(i=0;i<N;i++) scanf("%d",&n[i]);

	bool ok=1;
	for(i=0;i<M && ok;i++){
	if(m[i]>N) {ok=0; break;} //隊員數量大於桌子數量

	//將桌子的座位數量與index複製到temp
	//並依照剩餘座位數量排序
	for(j=0;j<N;j++) {
	temp[j].t=&n[j];
	temp[j].index=j;
	}
	sort(temp,temp+N,cmp);

	int n_ans=0;
	//隊員m[i]個，排入剩餘位子前m[i]多的桌子
	for(j=0;j<m[i];j++){
	if(*(temp[j].t)<=0) {ok=0; break;}
	else {
	(*(temp[j].t))--;
	ans[i][n_ans++]=temp[j].index;
	}
	}
	sort(ans[i],ans[i]+n_ans); //將index由小排到大
	}
	if(ok){
	printf("1\n");
	for(i=0;i<M;i++) {
	for(j=0;j<m[i];j++)
	printf("%d ",ans[i][j]+1);
	printf("\n");
	}
	}
	else printf("0\n");
	}
	return 0;
	}

view raw [UVa] 10249 The Grrand Dinner.cpp hosted with ❤ by GitHub

UVa 10020 Minimal Converge

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

想法：

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;

	struct line{
	int L;
	int R;
	}a[100001];

	bool cmp(line a,line b){
	if(a.L == b.L) return a.R < b.R;
	return a.L < b.L;
	}
	int main()
	{
	int T,M;
	scanf("%d",&T);
	while (T--){
	scanf("%d",&M);
	int i,j,n=0;
	while (scanf("%d%d", &a[n].L,&a[n].R)){
	if (!a[n].L && !a[n].R) break;
	n++;
	}
	sort(a,a+n,cmp);

	int ans=0,left=0,right=0,Max=0,Max_index; //left是存a_index,right是存max
	int List[100001],l_index=0;
	bool Ans=1;

	while (Max<M){ //不斷靠近M
	right=Max;
	for(i=left;a[i].L<=right && i<n;i++){ /a[i].L不能>right，不然範圍會沒有覆蓋/
	if (Max<a[i].R){ //在沒有超過範圍的情況下，不斷找最靠近右邊的R
	Max=a[i].R;
	Max_index=i;
	}
	}
	if (Max==right) {Ans=0; break;} //找不到的情況
	List[l_index++]=Max_index; //將找到的點放入List
	ans++;
	left = i;
	}

	if(Ans){
	printf("%d\n",ans);
	for(i=0;i<l_index;i++)
	printf("%d %d\n",a[List[i]].L,a[List[i]].R);
	}
	else printf("0\n");

	if(T) printf("\n");

	}
	return 0;
	}

view raw [UV] 10020 Minimal Converge.cpp hosted with ❤ by GitHub

UVa 311 Packets

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

想法：

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

	#include <cstdio>
	using namespace std;
	void parcel(int &box,int num[],int &space,int w);
	int main()
	{
	int num[7];
	while(scanf("%d %d %d %d %d %d",&num[1],&num[2],&num[3],&num[4],&num[5],&num[6])){
	int i=1;
	for(;i<=6;i++)
	if(num[i]!=0) break;
	if(i==7) break;

	int box=num[6]+num[5]+num[4];
	num[1]-=11*num[5]; //一個5x5搭配11個1x1
	num[2]-=5*num[4]; //一個4x4搭配5個2x2(如果2x2不夠的情況最底下會考慮)

	box+=(num[3]/4); if(num[3]%4) box++;
	switch(num[3]%4){ //3x3情況要特別討論
	case 0: break;
	case 1:
	num[2]-=5;
	num[1]-=7;
	break;
	case 2:
	num[2]-=3;
	num[1]-=6;
	break;
	case 3:
	num[2]-=1;
	num[1]-=5;
	break;
	}

	if (num[2]>0){ //如果2x2還有剩
	box+=num[2]/9; if(num[2]%9) box++;
	num[1]-=(36-(num[2]%9)*4);
	}
	else if (num[2]<0)
	num[1]-=(-num[2])*4; //將不夠的2x2用4個1x1來補

	if (num[1]>0){ //如果1x1還有剩
	box+=(num[1]/36); if(num[1]%36) box++;
	}
	printf("%d\n",box);
	}
	return 0;
	}

view raw [UVa] 311 Packets.cpp hosted with ❤ by GitHub

2014年1月10日星期五

UVa 10282 & POJ 2503 Babelfish

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

	#include <cstdio>
	#include <map>
	#include <string>

	using namespace std;
	int main()
	{
	map<string,string>m;
	char line[200];
	while(gets(line)){
	if (line[0]=='\0') break;
	char a[50],b[50];
	sscanf(line,"%s %s",a,b);
	m[b]=a;
	}
	while(gets(line)){
	if (line[0]=='\0') break;
	if (m[line]=="\0") //map如果沒對應到，其內容為"\0"
	printf("eh\n");
	else
	printf("%s\n",m[line].c_str()); //把C++字串換回C字串
	}
	return 0;
	}

view raw [POJ] 2503 Babelfish.cpp hosted with ❤ by GitHub

2014年1月7日星期二

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}

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

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

	#include <cstdio>
	using namespace std;

	int stk[32],nOfstk,Max,Max_pos;
	void flip(int n);
	//在code裡為求方便index是從左邊1,2,..,n到右邊，與題目的位置標示相反，在print的時候才換成題目的標示方法
	int main()
	{
	char line[200];
	while(gets(line)){
	nOfstk=0;
	for(int i=0;i<32;i++) stk[i]=0;
	for(int i=0;line[i];i++){
	if(line[i]==' '){
	printf("%d ",stk[nOfstk]);
	nOfstk++;
	}
	else{
	stk[nOfstk]*=10;
	stk[nOfstk]+=(line[i]-'0');
	}
	}
	printf("%d\n",stk[nOfstk]);

	//每次都將最大值放到右邊
	for(int i=nOfstk;i>=0;i--){
	Max=0;
	for(int j=0;j<=i;j++) //找剩下未排序的最大值
	if(stk[j]>Max){ Max=stk[j]; Max_pos=j;}
	if(Max_pos!=i){ //最大值不在最右
	if(Max_pos!=0) //不在最左
	flip(Max_pos); //先翻到最左
	flip(i); //再翻到最右
	}
	}
	printf("0\n");
	}
	return 0;
	}
	void flip(int n)
	{
	printf("%d ",nOfstk-n+1);
	int temp[32];
	for(int i=0;i<=n;i++)
	temp[i]=stk[i];
	for(int i=0,j=n;i<=n;i++,j--){
	stk[i]=temp[j];
	if(stk[i]==Max) Max_pos=i;
	}
	}

view raw [UVa] 120 Stacks of Flapjacks.cpp hosted with ❤ by GitHub

2014年1月5日星期日

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

	#include <cstdio>
	#include <algorithm>
	#include <cmath>
	using namespace std;
	struct point_type{
	double x;
	double y;
	};
	bool cmp(point_type a,point_type b)
	{
	return a.x<b.x;
	}
	double distance(point_type a,point_type b);
	double divide(point_type a[],int low,int high);
	double combine(point_type a[],int low,int mid,int high,double min_left,double min_right);
	int main()
	{
	int N;
	point_type point[10001];
	while(scanf("%d",&N))
	{
	if (N==0) break;
	for(int i=0;i<N;i++)
	scanf("%lf %lf",&point[i].x,&point[i].y);
	sort(point,point+N,cmp);
	double dis=divide(point,0,N-1);
	if(dis>=10000.0) printf("INFINITY\n");
	else printf("%.4lf\n",dis);
	}
	return 0;
	}
	double Distance(point_type a,point_type b)
	{
	return (double)sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
	}
	double divide(point_type a[],int low,int high)
	{
	if(low>=high) return 99999; //切到只剩1個點，return inf

	int mid=(low+high)/2;
	double min_left=divide(a,low,mid);
	double min_right=divide(a,mid+1,high);
	return combine(a,low,mid,high,min_left,min_right);
	}
	double combine(point_type a[],int low,int mid,int high,double min_left,double min_right)
	{
	double d=(min_left<min_right)?min_left:min_right;
	double line=(double)(a[mid].x+a[mid+1].x)*0.5; //line:左集合與右集合的中間線x座標
	double min_D=d;
	for(int i=mid+1;a[i].x<line+d && i<=high;i++){ //枚舉line+-d範圍內左右集合的點
	for(int j=mid;a[j].x>line-d && j>=low;j--){
	double temp=Distance(a[i],a[j]);
	if(temp<min_D) min_D=temp;
	}
	}
	return min_D;
	}

view raw [UVa] 10245 The Closest Pair Problem.cpp hosted with ❤ by GitHub

2014年1月2日星期四

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...得知

	#include <cstdio>
	#include <cmath>
	using namespace std;
	typedef long long int llt;

	llt round(llt x){ //Team x到達哪個Round(在哪個Round 輸掉)
	for(llt i=1,j=1;;i*=2,j++)
	if(x%i) return j-1;
	}
	llt win(llt x){ //贏Team x的Team
	return x-pow(2,round(x)-1);
	}
	llt optimistic(llt n,llt x){
	if (x==0) return 1;
	llt num=0; //贏Team X的隊數
	while(1){
	x=win(x);
	num++;
	if(x==0) break;
	}
	return num+1;
	}
	llt pessimistic(llt n,llt x){
	if (x==0) return 1;
	llt all=pow(2,n);
	llt numOfx_worse=pow(2,round(x)-1)-1; //比Team x差的隊數
	return all-numOfx_worse;
	}

	int main()
	{
	llt M,N,X;
	scanf("%lld",&M);
	while(M--){
	scanf("%lld %lld",&N,&X);
	printf("%lld %lld\n",optimistic(N,X),pessimistic(N,X));
	}
	return 0;
	}

view raw [UVa] 10666 The Eurocup is Here!.cpp hosted with ❤ by GitHub

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

	#include<cstdio>
	using namespace std;
	long long int sum=0;
	void func(int m,int n);

	int main()
	{
	int t,m,n,i,j;
	scanf("%d",&t);
	while(t--){
	sum=0;
	scanf("%d %d",&m,&n);
	func(m,n);
	printf("%lld\n",sum);
	}
	return 0;
	}
	void func(int m,int n) //m顆蘋果分n堆
	{
	if(m==0 \|\| n==1) {
	sum++;
	return ;
	}
	int i,j;
	for(i=n;i>=1;i++){ //n堆~1堆
	if(m-i>=0)
	func(m-i,i);
	}
	}

view raw [POJ] 1664 放蘋果.cpp hosted with ❤ by GitHub

POJ 1068 Parencodings

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

P-sequence    4 5 6666

W-sequence    1 1 1456

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

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

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

	#include <cstdio>
	using namespace std;
	int main()
	{
	int t,n,p_seq[25],parenthes[10000],n_p=0,i,j;
	scanf("%d",&t);
	while(t--){
	scanf("%d",&n);
	for(p_seq[0]=0,i=1,n_p=0;i<=n;i++){
	scanf("%d",&p_seq[i]);
	for(j=0;j<p_seq[i]-p_seq[i-1];j++)
	parenthes[n_p++]=0;
	parenthes[n_p++]=1;
	}
	bool matched[10000]={0}; //1:left parenthes is matched
	for(i=0;i<n_p;i++){
	int num=0;
	if(parenthes[i]==1){
	for(j=1;i-j>=0;j++){
	if(parenthes[i-j]==0 && matched[i-j]==0){
	num++;
	matched[i-j]=1;
	printf("%d ",num);
	break;
	}
	else if(parenthes[i-j]==0 && matched[i-j]==1)
	num++;
	}
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [POJ] 1068 Parencodings.cpp hosted with ❤ by GitHub

2014/2/17 更新：

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

	#include <cstdio>
	using namespace std;
	int main()
	{
	int t,n;
	int p[30];
	int diff[30];
	while (scanf("%d%d" ,&t,&n) != EOF){
	for (int i=0; i<n; i++) scanf("%d",&p[i]);
	diff[0] = p[0];
	for (int i=1; i<n; i++) diff[i] = p[i]-p[i-1];

	printf("1");
	for (int i=1; i<n; i++){
	for (int Count = 1, j = i; j >= 0; --j, ++Count)
	if (diff[j] > 0){
	diff[j]--;
	printf(" %d",Count);
	break;
	}
	}
	printf("\n");
	}
	return 0;
	}

view raw [POJ] 1068-2 Parencodings.cpp hosted with ❤ by GitHub

POJ 3262 Protecting the Flowers

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

	#include<cstdio>
	#include<algorithm>
	using namespace std;

	struct cow{
	int T;
	int D;
	};
	bool cmp(cow a,cow b)
	{
	return (a.D1.0/a.T)>(b.D1.0/b.T); //*1.0
	}

	int main()
	{
	int N,i,j;
	long long sum=0,ans=0; //long long int
	cow a[100001];
	while(scanf("%d",&N)!=EOF){
	for (i=0;i<N;i++){
	scanf("%d%d",&a[i].T,&a[i].D);
	sum+=a[i].D;
	}

	sort(a,a+N,cmp);

	for(i=0;i<N;i++){
	sum-=a[i].D;
	ans+=(sum2a[i].T);
	}
	printf("%lld\n",ans);
	}
	return 0;
	}

view raw [POJ] 3262 Protecting the Flowers.cpp hosted with ❤ by GitHub

POJ 1007 DNA Sorting

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

	#include <cstdio>
	#include <algorithm>
	using namespace std;
	struct sortedDNA
	{
	int num;
	char *line;
	}a[101];

	int bubble_sort(char a[],int n);
	bool cmp(sortedDNA a,sortedDNA b);
	int main()
	{
	int n,m,i,j;
	char DNA[101][52];
	scanf("%d %d\n",&n,&m);

	for(i=0;i<m;i++){
	gets(DNA[i]);
	a[i].line=DNA[i];
	a[i].num=bubble_sort(DNA[i],n);
	}

	sort(a,a+m,cmp);

	for(i=0;i<m;i++){
	for(j=0;j<n;j++){
	printf("%c",a[i].line[j]);
	}
	printf("\n");
	}
	return 0;
	}
	bool cmp(sortedDNA a,sortedDNA b)
	{
	return a.num<b.num;
	}
	int bubble_sort(char a[],int n)
	{
	int i,j,num=0;
	for(i=0;i<n-1;i++)
	for(j=i+1;j<n;j++)
	if(a[i]>a[j]) num++;
	return num;
	}

view raw [POJ] 1007 DNA Sorting.cpp hosted with ❤ by GitHub

POJ 1035 Spell Checker

想法：

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

	#include <cstdio>
	using namespace std;

	struct dictionary
	{
	char l[20];
	int num;
	}dic[10002];

	int main()
	{
	char check[20];
	int i,j,k;
	for(i=0;;i++){
	scanf("%s",dic[i].l);
	if(dic[i].l[0]=='#') break;
	for(dic[i].num=0;dic[i].l[dic[i].num];dic[i].num++); //計算字元數
	}
	int numOfdic=i;

	while(1){
	scanf("%s",check);
	if(check[0]=='#') break;
	int nOfcheck=0;
	for(;check[nOfcheck];nOfcheck++);

	int diff=0,same=0; //same=1表示完全正確
	char *correct[10002]; int nOfcorrect=0;

	for(i=0,diff=0,same=0;i<numOfdic;i++,diff=0){
	if (nOfcheck-dic[i].num>1 \|\| nOfcheck-dic[i].num<-1) continue;

	else if(nOfcheck==dic[i].num){ //字數相等的情況
	for(j=0;check[j];j++)
	if(check[j]!=dic[i].l[j])
	diff++;

	if (diff==0){
	same=1;
	printf("%s is correct\n",check);
	break;
	}
	else if(diff==1) correct[nOfcorrect++]=&dic[i].l[0];
	}

	else{ //字數相差1的情況
	int d_i=0,c_i=0; //dic_index,check_index
	while(dic[i].l[d_i] && check[c_i]){
	if(dic[i].l[d_i]==check[c_i]){d_i++; c_i++;}
	else{
	diff++;
	if(diff>1) break;
	if(nOfcheck>dic[i].num) c_i++;
	else d_i++;
	}
	}
	if(diff<=1) correct[nOfcorrect++]=&dic[i].l[0];
	}
	}
	if(!same){
	printf("%s:",check);
	for(j=0;j<nOfcorrect;j++)
	printf(" %s",correct[j]);
	printf("\n");
	}
	}
	return 0;
	}

view raw [POJ] 1035 Spell Checker.cpp hosted with ❤ by GitHub

訂閱：文章 (Atom)

網頁

2014年6月5日 星期四

2014年6月3日 星期二

2014年5月31日 星期六

2014年5月30日 星期五

2014年5月27日 星期二

2014年5月26日 星期一

2014年5月22日 星期四

2014年5月8日 星期四

2014年5月1日 星期四

2014年4月30日 星期三

2014年4月29日 星期二

2014年4月24日 星期四

2014年4月20日 星期日

2014年4月18日 星期五

2014年4月16日 星期三

2014年4月11日 星期五

2014年4月7日 星期一

2014年4月6日 星期日

2014年4月5日 星期六

2014年4月3日 星期四

2014年3月29日 星期六

2014年3月21日 星期五

2014年3月20日 星期四

2014年3月19日 星期三

2014年3月17日 星期一

2014年3月16日 星期日

2014年3月11日 星期二

2014年3月10日 星期一

2014年3月9日 星期日

2014年3月7日 星期五

2014年3月5日 星期三

2014年3月4日 星期二

2014年3月3日 星期一

2014年3月2日 星期日

2014年3月1日 星期六

2014年2月28日 星期五

2014年2月27日 星期四

2014年6月5日星期四

2014年6月3日星期二

2014年5月31日星期六

2014年5月30日星期五

2014年5月27日星期二

2014年5月26日星期一

2014年5月22日星期四

2014年5月8日星期四

2014年5月1日星期四

2014年4月30日星期三

2014年4月29日星期二

2014年4月24日星期四

2014年4月20日星期日

2014年4月18日星期五

2014年4月16日星期三

2014年4月11日星期五

2014年4月7日星期一

2014年4月6日星期日

2014年4月5日星期六

2014年4月3日星期四

2014年3月29日星期六

2014年3月21日星期五

2014年3月20日星期四

2014年3月19日星期三

2014年3月17日星期一

2014年3月16日星期日

2014年3月11日星期二

2014年3月10日星期一

2014年3月9日星期日

2014年3月7日星期五

2014年3月5日星期三

2014年3月4日星期二

2014年3月3日星期一

2014年3月2日星期日

2014年3月1日星期六

2014年2月28日星期五

2014年2月27日星期四