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