NOIP2010提高組復賽試題及解題報告

NOIP2010提高組復賽試題及解題報告1．機器翻譯

(translate.pas/c/cpp)【問題描述】小晨的電腦上安裝了一個機器翻譯軟件，他經常用這個軟件來翻譯英語文章。這個翻譯軟件的原理很簡單，它只是從頭到尾，依次將每個英文單詞用對應的中文含義來替換。對于每個英文單詞，軟件會先在內存中查找這個單詞的中文含義，如果內存中有，軟件就會用它進行翻譯；如果內存中沒有，軟件就會在外存中的詞典內查找，查出單詞的中文含義然后翻譯，并將這個單詞和譯義放入內存，以備后續(xù)的查找和翻譯。假設內存中有M個單元，每單元能存放一個單詞和譯義。每當軟件將一個新單詞存入內存前，如果當前內存中已存入的單詞數不超過M-1,軟件會將新單詞存入一個未使用的內存單元；若內存中已存入M個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，存放新單詞。假設一篇英語文章的長度為N個單詞。給定這篇待譯文章，翻譯軟件需要去外存查找多少次詞典？假設在翻譯開始前，內存中沒有任何單詞?！据斎搿枯斎胛募麨閠ranslated，輸入文件共2行。每行中兩個數之間用一個空格隔開。第一行為兩個正整數M和N，代表內存容量和文章的長度。第二行為N個非負整數，按照文章的順序，每個數(大小不超過1000)代表一個英文單詞。文章中兩個單詞是同一個單詞，當且僅當它們對應的非負整數相同?！据敵觥枯敵鑫募ranslate.out共1行，包含一個整數，為軟件需要查詞典的次數?！据斎胼敵鰳永?】ranstate.out3751215441【輸入輸出樣例1說明】整個查字典過程如下：每行表示一個單詞的翻譯，冒號前為本次翻譯后的內存狀況：空：內存初始狀態(tài)為空。1：查找單詞1并調入內存。12：查找單詞2并調入內存。12：在內存中找到單詞1。125：查找單詞5并調入內存。254：查找單詞4并調入內存替代單詞1。254：在內存中找到單詞4。541：查找單詞1并調入內存替代單詞2。共計查了5次詞典?！据斎胼敵鰳永?】ranslate.out210882411781178117882646【數據范圍】對于10%的數據有M=1,N<5o對于100%的數據有02.烏龜棋

