信息學奧賽試題精選33題(附帶題解)重點

1、第110題為基礎題，第1120題為提高題，第2133為綜合題注：因為在本文檔中需要用到一些特殊的數(shù)學符號（如：求和號、分數(shù)等），所以當您在百 度文庫中瀏覽時，一些數(shù)學符號可能會顯示不出來，不過當您把本文檔下載下來在本地瀏覽 時，所有的符號即可全部都顯示出來。A_A基礎題：【1 Prime Freque ncy 】【問題描述】給出一個僅包含字母和數(shù)字（0-9, A-Z以及a-z）的字符串，請您計算頻率（字符 出現(xiàn)的次數(shù)），并僅報告哪些字符的頻率是素數(shù)。輸入: 輸入的第一行給出一個整數(shù)T （ 0VTV201，表示測試用例個數(shù)。后面的T行每行給 出一個測試用例：一個字母-數(shù)字組成的字符串。字符串的長

2、度是小于 2001的一個 正整數(shù)。輸出：對輸入的每個測試用例輸出一行，給出一個輸出序列號，然后給出在輸入的字符串 中頻率是素數(shù)的字符。這些字符按字母升序排列。所謂字母升序”意謂按ASCII值升序排列。如果沒有字符的頻率是素數(shù)，輸出“ empty”（沒有引號）。樣例輸出Case 1: CCase 2: ADCase 3: empty樣例輸入3ABCCAABBBBDDDDDABCDFFFF注:試題來源： Ban gladesh Natio nal Computer Programmi ng Con test在線測試：UVA 10789提示先離線計算出2 - 2200的素數(shù)篩 叩。然后每輸入一個測試

