A. Artificial Intelligence?

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

題意：功率的計算公式為P = UI，給定一句話，這句話中一定會包含三個變量中的兩個，求另外一個，并且單位會有三種前綴m(毫)，k(千)，M(兆)。

題解：字符串掃描。

gets讀入字符串，進行一次遍歷，查找是否包含子串’P=’, ‘U=’, ‘I=’, 格式化它后面的數(shù)字，需要用double來存，然后檢查單位前綴，m需要將原值除上103，k需要將原值乘上103，M需要將原值常上106。然后分三種情況計算未知的那個值即可。

B. Balancing Bank Accounts

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

題意：給定N(N <= 20)個人，以及M(M <= 1000)條關(guān)系，每條關(guān)系的描述為nameA nameB C，表示nameA這個人給了nameB這個人C塊錢，為了讓所有人都不虧，需要再給出至多N-1條關(guān)系，使得所有人都收支平衡。

題解：貪心。

首先將所有人分成兩堆，from_set表示收入大于支出的人的集合，to_set表示支出大于收入的人的集合，并且記錄他們各自的 |收入-支出|，然后對于所有的from_set的人按 |收入-支出| 進行遞增排序，枚舉每個from_set中的人f，去to_set中找到一個人t，滿足f剩余的錢小于等于t虧損的錢，并且t是to_set中虧損最少的人，如果找不到這樣的人，那么找到虧損最多的那個人，將f的錢給t，循環(huán)往復(fù)，直到f的錢給完為止。

當from_set中的所有人將錢全部給了to_set中的人后，to_set中也就沒有人虧損了，所有人達到收支平衡。

C. The Settlers of Catan

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

題意：給定一個N(N <= 25)個點，M(M <= 25)條邊的圖，求圖的最長路，點允許重復(fù)，邊不允許重復(fù)。

題解：前向星 + dfs。

利用前向星存雙向邊，以每個點為起點深搜遍歷整個圖，訪問過的邊哈希，搜索過程更新最長路即可。

D. Team Queue

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

題意：Team Queue是這樣一種queue，每個元素都有一個Team。

對于queue的push操作，被push的元素從queue中從頭到尾掃描，如果掃到一個元素和它屬于同一個Team，那么直接將它插入到這個元素后面；如果沒有掃到，直接插到對列尾。

對于queue的pop操作，等同于普通queue的pop操作。

隊伍數(shù)N小于等于1000。

題解：模擬，開1000個隊列。

對于插入操作，每個Team的元素插入到對應(yīng)的隊列中，并且記錄當前Team的最早插入時間。O(1)

對于彈出操作，枚舉所有Team的隊列首元素，從中找時間最早的，然后對那個隊列執(zhí)行彈出操作。O(N)。

E. Error Correction

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

題意：給定N*N(N < 100)的01矩陣，問是否所有 行和 和 列和 都是偶數(shù)，如果是輸出OK，如果不是，是否能夠通過改變一個值保證 都是偶數(shù)， 都不行輸出Corrupt。

題解：掃描。

掃描所有 行和 和 列和，如果正好有其中一行R是奇數(shù)，并且其中一列C是奇數(shù)，那么改變(R, C)的值就能保證全是偶數(shù)，否則要么是OK，要么是Corrupt。

F. France '98

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

題意：給定16個國家進行淘汰賽，以及一個16*16的矩陣A，其中A[i][j]表示i號國家打敗j號國家的概率，問每個國家取得冠軍的概率。

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

dp[0][i]   表示 1/2決賽 第i個人獲勝的概率

dp[1][i]   表示 1/4決賽 第i個人獲勝的概率

dp[2][i]   表示 1/8決賽 第i個人獲勝的概率

dp[3][i]   表示  總決賽 第i個人獲勝的概率 

1) 那么顯然dp[0][i] = A[i][i^1]

2) dp[1][i]的概率取決于1/2決賽時第i個人獲勝的概率乘上他打敗1/4決賽中同組的那兩個人的概率；

3) dp[2][i]的概率取決于1/4決賽時第i個人獲勝的概率乘上他打敗1/8決賽中同組的那四個人的概率；

4) dp[3][i]的概率取決于1/8決賽時第i個人獲勝的概率乘上他打敗 總決賽中同組的那八個人的概率；

直接遞推求解，dp[3][i]就是所求。

G. Goldbach's Conjecture

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

題意：將一個數(shù)分解成兩個奇素數(shù)的和。

題解：素數(shù)篩選，枚舉。

H. Heavy Cargo

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

題意：給定一個有向圖，邊權(quán)W(u, v)表示從u到v的最大載重為W(u, v)，在給定s和t，求s到t 的最大可能載重。

題解：二分答案 + 判斷連通性。

二分枚舉答案T，然后從起點到終點進行連通性判定，如果邊權(quán)小于T的邊不可達，二分的最大值就是答案。