A. Up and Down
PKU 3912
http://poj.org/problem?id=3912
題意：給定一個(gè)一維的棋盤(pán)，范圍為[0, W] (W <= 1000,000,000)，某兩個(gè)點(diǎn)之間有梯子或蟲(chóng)洞，梯子的下端點(diǎn)到上端點(diǎn)以及蟲(chóng)洞的上端點(diǎn)到下端點(diǎn)花費(fèi)的步數(shù)為0，其它任意點(diǎn)之間的距離通過(guò)跳躍來(lái)計(jì)算，最多每次跳躍不超過(guò)S格（S<= 6），跳躍的過(guò)程中如果跳到梯子的下端點(diǎn)或者蟲(chóng)洞的上端點(diǎn)就會(huì)被直接傳送到另一端，并且每次跳躍只能從小的點(diǎn)跳到大的點(diǎn)（蟲(chóng)洞是個(gè)例外），求從0到W的最短距離。
圖A-1
題解：
離散化 + SPFA。
將所有梯子和蟲(chóng)洞的兩端點(diǎn)、0和W以及他們往前往后S步以?xún)?nèi)的數(shù)全部記錄下來(lái)，梯子和蟲(chóng)洞有P（P <= 40）個(gè)，加上起點(diǎn)終點(diǎn)，總共82個(gè)點(diǎn)，算上前后各六步，總共82 * 13 = 1066個(gè)點(diǎn)，然后將這些點(diǎn)排序后離散化，最后就是要構(gòu)建一個(gè)網(wǎng)絡(luò)圖，通過(guò)網(wǎng)絡(luò)求0到W的最短路，最短路可以用SPFA求解。
談?wù)劷▓D的過(guò)程，對(duì)于任意兩個(gè)點(diǎn)，他們之間必定可以連一條邊，然后有一個(gè)步數(shù)表示邊的權(quán)值（這里的步數(shù)也可能是正無(wú)窮，也即永遠(yuǎn)都無(wú)法到達(dá)）。
對(duì)于任意兩個(gè)點(diǎn)(u, v)，他們的步數(shù)w(u, v)（邊權(quán)）我們做如下討論（這里的u、v是離散化后的點(diǎn)）：
1）如果u是梯子的下端點(diǎn)，v是梯子的上端點(diǎn) 或者 u是蟲(chóng)洞的上端點(diǎn)，v是蟲(chóng)洞的下端點(diǎn)，那么w(u, v) = 0，否則進(jìn)入2)的判斷;
2）如果u的編號(hào)大于v，w(u, v) = inf，表示永遠(yuǎn)不可達(dá)，因?yàn)槟炒翁S只能從小的點(diǎn)跳到大的點(diǎn)，否則進(jìn)入3）的判斷;
3）如果u的實(shí)際位置和v的實(shí)際位置差值小于等于S，則w(u, v) = 1；
4）檢查u和v之間是否有蟲(chóng)洞的上端點(diǎn)或者梯子的下端點(diǎn)，之后將這兩種點(diǎn)稱(chēng)為X點(diǎn)
a）如果有，判斷他們是否連續(xù)，
i) 如果不連續(xù)w(u, v) = inf（這一步這么做是為了簡(jiǎn)單化，試想一下，如果X點(diǎn)不是全部連續(xù)，說(shuō)明u可以先跳到他們中間的某個(gè)非X的點(diǎn)，然后再跳到v點(diǎn)，這一步是通過(guò)SPFA來(lái)實(shí)現(xiàn)迭代的，建邊的時(shí)候可以不考慮）。
ii）如果連續(xù)，判斷他們連續(xù)的格子的數(shù)目，如果大于等于S說(shuō)明這個(gè)連續(xù)的塊必定跳不過(guò)去，所以w(u, v) = inf，否則可以先跳到最先的一個(gè)X點(diǎn)的前面一個(gè)點(diǎn)，然后經(jīng)過(guò)一步S跳躍將這個(gè)連續(xù)塊跳過(guò)去，再跳到v。
b）如果沒(méi)有X點(diǎn)，那么直接從u點(diǎn)跳到v點(diǎn)。
這里我們需要計(jì)算從a點(diǎn)跳到b點(diǎn)不考慮蟲(chóng)洞和梯子的最短距離，可以貪心的跳，每次往大的跳，直到剩余格子不足S格，即(b-a + S-1) / S （b-a對(duì)S求商的上整）。
邊建立完成就可以利用廣搜求解0-W的最短路了。
B. Gnome Sequencing
PKU 3913 http://poj.org/problem?id=3913
水題，判斷三個(gè)數(shù)是全遞增還是全遞減還是無(wú)序。
C. DuLL
PKU 3914 http://poj.org/problem?id=3914
題意：給定一些dll文件和它占用的內(nèi)存空間，以及一些可執(zhí)行程序占用的內(nèi)存空間和它依賴(lài)的dll文件，程序以進(jìn)程為單位，兩個(gè)相同的程序可能有不同的進(jìn)程，進(jìn)行一些下列的操作：
1）某個(gè)程序運(yùn)行的時(shí)候需要它依賴(lài)的dll文件也加載到內(nèi)存中，多個(gè)程序可以共用一個(gè)dll文件；
2）某個(gè)程序退出的時(shí)候，如果它所依賴(lài)的dll文件沒(méi)有其它程序使用，需要釋放這段內(nèi)存空間；
給定一系列的運(yùn)行進(jìn)程，求某個(gè)時(shí)刻的最大內(nèi)存占用。
題解：HASH的簡(jiǎn)單應(yīng)用。
初始化內(nèi)存占用V = 0，
對(duì)于給定的輸入進(jìn)程：
1）如果是新運(yùn)行的進(jìn)程，將V加上這個(gè)進(jìn)程的內(nèi)存占用，并將它所有依賴(lài)的dll文件檢查一遍，如果引用計(jì)數(shù)為0，則將對(duì)應(yīng)dll文件的內(nèi)存累加到V上，引用計(jì)數(shù)+1；
2）如果是退出進(jìn)程，將V減去這個(gè)進(jìn)程的內(nèi)存占用，并將它所有依賴(lài)的dll文件檢查一遍，如果引用計(jì)數(shù)為1，則用V減去對(duì)應(yīng)dll文件的占用量，引用計(jì)數(shù)-1；
每次操作記錄最大的V就是最后的答案。
D. Black Vienna
PKU 3915 http://poj.org/problem?id=3915
題意：三個(gè)人，每個(gè)人五張牌，互相不知道對(duì)方的牌，還有額外的三張牌放在一邊（所有牌編號(hào)為A - R）。每一輪，由 (i-1)%3+1 (1 <= i <= 15) 號(hào)玩家進(jìn)行發(fā)問(wèn)，問(wèn)Ai (1 <= Ai <= 3) 號(hào)玩家XYZ（代表任意三個(gè)牌號(hào)）三張牌中有多少?gòu)堅(jiān)谒稚希缓笏卮?/span>Bi (0 <= Bi <= 3)，問(wèn)經(jīng)過(guò)多少輪之后有某位玩家知道 額外 的那三張牌是什么。
題解：dfs枚舉 + 剪枝。
首先枚舉到某個(gè)詢(xún)問(wèn)i的時(shí)候玩家j能夠猜出的那三張牌的情況，如果枚舉完所有情況最后確定只有一個(gè)解滿(mǎn)足條件的時(shí)候，那個(gè)詢(xún)問(wèn)的編號(hào)i就是答案了。
類(lèi)似IDA*的思路，先枚舉詢(xún)問(wèn)最大深度，如果到達(dá)那個(gè)詢(xún)問(wèn)不能確定額外的那三張牌或者有很多種情況，那么說(shuō)明還需要更多的詢(xún)問(wèn)，迭代深度繼續(xù)枚舉。
對(duì)于某個(gè)詢(xún)問(wèn)i，找到詢(xún)問(wèn)的那三張牌中已經(jīng)是Ai號(hào)選手的數(shù)量ansCnt，以及尚未確定牌的歸屬的牌的數(shù)量xCnt，如果已經(jīng)確定位置的牌數(shù)量 大于 實(shí)際他回答的數(shù)量（ansCnt > Bi）或者 尚未確定位置的牌數(shù)量 + 已經(jīng)確定為他的牌數(shù)量 小于 實(shí)際他回答的數(shù)量（ansCnt + xCnt < Bi）都是不合理的情況，剪枝，不用繼續(xù)往下搜索；
否則，將(Bi - ansCnt)張牌分配給Ai，(xCnt - (Bi - ansCnt))張牌分配給其它兩位玩家以及額外的那一堆，這里需要用到嵌套dfs枚舉，枚舉完后進(jìn)入下一個(gè)詢(xún)問(wèn)的枚舉，每次詢(xún)問(wèn)的時(shí)候可以有幾個(gè)剪枝：
1）如果某個(gè)階段某個(gè)人的牌數(shù)超過(guò)5張；
2）枚舉的解的數(shù)量超過(guò)2個(gè)；
3) 對(duì)于一次完全枚舉，枚舉完所有詢(xún)問(wèn)后還是有無(wú)法確定三張額外的牌的情況；
E. Duplicate Removal
PKU 3916 http://poj.org/problem?id=3916
水題，對(duì)輸入的元素進(jìn)行連續(xù)判重輸出。
F. Rock, Paper, Scissors
PKU 3917 http://poj.org/problem?id=3917
水題，剪刀石頭布！O_o
G. A to Z Numerals
PKU 3918 http://poj.org/problem?id=3918
題意：復(fù)雜模擬。（沒(méi)做出來(lái)，#-_-# 樣例的98是怎么出來(lái)的呀！！！）
H. Cell Towers
PKU 3919 http://poj.org/problem?id=3919
題意：給出一條曲折的連續(xù)線(xiàn)段，曲線(xiàn)從起點(diǎn)開(kāi)始每經(jīng)過(guò)一個(gè)長(zhǎng)度為1的單位會(huì)放置一個(gè)守衛(wèi)K，在曲線(xiàn)以外的某些地方會(huì)有T(T <= 10)個(gè)信號(hào)發(fā)射器，用A、B、C...來(lái)表示，每個(gè)信號(hào)發(fā)射器有它的信號(hào)強(qiáng)度Pi，每個(gè)信號(hào)發(fā)射器到守衛(wèi)K的距離如果是D，那么它能接收到的信號(hào)值為Pi / D2的最近整數(shù)，并且對(duì)于守衛(wèi)K，它只會(huì)接收最大的信號(hào)值，如果有多個(gè)發(fā)射器對(duì)于K的信號(hào)值相同，那么選擇字典序最小的發(fā)射器。需要求是一些守衛(wèi)集合，這些守衛(wèi)分別和它的前一個(gè)守衛(wèi)所接收的信號(hào)發(fā)射器不一樣。
題解：計(jì)算幾何、向量的簡(jiǎn)單應(yīng)用。
對(duì)于每條射線(xiàn)，終點(diǎn)減去起點(diǎn)，再單位化后就可以得到這條射線(xiàn)的單位向量，利用這一點(diǎn)可以很簡(jiǎn)單的將所有守衛(wèi)的坐標(biāo)求出來(lái)，然后對(duì)于每個(gè)守衛(wèi)判斷接收的是哪個(gè)發(fā)射器，判斷和之前那個(gè)守衛(wèi)是否相同即可。
需要注意的是最后一個(gè)守衛(wèi)，當(dāng)和上一個(gè)守衛(wèi)距離小于0.5的時(shí)候不會(huì)建立新的守衛(wèi)。
I. RIPOFF
PKU 3920 http://poj.org/problem?id=3920
題意：給定N(N <= 200)個(gè)數(shù)的一維數(shù)組A，取不大于T+2個(gè)數(shù)，每相鄰兩個(gè)數(shù)之間的下標(biāo)不大于S，問(wèn)最大的取值總和(第0個(gè)和第N+1個(gè)數(shù)必取，且權(quán)值為0)。
題解：動(dòng)態(tài)規(guī)劃。
DP[i][j] 表示第j個(gè)數(shù)取 A[i]的最大值，那么狀態(tài)轉(zhuǎn)移方程可以表示為：
DP[i][j] = max{ DP[k][j-1] + A[i], i > k > i-1-S && k >= 0};
特殊的，DP[0][0] = 0，其他的DP[i][j] 都初始化為INF;
最后計(jì)算出的DP[N+1][i]中的最大值就是答案了。