藍(lán)橋杯題庫中的算法訓(xùn)練試題資料

1、登錄后才能查看試題。1. 算法訓(xùn)練 P1103  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3編程實現(xiàn)兩個復(fù)數(shù)的運算。設(shè)有兩個復(fù)數(shù) 和 ，則他們的運算公式為：要求：（1）定義一個結(jié)構(gòu)體類型來描述復(fù)數(shù)。（2）復(fù)數(shù)之間的加法、減法、乘法和除法分別用不用的函數(shù)來實現(xiàn)。（3）必須使用結(jié)構(gòu)體指針的方法把函數(shù)的計算結(jié)果返回。說明：用戶輸入：運算符號(+,-,*,/) a b c d.輸出：a+bi，輸出時不管a,b是小于0或等于0都按該格式輸出，輸出時a,b都保留兩位。輸入：- 2.5 3.6 1.5 4.9輸出：1.00+-1.30i2. 算法訓(xùn)練 Lift a

2、nd Throw  時間限制：3.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述給定一條標(biāo)有整點(1, 2, 3, .)的射線. 定義兩個點之間的距離為其下標(biāo)之差的絕對值.Laharl, Etna, Flonne一開始在這條射線上不同的三個點, 他們希望其中某個人能夠到達(dá)下標(biāo)最大的點.每個角色只能進行下面的3種操作, 且每種操作不能每人不能進行超過一次.1.移動一定的距離2.把另一個角色高舉過頭3.將舉在頭上的角色扔出一段距離每個角色有一個movement range參數(shù), 他們只能移動到?jīng)]有人的位置, 并且起點和終點的距離不超過movement range.

3、如果角色A和另一個角色B距離為1, 并且角色B沒有被別的角色舉起, 那么A就能舉起B(yǎng). 同時, B會移動到A的位置,B原來所占的位置變?yōu)闆]有人的位置. 被舉起的角色不能進行任何操作, 舉起別人的角色不能移動.同時, 每個角色還有一個throwing range參數(shù), 即他能把舉起的角色扔出的最遠(yuǎn)的距離. 注意, 一個角色只能被扔到?jīng)]有別的角色占據(jù)的位置. 我們認(rèn)為一個角色舉起另一個同樣舉起一個角色的角色是允許的. 這種情況下會出現(xiàn)3個人在同一個位置的情況. 根據(jù)前面的描述, 這種情況下上面的兩個角色不能進行任何操作, 而最下面的角色可以同時扔出上面的兩個角色. 你的任務(wù)是計算這些角色能夠到達(dá)的

4、位置的最大下標(biāo), 即最大的數(shù)字x, 使得存在一個角色能夠到達(dá)x.輸入格式輸入共三行, 分別為Laharl, Etna, Floone的信息.每一行有且僅有3個整數(shù), 描述對應(yīng)角色的初始位置, movement range, throwing range.數(shù)據(jù)保證3個角色的初始位置兩兩不相同且所有的數(shù)字都在1到10之間.</div>輸出格式僅有1個整數(shù), 即Laharl, Etna, Flonne之一能到達(dá)的最大距離.樣例輸入9 3 34 3 12 3 3樣例輸出15樣例說明一開始Laharl在位置9, Etna在位置4, Flonne在位置2.首先, Laharl移動到6.然后Fl

5、onne移動到位置5并且舉起Etna.Laharl舉起Flonne將其扔到位置9.Flonne把Etna扔到位置12.Etna移動到位置15.3. 算法訓(xùn)練 Multithreading  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述現(xiàn)有如下一個算法：repeat ni timesyi := yy := yi+1end repeat令n1為你需要算加法的第一個數(shù)字，n2為第二個，.nN為第N個數(shù)字（N為需要算加法的數(shù)字個數(shù)），并令y初始值為0，先令i=1運行這個算法（如上所示，重復(fù)ni次），然后令i=2運行這個算法。直到i=N。注意y值一直不要

6、清零。最后y的值就是你需要的加法答案。你想知道，有沒有某種運算順序能使答案等于W。一個循環(huán)中的全部語句，是不能改變在總的語句排列中的相對順序的。（這里的第i個循環(huán)是指這ni*2條語句。就是你把屬于第i個循環(huán)的語句抽出來看，它們需要按照原順序排列。在你沒有運行完這個循環(huán)的最靠前一條未完成的 語句的時候，你是不能跳過它先去完成這個循環(huán)后面的語句的。你能做的僅是把若干個循環(huán)按照你所規(guī)定的順序“歸并”起來。）舉個例子，n1= 2 ,n2=1, W=1.一種可行的運算順序是“2 1 1 1 1 2”，數(shù)字為幾表示運行第幾個算法的下一條語句（你可以看到”1”出現(xiàn)了4次，是因為n1=2即循環(huán)兩次，而每次循環(huán)

