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       最底層

UVa 501 Black Box

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



這是用set的版本：

UVa 902 Password Search

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

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

POJ 3481 Double Queue

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

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，就能產生最遠的距離。

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的步數。

UVa 10946 You want what filled

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

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

UVa 10592 Freedom FIghter

題意：

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

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

BBB

PP

不會有底下這種情況

BBB

PP

BBB

想法：

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

UVa 705 Slash Maze

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

UVa 10009 All Roads Lead Where?

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

UVa 10004 Bicoloring

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

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

UVa 762 We Ship Cheap

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

UVa 567 Risk

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

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

UVa 539 The Settlers of Catan

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

UVa 439 Knight Moves

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

UVa 571 Jugs

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

UVa 336 A Node Too Far

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

UVa 383 Shipping Routes

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

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

UVa 260 Il Gioco dell'X

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

UVa 113 Power of Cryptography

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

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)]
• 把以上三式加起來即是答案

UVa 10763 Foreign Exchange

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

UVa 10222 Decode the Mad man

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

UVa 579 ClockHands

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

UVa 10905 Children's Game

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

UVa 12079 Pie

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

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

UVa 352 The Seasonal War

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

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

UVa 532 Dungeon Master

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

UVa 10776 Determine The Combination

想法：

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

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

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

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

UVa 12337 Bob's Beautiful Balls

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

UVa 12667 Last Blood

想法：

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

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'轉為'*'。

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

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]為未知數。

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値，接下來就能求出答案了。

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的最小奇數(奇=奇-偶)。

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。

UVa 10392 Factoring Large Number

題意：質因數分解

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

UVa 10061 How many zero's and how many digits

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

想法：

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

UVa 408 Uniform Generator

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

UVa 10110 Light, more light

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

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

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開始分配，使得每個數盡量靠近。

UVa 424 Integer Inquiry

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

UVa 10494 If We Were a Child Again

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

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裡囉，不用自己換行)。

UVa 409 Excuses, Excuses!

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

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

UVa 537 Artificial Intelligence?

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

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

UVa 10361 Automatic Poetry

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

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

UVa 10010 Where's Waldorf?

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

UVa 401 Palindromes

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

UVa 445 Marvelous Mazes

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

UVa 490 Rotating Sentences

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

UVa 414 Machined Surfaces

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

UVa 10082 WERTYU

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

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