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

2、度是小于2001的一個正整數(shù)。輸出：對輸入的每個測試用例輸出一行，給出一個輸出序列號，然后給出在輸入的字符串中頻率是素數(shù)的字符。這些字符按字母升序排列。所謂“字母升序”意謂按ASCII 值升序排列。如果沒有字符的頻率是素數(shù)，輸出“empty”（沒有引號）。樣例輸入樣例輸出3ABCCAABBBBDDDDDABCDFFFFCase 1: CCase 2: ADCase 3: empty注： 試題來源：Bangladesh National Computer Programming Contest在線測試：UVA 10789提示 先離線計算出22200的素數(shù)篩u。然后每輸入一個測試串，以ASCLL碼

3、為下標統(tǒng)計各字符的頻率p，并按照ASCLL碼遞增的順序（0i299）輸出頻率為素數(shù)的字符（即upi=1且ASCLL碼值為i的字符）。若沒有頻率為素數(shù)的字符，則輸出失敗信息?！? 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行，每行給出一個整數(shù)S (1 S 100

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

5、的計算方法如下：使用篩選法計算出2，20000000的素數(shù)篩u；按遞增順序枚舉該區(qū)間的每個整數(shù)i：若i和i+2為雙素數(shù)對（ui&&ui+2）,則雙素數(shù)對序列增加一個元素（ans+num=i）。在離線計算出ans的基礎上，每輸入一個編號s，則代表的雙素數(shù)對為(anss，anss+2)?！? Less Prime】【問題描述】設n為一個整數(shù)，100n10000，請找到素數(shù)x，x n，使得n-p*x最大，其中 p是整數(shù)，使得p*xn<(p+1)*x。輸入:輸入的第一行給出一個整數(shù)M，表示測試用例的個數(shù)。每個測試用例一行，給出一個整數(shù)N，100N10000。輸出:對每個測試用例，

6、輸出一行，給出滿足上述條件的素數(shù)。 樣例輸入樣例輸出543996148201101704822033114111533527注： 試題來源：III Local Contest in Murcia 2005在線測試：UVA 10852提示要使得n-p*x最大（x為素數(shù)，p為整數(shù)，p*x n<(p+1)*x），則x為所有小于n的素數(shù)中，被n除后余數(shù)最大的一個素數(shù)。由此得出算法：先離線計算出211111的素數(shù)表su，表長為num。然后每輸入一個整數(shù)n，則枚舉小于n的所有素數(shù)，計算tmp=，滿足條件的素數(shù)即為對應tmp=n%suk的素數(shù)suk?！? Prime Words】【問題描述】一個素數(shù)是

7、僅有兩個約數(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個字母，1L20。輸入以EOF結束。輸出：如果一個單詞字母的和為素數(shù)，則輸出“It is a prime word.”；否則輸出“It is not a

8、 prime word.”。 樣例輸入樣例輸出UFRNcontestAcMIt is a prime word.It is not a prime word.It is not a prime word.注： 試題來源：UFRN-2005 Contest 1在線測試：UVA 10924提示由于字母對應數(shù)字的上限為52，而單詞的長度上限為20，因此我們首先使用篩選法，離線計算出21010的素數(shù)素數(shù)篩u。然后每輸入一個長度為n的單詞，計算單詞字母對應的數(shù)字和X=若x為21010中的一個素數(shù)（ux=1），則表明該單詞為素單詞；否則該單詞非素單詞?！? Sum of Different Primes】

9、【問題描述】一個正整數(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，k = 2，答案是3，因為存在3個集合5, 19, 7, 17以及11, 13。如果n = 2，k = 1，答案是1，因為只有一個集合2 ，其總和為2。如果n = 1，k = 1，答案是0，因為1不是素數(shù)，不能

10、將1計入。如果n = 4，k = 2，答案是0，因為不存在兩個不同素數(shù)的集合，總和為4。請您編寫一個程序，對給出的n和k，輸出答案。輸入：輸入由一系列的測試用例組成，最后以一個空格分開的兩個0結束。每個測試用例一行，給出以一個空格分開的兩個正整數(shù)n和k。本題設定n 1120，k 14。輸出：輸出由若干行組成，每行對應一個測試用例，一個輸出行給出一個非負整數(shù)，表示對相應輸入中給出的n和k有多少答案。本題設定答案小于231。樣例輸入樣例輸出24 324 22 11 14 218 317 117 317 4100 51000 101120 140 02310021015520010289920793

11、24314注：試題來源：ACM Japan 2006在線測試：POJ 3132，ZOJ 2822，UVA 3619提示設 su為2.1200的素數(shù)表；fij為j拆分成i個素數(shù)和的方案數(shù)(1i14, suij1199)。顯然，邊界值f00=1。首先，采用篩選法計算素數(shù)表su，表長為num。然后每輸入一對n和k，使用動態(tài)規(guī)劃方法計算k個不同素數(shù)的和為n的方案總數(shù)：枚舉su表中的每個素數(shù)sui(1inum） 按遞減順序枚舉素數(shù)個數(shù)j(j=141)： 按遞減順序枚舉前j個素數(shù)的和p（p=1199sui）: 累計sui作為第j個素數(shù)的方案總數(shù)fjp+=fj-1p-sui;最后得出的fkn即為問題解?！?

12、 Common Permutation】【問題描述】給出兩個小寫字母的字符串，a和b，輸出最長的小寫字母字符串x使得存在x的一個排列，是a的子序列，同時也存在x的一個排列是b的子序列。輸入：輸入有若干行。連續(xù)的兩行組成一個測試用例，也就是說，第1和第2行構成一個測試用例，第3和第4行構成一個測試用例，等等。每個測試用例的第一行是字符串a(chǎn)，第二行是字符串b。每個字符串一行，至多由1000個小寫字母組成。輸出：對每個測試用例，輸出一行，給出x。如果有若干個x滿足上述要求，選擇按字母序列第一個。樣例輸入樣例輸出prettywomenwalkingdownthestreetenwet注： 試題來源：W

13、orld Finals Warm-up Contest, University of Alberta Local Contest在線測試：UVA 10252提示試題要求按遞增順序輸出兩串公共字符的排列。計算方法如下： 設S1=a1a2，S2= b1b2。先分別統(tǒng)計S1中各字母的頻率c1i和S2中各字母的頻率c2i（1i26,其中字母a對應數(shù)字1, 字母b對應數(shù)字2,，字母z對應數(shù)字26）。然后計算S1和S2的公共字符的排列：遞增枚舉i(1i26)，若i對應的字母在S1和S2中同時存在（c1i0）&&（c2i0）,則字母'a'+i在排列中出現(xiàn)k=minc1i，c2

14、i次?！? Anagram】【問題描述】給出一個字母的集合，請您編寫一個程序，產(chǎn)生從這個集合能構成的所有可能的單詞。例如：給出單詞"abc"，您的程序產(chǎn)生這三個字母的所有不同的組合輸出單詞"abc", "acb", "bac", "bca", "cab" 和"cba"。程序從輸入中獲取一個單詞，其中的一些字母會出現(xiàn)一次以上。對一個給出的單詞，程序產(chǎn)生相同的單詞只能一次，而且這些單詞按字母升序排列。輸入：輸入給出若干單詞。第一行給出單詞數(shù)，然后每行給出一個單

15、詞。一個單詞是由A到Z的大寫或小寫字母組成。大寫字母和小寫字母被認為是不同的，每個單詞的長度小于13。輸出：對輸入中的每個單詞，輸出這個單詞的字母產(chǎn)生的所有不同的單詞。輸出的單詞按字母升序排列。大寫字母排在相應的小寫字母前，即'A'<'a'<'B'<'b'<.<'Z'<'z'。樣例輸入樣例輸出3aAbabcacbaAabAbaaAbabAbAabaAabcacbbacbcacabcbaaabcaacbabacabcaacabacbabaacbacabcaacaab

16、cabacbaa注： 試題來源：ACM Southwestern European Regional Contest 1995在線測試：POJ 1256，UVA 195提示建立字母與整數(shù)間的對應關系：字母a對應0，字母A對應1;；字母z對應50，字母Z對應51。為了按照字母升序的要求生成單詞的所有排列，首先將單詞的所有字母轉化為數(shù)字，然后遞增排序數(shù)串，排列中每個位置的數(shù)字按由左而右順序從數(shù)串中選擇。設單詞長度為l，數(shù)串的第i個位置已訪問標志為v1i，初始時v1清零；數(shù)字k對應的字母已使用標志為v2k，v2為遞歸程序內的局部變量（0il-1，0k51）。生成所有排列的計算過程為一個遞歸子程序：v

17、oid dfs(int d) /從當前位置d出發(fā)，遞歸計算單詞的所有排列if (d=l) 輸出當前數(shù)字排列對應的單詞； /生成單詞的一個排列elsev2清零; /所有字母未確定for(int i=0;i<l;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個位置未訪問標志

18、顯然，主程序設數(shù)串的所有位置未訪問（v1清零），遞歸調用dfs(0)，便可按字母升序要求輸出單詞的所有排列。【8 How Many Points of Intersection?】【問題描述】給出兩行，在第一行有a個點，在第二行有b個點。我們用直線將第一行的每個點與第二行的每個點相連接。這些點以這樣的方式排列，使得這些線段之間相交的數(shù)量最大。為此，不允許兩條以上的線段在一個點上相交。在第一行和第二行中的相交點不被計入，在兩行之間允許兩條以上的線段相交。給出a和b的值，請計算P(a, b)，在兩行之間相交的數(shù)量。例如，在下圖中a = 2，b = 3，該圖表示P(2, 3) = 3。輸入：輸入的每

19、行給出兩個整數(shù)a ( 0<a£20000)和b ( 0< b£20000)。輸入以a=b=0的一行為結束標志，這一測試用例不用處理。測試用例數(shù)最多1200個。輸出：對輸入的每一行，輸出一行，給出序列編號，然后給出P(a, b)的值。本題設定輸出值在64位有符號整數(shù)范圍內。樣例輸入樣例輸出2 22 33 30 0Case 1: 1Case 2: 3Case 3: 9注： 試題來源：Bangladesh National Computer Programming Contest, 2004在線測試：UVA 10790提示如3線交于一點，則一定可以通過左右移動一個點使

20、其交點分開，上面線段上的兩點與下面線段上的兩點可以產(chǎn)生一個交點。按照乘法原理，p(a，b)=。【9 Stripies】【問題描述】生化學家發(fā)明了一種很有用途的生物體，叫 stripies ，（實際上，最早的俄羅斯名叫 polosatiki ，不過科學家為了申請國際專利時方便不得不起了另一個英文名）。stripies 是透明，無定型的，群居在一些象果子凍那樣的有營養(yǎng)的環(huán)境里。在大部分時間stripies是在移動中，當兩條stripies碰撞時，這兩條stripies就融合產(chǎn)生一條新的stripies。經(jīng)過長時間的觀察，科學家們發(fā)現(xiàn)當兩條stripies碰撞融合在一起時，新的stripies的重量

21、并不等于碰撞前兩條stripies 的重量。不久又發(fā)現(xiàn)兩條重量為m1和m2的stripies 碰撞融合在一起，其重量變?yōu)?*sqrt(m1*m2)?？茖W家很希望知道有什么辦法可以限制一群stripies 的總重量的減少。請您編寫程序來解決這個問題。本題設定3條或更多的stripies 從來不會碰撞在一起。輸入：第一行給出N (1 N 100)，表示群落中stripies 的數(shù)量。后面的N行每行為一條stripie 的重量，范圍為1-1000。輸出：輸出stripies群落可能的最小總重量。 精確到小數(shù)點后3位。樣例輸入樣例輸出3723050120.00注： 試題來源：ACM Northeast

22、ern Europe 2001, Northern Subregion在線測試：POJ 1862，ZOJ 1543，Ural 1161提示設群落中n條stripies的重量為m1m2mn。經(jīng)過n-1次碰撞后的總重量為W=顯然，m1m2mn按照重量遞減的順序排列，得出的總重量w是最小的。【10 The Product of Digits】【問題描述】請您尋找一個最小的正整數(shù)Q，Q的各個位置上的數(shù)字乘積等于N。輸入：輸入給出一個整數(shù)N (0 N 109)。輸出：輸出一個整數(shù)Q，如果這個數(shù)不存在，則輸出1。樣例輸入樣例輸出1025注： 試題來源：USU Local Contest 1999在線測試：

23、Ural 1014提示 分解N的因子的度量標準：盡量分解出大因子。注意，有兩個特例： N=0時,Q=0； N=1時,Q=1； 否則采取貪心策略，按從9到2的順序分解n的因子：先試將n分解出盡量多的因子9，再試分解出盡量多的因子8。若最終分解后的結果不為1，則無解；否則因子由小到大組成最小的正整數(shù)Q。提高題：【11 Democracy in Danger】【問題描述】在Caribbean 盆地中的一個國家，所有的決策是由在公民大會上簡單的多數(shù)投票被通過的。當?shù)氐囊粋€政黨，希望權力盡可能地合法，要求改革選舉制度。他們主要論點是，島上的居民最近增加了，它不再輕易舉行公民大會。改革的方式如下：投票者被

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

25、（K101）；第二行給出K個數(shù)，分別是每一組的人數(shù)。K以及每組的人數(shù)都是奇數(shù)?？側藬?shù)不會超過9999人。輸出：支持某個黨派對決策產(chǎn)生影響至少需要的人數(shù)。樣例輸入樣例輸出35 7 56注：試題來源：Autumn School Contest 2000在線測試：Ural 1025提示把每組人數(shù)從小到大排序，總共n組，則需要有+1組同意，即人數(shù)最少的前+1組。對于一個人數(shù)為k的組需要同意，則需要有+1人同意。由此得出貪心策略：人數(shù)最少的前+1組中，每組取半數(shù)剛過的人數(shù)。【12 Box of Bricks】【問題描述】小Bob喜歡玩方塊磚，他把磚一塊放在另一塊的上面堆砌起來，堆成不同高度的棧?！翱矗?/p>

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

27、對每個測試用例，首先如樣例輸出所示，輸出測試用例編號。然后輸出一行"The minimum number of moves is k."，其中k是移動磚塊使得所有的棧高度相同的最小數(shù)。在每個測試用例后輸出一個空行。樣例輸入樣例輸出65 2 4 1 7 50Set #1The minimum number of moves is 5.注：試題來源：ACM Southwestern European Regional Contest 1997在線測試：POJ 1477，ZOJ 1251，UVA 591提示設平均值avg=，avg即為移動后棧的相同高度。 第i個棧中磚頭被移動的度

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

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

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

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

32、幅圖片嗎？輸入：輸入包含若干測試用例。每個測試用例的第一行給出4個整數(shù)n，m，r和c，（1 r n 100, 1 c m 100），然后的n行每行給出您要畫的圖的一行像素。第i行由m個字符組成，描述在結束繪畫時第i行的像素值('0'表示白色，'1'表示黑色)。最后一個測試用例后的一行給出4個0。輸出：對每個測試用例，輸出產(chǎn)生最終繪畫結果需要操作的最小數(shù)；如果不可能，輸出-1。樣例輸入樣例輸出3 3 1 10101010104 3 2 10111100111103 4 2 20110011100000 0 0 046-1注： 試題來源：Ulm Local 2007

33、在線測試：POJ 3363提示進行一次操作的度量標準：當前子矩陣左上角的像素和目標矩陣的對應像素的顏色不同。貪心實現(xiàn)的方法如下 由左而右、自上而下枚舉子矩陣的左上角aij (1in-r+1，1jm-c+1)： 若左上角像素的顏色與目標矩陣對應元素的顏色不同（aij!=bij），則操作次數(shù)c+1；子矩陣內所有像素的顏色取反（akl=1，iki+k-1，jlj+c-1）。 最后再檢驗一遍當前矩陣a和目標矩陣b是否完全一樣。若還有不一樣的地方，則說明無解；否則c為產(chǎn)生最終繪畫結果需要操作的最少次數(shù)?！?5 Troublemakers】【問題描述】每所學校都有麻煩制造者（troublemaker） 那

34、些孩子們可以使教師的生活苦不堪言。一個麻煩制造者還是可以管理的，但是當你把若干對麻煩制造者放在同一個房間里，教學就變得非常困難。在Shaida夫人的數(shù)學課上有n個孩子，其中有m對麻煩制造者。情況變得如此的差，使得Shaida夫人決定將一個班級分成兩個班級。請您幫Shaida夫人將麻煩制造者的對數(shù)減少至少一半。輸入：輸入的第一行給出測試用例數(shù)N，然后給出N個測試用例。每個測試用例的第一行給出n (0n100)和m (0<m<5000)，然后m行每行給出一對整數(shù)u和v，表示u和v在同一個房間里的時候，他們是一對麻煩制造者。孩子編號從1到n。輸出：對于每個測試用例，先輸出一行"

35、Case #x:"，后面給出L 要轉到另一間房間的孩子的數(shù)目，下一行列出那些孩子。在兩個房間中麻煩制造者對數(shù)的總數(shù)至多是m/2。如果不可能，則輸出"Impossible."代替L，然后輸出一個空行。樣例輸入樣例輸出24 31 22 33 44 61 21 31 42 32 43 4Case #1: 31 3 4Case #2: 21 2注： 試題來源：Abednego's Graph Lovers' Contest, 2006在線測試：UVA 10982提示以孩子為節(jié)點，每對麻煩制造者之間連邊，構造無向圖g。設兩個班級分別對應集合s0和集合s1，其

36、中s1中的人數(shù)較少。依次確定每個孩子i（1in）所在的班級：將孩子1孩子i-1中與孩子i結對制造麻煩的孩子劃分成s0和s1集合。若s1中的孩子數(shù)較少，則孩子i送入s1集合，這就是孩子i轉移到另一間房間的度量標準。貪心實現(xiàn)的方法是依次搜索每個節(jié)點i（1in）： 統(tǒng)計節(jié)點1i-1中與節(jié)點i有邊相連的點在集合s0和集合s1的點數(shù)； 若s1中的點數(shù)較少，則節(jié)點i送入s1集合；最后s1集合中的節(jié)點對應要轉到另一間房間的孩子?！?6 Constructing BST】【問題描述】BST（Binary Search Tree，二叉搜索樹）是一個用于搜索的有效的數(shù)據(jù)結構。在一個BST中，所有左子樹中的元素小于

37、根，右子樹中的元素大于根。我們通常通過連續(xù)地插入元素來構造BST，而插入元素的順序對于樹的結構有很大的影響。請看下例：在本題中，我們要給出從1到N的整數(shù)來構造BST，使得樹的高度至多為H。BST的高度定義如下：1. 沒有結點的BST的高度為0；2. 否則，BST的高度等于左子樹和右子樹的高度的最大值加1?？梢源嬖谌舾身樞蚩梢詽M足這一要求。在這種情況下，取小數(shù)字排在前的序列。例如，對于N=4，H=3，我們給出的序列是1 3 2 4，而不是2 1 4 3或3 2 1 4。輸入：每個測試用例給出兩個正整數(shù)N（1N10000）和H（1H30）。輸入以N=0，H=0結束，這一情況不用處理。至多有30個測

38、試用例。輸出：對于每個測試用例，輸出一行，以“Case #: “開始，其中#是測試用例的編號；然后在這一行中給出N個整數(shù)的序列，在一行的結束沒有多余的空格。如果無法構造這樣的樹，則輸出“Impossible.”（沒有引號）。樣例輸入樣例輸出4 34 16 30 0Case 1: 1 3 2 4Case 2: Impossible.Case 3: 3 1 2 5 4 6注：試題來源：ACM ICPC World Finals Warmup 1，2005在線測試：UVA 10821提示試題要求輸出BST的前序遍歷，即第一個輸出根。因為要求字典序最小，所以要讓根盡量小。對于把編號為1到n的節(jié)點排成一

39、個高度不高于h的bst，左右子樹的節(jié)點數(shù)不應超過2h-1-1。根節(jié)點的度量標準是若根的右側可以放滿節(jié)點，則根的編號root為n-(2h-1-1)；否則根的編號root為1，即根編號root=max1，n-(2h-1-1)。之后問題就轉化成了把編號為1到root-1的節(jié)點排成一個高度不高于h-1的左bst子樹和把編號為root+1到n的節(jié)點排成一個高度不高于h-1的右bst子樹。上述貪心解法是遞歸定義的，可遞歸解決?！?7 Ordering Tasks】John有n項任務要做。不幸的是，這些任務并不是獨立的，有的任務只有在其他一些任務完成以后才能開始做。輸入：輸入由幾個測試用例組成。每個用例的第

40、一行給出兩個整數(shù)：1n100和m。n是任務的數(shù)量 (從1到n編號)，m 是在兩個任務之間直接優(yōu)先關系的數(shù)量。然后是m行，每行兩個整數(shù)i和j，表示任務i必須在任務j之前執(zhí)行。以實例n=m=0結束輸入。輸出：對每個測試用例，輸出一行，給出n個整數(shù)，表示任務執(zhí)行的一個可能的順序。樣例輸入樣例輸出5 41 22 31 31 50 01 4 2 5 3注： 試題來源：GWCF Contest 2 （Golden Wedding Contest Festival）在線測試：UVA 10305提示任務作為節(jié)點，兩個任務之間的直接優(yōu)先關系作為邊：若任務i必須在任務j之前執(zhí)行，則對應有向邊<i-1,j-1

41、>，這樣可將任務間的先后關系轉化為一張有向圖，使得任務執(zhí)行的一個可能的順序對應這張有向圖的拓撲排序。設節(jié)點的入度序列為ind，其中節(jié)點i的入度為indi(0in-1)；鄰接表為lis，其中節(jié)點i的所有出邊的另一端點存儲在lisi中，lisi為一個List容器隊列q存儲當前入度為0的節(jié)點，隊首指針為h，隊尾指針為t；我們在輸入信息的同時構建鄰接表lis，計算節(jié)點的入度序列為ind，并將所有入度為0的節(jié)點送入隊列q；然后依次處理q隊列中每個入度為0的節(jié)點： 取出隊首節(jié)點x； lisx容器中每個相鄰節(jié)點的入度-1，相當于刪除x的所有出邊； 新增入度為0的節(jié)點入q隊列；依次類推，直至隊列空為止。

42、相繼出隊的節(jié)點q0qn-1 即為一個拓撲序列?！?8 Spreadsheet】在1979年，Dan Bricklin和Bob Frankston編寫了第一個電子制表應用軟件VisiCalc，這一軟件獲得了巨大的成功，并且在那時成為Apple II計算機的重要應用軟件?，F(xiàn)在電子制表是大多數(shù)計算機的重要的應用軟件。電子制表的思想非常簡單，但非常實用。一個電子制表由一個表格組成，每個項不是一個數(shù)字就是一個公式。一個公式可以基于其他項的值計算一個表達式。文本和圖形也可以加入用于表示。請編寫一個非常簡單的電子制表應用程序，輸入若干份表格，表格的每一個項或者是數(shù)字（僅為整數(shù)），或者是支持求和的公式。在計算

43、了所有公式的值以后，程序輸出結果表格，所有的公式都已經(jīng)被它們的值代替。 輸入：輸入文件第一行給出測試用例中的表格的數(shù)目。每個表格的第一行給出用一個空格分開的兩個整數(shù)，表示表格的列數(shù)和行數(shù)，然后給出表格，每行表示表格的一行，每行由該行的項組成，每個項用一個空格分開。 一個項或者是一個數(shù)字值，或者是一個公式。一個公式由一個等號開始(=)，后面是一個或多個用加號(+)分開的項的名稱，這樣公式的值是在相應的項中的所有值的總和。這些項也可以是一個公式，在公式中沒有空格?？梢栽O定在這些項之間沒有循環(huán)依賴，因此每個表格可以是完全可計算的。每一個項的名字是由1到3個字母（按列），后面跟著數(shù)字從1到999（按行

44、）組成。按列的字母構成如下序列：A, B, C, ., Z, AA, AB, AC, ., AZ, BA, ., BZ, CA, ., ZZ, AAA, AAB, ., AAZ, ABA, ., ABZ, ACA, ., ZZZ。這些字母相應于從1到18278的數(shù)字，如圖所示，左上角的項取名為A1。左上方的項的命名圖 輸出：除了表格的數(shù)目以及列和行的數(shù)目不重復以外，程序輸出和輸入的格式一樣。而且，所有的公式要被它們的值取代。樣例輸入樣例輸出14 310 34 37 =A1+B1+C140 17 34 =A2+B2+C2=A1+A2 =B1+B2 =C1+C2 =D1+D210 34 37 81

45、40 17 34 9150 51 71 172注： 試題來源：1995 ACM Southwestern European Regional Contest在線測試：POJ 1420，UVA 196提示在表達式中各項的命名格式，字母AZZZ代表列，數(shù)字1999代表行。需要將列字母轉化為列序號，行數(shù)串轉化為行序號。轉化方法：A代表1，Z代表26，字母序列ckc1對應一個26進制的列序號y=；數(shù)串bpb1應一個十進制的行序號x=。即表達式中的項ckc1 bpb1對應表格位置（x，y）。 設數(shù)值表格為w； 表達式項所在位置值為d，（i,j）對應位置值d=j*1000+i，即d % 1000為行號，為

46、列號。 我們將表格轉化為一個有向圖：每項為一個節(jié)點，數(shù)值項與表達式項間的關聯(lián)關系為有向邊。若數(shù)值項（x,y）對應表達式項（i,j）中的某項，則（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）的位置值送入gxy鄰接表，并累計（i,j）的入度（+indij）。

47、使用刪邊法計算有向圖的拓撲序列首先將圖中所有入度為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】火星人直系親屬關系的系統(tǒng)非?；靵y?；鹦侨嗽诓煌娜后w中群居生活，因此一個火星

48、人可以有一個父母，甚至也可以有十個父母；而且一個火星人有100個孩子也不會讓人感到奇怪。火星人已經(jīng)習慣了這樣的生活方式，對于他們來說這很自然。在行星理事會（Planetary Council）中，這樣混亂的家譜系統(tǒng)導致了一些尷尬。這些火星人中的杰出人士去參加會議，為了在討論中不冒犯長輩，討論中總是輩分高的火星人優(yōu)先發(fā)言，然后是輩分低的火星人發(fā)言，最后是輩分最低還沒有子女的火星人發(fā)言。然而，這個秩序的維持確實不是一個簡單的任務。一個火星人并不知道他所有的父母（當然也不知道他的所有的祖父母），但如果一個孫子在比他年輕的曾祖父之前發(fā)言，這就是一個重大的錯誤了。請編寫一個程序，對所有的成員定義一個次序

49、，這個次序要保證理事會的每一個成員所在的位置先于他的所有后代。輸入：標準輸入的第一行只包含一個整數(shù)N，1N100，表示火星理事會（Martian Planetary Council）的成員數(shù)。理事會成員的編號從1到N。在后面給出N行，而且第i行給出第i個成員的孩子的列表。孩子的列表是孩子編號按任意次序用空格分開的一個序列。孩子的列表可以為空。列表（即使是空列表）以0結束。輸出：標準輸出僅給出一行，給出一個編號的序列，編號以空格分開。如果存在幾個序列滿足這一問題的條件，請輸出其中任何一個。這樣的序列至少存在一個。樣例輸入樣例輸出504 5 1 01 05 3 03 02 4 5 3 1注： 試題

50、來源：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中的每個節(jié)點： 取隊首節(jié)點x；x的每個兒子的入度-1。若減至0，則該兒子進入隊列q； 依次類推，直至隊列空為止。 最后輸出輸出拓撲序列，即q的出隊順序?！?0

51、 Rare Order】一個珍稀書籍的收藏家最近發(fā)現(xiàn)了一本用一種陌生的語言寫的一本書，這種語言采用和英語一樣的字母。這本書有簡單的索引，但在索引中的條目的次序不同于根據(jù)英語字母表給出的字典排序的次序。這位收藏家試圖通過索引來確定這個古怪的字母表的字符的次序，(即對索引條目組成的序列進行整理)，但因為任務冗長而乏味，就放棄了。請編寫程序完成這位收藏家的任務，程序輸入一個按特定的序列排序的字符串集合，確定字符的序列是什么。輸入：輸入是由大寫字母組成的字符串的有序列表，每行一個字符串。每個字符串最多包含20個字符。該列表的結束標志是一個單一字符的一行。并不是所有的字母都被用到，但該列表蘊涵對于被采用

52、的那些字母存在著一個完全的次序。 輸出：輸出一行大寫字母，字母的排序順序列按輸入數(shù)據(jù)進行整理所給出。 樣例輸入樣例輸出XWYZXZXYZXWYWWX#XZYW注： 試題來源：1990 ACM ICPC World Finals 在線測試：UVA 200，UVA 5139提示輸入字符串的有序列表T（T表的長度為tot），按照下述方法將T表轉化為有向圖的相鄰矩陣v：每個大寫字母為一個節(jié)點，節(jié)點序號為字母對應的數(shù)值（大寫字母序列AZ映射為數(shù)值序列126），T表中同一位置上不同字母代表的節(jié)點間連有向邊：for (int i = 0; i < tot; i+)for (int j = i + 1;

53、 j < tot; j+) len = min(Ti的串長, Tj的串長); for (int k=0; k<len; k+) if (Ti中第k個字母 != Tj中第k個字母) vTi中第k個字母對應的節(jié)點序號Tj中第k個字母對應的節(jié)點序號=true; break; 計算有向圖的拓撲序列，拓撲序列中節(jié)點對應的字母即為字母表中字符的次序。計算方法如下初始化：置圖中所有節(jié)點未訪問標志，統(tǒng)計節(jié)點的入度（若vij=true，則inqi=inqj=true，+indj。1i,j26）；將入度為0的節(jié)點（inqi && indi=0）送入隊列q。依次處理隊列q中的節(jié)點：取出隊首節(jié)點x，x的所有相鄰節(jié)點i的入度減1。若減至0（vxi && -indi = 0），則i節(jié)點入隊。依此類推，直至隊列空為止。此時出隊順序對應的字母即為字母表中字符的次序。綜合題：【21 Pushing Boxes】想象您正站在一個二維的迷宮中，迷宮由是正方形的方格組成，這些方格可能被巖石阻塞，也可能沒有。您可以向北，南，東或西一步移到下一個方格。這些移動被稱為行走（walk）。 在一個空方格中放置了一個箱子，您可以挨著箱子站著，然后按這個方向推動這個箱子，這個箱子就可以