7、里面有兩條語句，所以2*2=4次）y值y1 值y2 值執(zhí)行0條語句過后000執(zhí)行1條過后(y2=y)000執(zhí)行2條過后(y1=y)000執(zhí)行3條過后(y=y1+1)100執(zhí)行4條過后(y1=y)110執(zhí)行5條過后(y=y1+1)210執(zhí)行6條過后(y=y2+1)110可以看到，最后y值變成了1，也就完成了我們的任務(wù)。輸入格式第一行你會得到用空格分開的兩個整數(shù)N(1<=N<=100)和W(-109<=W<=109)，（N為需要算加法的數(shù)字個數(shù)，W是你希望算出的數(shù)）。第二行你會得到n個整數(shù)ni (1<=ni<=1000).輸出格式第一行您應(yīng)該輸出Yes(若能以某

8、種順序使得這個算法得出W的值) 或No。如果第一行是No，接下來就不用繼續(xù)輸出了。如果是Yes, 請在第2行輸出2*sigma(ni)個用空格隔開的數(shù)，表示任意一種滿足條件的運算順序。樣例輸入1 1011樣例輸出No樣例輸入2 34 4樣例輸出Yes1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 2樣例輸入3 61 2 3樣例輸出Yes1 1 2 2 2 2 3 3 3 3 3 3數(shù)據(jù)規(guī)模和約定對于30%的數(shù)據(jù)，n<=4, ni的和小于10.對于100%的數(shù)據(jù)，n<=100 , -109<=W<=109, 1<=ni<=10004. 算法訓(xùn)練 T

9、ricky and Clever Password  時間限制：2.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述在年輕的時候，我們故事中的英雄國王 Copa他的私人數(shù)據(jù)并不是完全安全地隱蔽。對他來說是，這不可接受的。因此，他發(fā)明了一種密碼，好記又難以破解。后來，他才知道這種密碼是一個長度為奇數(shù)的回文串。Copa 害怕忘記密碼，所以他決定把密碼寫在一張紙上。他發(fā)現(xiàn)這樣保存密碼不安全，于是他決定按下述方法加密密碼：他選定一個整數(shù) X ，保證 X 不小于 0 ，且 2X 嚴(yán)格小于串長度。然后他把密碼分成 3 段，最前面的 X 個字符為一段，最后面的 X 個字符為一

10、段，剩余的字符為一段。不妨把這三段依次稱之為 prefix, suffix, middle 。顯然， middle 的長度為一個大于 0 的奇數(shù)，且 prefix 、 suffix 的長度相等。他加密后的密碼即為 A + prefix + B + middle + C + suffix ，其中 A 、 B 、 C 是三個由 Copa 選定的字符串，且都有可能為空， + 表示字符串相連。許多年過去了。Copa 昨天找到了當(dāng)年寫下加密后字符串的那張紙。但是，Copa 把原密碼、A、B、C 都忘了?，F(xiàn)在，他請你找一個盡量長的密碼，使得這個密碼有可能被當(dāng)年的 Copa 發(fā)明、加密并寫下。輸入格式輸入包

11、含一個只含有小寫拉丁字母的字符串，長度在 1 到 105 之內(nèi)。輸出格式第一行包含一個整數(shù) k ，表示你找到的原密碼分成的 3 個部分中有多少個非空字符串。顯然 k in 1, 3 。接下來 k 行，每行 2 個用空格分開的整數(shù) x_i l_i ，表示這一部分的起始位置和長度。要求輸出的 x_i 遞增。起始位置 x_i 應(yīng)該在 1 到加密后的字符串長度之間。 l_i 必須是正整數(shù)，因為你只要輸出非空部分的信息。 middle 的長度必須為奇數(shù)。如果有多組答案，任意一組即可。提示：你要最大化的是輸出的 l_i 的總和，而不是 k 。樣例輸入abacaba樣例輸出11 7樣例輸入axbya樣例輸出

12、31 12 15 1樣例輸入xabyczba樣例輸出32 24 17 2數(shù)據(jù)規(guī)模和約定對于 10% 的數(shù)據(jù)： n <= 10對于 30% 的數(shù)據(jù)： n <= 100對于 100% 的數(shù)據(jù)： n <= 100000存在 20% 的數(shù)據(jù)，輸出文件第一行為 1 。5. 算法訓(xùn)練 Beaver's Calculator  時間限制：3.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述從萬能詞典來的聰明的海貍已經(jīng)使我們驚訝了一次。他開發(fā)了一種新的計算器，他將此命名為"Beaver's Calculator 1.0"。它

13、非常特別，并且被計劃使用在各種各樣的科學(xué)問題中。為了測試它，聰明的海貍邀請了n位科學(xué)家，編號從1到n。第i位科學(xué)家給這個計算器帶來了 ki個計算題。第i個科學(xué)家?guī)淼膯栴}編號1到n，并且它們必須按照編號一個一個計算，因為對于每個問題的計算都必須依賴前一個問題的計算結(jié)果。每個教授的每個問題都用一個數(shù) ai,j 來描述，i（1in）是科學(xué)家的編號，j（1j ki ）是問題的編號， ai,j 表示解決這個問題所需資源單位的數(shù)量。這個計算器非常不凡。它一個接一個的解決問題。在一個問題解決后，并且在下一個問題被計算前，計算器分配或解放資源。計算器中最昂貴的操作是解放資源，解放遠(yuǎn)遠(yuǎn)慢于分配。所以對計算器而

