**
全國信息學奧林匹克聯(lián)賽（NOIP2010）復(fù)賽
提高組
1．機器翻譯 (translate. pas/c/cpp) 【問題描述】 小晨的電腦上安裝了一個機器翻譯軟件， 他經(jīng)常用這個軟件來翻譯英語文章。 這個翻譯軟件的原理很簡單， 它只是從頭到尾， 依次將每個英文單詞用對應(yīng)的中文含義來替換。 對于每個英文單詞， 軟件會先在內(nèi)存中查找這個單詞的中文含義， 如果內(nèi)存中有，軟件就會用它進行翻譯； 如果內(nèi)存中沒有， 軟件就會在外存中的詞典內(nèi)查找， 查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內(nèi)存，以備后續(xù)的查找和翻譯。 假設(shè)內(nèi)存中有 M個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內(nèi)存前， 如果當前內(nèi)存中已存入的單詞數(shù)不超過 M?1， 軟件會將新單詞存入一個未使用的內(nèi)存單元； 若內(nèi)存中已存入 M個單詞， 軟件會清空最早進入內(nèi)存的那個單詞， 騰出單元來，存放新單詞。 假設(shè)一篇英語文章的長度為 N個單詞。給定這篇待譯文章， 翻譯軟件需要去外存查找多少次詞典？假設(shè)在翻譯開始前， 內(nèi)存中沒有任何單詞。
【輸入】 輸入文件名為 translate.in， 輸入文件共2行。 每行中兩個數(shù)之間用一個空格隔開。 第一行為兩個正整數(shù) M和 N， 代表內(nèi)存容量和文章的長度。 第二行為 N個非負整數(shù)，按照文章的順序，每個數(shù)（大小不超過1000）代表一個英文單詞。 文章中兩個單詞是同一個單詞， 當且僅當它們對應(yīng)的非負整數(shù)相同。
【輸出】 輸出文件translate.out共1行，包含一個整數(shù)，為軟件需要查詞典的次數(shù)。
還算挺簡單的一道題，大概的思路就是用一個循環(huán)隊列模擬這個過程：記錄內(nèi)存最大值m，定義存儲指針（其實就是個變量）K，判斷只要K>=m就將K歸一，其他情況下就只需要判斷某個單詞是否在隊列里（用bool型），在，就跳過，不在，就加入隊列（注意要將原位置的單詞覆蓋，對應(yīng)單詞的bool型也要設(shè)為false）。有一點要注意，就是隊列初始化要用-1，因為如果有單詞為0的話會有bug。
比較簡單就不附代碼了。
2．烏龜棋 (tortoise. pas/c/cpp) 【問題描述】 小明過生日的時候， 爸爸送給他一副烏龜棋當作禮物。 烏龜棋的棋盤是一行N個格子，每個格子上一個分數(shù)（非負整數(shù)）。棋盤第1格是唯一的起點， 第 N格是終點， 游戲要求玩家控制一個烏龜棋子從起點出發(fā)走到終點。
……
1 2 3 4 5 …… N 烏龜棋中 M張爬行卡片， 分成4種不同的類型（M張卡片中不一定包含所有4種類型的卡片，見樣例），每種類型的卡片上分別標有1、2、3、4四個數(shù)字之一，表示使用這種卡片后， 烏龜棋子將向前爬行相應(yīng)的格子數(shù)。 游戲中， 玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進相應(yīng)的格子數(shù)，每張卡片只能使用一次。游戲中，烏龜棋子自動獲得起點格子的分數(shù)，并且在后續(xù)的爬行中每到達一個格子，就得到該格子相應(yīng)的分數(shù)。玩家最終游戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的 分數(shù)總和。 很明顯， 用不同的爬行卡片使用順序會使得最終游戲的得分不同， 小明想要找到一種卡片使用順序使得最終游戲得分最多。 現(xiàn)在，告訴你棋盤上每個格子的分數(shù)和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？
【輸入】 輸入文件名 tortoise.in。 輸入文件的每行中兩個數(shù)之間用一個空格隔開。 第1行2個正整數(shù) N和 M， 分別表示棋盤格子數(shù)和爬行卡片數(shù)。 第2行 N個非負整數(shù)， a1, a2, ……, aN， 其中 ai表示棋盤第 i個格子上的分數(shù)。 第3行 M個整數(shù)， b1,b2, ……, bM， 表示 M張爬行卡片上的數(shù)字。 M 輸入數(shù)據(jù)保證到達終點時剛好用光 M張爬行卡片， 即 N?1=∑ bi。 1
【輸出】 輸出文件名 tortoise.out。
【數(shù)據(jù)范圍】 對于30%的數(shù)據(jù)有1≤ N≤30， 1≤ M≤12。 對于50%的數(shù)據(jù)有1≤N≤120， 1≤ M≤50， 且4種爬行卡片， 每種卡片的張數(shù)不會超過20。 對于100%的數(shù)據(jù)有1≤N≤350，1≤M≤120，且4種爬行卡片，每種卡片的張數(shù)不會超過40； 0≤ai≤100，1≤i≤N；1≤bi≤4，1≤i≤M。輸入數(shù)據(jù)保證N?1=∑bi。
一道DP題，開始做的時候想得太簡單了，就開了個一維的DP數(shù)組，后來覺得不對，又開成二維…….再想想？………開三維…….發(fā)現(xiàn)三維都不夠，模擬了一下發(fā)現(xiàn)狀態(tài)有點多，以為是一個狀壓DP，看見數(shù)據(jù)這么大有點虛,就硬生生地寫了一個“狀壓記憶化搜索”…..最后還沒調(diào)出來，U盤中毒文件掉了就不放記憶化搜索了，放一個DP正解吧。
其實我考慮的狀態(tài)多是對的，不過沒有狀壓那么多。 首先我們要開一個四維數(shù)組 f[x1][x2][x3][x4]來保存所得的分數(shù)。 為什么呢？看題：有四種卡片，保證所有卡片用完就能到終點，且每種卡片不超過40張。很明顯，只要枚舉每一種卡片的組合就能覆蓋每一種情況，在其中挑選最優(yōu)解，最后輸出就行了。
附上偽代碼：
f[0][0][0][0] = sc[1]; for( int l1 = 0; l1 <= cnt[1]; l1++ ) for( int l2 = 0; l2 <= cnt[2]; l2++ ) for( int l3 = 0; l3 <= cnt[3]; l3++ ) for( int l4 = 0; l4 <= cnt[4]; l4++ ) { int pos = l1 + 2 * l2 + 3 * l3 + 4 * l4 + 1; if( l1 ) f[l1][l2][l3][l4] = max( f[l1-1][l2][l3][l4] + sc[pos], f[l1][l2][l3][l4] ); if( l2 ) f[l1][l2][l3][l4] = max( f[l1][l2-1][l3][l4] + sc[pos], f[l1][l2][l3][l4] ); if( l3 ) f[l1][l2][l3][l4] = max( f[l1][l2][l3-1][l4] + sc[pos], f[l1][l2][l3][l4] ); if( l4 ) f[l1][l2][l3][l4] = max( f[l1][l2][l3][l4-1] + sc[pos], f[l1][l2][l3][l4] ); }四個for循環(huán)枚舉卡片組合，每枚舉一次挑選最優(yōu)值，在加上跳到的地方的分數(shù)就行了。（sc保存每個格子的分值）
3．關(guān)押罪犯 (PRison. pas/c/cpp) 【問題描述】 S城現(xiàn)有兩座監(jiān)獄，一共關(guān)押著 N名罪犯，編號分別為1~N。他們之間的關(guān)系自然也極 不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時可能爆發(fā)沖突。我們用“怨氣值”（一個正整數(shù)值）來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為 c的罪犯被關(guān)押在同一監(jiān)獄，他們倆之間會發(fā)生摩擦，并造成影響力為 c的沖突事件。 每年年末， 警察局會將本年內(nèi)監(jiān)獄中的所有沖突事件按影響力從大到小排成一個列表，然后上報到 S城 Z市長那里。 公務(wù)繁忙的 Z市長只會去看列表中的第一個事件的影響力，如果影響很壞，他就會考慮撤換警察局長。 在詳細考察了 N名罪犯間的矛盾關(guān)系后， 警察局長覺得壓力巨大。他準備將罪犯們在兩座監(jiān)獄內(nèi)重新分配， 以求產(chǎn)生的沖突事件影響力都較小， 從而保住自己的烏紗帽。假設(shè)只要處于同一監(jiān)獄內(nèi)的某兩個罪犯間有仇恨， 那么他們一定會在每年的某個時候發(fā)生摩擦。 那么，應(yīng)如何分配罪犯，才能使 Z市長看到的那個沖突事件的影響力最小？這個最小值是多少？
【輸入】 輸入文件名為 prison.in。 輸入文件的每行中兩個數(shù)之間用一個空格隔開。第一行為兩個正整數(shù) N和 M， 分別表示罪犯的數(shù)目以及存在仇恨的罪犯對數(shù)。接下來的 M行每行為三個正整數(shù) aj， bj， cj，表示 aj號和 bj號罪犯之間存在仇恨，其怨氣值為 cj。 【輸出】 輸出文件 prison.out共1行， 為 Z市長看到的那個沖突事件的影響力。如果本年內(nèi)監(jiān)獄中未發(fā)生任何沖突事件，請輸出 0。
【數(shù)據(jù)范圍】 對于30%的數(shù)據(jù)有 N≤15。 對于70%的數(shù)據(jù)有 N≤2000， M≤50000。 對于100%的數(shù)據(jù)有N≤20000， M≤100000。
一開始想得有些復(fù)雜，打算用Kruskal找到最小生成樹再刪邊。 如樣例圖， 找到 1-> 4-> 2-> 3 是一顆最小生成樹，然后由定義知最小生成樹就是一條鏈，就O（n）枚舉每一條邊，看刪哪條使得剩下的兩部分最大沖突最小。
…….非常復(fù)雜，160多行，沒調(diào)出來…..
……Kruskal…….
void kruskal(){ memset( exi, false, sizeof(exi)); sort( able+1, able+tail+1, cmp ); for( int i = 1; i <= numm; i++ ) fa[pers[i]] = pers[i]; st = edg[able[1]].from; exi[st] = true; for( int i = 1; i <= numm-1; i++ ) { int x = edg[able[i]].from, y = edg[able[i]].dest; if( getfa[x] != getfa[y] ) { chois[++cnt] = able[i]; fa[y] = fa[x]; exi[edg[i].dest] = true; } }}然后發(fā)現(xiàn)一個問題…..如果不連通呢？趕緊加了一個DFS判連同，順便把同一個連通分量里的點和邊加進數(shù)組pers 和 able…… DFS……
void dfs_way( int u, int f ){ for( int i = head[u]; i; i = poin[i].last ) { int v = edg[i].dest; if( v == f ) continue; pers[++numm] = v; able[++tail] = stat[v]; vis[v] = true; dfs_way( v, u ); }}邊表+鄰接表……
struct rod{ int dest, from, hat; rod() { dest = from = hat = 0; }} edg[maxx<<1];int ppoi = 0, head[maxn], taill = 0;struct usea{ int dest, last, hatt;} poin[maxx<<1];void addpoin( int x, int y, int z ){ ppoi++; poin[ppoi].dest = y; poin[ppoi].last = ppoi; poin[ppoi].hatt = z; head[x] = ppoi;}int num = 0;int able[maxx<<1], tail = 0, pers[maxn], numm = 0, chois[maxn], cnt = 0, stat[maxn];void adde( int x, int y, int w ){ num++; edg[num].dest = y; edg[num].from = x; edg[num].hat = w; stat[x] = numm; stat[y] = numm;}DFS算鏈的前綴和（還要先找出這條鏈的頭和尾，超麻煩啊啊啊）
void dfs( int u, int tot, int f ){ if( tot == numm ) return; for( int i = head[u]; i; i = poin[i].last ) { int v = poin[i].dest; if( v == f || !exi[v] ) continue; dis[v] = dis[u] + poin[i].hatt; point[++cntt] = v; dfs( v, tot+1, u ); }}最后計算鏈上最大值……
long long minhat(){ long long res = 0x7fffffff; for( int i = 1; i <= cntt-1; i++ ) { res = minn( res, dis[i] + dis[cntt] - dis[i+1] ); } return res;}最后在main函數(shù)里加上操作…
for( int i = 1; i <= n; i++ ) { if( !vis[i] ) { u = i; vis[u] = true; pers[++numm] = u; dfs_way( u, 0 ); kruskal(); dis[st] = 0; point[++cntt] = st; dfs( st, 1, 0 ); ress += minhat(); } }編完了一次編譯通過那個興奮…..然后發(fā)現(xiàn)…..它要的是兩人之間最大沖突值…….當時就崩潰了…. 
最后評講的時候講的是并查集……核心代碼不到15行….. 有種想砸電腦的沖動，但是是學校的電腦…..沒辦法，接受現(xiàn)實。
接下來講一下正解：
因為要求的是兩人之間沖突最大值，所以我們可以將犯人組合按沖突大小排序 然后從大到小拆散他們——也就是將他們放在不同的監(jiān)獄。就這樣一組一組地拆，拆到有一組已經(jīng)在同一個監(jiān)獄了，就輸出他們的沖突值。為什么這是對的呢？假設(shè)我們不拆這一組，而是繼續(xù)將他們放在不同的監(jiān)獄，到么導(dǎo)致的后果是——之所以他們在一個監(jiān)獄，是因為他們其中的至少一個人與另外一個監(jiān)獄的人有更大的沖突，如果將他們放回去，肯定會使沖突值變大（先放的組合沖突值一定大于后放的組合），所以只能將他們放在一起，又得知后面任意一組的沖突值不會高于這一組，因此得出這一組的沖突值即為最大值，故輸出。（注意，如果全部分完了還沒有出現(xiàn)要輸出的情況，一定要輸出0）
附上代碼：
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxx = 100005;const int maxn = 20005;int n, m, num = 0, fa[maxn*2];struct rod//存組{ int x, y, hat;} pai[maxx];int cmp( const rod & a, const rod & b )//sort{ if( a.hat < b.hat ) return 0; return 1;}int getfa( int a )//并查集{ if( fa[a] == a ) return a; return fa[a] = getfa( fa[a] );}int solve()//核心{ for( int i = 1; i <= m; i++ ) { int far = getfa( pai[i].x ), fbr = getfa( pai[i].y ); if( far == fbr ) return pai[i].hat; fa[far] = getfa( pai[i].y + n ); fa[fbr] = getfa( pai[i].x + n ); } return 0;}int main(){ freopen( "prison.in", "r", stdin ); freopen( "prison.out", "w", stdout ); cin>>n>>m; for( int i = 1; i <= m; i++ ) { int x, y, hat; scanf( "%d%d%d", &x, &y, &hat ); pai[i].x = x; pai[i].y = y; pai[i].hat = hat; } for( int i = 1; i <= 2*n; i++ ) fa[i] = i; sort( pai+1, pai+m+1, cmp ); printf( "%d/n", solve() ); return 0;}4 .引水入城 (flow. pas/c/cpp)
【問題描述】 湖泊
沙漠 在一個遙遠的國度，一側(cè)是風景秀美的湖泊，另一側(cè)則是漫無邊際的沙漠。該國的行政區(qū)劃十分特殊， 剛好構(gòu)成一個 N行 M列的矩形， 如上圖所示， 其中每個格子都代表一座城市， 每座城市都有一個海拔高度。 為了使居民們都盡可能飲用到清澈的湖水， 現(xiàn)在要在某些城市建造水利設(shè)施。 水利設(shè)施有兩種， 分別為蓄水廠和輸水站。 蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差， 將湖水從高處向低處輸送。 故一座城市能建造輸水站的前提， 是存在比它海拔更高且擁有公共邊的相鄰城市， 已經(jīng)建有水利設(shè)施。 由于第 N行的城市靠近沙漠， 是該國的干旱區(qū)， 所以要求其中的每座城市都建有水利 設(shè)施。那么，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求干旱區(qū)中不可能建有水利設(shè)施的城市數(shù)目 。
【輸入】 輸入文件名為 flow.in。 輸入文件的每行中兩個數(shù)之間用一個空格隔開。 輸入的第一行是兩個正整數(shù) N和 M， 表示矩形的規(guī)模。 接下來 N行， 每行 M個正整數(shù)， 依次代表每座城市的海拔高度。
【輸出】 輸出文件名為 flow.out。 輸出有兩行。如果能滿足要求，輸出的第一行是整數(shù)1，第二行是一個整數(shù)，代表最少建造幾個蓄水廠；如果不能滿足要求，輸出的第一行是整數(shù)0，第二行是一個整數(shù)，代表有幾座干旱區(qū)中的城市不可能建有水利設(shè)施。
這道題其實不是很難。根據(jù)題意，只需要覆蓋完沿沙漠的一排城市就可以了，所以我們先用BFS算出每一個沿海的城市建造蓄水池可以覆蓋多長的沙漠城市，在區(qū)間覆蓋DP算出怎樣用最少的城市覆蓋完沙漠城市。（注意最好用BFS，DFS有坑…）
BFS：
void bfs( int stx, int sty ){ memset( vis, false, sizeof(vis)); int sitx[maxx*maxx], sity[maxx*maxx]; int k1 = 0, k2 = 1; sitx[1] = stx; sity[1] = sty; vis[stx][sty] = true; do { k1++; for( int i = 1; i <= 4; i++ ) { int nx = sitx[k1] + xx[i], ny = sity[k1] + yy[i]; if( nx > n || nx < 1 || ny > m || ny < 1 ) continue; if( map[sitx[k1]][sity[k1]] <= map[nx][ny] ) continue; vis[nx][ny] = true, vv[nx][ny] = true; k2++; sitx[k2] = nx, sity[k2] = ny; } }while( k1 < k2 ); int lf = 0, rg = 0; for( int i = 1; i <= m; i++ ) if( vis[n][i] ){lf = i; break;} for( int i = m; i >= 1; i-- ) if( vis[n][i] ){rg = i; break;} /*if( lf && rg ) */peri[++num].x = lf, peri[num].y = rg;}記得每次BFS前都要重置vis數(shù)組，全局還要有一個vv數(shù)組判斷能不能被完全覆蓋。 寫這個只得了70分，應(yīng)該是DP寫錯了就不附代碼了……
總之考試時讀題太重要了，一定要 細心讀題，用心想題，專心寫題，耐心改題。
新聞熱點
疑難解答
