A . The Hardest Problem Ever

       PKU 1298 http://poj.org/problem?id=1298

         題意：解碼題，按照如下對應關系解碼：

       密文 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
       原文 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 

       題解：簡單題。

 

B. Polar Explorer

PKU 1299 http://poj.org/problem?id=1299

題意：給定圓的半徑X，求圓周上兩個點A和B的距離，其中圓心角AOB的角度為Z(0 <= Z <= 360)。

題解：核心是Z如果大于180，則Z = 360 - Z，即走劣弧。而且題目求的是來回一次，所以計算的時候弧長要乘2。

 

C. Door Man

PKU 1300 http://poj.org/problem?id=1300

題意：給定一些邊和起點s，求能否找到一條從s到0的通路，并且要求訪問所有的邊。

題解：歐拉回路可行解判定。

首先利用flood fill從s遍歷全圖，如果0點沒有被訪問到則必定不存在；然后判斷度數不為0的點是否有未被訪問到的，如果有，說明圖不連通，也必定不存在解；最后統計度數為奇數的點的個數P，以及具體的點：

1)  P = 0，則必定有解；

2)  P > 2，則無解；

3)  P =2, 那么有解的前提是兩個奇度數點中一個是s，另一個是0；否則無解。

 

D . The Umbrella Problem 2054

PKU 1301 http://poj.org/problem?id=1301

題意：給定一個10X10的地圖，玩家從第一行的某一個點出發，每一步行編號+1，列編號增量有三種選擇(-1, 0, 1)，圖中標記為S(laser gun)的點不能走，并且S的點會發出鐳射光，第0秒朝上發射，第1秒朝右，第2秒朝下，第3秒朝左，循環往復，發射長度一直到地圖邊緣。問能否走到最后一行標記為G(grass)的地方。

題解：廣搜。

hash[4][R][C]表示狀態，每走一步，利用步數 mod 4計算出鐳射光的方向，然后將所有的鐳射光可達區域全部標記出來，未標記的點為可達點，枚舉三個方向進行搜索。

E. Blue Gene, Jr.

       PKU 1302 http://poj.org/problem?id=1302

       題意：一個長度為N(N <= 20)的病毒基因串A[1...N]進行變異，變異過程從左往右，分情況討論：

       1) 如果第i個字符是 A-Z，則它將變異成數字n mod 10，n表示A[i+1...N]中變異基因的數目；

       2) 如果第i個字符是 1-9，則它變異成A[i] - 1，并且如果第p (p = i + A[i])個基因存在的話，從第p個基因開始變異；否則從第i+1個基因開始變異；

       題解：題意理解后就是個水題了，遞歸求解。

 

F . Byte Me!

       PKU 1303 http://poj.org/problem?id=1303

       題意：二進制二十一點(二進制黑杰克)是由兩種牌組成的游戲，一種稱為bytes(一個8比特的序列表示0-255之間的數)，一種稱為nibbles((一個4比特的序列表示0-15之間的數)，游戲玩法如下：

       1) 游戲的目標是獲得盡量接近510分，并且不能超過它；

       2) 每個玩家有兩張牌，一張面朝上，一張面朝下(莊家不知道是什么牌)；

       3) 每個玩家有四次叫牌機會，可以叫bytes，也可以叫nibbles，但是如果分數超過510則不能再叫牌；

       4) 所有的叫牌都是面朝上的；

       5) 如果玩家分數超過510，立即判為輸；

       5) 莊家最后一個叫牌；

       7) 平局的情況莊家勝(如果所有人都超過510分，莊家還是贏的)；

      

莊家的規則如下：

       1) 當看到自己和其他人面朝上的牌，判斷已經必勝時不要再叫牌了；

       2) 如果總分小于382時 需要叫一次byte牌；

       3) 如果總分小于等于500時 需要叫一次nibble牌；

 

還有兩個隱藏規則：

       1) 你是莊家；

       2) 每個非莊家的玩家面朝下的牌是11111111（但是莊家不知道），面朝上的牌給定；

       3) 非莊家不會叫牌(因為他們比較笨)；

      

       給定莊家的牌和其他玩家面朝上的牌，以及牌堆中的bytes牌和nibble牌，求莊家的四次叫牌能否獲勝；

 

       題解：題目說了一大堆，最后非莊家的玩家都不會叫牌，o(╯□╰)o...所以只要根據莊家的規則進行叫牌，然后判斷是否能夠勝出即可；

       因為其他人都不叫牌，每個人都有兩張牌，所以其他人的總分不可能超過510分，所以，如果莊家叫牌超過510分直接被判為負。

       每次叫牌前先判斷所有玩家的朝上的卡片分數加上255和莊家當前得分進行比較，如果有一個玩家分數大于莊家分數，則莊家按照382和500這兩個區間進行叫牌。

       四次叫牌結束，如果所有玩家分數都小于等于莊家分數，則判斷莊家分數是否大于510，如果是，輸出Bust!，否則輸出Win!；如果小于某個玩家的分數，那么輸出Lose!。

 

G . World's Worst Bus Schedule

       PKU 1304 http://poj.org/problem?id=1304

       題意：公交車站有N(N <= 20)輛車，每輛車的發車時間間隔為a1 a2 a3 a4... a1 a2 a3 a4... a1 a2 a3 a4...，循環發車，問某人在T時刻趕到公交車站，最少需要等待多少時間能夠乘上公交車。

       題解：對于每輛公交車，設它的所有時間間隔之和為S，令T' = T mod S，然后枚舉所有的發車間隔，前i個發車間隔a[i]之和減去T'中的最小正值就是等這輛公交車需要的時間，取所有公交車的最小時間就是所求。