14、言，每一個接下來的問題所需的資源不少于前一個，是非常重要的。給你關(guān)于這些科學(xué)家所給問題的相關(guān)信息。你需要給這些問題安排一個順序，使得“壞對”盡可能少。所謂“壞對”，就是相鄰兩個問題中，后一個問題需求的資源比前一個問題少。別忘了，對于同一個科學(xué)家給出的問題，計算它們的相對順序必須是固定的。輸入格式第一行包含一個整數(shù)n，表示科學(xué)家的人數(shù)。接下來n行每行有5個整數(shù)，ki, ai,1, xi, yi, mi (0ai,1<mi109, 1xi,yi109) ，分別表示第i個科學(xué)家的問題個數(shù)，第1個問題所需資源單位數(shù)，以及3個用來計算 ai,j 的參量。ai,j=(ai,j-1*xi+yi)mod

15、 mi。輸出格式第一行輸出一個整數(shù)，表示最優(yōu)順序下最少的“壞對”個數(shù)。如果問題的總個數(shù)不超過200000,接下來輸出 行，表示解決問題的最優(yōu)順序。每一行兩個用空格隔開的整數(shù)，表示這個問題所需的資源單位數(shù)和提供這個問題的科學(xué)家的編號。樣例輸入22 1 1 1 102 3 1 1 10樣例輸出01 12 13 24 2數(shù)據(jù)規(guī)模和約定20%的數(shù)據(jù) n=2, 1ki2000；另外30%的數(shù)據(jù) n=2, 1ki200000；剩下50%的數(shù)據(jù) 1n5000, 1ki5000。6. 算法訓(xùn)練 Cowboys  時間限制：2.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述一個

16、間不容發(fā)的時刻：n個牛仔站立于一個環(huán)中，并且每個牛仔都用左輪手槍指著他旁邊的人！每個牛仔指著他順時針或者逆時針方向上的相鄰的人。正如很多西部片那樣，在這一刻，繩命是入刺的不可惜對峙的場景每秒都在變化。每秒鐘牛仔們都會分析局勢，當(dāng)一對相鄰的牛仔發(fā)現(xiàn)他們正在互指的時候，就會轉(zhuǎn)過身。一秒內(nèi)每對這樣的牛仔都會轉(zhuǎn)身。所有的轉(zhuǎn)身都同時在一瞬間發(fā)生。我們用字母來表示牛仔所指的方向?！癆”表示順時針方向，“B”表示逆時針方向。如此，一個僅含“A”“B”的字符串便用來表示這個由牛仔構(gòu)成的環(huán)。這是由第一個指著順時針方向的牛仔做出的記錄。例如，牛仔環(huán)“ABBBABBBA”在一秒后會變成“BABBBABBA”；而牛仔

17、環(huán)“BABBA”會變成“ABABB”。 這幅圖說明了“BABBA”怎么變成“ABABB” 一秒過去了，現(xiàn)在用字符串s來表示牛仔們的排列。你的任務(wù)是求出一秒前有多少種可能的排列。如果某個排列中一個牛仔指向順時針，而在另一個排列中他指向逆時針，那么這兩個排列就是不同的。輸入格式輸入數(shù)據(jù)包括一個字符串s，它只含有“A”和“B”。輸出格式輸出你求出來的一秒前的可能排列數(shù)。數(shù)據(jù)規(guī)模和約定s的長度為3到100（包含3和100）樣例輸入BABBBABBA樣例輸出2樣例輸入ABABB樣例輸出2樣例輸入ABABAB樣例輸出4樣例說明測試樣例一中，可能的初始排列為："ABBBABBAB"和 &

18、quot;ABBBABBBA"。測試樣例二中，可能的初始排列為："AABBB"和"BABBA"。7. 算法訓(xùn)練 數(shù)字三角形  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述（圖.）示出了一個數(shù)字三角形。 請編一個程序計算從頂至底的某處的一條路徑，使該路徑所經(jīng)過的數(shù)字的總和最大。每一步可沿左斜線向下或右斜線向下走；1三角形行數(shù)100；三角形中的數(shù)字為整數(shù)0，1，99；.（圖.）輸入格式文件中首先讀到的是三角形的行數(shù)。接下來描述整個三角形輸出格式最大總和（整數(shù)）樣例輸入573 88 1 02 7 4

19、44 5 2 6 5樣例輸出308. 算法訓(xùn)練 未名湖邊的煩惱  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述每年冬天，北大未名湖上都是滑冰的好地方。北大體育組準(zhǔn)備了許多冰鞋，可是人太多了，每天下午收工后，常常一雙冰鞋都不剩。每天早上，租鞋窗口都會排起長龍，假設(shè)有還鞋的m個，有需要租鞋的n個。現(xiàn)在的問題是，這些人有多少種排法，可以避免出現(xiàn)體育組沒有冰鞋可租的尷尬場面。（兩個同樣需求的人（比如都是租鞋或都是還鞋）交換位置是同一種排法）輸入格式兩個整數(shù)，表示m和n輸出格式一個整數(shù)，表示隊伍的排法的方案數(shù)。樣例輸入3 2樣例輸出5數(shù)據(jù)規(guī)模和約定m,n

20、0,18問題分析9. 算法訓(xùn)練 最大的算式  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述題目很簡單，給出N個數(shù)字，不改變它們的相對位置，在中間加入K個乘號和N-K-1個加號，（括號隨便加）使最終結(jié)果盡量大。因為乘號和加號一共就是N-1個了，所以恰好每兩個相鄰數(shù)字之間都有一個符號。例如：N=5，K=2，5個數(shù)字分別為1、2、3、4、5，可以加成：1*2*(3+4+5)=241*(2+3)*(4+5)=45(1*2+3)*(4+5)=45輸入格式輸入文件共有二行，第一行為兩個有空格隔開的整數(shù)，表示N和K，其中（2<=N<=15, 0&

