A . John

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

題意：N堆石子，兩人輪流從其中一堆中取任意石子，最后一個(gè)取完石子的人輸。

題解：博弈。

1) 當(dāng)所有石子的SG值異或和不等于0時(shí)：

a) 個(gè)數(shù)大于1的堆數(shù)=0，必定是奇數(shù)個(gè)1，所以先手必輸；

b) 個(gè)數(shù)大于1的堆數(shù)=1，總能想辦法將局面變成奇數(shù)個(gè)1，所以先手必勝；

c) 個(gè)數(shù)大于1的堆數(shù)>1，總能取掉某些石子，使得所有石子的SG值異或和為0，并且個(gè)數(shù)大于1的堆數(shù)至少還剩兩堆；

2) 當(dāng)所有石子的SG值異或和等于0時(shí)：

a) 個(gè)數(shù)大于1的堆數(shù)=0，必定是偶數(shù)個(gè)1，先手必勝；

b) 個(gè)數(shù)大于1的堆數(shù)=1（不存在）；

c) 個(gè)數(shù)大于1的堆數(shù)>1，無(wú)論怎么取，SG值異或和都不可能為0。并且無(wú)論先手怎么移，后手可以要么進(jìn)入偶數(shù)個(gè)1的狀態(tài)，要么保持SG值和為0并且非全1的狀態(tài)（該狀態(tài)先手必輸），所以這種情況，先手必?cái)　?/span>

由于1) 的c)情況可以到達(dá)2的c)情況，所以1的c)情況為先手必勝點(diǎn)。

B . Double Queue

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

題意：給定一些數(shù)據(jù)(K,P)和一些詢問(wèn)，K為數(shù)據(jù)值，P為優(yōu)先級(jí)，每次詢問(wèn)輸出當(dāng)前優(yōu)先級(jí)最高或者最低的數(shù)據(jù)的K的值，詢問(wèn)完刪除這個(gè)數(shù)據(jù)。

題解：平衡樹(shù)。

可以用SLT的set(內(nèi)部也是平衡樹(shù)的實(shí)現(xiàn))水過(guò)去。

C . ‘JBC’

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

題意：進(jìn)制轉(zhuǎn)換，數(shù)字位可以是任何的可見(jiàn)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)個(gè)任務(wù)，每個(gè)任務(wù)是一個(gè)二元組(Pi, Di)，表示如果在[0, Di]的某個(gè)時(shí)刻內(nèi)完成則可以得到Pi的利潤(rùn)，每個(gè)時(shí)間點(diǎn)最多只能有L(L <= 100)個(gè)任務(wù)，求取一個(gè)任務(wù)子集來(lái)完成的的最大利潤(rùn)總和。

題解：貪心。

初始化每個(gè)時(shí)間點(diǎn)的可用任務(wù)數(shù)為L(zhǎng)，初始化任務(wù)利潤(rùn)和S。

將所有任務(wù)按Pi從大到小排序，對(duì)于每個(gè)任務(wù)，從Di到0枚舉它的完成時(shí)間t，如果t這個(gè)時(shí)間點(diǎn)還有可用任務(wù)，累加Pi到S，并且將t這個(gè)時(shí)間點(diǎn)的可用任務(wù)數(shù)減1，枚舉完所有任務(wù)后S即為所求。

E . Showstopper

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

題意：給定一些三元組(X, Y, Z)，一個(gè)三元組表示滿足X + K*Z <= Y (K = 0, 1, 2, 3 ... ) 的所有正整數(shù) X + K*Z出現(xiàn)了一次。對(duì)于多個(gè)三元組，保證所有數(shù)中至多只有一個(gè)數(shù)出現(xiàn)奇數(shù)次，求這個(gè)數(shù)以及它出現(xiàn)的次數(shù)。

題解：二分答案。

對(duì)于出現(xiàn)奇數(shù)次的那個(gè)數(shù)T，那么如果小于T的所有數(shù)的和必定是偶數(shù)，大于等于T的所有數(shù)的和必定是奇數(shù)，利用這一點(diǎn)可以二分枚舉這個(gè)T，然后利用所有小于等于T的數(shù)的個(gè)數(shù)的奇偶性進(jìn)行二分判定。

對(duì)于某個(gè)三元組(X, Y, Z)，小于等于T的個(gè)數(shù)分幾種情況討論：

1) 當(dāng)T >= Y，個(gè)數(shù)為 (Y-X)/Z + 1;

