網頁

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)題目
想法:
    這裡提供兩種方法:

  1. 把已經讀入的數字存起來,每次讀一個新的數字i的時候,就把LIS[i]設成1,然後把現在這個新數字i與以前已經讀入的數字j做比較,如果i比j大且LIS[i]<LIS[j]+1,就把LIS[i]=LIS[j]+1。最後輸出最大的LIS值即可。
  2. 與上面不同,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個骨牌。


UVa 291 The House Of Santa Claus

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


UVa 598 Bundling Newspapers

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


UVa 574 Sum It Up

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


UVa 524 Prime Ring Problem

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


UVa 11085 Back to the 8-Queens

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


UVa 624 CD

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


UVa 989 Su Doku

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


2014年3月7日 星期五

UVa 441 Lotto

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

UVa 167 The Sultan's Successors

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


UVa 10305 Ordering Tasks

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


UVa 11606 Pick up sticks

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


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。


UVa 11060 Becerages

想法:
  記錄每個點被其他點連入的數量(Ex: A->B, C->B,則beConnected[B]=2),和記錄各個點連到哪些點。
  1. 每次從頭找beConnected[i]==0(表示沒有點連到i)的Node
  2. 將這個Node輸出
  3. 同時將beConnected[i]改成-1表示這Node已經輸出過了
  4. 然後其他每個被Node i連入的Node j,把beConnected[j]--
  5. 執行1~4 N次,把每個Node都輸出過

POJ 2442 Sequence

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


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)。
  1. 將L1遞增排序
  2. 將L2遞增排序。
  3. 然後把L1裡面每個數字和L2[0]加起來,val=L1[i]+L2[0]和pos=0放到PQ裡面。
  4. L1的數字就不會用到了
  5. 之後每次從PQ裡面拿出第一個(最小的val),將這個val放入L1(覆蓋以重複利用L1),然後將這個val=(val-L2[pos]+L2[pos+1])和pos=pos+1丟回PQ裡
  6. 重複步驟5 K次,L1裡面就有K個數字,表示這兩行已經合併成功
  7. 讀入下一個L2,並重複步驟2~7,直到將K行合併成一行
  8. 輸出L1
用這方法將兩行合併成一行的時候,只要做K次即可,因為我們已經將L1都丟進PQ裡面,然後每次都選最小和出來,並同時把可能的答案丟入PQ。


2014年3月5日 星期三

POJ 2255 Tree Recovery

想法:
  原本的字串是整棵Tree,我們可先找到這個Tree的Root,再將其分為左右Sub Tree,一直遞迴下去直到Sub Tree只剩一個元素。
  具體做法是:
  1. 先用Preorder String找出Root(P_root),再透過P_root找到Inorder String的Root(I_root)
  2. 然後用I_root分別找出左右Sub Tree在Inorder String的左右界(會有4個index:左子樹的左右界和右子樹的左右界),再用剛才4個index的結果來找出左右子樹在Preoder String的左右界(一樣有4個index)。
  3. 依照Post Order的順序:
    1. 先遞迴左子樹
    2. 再遞迴右子樹
    3. 輸出Root
底下有附詳細註解的Code:


2014年3月4日 星期二

UVa 11987 Almost Union-Find

想法:
  • int Root[] : 表示i這個點存放在哪個Set(也就是Set[Root[i]]裡面可以找到i這個數字)
  • vector<int> Set[] : 每個Set裡面可以存放很多數字
分成三個操作:
  1. Union:如果x和y不在同個Set,那就把元素個數較少的那個Set裡面的每個元素移動到另一個Set,並同時將Root[]重新指向。例如Set[Root[y]]元素較少,就把Set[Root[y]]內的元素加入到Set[Root[x]],並且把Set[Root[y]]的元素n,使得Root[n]=Root[x]。
  2. Move:如果x和y不在同個Set,就把Set[Root[x]]這個Set內的元素x刪除,並在Set[Root[y]]加入x,記得將Root[x] = Root[y]。
  3. Output:輸出Set[Root[x]].size()和該Set內每個元素的和。


UVa 11503 Virtual Friends

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


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將它轉成數字編號。


UVa 10608 Friends

想法:
  做Disjoint Set,詳細看底下Code~。


UVa 10583 Ubiquitous Religions

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


2014年3月3日 星期一

UVa 879 Circuit Nets

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



UVa 793 Network Connections

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

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


POJ 3253 Fence Repair

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


2014年3月2日 星期日

POJ 2431 Expedition

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

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



UVa 12347 Binary Search Tree

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


2014年3月1日 星期六

UVa 11995 I Can Guess the Data Structure

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



UVa 10821 Constructing BST

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



UVa 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。