21、lt;=K<=N-1）。第二行為 N個用空格隔開的數(shù)字（每個數(shù)字在0到9之間）。輸出格式輸出文件僅一行包含一個整數(shù)，表示要求的最大的結(jié)果樣例輸入5 21 2 3 4 5樣例輸出120樣例說明(1+2+3)*4*5=12010. 算法訓(xùn)練 圖形顯示  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述編寫一個程序，首先輸入一個整數(shù)，例如5，然后在屏幕上顯示如下的圖形（5表示行數(shù)）：* * * * * * * * * * *11. 算法訓(xùn)練 排序  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述編寫一

22、個程序，輸入3個整數(shù)，然后程序?qū)@三個整數(shù)按照從大到小進行排列。輸入格式：輸入只有一行，即三個整數(shù)，中間用空格隔開。輸出格式：輸出只有一行，即排序后的結(jié)果。輸入輸出樣例樣例輸入9 2 30樣例輸出30 9 2登錄后才能查看試題。12. 算法訓(xùn)練 2的次冪表示  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述任何一個正整數(shù)都可以用2進制表示，例如：137的2進制表示為10001001。將這種2進制表示寫成2的次冪的和的形式，令次冪高的排在前面，可得到如下表達(dá)式：137=27+23+20現(xiàn)在約定冪次用括號來表示，即ab表示為a（b）此時，137可表