2) 當(dāng)T < X，個(gè)數(shù)為0;

3) 當(dāng) X <= T < Y，個(gè)數(shù)為 (T-X)/Z + 1;

每次枚舉T，將所有區(qū)間的數(shù)相加判斷奇偶性即可。

F . Highway

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

題意：給定一條高速公路的長(zhǎng)度L(范圍為0到L)和N個(gè)村莊，要求在高速公路上建一些出口，使得每個(gè)村莊到高速公路至少有一個(gè)出口的距離不大于D，并且出口總數(shù)最少。

題解：貪心。

計(jì)算出每個(gè)村莊到高速公路距離D范圍內(nèi)的左右區(qū)間[Li, Ri]，對(duì)這些區(qū)間進(jìn)行排序，排序規(guī)則為如果左端點(diǎn)一致則按照右端點(diǎn)遞增排序，否則按照左端點(diǎn)遞增排序。然后按左端點(diǎn)遞增枚舉每個(gè)區(qū)間（每個(gè)區(qū)間對(duì)應(yīng)一個(gè)村莊），對(duì)于尚未有高速公路可達(dá)的村莊，在其右端點(diǎn)建立一個(gè)出口（貪心所在，因?yàn)槭菑淖笸覓呙瑁栽谟叶它c(diǎn)建出口肯定比左端點(diǎn)建更優(yōu)），然后將它之后的左端點(diǎn)坐標(biāo)小于這個(gè)出口的區(qū)間全部hash掉（因?yàn)槟切┐迩f可以用這個(gè)出口，無(wú)須建立新的出口），直到所有區(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)過(guò)n年的最小花費(fèi)。

題解：動(dòng)態(tài)規(guī)劃。

DP[i]表示經(jīng)過(guò)i年的總開(kāi)銷(xiāo)，假設(shè)從第j年開(kāi)始買(mǎi)了一臺(tái)新的電腦，一直用到了第i年，那么前j年的總開(kāi)銷(xiāo)為DP[j]，從第j+1年到第i年的維修開(kāi)銷(xiāo)加上購(gòu)買(mǎi)花費(fèi)c，即DP[j] + m[j+1][i] + c，DP[i]就是這些開(kāi)銷(xiāo)中的最小值，即。

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)對(duì)男女，每個(gè)男人有對(duì)所有女人的好感度，每個(gè)女人也有對(duì)所有男人的好感度，A對(duì)B的好感度記為G(A, B), 求找出一種穩(wěn)定的婚配關(guān)系，使得對(duì)于任意一對(duì)夫婦X(M, W)，不存在 G(XM, YW) > G(XM, XW) 并且 G(XW, ZM) > G(XW, XM)，并且要求男士?jī)?yōu)先考慮（即男方如果能找到好的一定不會(huì)更差的）。通俗的講，就是XM更加喜歡別人的老婆，Xw更加喜歡別人的老公，這樣的婚姻是不穩(wěn)定的，雙方都有可能出現(xiàn)外遇。

題解：穩(wěn)定婚姻經(jīng)典算法。

由于是男士最優(yōu)，所以需要模擬男士求愛(ài)的方式。

用L[i][j]表示i號(hào)男子喜歡的第j個(gè)女子的編號(hào)；

用R[i][j]表示i號(hào)女子對(duì)j號(hào)男子的評(píng)分（越大評(píng)分越高，且對(duì)于確定的i肯定互不相同）；

算法如下：

1) 將所有的男子以及他們向多少個(gè)女人求過(guò)婚的信息入隊(duì)，每次彈出一個(gè)男子M，找到他下一個(gè)要求婚的對(duì)象（求婚順序按照對(duì)女生的好感度順序進(jìn)行）。

a) 如果當(dāng)前求婚對(duì)象W沒(méi)有配偶，直接配對(duì)，記Match[ W ] = M;

b) 如果當(dāng)前求婚對(duì)象有老公，即Match[ W ]，那么檢查M 和 Match[ W ]在W的評(píng)分，如果M的評(píng)分大于W的老公，則迫使其改嫁，前夫入隊(duì)，Match[ W ] = M；否則，該男子M繼續(xù)入隊(duì)；

2) 反復(fù)進(jìn)行1)直到所有人都找到的對(duì)象。

I . Arne Saknussemm

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

題意：簡(jiǎn)單字符串模擬。

題解：根據(jù)題意做就行了。