（tortoise.pas/c/cpp）【問題描述】小明過生日的時候，爸爸送給他一副烏龜棋當作禮物。烏龜棋的棋盤是一行N個格子，每個格子上一個分數（非負整數）。棋盤第1格是唯A的起點，第N格是終點，游戲要求玩家控制一個烏龜棋子從起點出發(fā)走到終點。烏龜棋中M張爬行卡片，分成4種不同的類型（乂張卡片中不一定包含所有4種類型的卡片，見樣例），每種類型的卡片上分別標有1、2、3、4四個數字之一，表示使用這種卡片后，烏龜棋子將向前爬行相應的格子數。游戲中，玩家每次需要從所有的爬行卡片中選擇一張之前沒有使用過的爬行卡片，控制烏龜棋子前進相應的格子數，每張卡片只能使用一次。游戲中，烏龜棋子自動獲得起點格子的分數，并且在后續(xù)的爬行中每到達一個格子，就得到格子相應的分數。玩家最終游戲得分就是烏龜棋子從起點到終點過程中到過的所有格子的分數總和。很明顯，用不同的爬行卡片使用順序會使得最終游戲的得分不同，小明想要找到一種卡片使用順序使得最終游戲得分最多?，F在，告訴你棋盤上每個格子的分數和所有的爬行卡片，你能告訴小明，他最多能得到多少分嗎？【輸入】輸入文件名tortoise.in。輸入文件的每行中兩個數之間用一個空格隔開。第1行2個正整數N和M,分別表示棋盤格子數和爬行卡片數。第2行N個非負整數，a1,a2,……,aN,其中ai表示棋盤第i個格子上的分數。第3行M個整數，b1,b2,……，bM,表示M張爬行卡片上的數字。【輸出】輸出文件名tortoise.out。輸出只有1行，1個整數，表示小明最多能得到的分數。【輸入輸出樣例1】ortoise.out9561014288185171312173【輸入輸出樣例1說明】小明使用爬行卡片順序為1，1，3，1，2，得到的分數為6+10+14+8+18+17=73。注意，由于起點是1，所以自動獲得第1格的分數6?！据斎胼敵鰳永?】ortoise.out1384961064551394535248983045511111241【數據范圍】對于30%的數據有1N301M12對于50%的數據有1N1201M50且4種爬行卡片，每種卡片的張數不會超過20。對于100%的數據有1N3501M120且4種爬行卡片，每種卡片的張數不會超過40；0ai1001iN1bi41iM.關押罪犯(prison.pas/c/cpp)【問題描述】S城現有兩座監(jiān)獄，一共關押著N名罪犯，編號分別為1~N。他們之間的關系自然也極不和諧。很多罪犯之間甚至積怨已久，如果客觀條件具備則隨時可能爆發(fā)沖突。我們用怨氣值(一個正整數值)來表示某兩名罪犯之間的仇恨程度，怨氣值越大，則這兩名罪犯之間的積怨越多。如果兩名怨氣值為c的罪犯被關押在同一監(jiān)獄，他們倆之間會發(fā)生摩擦，并造成影響力為c的沖突事件。每年年末，警察局會將本年內監(jiān)獄中的所有沖突事件按影響力從大到小排成一個列表，然后上報到S城Z市長那里。公務繁忙的Z市長只會去看列表中的第一個事件的影響力，如果影響很壞，他就會考慮撤換警察局長。在詳細考察了N名罪犯間的矛盾關系后，警察局長覺得壓力巨大。他準備將罪犯們在兩座監(jiān)獄內重新分配，以求產生的沖突事件影響力都較小，從而保住自己的烏紗帽。假設只要處于同一監(jiān)獄內的某兩個罪犯間有仇恨，那么他們一定會在每年的某個時候發(fā)生摩擦。那么，應如何分配罪犯，才能使Z市長看到的那個沖突事件的影響力最小？這個最小值是多少？【輸入】輸入文件名為prison.in。輸入文件的每行中兩個數之間用一個空格隔開。第一行為兩個正整數N和M,分別表示罪犯的數目以及存在仇恨的罪犯對數。接下來的M行每行為三個正整數aj,bj,cj,表示aj號和bj號罪犯之間存在仇恨，其怨氣值為cj。數據保證1aj【輸出】輸出文件prison.out共1行，為Z市長看到的那個沖突事件的影響力。如果本年內監(jiān)獄中未發(fā)生任何沖突事件，請輸出0【輸入輸出樣例】prison.inprison.out46142534351223351212283511366182418053412884【輸入輸出樣例說明】罪犯之間的怨氣值如下面左圖所示，右圖所示為罪犯的分配方法，市長看到的沖突事件影響力是3512(由2號和3號罪犯引發(fā))。其他任何分法都不會比這個分法更優(yōu)。【數據范圍】對于30%的數據有N15。對于70%的數據有N2000,M50000。對于100%的數據有N20000,M100000。.引水入城