23、示為：2（7）+2（3）+2（0）進一步：7=22+2+20 （21用2表示）3=2+20 所以最后137可表示為：2（2（2）+2+2（0）+2（2+2（0）+2（0）又如：1315=210+28+25+2+1所以1315最后可表示為：2（2（2+2（0）+2）+2（2（2+2（0）+2（2（2）+2（0）+2+2（0）輸入格式正整數(shù)（1<=n<=20000）輸出格式符合約定的n的0，2表示（在表示中不能有空格）樣例輸入137樣例輸出2(2(2)+2+2(0)+2(2+2(0)+2(0)樣例輸入1315樣例輸出2(2(2+2(0)+2)+2(2(2+2(0)+2(2(2)+2(0

24、)+2+2(0)提示用遞歸實現(xiàn)會比較簡單，可以一邊遞歸一邊輸出13. 算法訓(xùn)練 前綴表達(dá)式  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述編寫一個程序，以字符串方式輸入一個前綴表達(dá)式，然后計算它的值。輸入格式為：“運算符 對象1 對象2”，其中，運算符為“+”（加法）、“-”（減法）、“*”（乘法）或“/”（除法），運算對象為不超過10的整數(shù)，它們之間用一個空格隔開。要求：對于加、減、乘、除這四種運算，分別設(shè)計相應(yīng)的函數(shù)來實現(xiàn)。輸入格式：輸入只有一行，即一個前綴表達(dá)式字符串。輸出格式：輸出相應(yīng)的計算結(jié)果（如果是除法，直接采用c語言的“/”運算符

25、，結(jié)果為整數(shù)）。輸入輸出樣例樣例輸入+ 5 2樣例輸出714. 算法訓(xùn)練 Anagrams問題  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述Anagrams指的是具有如下特性的兩個單詞：在這兩個單詞當(dāng)中，每一個英文字母（不區(qū)分大小寫）所出現(xiàn)的次數(shù)都是相同的。例如，“Unclear”和“Nuclear”、“Rimon”和“MinOR”都是Anagrams。編寫一個程序，輸入兩個單詞，然后判斷一下，這兩個單詞是否是Anagrams。每一個單詞的長度不會超過80個字符，而且是大小寫無關(guān)的。輸入格式：輸入有兩行，分別為兩個單詞。輸出格式：輸出只有一個

26、字母Y或N，分別表示Yes和No。輸入輸出樣例樣例輸入UnclearNuclear樣例輸出Y15. 算法訓(xùn)練 出現(xiàn)次數(shù)最多的整數(shù)  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述編寫一個程序，讀入一組整數(shù)，這組整數(shù)是按照從小到大的順序排列的，它們的個數(shù)N也是由用戶輸入的，最多不會超過20。然后程序?qū)@個數(shù)組進行統(tǒng)計，把出現(xiàn)次數(shù)最多的那個數(shù)組元素值打印出來。如果有兩個元素值出現(xiàn)的次數(shù)相同，即并列第一，那么只打印比較小的那個值。輸入格式：第一行是一個整數(shù)N，N £ 20；接下來有N行，每一行表示一個整數(shù)，并且按照從小到大的順序排列。輸出格

27、式：輸出只有一行，即出現(xiàn)次數(shù)最多的那個元素值。輸入輸出樣例樣例輸入5100150150200250樣例輸出15016. 算法訓(xùn)練 字串統(tǒng)計  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述給定一個長度為n的字符串S，還有一個數(shù)字L，統(tǒng)計長度大于等于L的出現(xiàn)次數(shù)最多的子串（不同的出現(xiàn)可以相交），如果有多個，輸出最長的，如果仍然有多個，輸出第一次出現(xiàn)最早的。輸入格式第一行一個數(shù)字L。第二行是字符串S。L大于0，且不超過S的長度。輸出格式一行，題目要求的字符串。輸入樣例1：4bbaabbaaaaa輸出樣例1：bbaa輸入樣例2：2bbaabbaaaaa

28、輸出樣例2：aa數(shù)據(jù)規(guī)模和約定n<=60S中所有字符都是小寫英文字母。提示枚舉所有可能的子串，統(tǒng)計出現(xiàn)次數(shù)，找出符合條件的那個17. 算法訓(xùn)練 矩陣乘法  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述輸入兩個矩陣，分別是m*s，s*n大小。輸出兩個矩陣相乘的結(jié)果。輸入格式第一行，空格隔開的三個正整數(shù)m,s,n（均不超過200）。接下來m行，每行s個空格隔開的整數(shù)，表示矩陣A（i，j）。接下來s行，每行n個空格隔開的整數(shù)，表示矩陣B（i，j）。輸出格式m行，每行n個空格隔開的整數(shù)，輸出相乘後的矩陣C（i，j）的值。樣例輸入2 3 21 0

29、-11 1 -30 31 23 1樣例輸出-3 2-8 2提示矩陣C應(yīng)該是m行n列，其中C(i,j)等于矩陣A第i行行向量與矩陣B第j列列向量的內(nèi)積。例如樣例中C(1,1)=(1,0,-1)*(0,1,3) = 1 * 0 +0*1+(-1)*3=-318. 算法訓(xùn)練 大小寫轉(zhuǎn)換  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述編寫一個程序，輸入一個字符串（長度不超過20），然后把這個字符串內(nèi)的每一個字符進行大小寫變換，即將大寫字母變成小寫，小寫字母變成大寫，然后把這個新的字符串輸出。輸入格式：輸入一個字符串，而且這個字符串當(dāng)中只包含英文字母，不

30、包含其他類型的字符，也沒有空格。輸出格式：輸出經(jīng)過轉(zhuǎn)換后的字符串。輸入輸出樣例樣例輸入AeDb樣例輸出aEdB19. 算法訓(xùn)練 動態(tài)數(shù)組使用  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3從鍵盤讀入n個整數(shù)，使用動態(tài)數(shù)組存儲所讀入的整數(shù)，并計算它們的和與平均值分別輸出。要求盡可能使用函數(shù)實現(xiàn)程序代碼。平均值為小數(shù)的只保留其整數(shù)部分。樣例輸入: 5 3 4 0 0 2樣例輸出:9 1樣例輸入: 73 2 7 5 2 9 1樣例輸出:29 420. 算法訓(xùn)練 刪除數(shù)組零元素  時間限制：1.0s   內(nèi)存限制：512.0MB 

31、   錦囊1錦囊2錦囊3從鍵盤讀入n個整數(shù)放入數(shù)組中，編寫函數(shù)CompactIntegers，刪除數(shù)組中所有值為0的元素，其后元素向數(shù)組首端移動。注意，CompactIntegers函數(shù)需要接受數(shù)組及其元素個數(shù)作為參數(shù)，函數(shù)返回值應(yīng)為刪除操作執(zhí)行后數(shù)組的新元素個數(shù)。輸出刪除后數(shù)組中元素的個數(shù)并依次輸出數(shù)組元素。樣例輸入: （輸入格式說明：5為輸入數(shù)據(jù)的個數(shù)，3 4 0 0 2 是以空格隔開的5個整數(shù)）5 3 4 0 0 2樣例輸出:（輸出格式說明：3為非零數(shù)據(jù)的個數(shù)，3 4 2 是以空格隔開的3個非零整數(shù)）33 4 2樣例輸入: 70 0 7 0 0 9 0樣例輸出:27 9樣例輸入

32、: 30 0 0樣例輸出:021. 算法訓(xùn)練 最小乘積(基本型)  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述給兩組數(shù)，各n個。請調(diào)整每組數(shù)的排列順序，使得兩組數(shù)據(jù)相同下標(biāo)元素對應(yīng)相乘，然后相加的和最小。要求程序輸出這個最小值。例如兩組數(shù)分別為:1 3-5和-2 4 1那么對應(yīng)乘積取和的最小值應(yīng)為：(-5) * 4 + 3 * (-2) + 1 * 1 = -25輸入格式第一個行一個數(shù)T表示數(shù)據(jù)組數(shù)。后面每組數(shù)據(jù)，先讀入一個n，接下來兩行每行n個數(shù)，每個數(shù)的絕對值小于等于1000。n<=8,T<=1000輸出格式一個數(shù)表示答案。樣

33、例輸入231 3 -5-2 4 151 2 3 4 51 0 1 0 1樣例輸出-256登錄后才能查看試題。22. 算法訓(xùn)練 Torry的困惑(基本型)  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述Torry從小喜愛數(shù)學(xué)。一天，老師告訴他，像2、3、5、7這樣的數(shù)叫做質(zhì)數(shù)。Torry突然想到一個問題，前10、100、1000、10000個質(zhì)數(shù)的乘積是多少呢？他把這個問題告訴老師。老師愣住了，一時回答不出來。于是Torry求助于會編程的你，請你算出前n個質(zhì)數(shù)的乘積。不過，考慮到你才接觸編程不久，Torry只要你算出這個數(shù)模上50000的值。輸入

34、格式僅包含一個正整數(shù)n，其中n<=100000。輸出格式輸出一行，即前n個質(zhì)數(shù)的乘積模50000的值。樣例輸入1樣例輸出2登錄后才能查看試題。23. 算法訓(xùn)練 尋找數(shù)組中最大值  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述對于給定整數(shù)數(shù)組a,尋找其中最大值，并返回下標(biāo)。輸入格式整數(shù)數(shù)組a,數(shù)組元素個數(shù)小于1等于100。輸出數(shù)據(jù)分作兩行：第一行只有一個數(shù)，表示數(shù)組元素個數(shù)；第二行為數(shù)組的各個元素。輸出格式輸出最大值，及其下標(biāo)樣例輸入33 2 1樣例輸出3 024. 算法訓(xùn)練 關(guān)聯(lián)矩陣  時間限制：1.0s   內(nèi)存限制

35、：512.0MB錦囊1錦囊2錦囊3問題描述有一個n個結(jié)點m條邊的有向圖，請輸出他的關(guān)聯(lián)矩陣。輸入格式第一行兩個整數(shù)n、m，表示圖中結(jié)點和邊的數(shù)目。n<=100,m<=1000。接下來m行，每行兩個整數(shù)a、b，表示圖中有(a,b)邊。注意圖中可能含有重邊，但不會有自環(huán)。輸出格式輸出該圖的關(guān)聯(lián)矩陣，注意請勿改變邊和結(jié)點的順序。樣例輸入5 91 23 11 52 52 32 33 24 35 4樣例輸出1 -1 1 0 0 0 0 0 0-1 0 0 1 1 1 -1 0 00 1 0 0 -1 -1 1 -1 00 0 0 0 0 0 0 1 -10 0 -1 -1 0 0 0 0 1

36、25. 算法訓(xùn)練 送分啦  時間限制：1.0s   內(nèi)存限制：512.0MB錦囊1錦囊2錦囊3問題描述這題想得分嗎？想，請輸出“yes”；不想，請輸出“no”。輸出格式輸出包括一行，為“yes”或“no”。 26. 算法訓(xùn)練 操作格子  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述有n個格子，從左到右放成一排，編號為1-n。共有m次操作，有3種操作類型：1.修改一個格子的權(quán)值，2.求連續(xù)一段格子權(quán)值和，3.求連續(xù)一段格子的最大值。對于每個2、3操作輸出你所求出的結(jié)果。輸入格式第一行2個整數(shù)n，m。接下來一行n個整數(shù)

37、表示n個格子的初始權(quán)值。接下來m行，每行3個整數(shù)p,x,y，p表示操作類型，p=1時表示修改格子x的權(quán)值為y，p=2時表示求區(qū)間x,y內(nèi)格子權(quán)值和，p=3時表示求區(qū)間x,y內(nèi)格子最大的權(quán)值。輸出格式有若干行，行數(shù)等于p=2或3的操作總數(shù)。每行1個整數(shù)，對應(yīng)了每個p=2或3操作的結(jié)果。樣例輸入4 31 2 3 42 1 31 4 33 1 4 樣例輸出63 數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù)n <= 100，m <= 200。對于50%的數(shù)據(jù)n <= 5000，m <= 5000。對于100%的數(shù)據(jù)1 <= n <= 100000，m <= 100000，0

38、 <= 格子權(quán)值 <= 10000。27. 算法訓(xùn)練 逆序?qū)? 時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述Alice是一個讓人非常愉躍的人!他總是去學(xué)習(xí)一些他不懂的問題，然后再想出許多稀奇古怪的題目。這幾天，Alice又沉浸在逆序?qū)Φ目鞓樊?dāng)中，他已近學(xué)會了如何求逆序?qū)?shù)，動態(tài)維護逆序?qū)?shù)等等題目，他認(rèn)為把這些題讓你做簡直是太沒追求了，于是，經(jīng)過一天的思考和完善，Alice終于拿出了一道他認(rèn)為差不多的題目：有一顆2n-1個節(jié)點的二叉樹，它有恰好n個葉子節(jié)點，每個節(jié)點上寫了一個整數(shù)。如果將這棵樹的所有葉子節(jié)點上的數(shù)從左到右寫下來，

