A . John
PKU 3480 http://poj.org/problem?id=3480
題意：N堆石子，兩人輪流從其中一堆中取任意石子，最后一個取完石子的人輸。
題解：博弈。
1) 當所有石子的SG值異或和不等于0時：
a) 個數大于1的堆數=0，必定是奇數個1，所以先手必輸；
b) 個數大于1的堆數=1，總能想辦法將局面變成奇數個1，所以先手必勝；
c) 個數大于1的堆數>1，總能取掉某些石子，使得所有石子的SG值異或和為0，并且個數大于1的堆數至少還剩兩堆；
2) 當所有石子的SG值異或和等于0時：
a) 個數大于1的堆數=0，必定是偶數個1，先手必勝；
b) 個數大于1的堆數=1（不存在）；
c) 個數大于1的堆數>1，無論怎么取，SG值異或和都不可能為0。并且無論先手怎么移，后手可以要么進入偶數個1的狀態，要么保持SG值和為0并且非全1的狀態（該狀態先手必輸），所以這種情況，先手必敗。
由于1) 的c)情況可以到達2的c)情況，所以1的c)情況為先手必勝點。
B . Double Queue
PKU 3481 http://poj.org/problem?id=3481
題意：給定一些數據(K,P)和一些詢問，K為數據值，P為優先級，每次詢問輸出當前優先級最高或者最低的數據的K的值，詢問完刪除這個數據。
題解：平衡樹。
可以用SLT的set(內部也是平衡樹的實現)水過去。
C . ‘JBC’
PKU 3482 http://poj.org/problem?id=3482
題意：進制轉換，數字位可以是任何的可見ASCII碼，求所有可能進制下的串轉換成十進制后的和。
題解：模擬進制轉換，模擬大數運算。
D . Loan Scheduling
PKU 3483 http://poj.org/problem?id=3483
題意：給定N(N <= 10000)個任務，每個任務是一個二元組(Pi, Di)，表示如果在[0, Di]的某個時刻內完成則可以得到Pi的利潤，每個時間點最多只能有L(L <= 100)個任務，求取一個任務子集來完成的的最大利潤總和。
題解：貪心。
初始化每個時間點的可用任務數為L，初始化任務利潤和S。
將所有任務按Pi從大到小排序，對于每個任務，從Di到0枚舉它的完成時間t，如果t這個時間點還有可用任務，累加Pi到S，并且將t這個時間點的可用任務數減1，枚舉完所有任務后S即為所求。
E . Showstopper
PKU 3484 http://poj.org/problem?id=3484
題意：給定一些三元組(X, Y, Z)，一個三元組表示滿足X + K*Z <= Y (K = 0, 1, 2, 3 ... ) 的所有正整數 X + K*Z出現了一次。對于多個三元組，保證所有數中至多只有一個數出現奇數次，求這個數以及它出現的次數。
題解：二分答案。
對于出現奇數次的那個數T，那么如果小于T的所有數的和必定是偶數，大于等于T的所有數的和必定是奇數，利用這一點可以二分枚舉這個T，然后利用所有小于等于T的數的個數的奇偶性進行二分判定。
對于某個三元組(X, Y, Z)，小于等于T的個數分幾種情況討論：
1) 當T >= Y，個數為 (Y-X)/Z + 1;
2) 當T < X，個數為0;
3) 當 X <= T < Y，個數為 (T-X)/Z + 1;
每次枚舉T，將所有區間的數相加判斷奇偶性即可。
F . Highway
PKU 3485 http://poj.org/problem?id=3485
題意：給定一條高速公路的長度L(范圍為0到L)和N個村莊，要求在高速公路上建一些出口，使得每個村莊到高速公路至少有一個出口的距離不大于D，并且出口總數最少。
題解：貪心。
計算出每個村莊到高速公路距離D范圍內的左右區間[Li, Ri]，對這些區間進行排序，排序規則為如果左端點一致則按照右端點遞增排序，否則按照左端點遞增排序。然后按左端點遞增枚舉每個區間（每個區間對應一個村莊），對于尚未有高速公路可達的村莊，在其右端點建立一個出口（貪心所在，因為是從左往右掃描，所以在右端點建出口肯定比左端點建更優），然后將它之后的左端點坐標小于這個出口的區間全部hash掉（因為那些村莊可以用這個出口，無須建立新的出口），直到所有區間枚舉完畢，出口數也就得出了。
G . Computers
PKU 3486 http://poj.org/problem?id=3486
題意：故事背景是每年都要更換電腦或者進行一次維修，如果換電腦需要c的花費，如果不換電腦，那么第y年到第z年( 1 <= y <= z <= n)的總維修費用為m[y][z]，求經過n年的最小花費。
題解：動態規劃。
DP[i]表示經過i年的總開銷，假設從第j年開始買了一臺新的電腦，一直用到了第i年，那么前j年的總開銷為DP[j]，從第j+1年到第i年的維修開銷加上購買花費c，即DP[j] + m[j+1][i] + c，DP[i]就是這些開銷中的最小值，即。
DP[i] = min{ DP[j] + m[j+1][i] + c, 0 <= j < i };
H . The Stable Marriage Problem
PKU 3487 http://poj.org/problem?id=3487
題意：n(n < 27)對男女，每個男人有對所有女人的好感度，每個女人也有對所有男人的好感度，A對B的好感度記為G(A, B), 求找出一種穩定的婚配關系，使得對于任意一對夫婦X(M, W)，不存在 G(XM, YW) > G(XM, XW) 并且 G(XW, ZM) > G(XW, XM)，并且要求男士優先考慮（即男方如果能找到好的一定不會更差的）。通俗的講，就是XM更加喜歡別人的老婆，Xw更加喜歡別人的老公，這樣的婚姻是不穩定的，雙方都有可能出現外遇。
題解：穩定婚姻經典算法。
由于是男士最優，所以需要模擬男士求愛的方式。
用L[i][j]表示i號男子喜歡的第j個女子的編號；
用R[i][j]表示i號女子對j號男子的評分（越大評分越高，且對于確定的i肯定互不相同）；
算法如下：
1) 將所有的男子以及他們向多少個女人求過婚的信息入隊，每次彈出一個男子M，找到他下一個要求婚的對象（求婚順序按照對女生的好感度順序進行）。
a) 如果當前求婚對象W沒有配偶，直接配對，記Match[ W ] = M;
b) 如果當前求婚對象有老公，即Match[ W ]，那么檢查M 和 Match[ W ]在W的評分，如果M的評分大于W的老公，則迫使其改嫁，前夫入隊，Match[ W ] = M；否則，該男子M繼續入隊；
2) 反復進行1)直到所有人都找到的對象。
I . Arne Saknussemm
PKU 3488 http://poj.org/problem?id=3488
題意：簡單字符串模擬。
題解：根據題意做就行了。