1.機(jī)器翻譯 (translate.pas/c/cpp) 【問(wèn)題描述】 小晨的電腦上安裝了一個(gè)機(jī)器翻譯軟件，他經(jīng)常用這個(gè)軟件來(lái)翻譯英語(yǔ)文章。 這個(gè)翻譯軟件的原理很簡(jiǎn)單，它只是從頭到尾，依次將每個(gè)英文單詞用對(duì)應(yīng)的中文含義來(lái)替換。對(duì)于每個(gè)英文單詞，軟件會(huì)先在內(nèi)存中查找這個(gè)單詞的中文含義，如果內(nèi)存中有，軟件就會(huì)用它進(jìn)行翻譯；如果內(nèi)存中沒(méi)有，軟件就會(huì)在外存中的詞典內(nèi)查找，查出單詞的中文含義然后翻譯，并將這 個(gè)單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。 假設(shè)內(nèi)存中有 M 個(gè)單元，每單元能存放一個(gè)單詞和譯義。每當(dāng)軟件將一個(gè)新單詞存入內(nèi)存前，如果當(dāng)前內(nèi)存中已存入的單詞數(shù)不超過(guò) M-1，軟件會(huì)將新單詞存入一個(gè)未使用的內(nèi)存單元；若內(nèi)存中已存入 M 個(gè)單詞，軟件會(huì)清空最早進(jìn)入內(nèi)存的那個(gè)單詞，騰出單元來(lái)，存放新單詞。 假設(shè)一篇英語(yǔ)文章的長(zhǎng)度為 N個(gè)單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開(kāi)始前，內(nèi)存中沒(méi)有任何單詞。 【輸入】 輸入文件名為 translate.in，輸入文件共 2 行。每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第一行為兩個(gè)正整數(shù) M和 N，代表內(nèi)存容量和文章的長(zhǎng)度。 第二行為 N 個(gè)非負(fù)整數(shù)，按照文章的順序，每個(gè)數(shù)（大小不超過(guò) 1000）代表一個(gè)英文單詞。文章中兩個(gè)單詞是同一個(gè)單詞，當(dāng)且僅當(dāng)它們對(duì)應(yīng)的非負(fù)整數(shù)相同。 【輸出】 輸出文件 translate.out 共1行，包含一個(gè)整數(shù)，為軟件需要查詞典的次數(shù)。 【數(shù)據(jù)范圍】 對(duì)于 10%的數(shù)據(jù)有 M=1，N≤5。 對(duì)于 100%的數(shù)據(jù)有 M<=100 ,N<=1000。 **【解題報(bào)告】 模擬大水題，開(kāi)個(gè)隊(duì)列維護(hù)。 隊(duì)列就相當(dāng)于是題中的內(nèi)存，每輸入一個(gè)數(shù)字就在內(nèi)存區(qū)間里查找一遍，如果已經(jīng)存在的話就不管，如果沒(méi)有的話入隊(duì)。 當(dāng)然也可以再開(kāi)一個(gè)數(shù)組存位置到達(dá)查找時(shí)O（n）的復(fù)雜度，不過(guò)從數(shù)據(jù)范圍上來(lái)說(shuō)不需要。。。**

代碼如下