39、便得到一個序列a1an?，F(xiàn)在想讓這個序列中的逆序?qū)?shù)量最少，但唯一的操作就是選樹上一個非葉子節(jié)點，將它的左右兩顆子樹交換。他可以做任意多次這個操作。求在最優(yōu)方案下，該序列的逆序?qū)?shù)最少有多少。Alice自己已近想出了題目的正解，他打算拿來和你分享，他要求你在最短的時間內(nèi)完成。輸入格式第一行一個整數(shù)n。下面每行，一個數(shù)x。如果x=0，表示這個節(jié)點非葉子節(jié)點，遞歸地向下讀入其左孩子和右孩子的信息，如果x0，表示這個節(jié)點是葉子節(jié)點，權(quán)值為x。輸出格式輸出一個整數(shù)，表示最少有多少逆序?qū)Α?樣例輸入300312 樣例輸出1 數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù)，n <= 5000。對于100%的數(shù)據(jù)，1

40、 <= n <= 200000，0 <= ai<231。28. 算法訓(xùn)練 安慰奶牛  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述Farmer John變得非常懶，他不想再繼續(xù)維護供奶牛之間供通行的道路。道路被用來連接N個牧場，牧場被連續(xù)地編號為1到N。每一個牧場都是一個奶牛的家。FJ計劃除去P條道路中盡可能多的道路，但是還要保持牧場之間 的連通性。你首先要決定那些道路是需要保留的N-1條道路。第j條雙向道路連接了牧場Sj和Ej(1 <= Sj <= N; 1 <= Ej <= N; Sj !=

41、Ej)，而且走完它需要Lj的時間。沒有兩個牧場是被一條以上的道路所連接。奶牛們非常傷心，因為她們的交通系統(tǒng)被削減了。你需要到每一個奶牛的住處去安慰她們。每次你到達(dá)第i個牧場的時候(即使你已經(jīng)到過)，你必須花去Ci的時間和奶牛交談。你每個晚上都會在同一個牧場(這是供你選擇的)過夜，直到奶牛們都從悲傷中緩過神來。在早上 起來和晚上回去睡覺的時候，你都需要和在你睡覺的牧場的奶牛交談一次。這樣你才能完成你的 交談任務(wù)。假設(shè)Farmer John采納了你的建議，請計算出使所有奶牛都被安慰的最少時間。輸入格式第1行包含兩個整數(shù)N和P。接下來N行，每行包含一個整數(shù)Ci。接下來P行，每行包含三個整數(shù)Sj, E