3、串，以 ASCLL碼為下 標統(tǒng)計各字符的頻率p，并按照ASCLL碼遞增的順序(0W i<299)輸出頻率為素 數(shù)的字符(即upi=1且ASCLL碼值為i的字符)。若沒有頻率為素數(shù)的字符， 則輸出失敗信息。【2 Twin Primes 】【問題描述】雙素數(shù)(Twin Primes )是形式為(p, p+2,術語 雙素數(shù)"由Paul St?ckel (1892-1919給出，前 幾個雙素數(shù)是(3, 5, (5, 7, (11, 13, (17, 19, (29, 31, (41,43。在本題中請你給出第S對雙素數(shù)，其中S是輸入中給出的整數(shù)。輸入：輸入小于10001行，每行給出一個整

4、數(shù)S (1 < S < 10000表示雙素數(shù)對的序列編 號。輸入以EOF結束。輸出: 對于輸入的每一行，輸出一行，給出第 S對雙素數(shù)。輸出對的形式為(p1,空格p2, 其中 空格”是空格字符(ASCII 32。本題設定第100000對的素數(shù)小于20000000。樣例輸出(3, 5(5, 7(11, 13(17, 19樣例輸入1234注: 試題來源：Regionals Warmup Contest 2002, Venue: Southeast University, Dhaka, Bangladesh在線測試：UVA 1039410135271013527設雙素數(shù)對序列為ans。其中

5、ansi存儲第i對雙素數(shù)的較小素數(shù)(K i < num)。an s的計算方法如下：使用篩選法計算出2, 20000000的素數(shù)篩叩；按遞增順序枚舉該區(qū)間的每個整數(shù)i :若i和i+2為雙素數(shù)對(ui&&ui+2)，則雙 素數(shù)對序列增加一個元素(an s+nu m=i)。在離線計算出ans的基礎上，每輸入一個編號s,則代表的雙素數(shù)對為(anss, an ss+2?！? Less Prime【問題描述】設n為一個整數(shù)，100E1W 10000請找到素數(shù)x, x wn,使得n-p*x最大，其中p是 整數(shù)，使得 p*xWi<(p+1*Xo輸入：輸入的第一行給出一個整數(shù) M，表

6、示測試用例的個數(shù)。每個測試用例一行，給出一個整數(shù) N, 100WNW 10000輸出：對每個測試用例，輸出一行，給出滿足上述條件的素數(shù)。樣例輸入樣例輸出22033114399614411153820110135277048注：試題來源：III Local Contest in Murcia 2005在線測試：UVA 10852忘;提示要使得n-p*x最大(x為素數(shù)，p為整數(shù)，p*x < *(p+1*X，則x為所有小于n的 素數(shù)中，被n除后余數(shù)最大的一個素數(shù)。由此得出算法：先離線計算出2 - 11111的素數(shù)表su,表長為num。然后每輸入一個整數(shù)n,貝U 枚舉小于n的所有素數(shù)，計算tmp

7、二呼W%細小叩15，滿足條件的素數(shù)即為 對應 tmp=n%suk的素數(shù) suk。【4 Prime Words 】【問題描述】一個素數(shù)是僅有兩個約數(shù)的數(shù)：其本身和數(shù)字1。例如，1,2, 3, 5, 17, 101和10007是素數(shù)。本題輸入一個單詞集合，每個單詞由 a-z以及A-Z的字母組成。每個字母對應一個 特定的值，字母a對應1,字母b對應2,以此類推，字母z對應26;同樣，字母 A對應27,字母B對應28,字母Z對應52。一個單詞的字母的總和是素數(shù)，則這個單詞是素單詞(prime word)。請編寫程序，判定一個單詞是否為素單詞。輸入：輸入給出一個單詞集合，每個單詞一行，有 L個字母，K

8、LW2。輸入以EOF結 束。輸出：如果一個單詞字母的和為素數(shù)，則輸出 “It is a prime word.;否則輸出“It is not a prime word.?！睒永斎霕永敵鯱FRNIt is a prime word.con testIt is not a prime word.AcMIt is not a prime word.注: 試題來源：UFRN-2005 Co ntest 1在線測試：UVA 10924由于字母對應數(shù)字的上限為52,而單詞的長度上限為20,因此我們首先使用篩選 法，離線計算出2 - 1010的素數(shù)素數(shù)篩 叩。然后每輸入一個長度為n的單詞，計算單詞字母對

9、應的數(shù)字和V 舸界1$小S刃，血卜y十27八 fX/ZX= 1若x為2 - 1010中的一個素數(shù)（ux=1 ），則表明該單詞為素單詞；否則該單詞非 素單詞?！? Sum of Differe nt Primes 】【問題描述】一個正整數(shù)可以以一種或多種方式表示為不同素數(shù)的總和。給出兩個正整數(shù)n和k,請您計算將n表示為k個不同的素數(shù)的和會有幾種形式。如果是相同的素數(shù) 集，則被認為是相同的。例如 8可以被表示為3 + 5和5 + 3,但不區(qū)分。如果n和k分別為24和3,答案為2,因為有兩個總和為24的集合2, 3, 19和2, 5, 17，但不存在其他的總和為24的3個素數(shù)的集合。如果n = 24

10、, k = 2,答案是3,因為存在3個集合5,19, 7,17以及11,13。如果n = 2, k = 1,答案是1, 因為只有一個集合2,其總和為2。如果n = 1, k = 1,答案是0,因為1不是素樣例輸入24 324 22 11 14 218 317 117 317 4100 51000 101120 14數(shù)，不能將 計入。如果n = 4, k = 2,答案是0,因為不存在兩個不同素數(shù)的集 合，總和為4。請您編寫一個程序，對給出的n和k,輸出答案。輸入：輸入由一系列的測試用例組成，最后以一個空格分開的兩個0結束。每個測試用例一行，給出以一個空格分開的兩個正整數(shù) n和k。本題設定n &l

11、t; 1120 k < 14輸出：輸出由若干行組成，每行對應一個測試用例，一個輸出行給出一個非負整數(shù)，表示 對相應輸入中給出的n和k有多少答案。本題設定答案小于231。樣例輸出231002101552001028992079324314注: 試題來源：ACM Japan 2006在線測試：POJ 3132, ZOJ 2822, UVA 3619提示設su為2.1200的素數(shù)表；fij為j拆分成i個素數(shù)和的方案數(shù)(K i <14,sui < j <1199。顯然，邊界值 f00=1 o首先，采用篩選法計算素數(shù)表su,表長為num。然后每輸入一對n和k，使用動 態(tài)規(guī)劃方法計

12、算k個不同素數(shù)的和為n的方案總數(shù)：枚舉su表中的每個素數(shù)sui(1 < i < num)按遞減順序枚舉素數(shù)個數(shù)j(j=141:按遞減順序枚舉前j個素數(shù)的和p (p=1199sui):累計sui作為第j個素數(shù)的方案總數(shù)fjp+=fj-1p-sui;最后得出的fkn即為問題解?！? Common Permutati on】【問題描述】給出兩個小寫字母的字符串，a和b,輸出最長的小寫字母字符串x使得存在x的 一個排列，是a的子序列，同時也存在x的一個排列是b的子序列。輸入：輸入有若干行。連續(xù)的兩行組成一個測試用例，也就是說，第1和第2行構成一個測試用例，第3和第4行構成一個測試用例，等等

13、。每個測試用例的第一行是字符 串a，第二行是字符串b。每個字符串一行，至多由1000個小寫字母組成。輸出:對每個測試用例，輸出一行，給出x。如果有若干個x滿足上述要求，選擇按字母 序列第一個。e nw et樣例輸入樣例輸出pretty wome n walki ng dow n the street注: 試題來源： World Finals Warm-up Contest, University of Alberta Local Contest在線測試：UVA 10252試題要求按遞增順序輸出兩串公共字符的排列。計算方法如下：、rr/）,設 S仁a1a2 ,S2= b1b2 。先分別統(tǒng)計S1中

14、各字母的頻率c1i和S2中各字母的頻率c2i（ K i < 26,其中字母 a'對應數(shù)字1,字母b'對應數(shù)字2,，字母z'對應數(shù)字26）。然后計算S1和S2的公共字符的排列：遞增枚舉i（1 < i < 26,若i對應的字母在 S1 和 S2中同時存在（c1i工0） && （c2i工0）,則字母'a'+i在排列中出現(xiàn) k=minc1i，c2i次?！? Anagram 】【問題描述】 給出一個字母的集合，請您編寫一個程序，產生從這個集合能構成的所有可能的單 !詞。例如：給出單詞"abc"，您的程序產生這三

15、個字母的所有不同的組合一一輸出單詞"abc", "acb", "bac", "bca", "cab"和"cba"。程序從輸入中獲取一個單詞，其中的一些字母會出現(xiàn)一次以上。對一個給出的單 詞，程序產生相同的單詞只能一次，而且這些單詞按字母升序排列。輸入：輸入給出若干單詞。第一行給出單詞數(shù)，然后每行給出一個單詞。一個單詞是由A到Z的大寫或小寫字母組成。大寫字母和小寫字母被認為是不同的，每個單詞的 長度小于13。輸出：對輸入中的每個單詞，輸出這個單詞的字母產生的所有不同的單詞。輸出

16、的單詞按 字母升序排列。大寫字母排在相應的小寫字母前，即 A'v'a'v'B'v'b'vv'Z'v'z'。樣例輸入樣例輸出3AabaAbAbaabcaAbacbaabAbAabaAabcacbbacbcacabcba aabc aacb abac abca acab acba baac baca bcaa caab caba cbaa注：試題來源：ACM Southwestern European Regio nal Co ntest 1995在線測試：POJ 1256 , UVA 195提示建立字母與整數(shù)

17、間的對應關系：字母對應0，字母 A對應1;；字母 Z'應50,字母 Z寸應51。為了按照字母升序的要求生成單詞的所有排列，首先將單詞的所有字母轉化為數(shù)字，然 后遞增排序數(shù)串，排列中每個位置的數(shù)字按由左而右順序從數(shù)串中選擇。設單詞長度為I，數(shù)串的第i個位置已訪問標志為 v1i，初始時v1清零；數(shù)字k對應的字母已使用標志為v2k , v2為遞歸程序內的局部變量(0< i < l-1 , 0< kw 51)。生成所有排列的計算過程為一個遞歸子程序:void dfs(int d 從當前位置d出發(fā)，遞歸計算單詞的所有排列if (d=l輸出當前數(shù)字排列對應的單詞；生成單詞的一個排

18、列elsev2清零；/所有字母未確定for(i nt i=0;i按由左而右順序從數(shù)串中選擇d位置的字母：若數(shù)串的第i個位置未訪問且對應字母未在排列中出現(xiàn)，則設訪問標志，該字符進入排列中的第d個位置if(!v1i&&!v2i位置字母對應的數(shù)字v1i=1;v2i位置字母對應的數(shù)字 =1;i位置字母對應的數(shù)字放入當前排列的d位置；dfs(d+1; /遞歸排列的第d+1個位置v1i=0; 恢復數(shù)串的第i個位置未訪問標志顯然，主程序設數(shù)串的所有位置未訪問(v1清零)，遞歸調用dfs(0，便可按字母升序要求輸出單詞的所有排列?！? How Ma ny Poi nts of In terse

19、ctio n?】【問題描述】給出兩行，在第一行有a個點，在第二行有b個點。我們用直線將第一行的每個點 與第二行的每個點相連接。這些點以這樣的方式排列，使得這些線段之間相交的數(shù) 量最大。為此，不允許兩條以上的線段在一個點上相交。在第一行和第二行中的相 交點不被計入，在兩行之間允許兩條以上的線段相交。給出a和b的值，請計算P(a, b,在兩行之間相交的數(shù)量。例如，在下圖中a = 2，b = 3,該圖表示P(2, 3 =3。輸入：輸入的每行給出兩個整數(shù) a ( 0<a20000和b ( 0< b20000。輸入以a=b=0的一行為結 束標志，這一測試用例不用處理。測試用例數(shù)最多1200個

20、。輸出：對輸入的每一行，輸出一行，給出序列編號，然后給出P(a, b的值。本題設定輸出值在64位有符號整數(shù)范圍內。樣例輸入樣例輸出2 2Case 1: 12 3Case 2: 33 3Case 3: 90 0注:試題來源：Ban gladesh Nati onal Computer Programmi ng Con test, 2004在線測試：UVA 10790提示如3線交于一點，則一定可以通過左右移動一個點使其交點分開，上面線段上的兩 點與下面線段上的兩點可以產生一個交點。按照乘法原理，p(a，b='"-'-；【9 Stripies 】【問題描述】生化學家發(fā)明了一

21、種很有用途的生物體，叫stripies，(實際上，最早的俄羅斯名叫polosatiki ，不過科學家為了申請國際專利時方便不得不起了另一個英文名)。stripies是透明，無定型的，群居在一些象果子凍那樣的有營養(yǎng)的環(huán)境里。在大部分時間stripies是在移動中，當兩條stripies碰撞時，這兩條stripies就融合 產生一條新的stripies。經(jīng)過長時間的觀察，科學家們發(fā)現(xiàn)當兩條stripies碰撞融合在一起時，新的stripies的重量并不等于碰撞前兩條stripies的重量。不久又發(fā)現(xiàn)兩條重量為ml和m2的stripies碰撞融合在一起，其重量變?yōu)?*sqrt(m1*m2?？茖W家很希

22、望知道有什么辦法可以限制一群stripies的總重量的減少。請您編寫程序來解決這個問題。本題設定3條或更多的stripies從來不會碰撞在一起。輸入:第一行給出N (1眾 100表示群落中stripies的數(shù)量。后面的N行每行為一條 stripie的重量，范圍為1-1000。輸出：輸出stripies群落可能的最小總重量。精確到小數(shù)點后3位樣例輸出120.00樣例輸入37230注:50試題來源： ACM Northeastern Europe 2001, Northern Subregion在線測試：POJ 1862, ZOJ 1543, Ural 1161設群落中n條stripies的重量為

23、m1m2mn。經(jīng)過n-1次碰撞后的總重量為W='顯然，m1m2mn按照重量遞減的順序排列，得出的總重量 w是最小的。【10 The Product of Digits 】【問題描述】請您尋找一個最小的正整數(shù)Q, Q的各個位置上的數(shù)字乘積等于N輸入：輸入給出一個整數(shù) N (0 令1 < 109b輸出：輸出一個整數(shù)Q,如果這個數(shù)不存在，則輸出-1。樣例輸入樣例輸出1025注:試題來源：USU Local Con test 1999在線測試：Ural 1014提示分解N的因子的度量標準：盡量分解出大因子。注意，有兩個特例：N=0 時,Q=0 ；N=1 時,Q=1 ；否則采取貪心策略，按

24、從 9到2的順序分解n的因子：先試將 n分解出盡量多的因子 9，再試分解出盡量多的因子8。若最終分解后的結果不為1，則無解；否則因子由小到大組成最小的正整數(shù) Q。提高題：【11 Democracy in Dan ger】【問題描述】在Caribbean盆地中的一個國家，所有的決策是由在公民大會上簡單的多數(shù)投票被 通過的。當?shù)氐囊粋€政黨，希望權力盡可能地合法，要求改革選舉制度。他們主要 論點是，島上的居民最近增加了，它不再輕易舉行公民大會。改革的方式如下：投票者被分成 K個組（不一定相等），在每個組中對每個問題 進行投票，而且，如果一個組半數(shù)以上的成員投贊成”票，那么這個組就被認為投贊成”票，否

25、則這個組就被認為投 反對”票。如果超過半數(shù)的組投 贊成”票，決議 就被通過。開始島上的居民高興地接受了這一做法，然而，弓I入這一做法的黨派，可以影響投 票組的構成。因此，他們就有機會對不是多數(shù)贊同的決策施加影響。例如，有3個投票組，人數(shù)分別是有5人，5人和7人，那么，對于一個政黨，只 要在第一組和第二組各有3人支持就足夠了，有6個人贊成，而不是9個人贊成， 決議就能通過。請您編寫程序，根據(jù)給出的組數(shù)和每組的人數(shù)，計算通過決議至少需要多少人贊 成。輸入:第一行給出K，表示組數(shù)（K< 101）;第二行給出K個數(shù)，分別是每一組的人 數(shù)。K以及每組的人數(shù)都是奇數(shù)?？側藬?shù)不會超過 9999人。輸出

26、：支持某個黨派對決策產生影響至少需要的人數(shù)。樣例輸入樣例輸出365 7 5注:試題來源：Autu mn School Co ntest 2000在線測試：Ural 10257提示把每組人數(shù)從小到大排序，總共n組，則需要有+1組同意，即人數(shù)最少的前-J+1組。對于一個人數(shù)為 k的組需要同意,則需要有“ +1人同意。由此得出貪心策略：人數(shù)最少的前"+1組中，每組取半數(shù)剛過的人數(shù)。【12 Box of Bricks 】【問題描述】小Bob喜歡玩方塊磚，他把磚一塊放在另一塊的上面堆砌起來，堆成不同高度的 棧?？?，我建了一面墻”，他告訴他的姐姐Alice。不，你要讓所有的棧有相同的 高度，這樣

27、你就建了一面真正的墻了?！?Ace反駁說。Bob考慮了一下，認為他姐姐是對的。因此他開始重新一塊接一塊地重新安排磚塊，讓所有的棧有著相同的高 度。但由于Bob很懶惰，他要移動磚塊的數(shù)量最少。你能幫助他嗎？輸入由若干組測試用例組成。每組測試用例的第一行給出整數(shù) n,表示Bob建的棧 的數(shù)目。下一行給出n個數(shù)字，表示n個棧的高度hi，本題設定1令< 50并且1 呦 < 100磚塊的總數(shù)除以棧的數(shù)目是可除盡的。也就是說，重新安排磚塊使得所有的棧有相 同的高度是可以的。輸入由n = 0作為結束，程序對此不必處理。輸出：對每個測試用例，首先如樣例輸出所示，輸出測試用例編號。然后輸出一行&qu

28、ot;Theminimum number of moves is k."，其中k是移動磚塊使得所有的棧高度相同的最小 數(shù)。在每個測試用例后輸出一個空行。樣例輸出樣例輸入Set #1The mi nimum nu mber of moves is 5.注: 試題來源：ACM Southwestern European Regional Contest 佃 97在線測試：POJ 1477, ZOJ 1251，UVA 591rI I設平均值avg= , avg即為移動后棧的相同高度。第i個棧中磚頭被移動的度量標準：若 hi>avg，則棧中有hi-avg塊磚頭被移動。 貪心使用這個度量

29、標準是正確的，因為磚頭被移動至高度低于avg的棧中。由于磚塊總數(shù)除以棧的數(shù)目是可除盡的，因此這些棧中的磚頭是不須再移動的。由此得出S' (h - avg h > avg)最少移動的磚數(shù)ans=【13 Mi ni mal coverage】【問題描述】給出直線的若干條線段，直線是 X軸，線段的坐標為L i, Ri 。求最少要用多少條線 段可以覆蓋區(qū)間0, m。輸入：輸入的第一行給出測試用例的數(shù)目，后面給出一個空行。每個測試用例首先給出一個整數(shù) M(1 <1 < 5000接下來若干行，每行以"L i Ri"(|Li|,|Ri | < 5000&#

30、171; 10000表示線段。每個測試用例以“ 0 (為結束。兩個測試用例之間用一個空行分開。輸出：對每個測試用例，輸出的第一行是一個數(shù)字，表示覆蓋區(qū)間0, m的最少線段數(shù)。接下來若干行表示選擇的線段，給出線段的坐標，按左端(Li排序。程序不處理"00"。若無解，即0, m不可能被給出的線段覆蓋，貝u輸出"0"(沒有引號)。在兩個連續(xù)的測試用例之間輸出一個空行。樣例輸出樣例輸入-1 0-5 -3 2 50 01-1 00 10 0注：試題來源：USU Internal Contest March'2004在線測試：UVA 10020 , Ural

31、 1303提示把所有線段按左端點 為第一關鍵字、右端點為第2關鍵字遞增排序(Li < Li+1|(Li =Li+1 &&( Ri< R+1，1 < i w 線段數(shù)-1 )。選取覆蓋線段的度量標準：在所有左端點被覆蓋線段中找右端點最遠的線段。貪心實現(xiàn)的過程：設當前線段覆蓋到的位置為now;所有左端點被覆蓋的線段中可以覆蓋最遠的位置為len，該線段為 k。初始時 ans=now=len=0。依次分析序列中的每條線段：if (Li<now&& (len< Ri) len= Ri; k=i;if (Li+1 >now &&am

32、p;(now ) now=len ;將線段k作為新增的 覆蓋線段if (now > m輸出覆蓋線段并退出程序；分析了所有線段后 now，說明無法覆蓋0, m ，無解退出?！?4 Annoying pain ti ng tool【問題描述】你想知道一個惱人的繪畫工具是什么嗎？首先，本題所講的繪畫工具僅支持黑色和 白色，因此，圖片是一個像素組成的矩形區(qū)域，像素不是黑色就是白色。其次，只 有一個操作改變像素的顏色：選擇一個r行c列的像素組成的矩形，這個矩形是完全在一個圖片內。作為操作的 一個結果，在矩形內的每個像素會改變其顏色（從黑到白，從白到黑）。最初，所有的像素是白色的。創(chuàng)建一個圖片，應用

33、上述的操作數(shù)次。你能描繪出你 心目的那幅圖片嗎？輸入:輸入包含若干測試用例。每個測試用例的第一行給出 4個整數(shù)n，m，r和c，（ 1 <r wn < 100, 1 c < 100，然后的n行每行給出您要畫的圖的一行像素。第 i 行由m個字符組成，描述在結束繪畫時第i行的像素值（'0'表示白色，1'表示黑色。最后一個測試用例后的一行給出 4個0。輸出:對每個測試用例，輸出產生最終繪畫結果需要操作的最小數(shù)；如果不可能，輸出1。樣例輸出-1樣例輸入010 101 0100111100111103 4 2 20110011100000 0 0 0注：試題來源：

34、Ulm Local 2007在線測試：POJ 3363提示進行一次操作的度量標準：當前子矩陣左上角的像素和目標矩陣的對應像素的顏色不同。貪心實現(xiàn)的方法如下由左而右、自上而下枚舉子矩陣的左上角aij (1< i <n -r+1 , 1< j < mc+1 :若左上角像素的顏色與目標矩陣對應元素的顏色不同(aij!=bij)，則操作次數(shù)c+1;子矩陣內所有像素的顏色取反(aklA=1, i w kw i+k -1 , j < l wj+c -1 )。最后再檢驗一遍當前矩陣a和目標矩陣b是否完全一樣。若還有不一樣的地方，則說明無解；否則c為產生最終繪畫結果需要操作的最少

35、次數(shù)?！?5 Troublemakers 】【問題描述】每所學校都有麻煩制造者(troublemaker)那些孩子們可以使教師的生活苦不堪言。一個麻煩制造者還是可以管理的，但是當你把若干對麻煩制造者放在同一個 房間里，教學就變得非常困難。在 Shaida夫人的數(shù)學課上有n|個孩子，其中有m 對麻煩制造者。情況變得如此的差，使得Shaida夫人決定將一個班級分成兩個班級。請您幫Shaida夫人將麻煩制造者的對數(shù)減少至少一半。輸入:輸入的第一行給出測試用例數(shù) N，然后給出N個測試用例。每個測試用例的第一 行給出n (0韋< 10(和m (0<m<5000,然后m行每行給出一對整數(shù)

36、u和v,表示|u 和v在同一個房間里的時候，他們是一對麻煩制造者。孩子編號從1到n。輸出:對于每個測試用例，先輸出一行"Case故:"，后面給出L 要轉到另一間房間的 孩子的數(shù)目，下一行列出那些孩子。在兩個房間中麻煩制造者對數(shù)的總數(shù)至多是 m/2。如果不可能，則輸出"Impossible."代替L,然后輸出一個空行。2Case #1: 34 31 3 41 2Case #2: 22 31 23 44 6樣例輸入樣例輸出1 21 31 42 32 43 4注：試題來源：Abed nego's Graph Lovers' Co ntest,

37、2006在線測試：UVA 10982提示以孩子為節(jié)點，每對麻煩制造者之間連邊，構造無向圖g。設兩個班級分別對應集合s0和集合s1，其中s1中的人數(shù)較少。依次確定每個孩子i (K i w n)所在的班級：將孩子 1 孩子i-1中與孩子i結對制造麻 煩的孩子劃分成s0和s1集合。若s1中的孩子數(shù)較少，則孩子 i送入s1集合，這就是 孩子i轉移到另一間房間的度量標準。貪心實現(xiàn)的方法是依次搜索每個節(jié)點i (1 w i w n)：統(tǒng)計節(jié)點1i-1中與節(jié)點i有邊相連的點在集合s0和集合s1的點數(shù)；若s1中的點數(shù)較少，則節(jié)點i送入s1集合；最后s1集合中的節(jié)點對應要轉到另一間房間的孩子?！?6 Co nst

38、ructi ng BST 】【問題描述】BST (Binary Search Tree二叉搜索樹)是一個用于搜索的有效的數(shù)據(jù)結構。在一 個BST中，所有左子樹中的元素小于根，右子樹中的元素大于根。我們通常通過連續(xù)地插入元素來構造BST，而插入元素的順序對于樹的結構有很大的影響。請看下例：TJ 屯CDJED QI£Id* 12 3 4Odw 3$4 3 1 or .2 i 4 92 4. 12 4 > 1 or J 4 t 3在本題中，我們要給出從1到N的整數(shù)來構造BST，使得樹的高度至多為H BST的高度定義如下： 1.沒有結點的BST的高度為0；2.否則，BST的高度等于左子

39、樹和右子樹的高度的最大值加1?？梢源嬖谌舾身樞蚩梢詽M足這一要求。在這種情況下，取小數(shù)字排在前的序列。例如，對于N=4, H=3，我們給出的序列是1 3 2 4,而不是2 1 4 3或3 2 1 4輸入：每個測試用例給出兩個正整數(shù) N (1<N< 10000和H (1卻<30。輸入以N=0， H=0結束，這一情況不用處理。至多有 30個測試用例。輸出：對于每個測試用例，輸出一行，以“ Case #開始，其中是測試用例的編號；然后在這一行中給出N個整數(shù)的序列，在一行的結束沒有多余的空格。如果無法構 造這樣的樹，則輸出“Impossible.(沒有引號)。樣例輸入樣例輸出4 3Ca

40、se 1:1 3 2 44 1Case 2:Impossible6 3Case 3:3 1 2 5 4 60 0注:試題來源：ACM ICPC World Finals Warmup 1，2005在線測試：UVA 10821試題要求輸出BST的前序遍歷，即第一個輸出根。因為要求字典序最小，所以要讓根盡 量小。對于把編號為1到n的節(jié)點排成一個高度不高于h的bst，左右子樹的節(jié)點數(shù)不應超過2h-1 -1。根節(jié)點的度量標準是若根的右側可以放滿節(jié)點，則根的編號root為n-(2h-1-1 ;否則根的編號root為1，即根編號 root= max1， n-( 2h-1 -1。之后問題就轉化成了把編號為1

41、到root-1的節(jié)點排成一個高度不高于h-1的左bst子樹和把編號為root+1到n的節(jié)點排成一個高度不高于h-1的右bst子樹。上述貪心解法是遞歸定義的，可遞歸解決?！?7 Orderi ng Tasks 】John有n項任務要做。不幸的是，這些任務并不是獨立的，有的任務只有在其他一些任務 完成以后才能開始做。輸入：輸入由幾個測試用例組成。每個用例的第一行給出兩個整數(shù)：14W 100和m。n是任務的數(shù)量(從1到n編號，m是在兩個任務之間直接優(yōu)先關系的數(shù)量。然后是 m行，每行兩個整數(shù) i和j,表示任務i必須在任務j之前執(zhí)行。以實例 n=m=0結束輸入。輸出：對每個測試用例，輸出一行，給出n個整

42、數(shù)，表示任務執(zhí)行的一個可能的順序。樣例輸入樣例輸出5 41 22 31 31 5注:試題來源：GWCF Contest 2(Golden Wedding Contest Festival)在線測試：UVA 10305提示任務作為節(jié)點，兩個任務之間的直接優(yōu)先關系作為邊：若任務i必須在任務j之前執(zhí)行，則對應有向邊，這樣可將任務間的先后關系轉化為一張有向圖，使得任務執(zhí)行的一個可能的順序對應這張有向圖的拓撲排序。設節(jié)點的入度序列為ind，其中節(jié)點i的入度為indi（0 <i <n -1 ;鄰接表為lis，其中節(jié)點i的所有出邊的另一端點存儲在lisi 中，lisi 為一個List容器隊列q存

43、儲當前入度為0的節(jié)點，隊首指針為h,隊尾指針為t ;我們在輸入信息的同時構建鄰接表lis，計算節(jié)點的入度序列為ind，并將所有入度為0的節(jié)點送入隊列q；然后依次處理q隊列中每個入度為 0的節(jié)點：取出隊首節(jié)點x ；lisx容器中每個相鄰節(jié)點的入度-1，相當于刪除x的所有出邊；新增入度為0的節(jié)點入q隊列；依次類推，直至隊列空為止。相繼出隊的節(jié)點q0 -qn -1即為一個拓撲序列?！?8 Spreadsheet 】在1979年，Dan Bricklin和Bob Frankston編寫了第一個電子制表應用軟件VisiCalc，這一軟件獲得了巨大的成功，并且在那時成為Apple II計算機的重要應用軟件

44、?，F(xiàn)在電子制表是大多數(shù)計算機的重要的應用軟件。電子制表的思想非常簡單，但非常實用。一個電子制表由一個表格組成，每個項不是一個 數(shù)字就是一個公式。一個公式可以基于其他項的值計算一個表達式。文本和圖形也可以加入用 于表示。請編寫一個非常簡單的電子制表應用程序，輸入若干份表格，表格的每一個項或者是數(shù)字 （僅為整數(shù)），或者是支持求和的公式。在計算了所有公式的值以后，程序輸出結果表格，所 有的公式都已經(jīng)被它們的值代替。輸入:輸入文件第一行給出測試用例中的表格的數(shù)目。每個表格的第一行給出用一個空格分開的 兩個整數(shù)，表示表格的列數(shù)和行數(shù)，然后給出表格，每行表示表格的一行，每行由該行的項組 成，每個項用一個空

45、格分開。一個項或者是一個數(shù)字值，或者是一個公式。一個公式由一個等號開始（=，后面是一個或多個用加號（+分開的項的名稱，這樣公式的值是在相應的項中的所有值的總和。這些項也可以 是一個公式，在公式中沒有空格。可以設定在這些項之間沒有循環(huán)依賴，因此每個表格可以是完全可計算的。每一個項的名字是由1到3個字母（按列），后面跟著數(shù)字從1到999 （按行）組成。按列的字母構成如下序列：A, B, C,乙AA, AB, AC,AZ, BA,，BZ, CA,ZZ, AAA,AAB, ., AAZ, ABA, ., ABZ, ACA,ZZZ。這些字母相應于從1到18278的數(shù)字，如圖所10 34 37 =A1+B

46、1+C150 51 71 172示，左上角的項取名為A1。AlBlClDIElFl1 A2 1B2C2D2E21 F2 1A3B3C3D3E3F3A4B4C4D4E4F4A5B5C5D5E5F5rAoB6C606EGfgI左上方的項的命名輸出:除了表格的數(shù)目以及列和行的數(shù)目不重復以外，程序輸出和輸入的格式一樣。而且，所有 的公式要被它們的值取代。樣例輸出樣例輸入110 34 37 814 340 17 34 9110 34 37 =A1+B1+C150 51 71 17240 17 34 =A2+B2+C2=A1+A2 =B1+B2=C1+C2 =D1+D2注：試題來源：1995 ACM So

47、uthwestern European Regio nal Co ntest在線測試：POJ 1420, UVA 196提示在表達式中各項的命名格式，字母AZZZ代表列，數(shù)字1999代表行。需要將列字母轉化 為列序號，行數(shù)串轉化為行序號。轉化方 法：A代表1,Z代表26,字母序列ckc1對應 一個26進制的列序號1-；數(shù)串bp b1應一個十進制的行序號 £ （也-48LIOx=劌。即表達式中的項ck - c1 bp - b1對應表格位置（X, y）。數(shù)值表格為w；表達式項所在位置值為d=j*1000+i , 即 d % 1000 為行號，d,（ i,j ）對應位置值I d1000為列

48、號。我們將表格轉化為一個有向圖：每項為一個 節(jié)點，數(shù)值項與表達式項間的關聯(lián)關系為有 向邊。若數(shù)值項（x,y ）對應表達式項（i,j ）中 的某項，貝9（ x,y ）連一條有向邊至（i,j ）。設相鄰矩陣為g，其中gxy存儲與數(shù)值項（x,y ）關聯(lián)的所有表達式項的位置值；表達式項的入度序列為ind，即（i,j ）中的表達式目前含 indij 個未知項。顯然 indij=0,表明（i，j ）為數(shù)值項；構造有向圖我們邊輸入表格邊構造有向圖：若（i，j ） 為數(shù)值項，則數(shù)值存入wij；若（i,j ）為表達式項，則取出其中的每一項，計算其對應 的行號x和列號y,（ i,j ）的位置值送入 g【x】【y

49、鄰接表，并累計（i，j ）的入度（ +indij）。使用刪邊法計算有向圖的拓撲序列首先將圖中所有入度為0的節(jié)點（數(shù)值項）的位置值送入隊列q；然后依次按下述方 法處理隊列中的每一項：取出隊首節(jié)點的位置值，將之轉化為（x,y ）。依次取gxy中與數(shù)值項（x,y ）相關聯(lián)的每個表達式項的位置值，轉化為表格位置（tx,ty ）,將（x,y ）的值計入（tx,ty ）中的表達式項（wtxty+=wxy） ，（ tx,ty ）的入度-1 （ -indtxty）。若入度減至 0，則（tx,ty ）的位置值送入q隊列。依次類推，直至隊列空為止。最后輸出數(shù)值表格w?！?9 Genealogical Tree 】

50、火星人直系親屬關系的系統(tǒng)非?；靵y。火星 人在不同的群體中群居生活，因此一個火星 人可以有一個父母，甚至也可以有十個父 母；而且一個火星人有100個孩子也不會讓人 感到奇怪?；鹦侨艘呀?jīng)習慣了這樣的生活方 式，對于他們來說這很自然。在行星理事會（ Pla netary Cou ncil ） 中，這樣混亂的 家譜系統(tǒng)導致了一些尷尬。這些火星人中的 杰出人士去參加會議，為了在討論中不冒犯 長輩，討論中總是輩分高的火星人優(yōu)先發(fā) 言，然后是輩分低的火星人發(fā)言，最后是輩 分最低還沒有子女的火星人發(fā)言。然而，這 個秩序的維持確實不是一個簡單的任務。一 個火星人并不知道他所有的父母（當然也不 知道他的所有的祖父

51、母），但如果一個孫子 在比他年輕的曾祖父之前發(fā)言，這就是一個 重大的錯誤了。請編寫一個程序，對所有的成員定義一個次 序，這個次序要保證理事會的每一個成員所 在的位置先于他的所有后代。輸入:標準輸入的第一行只包含一個整數(shù)N，Martia n Pla netary Cou ncil)1到N。在后iW N < 100，表示火星理事會（ 的成員數(shù)。理事會成員的編號從面給出N行，而且第i行給出第i個成員的孩子 的列表。孩子的列表是孩子編號按任意次序 用空格分開的一個序列。孩子的列表可以為 空。列表（即使是空列表）以 0結束。輸出：標準輸出僅給出一行，給出一個編號的序 列，編號以空格分開。如果存在幾

52、個序列滿 足這一問題的條件，請輸出其中任何一個。 這樣的序列至少存在一個。樣例輸入樣例輸出52 4 5 3 104 5 1 01 05 3 03 0注：試題來源：Ural State University Internal Contest October'2000 Junior Session在線測試：Ural 1022提示將火星人設為節(jié)點，父親與兒子之間連一條有向邊。這個有向圖的拓撲序列即為所有成 員的次序。我們邊輸入信息邊構造相鄰矩陣g,并統(tǒng)計節(jié)點的入度序列ind （其中gx存儲x的所有兒子，indx為節(jié)點x的入度值）。接下來，將所有入度為 0的節(jié)點送入隊列q。然后依次處理隊列 q

53、中的每個節(jié)點：取隊首節(jié)點x; x的每個兒子的入度-1。若減至0,則該兒子進入隊列 q；依次類推，直至隊列空為止。最后輸出輸出拓撲序列，即q的出隊順序?！?0 Rare Order 】一個珍稀書籍的收藏家最近發(fā)現(xiàn)了一本用一種陌生的語言寫的一本書，這種語言采用和英 語一樣的字母。這本書有簡單的索引，但在索引中的條目的次序不同于根據(jù)英語字母表給出的 字典排序的次序。這位收藏家試圖通過索引來確定這個古怪的字母表的字符的次序，（即對索引條目組成的序列進行整理，但因為任務冗長而乏味，就放棄了。請編寫程序完成這位收藏家的任務，程序輸入一個按特定的序列排序的字符串集合，確定 字符的序列是什么。輸入：輸入是由大

54、寫字母組成的字符串的有序列表，每行一個字符串。每個字符串最多包含20個字符。該列表的結束標志是一個單一字符# '勺一行。并不是所有的字母都被用到，但該列表蘊涵對于被采用的那些字母存在著一個完全的次序。輸出：輸出一行大寫字母，字母的排序順序列按輸入數(shù)據(jù)進行整理所給出。樣例輸出XZYW樣例輸入XWYZXZXYZXWYWWX#注：試題來源：1990 ACM ICPC World Finals在線測試：UVA 200 , UVA 5139提示輸入字符串的有序列表 T (T表的長度為tot)，按照下述方法將T表轉化為有向圖的相鄰矩陣v:每個大寫字母為一個節(jié)點，節(jié)點序號為字母對應的數(shù)值(大寫字母序列A - Z映射為數(shù)值序列1 - 26), T表中同一位置上不同字母代表的節(jié)點間連有向邊：for (i nt