(flow.pas/c/cpp)【問題描述】在一個遙遠的國度，一側是風景秀美的湖泊，另一側則是漫無邊際的沙漠。該國的行政區(qū)劃十分特殊，剛好構成一個N行M列的矩形，如上圖所示，其中每個格子都代表一座城市，每座城市都有一個海拔高度。為了使居民們都盡可能飲用到清澈的湖水，現在要在某些城市建造水利設施。水利設施有兩種，分別為蓄水廠和輸水站。蓄水廠的功能是利用水泵將湖泊中的水抽取到所在城市的蓄水池中。因此，只有與湖泊毗鄰的第1行的城市可以建造蓄水廠。而輸水站的功能則是通過輸水管線利用高度落差，將湖水從高處向低處輸送。故一座城市能建造輸水站的前提，是存在比它海拔更高且擁有公共邊的相鄰城市，已經建有水利設施。由于第N行的城市靠近沙漠，是該國的干旱區(qū)，所以要求其中的每座城市都建有水利設施。那么，這個要求能否滿足呢？如果能，請計算最少建造幾個蓄水廠；如果不能，求干旱區(qū)中不可能建有水利設施的城市數目?！据斎搿枯斎胛募麨槭病４?^。輸入文件的每行中兩個數之間用一個空格隔開。輸入的第一行是兩個正整數N和M，表示矩形的規(guī)模。接下來N行，每行M個正整數，依次代表每座城市的海拔高度?！据敵觥枯敵鑫募麨閒low.out。輸出有兩行。如果能滿足要求，輸出的第一行是整數1,第二行是一個整數，代表最少建造幾個蓄水廠；如果不能滿足要求，輸出的第一行是整數0，第二行是一個整數，代表有幾座干旱區(qū)中的城市不可能建有水利設施?！据斎胼敵鰳永?】flow.inflow.out25915431876121【樣例1說明】只需要在海拔為9的那座城市中建造蓄水廠，即可滿足要求。【輸入輸出樣例2】flow.inflow.out3684564417343333322112【樣例2說明】上圖中，在3個粗線框出的城市中建造蓄水廠，可以滿足要求。以這3個蓄水廠為源頭在干旱區(qū)中建造的輸水站分別用3種顏色標出。當然，建造方法可能不唯一。NOIP2010解題報告首先對這次比賽做一個總體分析。第一題我覺得沒什么好說的，作為一道簡單題還是挺簡單的。第二題是動態(tài)規(guī)劃，樸素的做法可以得到30-50分，如果發(fā)現了方程中的一個小優(yōu)化并且穩(wěn)穩(wěn)當當地作對，可以拿到滿分。第三題暴力搜索可以拿到30分。如果想得到滿分，首先要想到二分答案，可能多數同學沒有想到這個方向上，再驗證是否是二分圖，通過BFS實現，就可以拿到滿分了。第三題還有一個并查集的方法也可以做。第四題確實較難，首先通過BFS判斷無解的情況，可以拿到30分，而對于有解的情況，需要仔細分析，得出一個重要結論,之后用到BFS和Dp可以拿到滿分。下面我將逐題進行分析第一題：（由于是NOIP，這道題的題解我就給個時間復雜度高一點但是好理解的吧，大牛們忽略此題題解）我們用一個a數組維護當前內存存儲的單詞，并且從1到m的位置就是單詞進入內存的先后順序。一開始內存是空的，所以所有位置上都是-1。我們順序操作文章中的n個單詞，對于每個單詞，我們都查找它當前是否在內存中。若它在內存中，直接忽略過去；若它不在內存中，就需要把內存的2~m位置上的單詞往前挪（挪到1~m-1處），并把新的這個單詞放到m處，并把答案類加1。最后輸出答案即可。第二題：我們的任務是用給定的卡片從1走到n，最終得分最大。動態(tài)規(guī)劃的味道似乎挺濃的，于是嘗試一下。動態(tài)規(guī)劃首先要用變量來表示出狀態(tài)。若要表示當前狀態(tài)，需要用的變量是：當前位置、當前還剩余哪些卡片。當前位置很好記錄，一個變量i即可。而當前還剩余哪些卡片似乎并不好記錄。但仔細觀察數據規(guī)模就會發(fā)現，卡片上的數值只會是1、2、3、4，并且每種不會超過40張，這樣我們可以用4個變量j1、j2、j3、j4也可以記錄了。而我們仔細觀察就會發(fā)現，這5個變量存在一個恒等式：i+j1+j2*2+j3*3+j4*4=n，也就是說其中一個可以通過另外四個推出來。于是我們只需要4個變量（j1,j2,j3,j4）就可以表示出當前的狀態(tài)了。我們另F[j1,j2,j3,j4]表示剩余j1張1卡片、剩余j2張2卡片、剩余j3張3卡片，剩余j4張4卡片，走到n的最大得分。而轉移成子問題似乎也很顯然：F[j1,j2,j3,j4]=a[n-j1+j2*2+j3*3+j4*4]+max（F[j1-1,j2,j3,j4]F[j1,j2-1,j3,j4]F[j1,j2,j3-1,j4]F[j1,j2,j3,j4-1]）邊界F[0,0,0,0]=a[n]。所求為F[m1,m2,m3,m4]。時間復雜度：O（p八4）其中p為題目給定的每種卡片不超過40第三題：這道題是一個明顯的“最大值最小”問題。解釋一下，就是讓你找出一個分配方案，使得所有沖突中的最大值盡量的小。“最大值最小”問題99%都可以用二分答案來做。再具體解釋一下：如果最后最小的最大沖突為ans。對于一個在區(qū)間[0,ans）的數k，一定不滿足命題所有沖突值都小于等于k,而對于一個在區(qū)間[ans,1000000000]的數k，一定滿足命題所有沖突值都小于等于k”這就好比是一個猜價格的游戲，你猜一個價格，我告訴你高了還是低了，如果高了你就往低猜，如果低了你就往高猜。而這道題是你猜一個k，根據它滿足命題還是不滿足命題決定再大點還是再小點。當然，最快的方法就是在區(qū)間[0,1000000000]上二分這個k。那接下來我們的任務就變成了，驗證一個k，是否能滿足命題所有沖突都小于等于k”而這個命題等價于所有沖突值大于k的兩個犯人必須被關押在不同的監(jiān)獄”那么通過BFS染色就可以判斷。時間復雜度：O（M*log（10人9））對于另一做法，需要一個更高級的知識——并查集。這里簡單說說。首先把所有沖突按照從大到小進行排序，然后進行操作。我們都檢驗，對于當前沖突的兩個人是否能把他倆分開。直到遇到兩個人，他倆不可能被分開（如果分開了就跟前面沖突了），那他倆的沖突度就是最后的答案了。而利用并查集可以維護已知的一些人的關系。時間復雜度：O（MlogM）第四題：這道題個人認為出的不錯。首先判斷是否有解。判斷方法很簡單：假設靠水庫的所有城市（（1,1）~（1,m））都建造水泵，判斷是否能覆蓋所有靠沙漠的城市。如果無解就順便輸出不能覆蓋的個數。這些都能通過一次BFS實現，時間復雜度O（N*M）。接下來考慮有解的情況。我就順著我考場上的思路說吧。我首先想到，能否通過一個預處理，求出：（1）對于單獨在每個靠水庫的城市（1,i）修建水泵，求出它能覆蓋到的靠沙漠的城市的**Ai。然后再考慮：（2）通過最少個數的Ai，使得它們的并集覆蓋1~n。面對這兩個問題，我同時進行思考，首先第一個問題N八3可以解決，N八2似乎沒有更好方法，但也勉強接受，畢竟夠90分了。面對第二個問題，嘗試往網絡流方向想，試圖構建最小割模型，可似乎沒什么進展。此時我仔細看了下第二個問題，發(fā)現它是NP問題！道理很簡單，我們把每個靠水庫的城市當做一個Boolean型變量Ri,建就是TRUE,不建就是FALSE。把每個靠沙漠的城市當做一個表達式，如果這個城市出現在某幾個水庫的**中，例如Ai、Aj、Ak、Ap、Aq中，那么這個表達式就是RiORjORkORpORq”我們的目的是滿足所有表達式。顯然這是一個多sat問題，而多sat問題是NP問題。(這段完全是思路,看不懂的就忽略過去)從而我們得出一個結論：這個圖、這個問題肯定有它的特殊性！究竟是什么特殊性呢？經過我的觀察,我大膽預測一個結論：如果某個靠水庫的城市構建水泵,它能覆蓋的Ai一定是連續(xù)的一段！(如果不是連續(xù)一段必然無解)道理很簡單：|<O--->|||||>X<例如，出現這樣一個靠水庫的城市O,它覆蓋的不是連續(xù)一段區(qū)間，即中間有一個或多個X。由于O到X的兩條路海拔高度都是嚴格遞降的(如箭頭方向)。也就是說，在這個環(huán)上無法找到一個點到X的路徑