42、j和Lj。輸出格式輸出一個整數(shù), 所需要的總時間(包含和在你所在的牧場的奶牛的兩次談話時間)。 樣例輸入5 71010206301 2 52 3 52 4 123 4 172 5 153 5 6 樣例輸出176 數(shù)據(jù)規(guī)模與約定5 <= N <= 10000，N-1 <= P <= 100000，0 <= Lj <= 1000，1 <= Ci <= 1,000。29. 算法訓(xùn)練 最短路  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述給定一個n個頂點，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒有負(fù)

43、環(huán)）。請你計算從1號點到其他點的最短路（頂點從1到n編號）。輸入格式第一行兩個整數(shù)n, m。接下來的m行，每行有三個整數(shù)u, v, l，表示u到v有一條長度為l的邊。輸出格式共n-1行，第i行表示1號點到i+1號點的最短路。 樣例輸入3 31 2 -12 3 -13 1 2 樣例輸出-1-2 數(shù)據(jù)規(guī)模與約定對于10%的數(shù)據(jù)，n = 2，m = 2。對于30%的數(shù)據(jù)，n <= 5，m <= 10。對于100%的數(shù)據(jù)，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點都能到達(dá)其他

44、所有頂點。30. 算法訓(xùn)練 結(jié)點選擇  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述有一棵 n 個節(jié)點的樹，樹上每個節(jié)點都有一個正整數(shù)權(quán)值。如果一個點被選擇了，那么在樹上和它相鄰的點都不能被選擇。求選出的點的權(quán)值和最大是多少？輸入格式第一行包含一個整數(shù) n 。接下來的一行包含 n 個正整數(shù)，第 i 個正整數(shù)代表點 i 的權(quán)值。接下來一共 n-1 行，每行描述樹上的一條邊。輸出格式輸出一個整數(shù)，代表選出的點的權(quán)值和的最大值。 樣例輸入51 2 3 4 51 21 32 42 5 樣例輸出12 樣例說明選擇3、4、5號點，權(quán)值和為 3+4+5 =

45、12 。 數(shù)據(jù)規(guī)模與約定對于20%的數(shù)據(jù)， n <= 20。對于50%的數(shù)據(jù)， n <= 1000。對于100%的數(shù)據(jù)， n <= 100000。權(quán)值均為不超過1000的正整數(shù)。31. 算法訓(xùn)練 K好數(shù)  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述如果一個自然數(shù)N的K進制表示中任意的相鄰的兩位都不是相鄰的數(shù)字，那么我們就說這個數(shù)是K好數(shù)。求L位K進制數(shù)中K好數(shù)的數(shù)目。例如K = 4，L = 2的時候，所有K好數(shù)為11、13、20、22、30、31、33 共7個。由于這個數(shù)目很大，請你輸出它對1000000007取模后的值。輸

46、入格式輸入包含兩個正整數(shù)，K和L。輸出格式輸出一個整數(shù)，表示答案對1000000007取模后的值。 樣例輸入4 2 樣例輸出7 數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù)，KL <= 106；對于50%的數(shù)據(jù)，K <= 16， L <= 10；對于100%的數(shù)據(jù)，1 <= K,L <= 100。登錄后才能查看試題。32. 算法訓(xùn)練 最大最小公倍數(shù)  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述已知一個正整數(shù)N，問從1N中任選出三個數(shù)，他們的最小公倍數(shù)最大可以為多少。輸入格式輸入一個正整數(shù)N。輸出格式輸出一個整數(shù)，表示你找到的最

47、小公倍數(shù)。樣例輸入9樣例輸出504數(shù)據(jù)規(guī)模與約定1 <= N <= 106。登錄后才能查看試題。33. 算法訓(xùn)練 區(qū)間k大數(shù)查詢  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述給定一個序列，每次詢問序列中第l個數(shù)到第r個數(shù)中第K大的數(shù)是哪個。輸入格式第一行包含一個數(shù)n，表示序列長度。第二行包含n個正整數(shù)，表示給定的序列。第三個包含一個正整數(shù)m，表示詢問個數(shù)。接下來m行，每行三個數(shù)l,r,K，表示詢問序列從左往右第l個數(shù)到第r個數(shù)中，從大往小第K大的數(shù)是哪個。序列元素從1開始標(biāo)號。輸出格式總共輸出m行，每行一個數(shù)，表示詢問的答案。 樣