烏龜棋中 M 張爬行卡片，分成 4 種不同的類型（M 張卡片中不一定包含所有 4 種類型的卡片，見(jiàn)樣例），每種類型的卡片上分別標(biāo)有 1、2、3、4 四個(gè)數(shù)字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應(yīng)的格子數(shù)。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒(méi)有使用過(guò)的爬行卡片，控制烏龜棋子前進(jìn)相應(yīng)的格子數(shù)，每張卡片只能使用一次。游戲中，烏龜棋子自動(dòng)獲得起點(diǎn)格子的分?jǐn)?shù)，并且在后續(xù)的爬行中每到達(dá)一個(gè)格子，就得到格子相應(yīng)的分?jǐn)?shù)。玩家最終游戲得分就是烏龜棋子從起點(diǎn)到終點(diǎn)過(guò)程中到過(guò)的所有格子的分?jǐn)?shù)總和。 很明顯，用不同的爬行卡片使用順序會(huì)使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多。 現(xiàn)在，告訴你棋盤上每個(gè)格子的分?jǐn)?shù)和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？ 【輸入】 輸入文件名 tortoise.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第 1 行2 個(gè)正整數(shù) N和 M，分別表示棋盤格子數(shù)和爬行卡片數(shù)。 第 2 行 N個(gè)非負(fù)整數(shù)，a1, a2, ……, aN，其中 ai 表示棋盤第 i 個(gè)格子上的分?jǐn)?shù)。 第 3 行M 個(gè)整數(shù)，b1,b2, ……, bM，表示 M 張爬行卡片上的數(shù)字。 【輸出】 輸出文件名 tortoise.out。 輸出只有 1行，1 個(gè)整數(shù)，表示小明最多能得到的分?jǐn)?shù)。 【數(shù)據(jù)范圍】 對(duì)于 30%的數(shù)據(jù)有 1≤N≤30，1≤M≤12。 對(duì)于 50%的數(shù)據(jù)有 1≤N≤120，1≤M≤50，且 4 種爬行卡片，每種卡片的張數(shù)不會(huì)超過(guò) 20。 對(duì)于 100%的數(shù)據(jù)有 1≤N≤350，1≤M≤120，且 4 種爬行卡片，每種卡片的張數(shù)不會(huì)超過(guò) 40；0≤ai≤100，1≤i≤N；1≤bi≤4，1≤i≤M。 **【結(jié)題報(bào)告】 一開(kāi)始看到這道題的數(shù)據(jù)范圍，還以為是裸考搜索，然而并不會(huì)這么簡(jiǎn)單粗暴。 其實(shí)是簡(jiǎn)單的DP，f[l1][l2][l3][l4]表示當(dāng)選擇l1個(gè)走1步的牌，l2個(gè)走2步的牌，l3個(gè)走3步的牌，l4個(gè)走4步的牌達(dá)到的最大收益。 轉(zhuǎn)移方程也就自然地出來(lái)了，寫成四個(gè)方便加條件判斷。 做題的時(shí)候數(shù)組開(kāi)小了，結(jié)果只有50分，還以為是算法的缺陷。。。**

代碼如下

3．關(guān)押罪犯 (prison.pas/c/cpp) 【問(wèn)題描述】 S城現(xiàn)有兩座監(jiān)獄，一共關(guān)押著 N名罪犯，編號(hào)分別為 1~N。他們之間的關(guān)系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時(shí)可能爆發(fā)沖突。我們用“怨氣值”（一個(gè)正整數(shù)值）來(lái)表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為 c 的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會(huì)發(fā)生摩擦，并造成影響力為 c 的沖突事件。 每年年末，警察局會(huì)將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個(gè)列表，然后上報(bào)到 S 城 Z 市長(zhǎng)那里。公務(wù)繁忙的 Z 市長(zhǎng)只會(huì)去看列表中的第一個(gè)事件的影響力，如果影響很壞，他就會(huì)考慮撤換警察局長(zhǎng)。 在詳細(xì)考察了 N 名罪犯間的矛盾關(guān)系后，警察局長(zhǎng)覺(jué)得壓力巨大。他準(zhǔn)備將罪犯?jìng)冊(cè)趦勺O(jiān)獄內(nèi)重新分配，以求產(chǎn)生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個(gè)罪犯間有仇恨，那么他們一定會(huì)在每年的某個(gè)時(shí)候發(fā)生摩擦。那么，應(yīng)如何分配罪犯，才能使 Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力最小？這個(gè)最小值是多少？ 【輸入】 輸入文件名為 prison.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 第一行為兩個(gè)正整數(shù) N和 M，分別表示罪犯的數(shù)目以及存在仇恨的罪犯對(duì)數(shù)。 接下來(lái)的 M行每行為三個(gè)正整數(shù) aj，bj，cj，表示 aj號(hào)和 bj號(hào)罪犯之間存在仇恨，其怨氣值為 cj。數(shù)據(jù)保證1≤aj 【輸出】 輸出文件prison.out 共1 行，為Z 市長(zhǎng)看到的那個(gè)沖突事件的影響力。如果本年內(nèi)監(jiān)獄中未發(fā)生任何沖突事件，請(qǐng)輸出0 【數(shù)據(jù)范圍】 對(duì)于 30%的數(shù)據(jù)有 N≤15。 對(duì)于 70%的數(shù)據(jù)有 N≤2000，M≤50000。 對(duì)于 100%的數(shù)據(jù)有 N≤20000，M≤100000。 **【結(jié)題報(bào)告】 一開(kāi)始看到題里面給出的圖還以為是圖論，感覺(jué)像是怎么割圖的問(wèn)題，一時(shí)間被嚇到了，所以直接就輸出了零不厚道地騙了十分。 其實(shí)可以用并查集來(lái)解決。 算法思路其實(shí)不難理解，大概就是 先將所有的仇恨值從大到小排個(gè)序，然后把每一組分別往兩個(gè)監(jiān)獄里面放， 直到出現(xiàn)沖突的那個(gè)就是最大值，如果一直沒(méi)有沖突就輸出零。**