48、例輸入51 2 3 4 521 5 22 3 2 樣例輸出42 數(shù)據(jù)規(guī)模與約定對于30%的數(shù)據(jù)，n,m<=100；對于100%的數(shù)據(jù)，n,m<=1000；保證k<=(r-l+1)，序列中的數(shù)<=106。34. 法訓(xùn)練 P1102  VIP時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3定義一個學(xué)生結(jié)構(gòu)體類型student，包括4個字段，姓名、性別、年齡和成績。然后在主函數(shù)中定義一個結(jié)構(gòu)體數(shù)組（長度不超過1000），并輸入每個元素的值，程序使用冒泡排序法將學(xué)生按照成績從小到大的順序排序，然后輸出排序的結(jié)果。輸入格式：第一行是一個整數(shù)N

49、（N<1000），表示元素個數(shù)；接下來N行每行描述一個元素，姓名、性別都是長度不超過20的字符串，年齡和成績都是整型。輸出格式：按成績從小到大輸出所有元素，若多個學(xué)生成績相同則成績相同的同學(xué)之間保留原來的輸入順序。輸入：3Alice female 18 98Bob male 19 90Miller male 17 92輸出：Bob male 19 90Miller male 17 92Alice female 18 9835. 算法訓(xùn)練 P1101  時間限制：1.0s   內(nèi)存限制：256.0MB 錦囊1錦囊2錦囊3有一份提貨單，其數(shù)據(jù)項目有：商品名（MC）、單價（

50、DJ）、數(shù)量（SL）。定義一個結(jié)構(gòu)體prut，其成員是上面的三項數(shù)據(jù)。在主函數(shù)中定義一個prut類型的結(jié)構(gòu)體數(shù)組，輸入每個元素的值，計算并輸出提貨單的總金額。輸入格式：第一行是數(shù)據(jù)項個數(shù)N(N<100)，接下來每一行是一個數(shù)據(jù)項。商品名是長度不超過100的字符串，單價為double類型，數(shù)量為整型。輸出格式：double類型的總金額。輸入：4book 12.5 3pen 2.5 10computer 3200 1flower 47 5輸出：3497.50000036. 算法訓(xùn)練 s01串  時間限制：1.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述s0

51、1串初始為"0"按以下方式變換0變1，1變01輸入格式1個整數(shù)(019)輸出格式n次變換后s01串樣例輸入3樣例輸出101數(shù)據(jù)規(guī)模和約定01937. 算法訓(xùn)練 Representative Sampling (30_points)  時間限制：2.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3【題目描述】來自ABBYY的小明有一個與“細(xì)胞與遺傳學(xué)研究所”的合作。最近，研究所用一個新的題目考驗小明。題目如下。有由n個細(xì)胞組成的一個集合（不一定不同）每個細(xì)胞是一個由小寫拉丁字母組成的字符串?？茖W(xué)家給小明提出的問題是從給定集合中選出一個大小為k的子集，使

52、得所選子集的代表值最大。小明做了些研究并得出了一個結(jié)論，即一個蛋白質(zhì)集合的代表制可以用一個方便計算的整數(shù)來表示。我們假設(shè)當(dāng)前的集合為a1,.,ak，包含了k個用以表示蛋白質(zhì)的字符串。那么蛋白質(zhì)集合的代表值可以用如下的式子來表示：其中f(x,y)表示字符串x和y的最長公共前綴的長度，例如：f("abc", "abd")=2 ， f("ab", "bcd")=0.因此，蛋白質(zhì)集合"abc", "abd", "abe"的代表值等于6，集合"aaa&qu

53、ot;, "ba", "ba"的代表值等于2。在發(fā)現(xiàn)了這個之后，小明要求賽事參與者寫一個程序選出，給定蛋白質(zhì)的集合中的大小為k的子集中，能獲得最大可能代表性值得一個子集。幫助他解決這個問題吧！【輸入格式】輸入數(shù)據(jù)第一行包含2個正整數(shù)n和k（1kn），由一個空格隔開。接下來的n行每一行都包含對蛋白質(zhì)的描述。每個蛋白質(zhì)都是一個僅有不超過500個小寫拉丁字母組成的非空字符串。有些字符串可能是相等的。輸出格式輸出一個整數(shù)，表示給定蛋白質(zhì)集合的大小為k的子集的代表值最大可能是多少?！緮?shù)據(jù)規(guī)?！?0%的數(shù)據(jù)保證：1n2050%的數(shù)據(jù)保證：1n100100%的數(shù)據(jù)保證：1n2000【樣例輸入1】3 2ababzdabq【樣例輸出1】2【樣例輸入2】4 3eeerrrtttqqq【樣例輸出2】0【樣例輸入3】4 3aaaabbaabbcabbd【樣例輸出3】938. 算法訓(xùn)練 Buying Sets  時間限制：2.0s   內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問題描述給定n個集合, 要求選出其中某些集合, 使得這些集合的并集的勢, 等于選出的集合的數(shù)目.對于任意的k(1<=k<=n), 滿從中