代碼如下

4.引水入城 (flow.pas/c/cpp） 【問(wèn)題描述】 在一個(gè)遙遠(yuǎn)的國(guó)度，一側(cè)是風(fēng)景秀美的湖泊，另一側(cè)則是漫無(wú)邊際的沙漠。該國(guó)的行政區(qū)劃十分特殊，剛好構(gòu)成一個(gè) N行 M 列的矩形，如上圖所示，其中每個(gè)格子都代表一座城市，每座城市都有一個(gè)海拔高度。 為了使居民們都盡可能飲用到清澈的湖水，現(xiàn)在要在某些城市建造水利設(shè)施。水利設(shè)施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第 1 行的城市可以建造蓄水廠。而輸水站的功能則是通過(guò)輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經(jīng)建有水利設(shè)施。 由于第 N 行的城市靠近沙漠，是該國(guó)的干旱區(qū)，所以要求其中的每座城市都建有水利設(shè)施。那么，這個(gè)要求能否滿足呢？如果能，請(qǐng)計(jì)算最少建造幾個(gè)蓄水廠；如果不能，求干旱區(qū)中不可能建有水利設(shè)施的城市數(shù)目。 【輸入】 輸入文件名為 flow.in。輸入文件的每行中兩個(gè)數(shù)之間用一個(gè)空格隔開(kāi)。 輸入的第一行是兩個(gè)正整數(shù) N和 M，表示矩形的規(guī)模。 接下來(lái) N行，每行 M 個(gè)正整數(shù)，依次代表每座城市的海拔高度。 【輸出】 輸出文件名為 flow.out。 輸出有兩行。如果能滿足要求，輸出的第一行是整數(shù) 1，第二行是一個(gè)整數(shù)，代表最少建造幾個(gè)蓄水廠；如果不能滿足要求，輸出的第一行是整數(shù) 0，第二行是一個(gè)整數(shù)，代表有幾座干旱區(qū)中的城市不可能建有水利設(shè)施。 **【解題報(bào)告】 一開(kāi)始以為是DP+貪心什么的，沒(méi)什么思路，所以特判了第四個(gè)n==1的點(diǎn)，又不厚道地騙了十分。 其實(shí)可以證明以某城市為蓄水池，能夠覆蓋到的沙漠城市一定是連續(xù)的。 這樣就可以用BFS先得到以每一個(gè)海濱城市蓄水能覆蓋到的沙漠城市的區(qū)域（DFS會(huì)暴棧）， 然后DP解決區(qū)間覆蓋問(wèn)題就行了。**

代碼如下

2017.2.18測(cè)試