藍(lán)橋杯題庫(kù)的歷屆真題.doc

1. 歷屆試題 矩陣翻硬幣 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述小明先把硬幣擺成了一個(gè) n 行 m 列的矩陣。隨后，小明對(duì)每一個(gè)硬幣分別進(jìn)行一次 Q 操作。對(duì)第x行第y列的硬幣進(jìn)行 Q 操作的定義：將所有第 i*x 行，第 j*y 列的硬幣進(jìn)行翻轉(zhuǎn)。其中i和j為任意使操作可行的正整數(shù)，行號(hào)和列號(hào)都是從1開(kāi)始。當(dāng)小明對(duì)所有硬幣都進(jìn)行了一次 Q 操作后，他發(fā)現(xiàn)了一個(gè)奇跡所有硬幣均為正面朝上。小明想知道最開(kāi)始有多少枚硬幣是反面朝上的。于是，他向他的好朋友小M尋求幫助。聰明的小M告訴小明，只需要對(duì)所有硬幣再進(jìn)行一次Q操作，即可恢復(fù)到最開(kāi)始的狀態(tài)。然而小明很懶，不愿意照做。于是小明希望你給出他更好的方法。幫他計(jì)算出答案。輸入格式輸入數(shù)據(jù)包含一行，兩個(gè)正整數(shù) n m，含義見(jiàn)題目描述。輸出格式輸出一個(gè)正整數(shù)，表示最開(kāi)始有多少枚硬幣是反面朝上的。樣例輸入2 3樣例輸出1數(shù)據(jù)規(guī)模和約定對(duì)于10%的數(shù)據(jù)，n、m = 103；對(duì)于20%的數(shù)據(jù)，n、m = 107；對(duì)于40%的數(shù)據(jù)，n、m = 1015；對(duì)于10%的數(shù)據(jù)，n、m = 101000（10的1000次方）。2. 歷屆試題 蘭頓螞蟻 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述蘭頓螞蟻，是于1986年，由克里斯蘭頓提出來(lái)的，屬于細(xì)胞自動(dòng)機(jī)的一種。平面上的正方形格子被填上黑色或白色。在其中一格正方形內(nèi)有一只“螞蟻”。螞蟻的頭部朝向?yàn)椋荷舷伦笥移渲幸环健Ｎ浵伒囊苿?dòng)規(guī)則十分簡(jiǎn)單：若螞蟻在黑格，右轉(zhuǎn)90度，將該格改為白格，并向前移一格；若螞蟻在白格，左轉(zhuǎn)90度，將該格改為黑格，并向前移一格。規(guī)則雖然簡(jiǎn)單，螞蟻的行為卻十分復(fù)雜。剛剛開(kāi)始時(shí)留下的路線都會(huì)有接近對(duì)稱(chēng)，像是會(huì)重復(fù)，但不論起始狀態(tài)如何，螞蟻經(jīng)過(guò)漫長(zhǎng)的混亂活動(dòng)后，會(huì)開(kāi)辟出一條規(guī)則的“高速公路”。螞蟻的路線是很難事先預(yù)測(cè)的。你的任務(wù)是根據(jù)初始狀態(tài)，用計(jì)算機(jī)模擬蘭頓螞蟻在第n步行走后所處的位置。輸入格式輸入數(shù)據(jù)的第一行是 m n 兩個(gè)整數(shù)（3 m, n 100），表示正方形格子的行數(shù)和列數(shù)。接下來(lái)是 m 行數(shù)據(jù)。每行數(shù)據(jù)為 n 個(gè)被空格分開(kāi)的數(shù)字。0 表示白格，1 表示黑格。接下來(lái)是一行數(shù)據(jù)：x y s k, 其中x y為整數(shù)，表示螞蟻所在行號(hào)和列號(hào)（行號(hào)從上到下增長(zhǎng)，列號(hào)從左到右增長(zhǎng)，都是從0開(kāi)始編號(hào)）。s 是一個(gè)大寫(xiě)字母，表示螞蟻頭的朝向，我們約定：上下左右分別用：UDLR表示。k 表示螞蟻?zhàn)叩牟綌?shù)。輸出格式輸出數(shù)據(jù)為兩個(gè)空格分開(kāi)的整數(shù) p q, 分別表示螞蟻在k步后，所處格子的行號(hào)和列號(hào)。樣例輸入5 60 0 0 0 0 00 0 0 0 0 00 0 1 0 0 00 0 0 0 0 00 0 0 0 0 02 3 L 5樣例輸出1 3樣例輸入3 30 0 01 1 11 1 11 1 U 6樣例輸出0 03. 歷屆試題 分糖果 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述有n個(gè)小朋友圍坐成一圈。老師給每個(gè)小朋友隨機(jī)發(fā)偶數(shù)個(gè)糖果，然后進(jìn)行下面的游戲：每個(gè)小朋友都把自己的糖果分一半給左手邊的孩子。一輪分糖后，擁有奇數(shù)顆糖的孩子由老師補(bǔ)給1個(gè)糖果，從而變成偶數(shù)。反復(fù)進(jìn)行這個(gè)游戲，直到所有小朋友的糖果數(shù)都相同為止。你的任務(wù)是預(yù)測(cè)在已知的初始糖果情形下，老師一共需要補(bǔ)發(fā)多少個(gè)糖果。輸入格式程序首先讀入一個(gè)整數(shù)N(2N100)，表示小朋友的人數(shù)。接著是一行用空格分開(kāi)的N個(gè)偶數(shù)（每個(gè)偶數(shù)不大于1000，不小于2）輸出格式要求程序輸出一個(gè)整數(shù)，表示老師需要補(bǔ)發(fā)的糖果數(shù)。樣例輸入32 2 4樣例輸出4登錄后才能查看試題。4. 歷屆試題 小朋友排隊(duì) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述n 個(gè)小朋友站成一排。現(xiàn)在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個(gè)小朋友。每個(gè)小朋友都有一個(gè)不高興的程度。開(kāi)始的時(shí)候，所有小朋友的不高興程度都是0。如果某個(gè)小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類(lèi)推。當(dāng)要求某個(gè)小朋友第k次交換時(shí)，他的不高興程度增加k。請(qǐng)問(wèn)，要讓所有小朋友按從低到高排隊(duì)，他們的不高興程度之和最小是多少。如果有兩個(gè)小朋友身高一樣，則他們誰(shuí)站在誰(shuí)前面是沒(méi)有關(guān)系的。輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示小朋友的個(gè)數(shù)。第二行包含 n 個(gè)整數(shù) H1 H2 Hn，分別表示每個(gè)小朋友的身高。輸出格式輸出一行，包含一個(gè)整數(shù)，表示小朋友的不高興程度和的最小值。樣例輸入33 2 1樣例輸出9樣例說(shuō)明首先交換身高為3和2的小朋友，再交換身高為3和1的小朋友，再交換身高為2和1的小朋友，每個(gè)小朋友的不高興程度都是3，總和為9。數(shù)據(jù)規(guī)模和約定對(duì)于10%的數(shù)據(jù)， 1=n=10；對(duì)于30%的數(shù)據(jù)， 1=n=1000；對(duì)于50%的數(shù)據(jù)， 1=n=10000；對(duì)于100%的數(shù)據(jù)，1=n=100000，0=Hi=1000000。登錄后才能查看試題。5. 歷屆試題 波動(dòng)數(shù)列 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述觀察這個(gè)數(shù)列：1 3 0 2 -1 1 -2 .這個(gè)數(shù)列中后一項(xiàng)總是比前一項(xiàng)增加2或者減少3。棟棟對(duì)這種數(shù)列很好奇，他想知道長(zhǎng)度為 n 和為 s 而且后一項(xiàng)總是比前一項(xiàng)增加a或者減少b的整數(shù)數(shù)列可能有多少種呢？輸入格式輸入的第一行包含四個(gè)整數(shù) n s a b，含義如前面說(shuō)述。輸出格式輸出一行，包含一個(gè)整數(shù)，表示滿足條件的方案數(shù)。由于這個(gè)數(shù)很大，請(qǐng)輸出方案數(shù)除以100000007的余數(shù)。樣例輸入4 10 2 3樣例輸出2樣例說(shuō)明這兩個(gè)數(shù)列分別是2 4 1 3和7 4 1 -2。數(shù)據(jù)規(guī)模和約定對(duì)于10%的數(shù)據(jù)，1=n=5，0=s=5，1=a,b=5；對(duì)于30%的數(shù)據(jù)，1=n=30，0=s=30，1=a,b=30；對(duì)于50%的數(shù)據(jù)，1=n=50，0=s=50，1=a,b=50；對(duì)于70%的數(shù)據(jù)，1=n=100，0=s=500，1=a, b=50；對(duì)于100%的數(shù)據(jù)，1=n=1000，-1,000,000,000=s=1,000,000,000，1=a, b2)對(duì)于給定的整數(shù) n 和 m，我們希望求出：f(1) + f(2) + . + f(n) 的值。但這個(gè)值可能非常大，所以我們把它對(duì) f(m) 取模。公式如下但這個(gè)數(shù)字依然很大，所以需要再對(duì) p 求模。輸入格式輸入為一行用空格分開(kāi)的整數(shù) n m p (0 n, m, p 1018)輸出格式輸出為1個(gè)整數(shù)，表示答案樣例輸入2 3 5樣例輸出0樣例輸入15 11 29樣例輸出257. 歷屆試題 地宮取寶 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述X 國(guó)王有一個(gè)地宮寶庫(kù)。是 n x m 個(gè)格子的矩陣。每個(gè)格子放一件寶貝。每個(gè)寶貝貼著價(jià)值標(biāo)簽。地宮的入口在左上角，出口在右下角。小明被帶到地宮的入口，國(guó)王要求他只能向右或向下行走。走過(guò)某個(gè)格子時(shí)，如果那個(gè)格子中的寶貝價(jià)值比小明手中任意寶貝價(jià)值都大，小明就可以拿起它（當(dāng)然，也可以不拿）。當(dāng)小明走到出口時(shí)，如果他手中的寶貝恰好是k件，則這些寶貝就可以送給小明。請(qǐng)你幫小明算一算，在給定的局面下，他有多少種不同的行動(dòng)方案能獲得這k件寶貝。輸入格式輸入一行3個(gè)整數(shù)，用空格分開(kāi)：n m k (1=n,m=50, 1=k=12)接下來(lái)有 n 行數(shù)據(jù)，每行有 m 個(gè)整數(shù) Ci (0=Ci=12)代表這個(gè)格子上的寶物的價(jià)值輸出格式要求輸出一個(gè)整數(shù)，表示正好取k個(gè)寶貝的行動(dòng)方案數(shù)。該數(shù)字可能很大，輸出它對(duì) 1000000007 取模的結(jié)果。樣例輸入2 2 21 22 1樣例輸出2樣例輸入2 3 21 2 32 1 5樣例輸出14登錄后才能查看試題。8. 歷屆試題 螞蟻感冒 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述長(zhǎng)100厘米的細(xì)長(zhǎng)直桿子上有n只螞蟻。它們的頭有的朝左，有的朝右。每只螞蟻都只能沿著桿子向前爬，速度是1厘米/秒。當(dāng)兩只螞蟻碰面時(shí)，它們會(huì)同時(shí)掉頭往相反的方向爬行。這些螞蟻中，有1只螞蟻感冒了。并且在和其它螞蟻碰面時(shí)，會(huì)把感冒傳染給碰到的螞蟻。請(qǐng)你計(jì)算，當(dāng)所有螞蟻都爬離桿子時(shí)，有多少只螞蟻患上了感冒。輸入格式第一行輸入一個(gè)整數(shù)n (1 n 50), 表示螞蟻的總數(shù)。接著的一行是n個(gè)用空格分開(kāi)的整數(shù) Xi (-100 Xi 100), Xi的絕對(duì)值，表示螞蟻離開(kāi)桿子左邊端點(diǎn)的距離。正值表示頭朝右，負(fù)值表示頭朝左，數(shù)據(jù)中不會(huì)出現(xiàn)0值，也不會(huì)出現(xiàn)兩只螞蟻占用同一位置。其中，第一個(gè)數(shù)據(jù)代表的螞蟻感冒了。輸出格式要求輸出1個(gè)整數(shù)，表示最后感冒螞蟻的數(shù)目。樣例輸入35 -2 8樣例輸出1樣例輸入5-10 8 -20 12 25樣例輸出39. 歷屆試題 最大子陣 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述給定一個(gè)n*m的矩陣A，求A中的一個(gè)非空子矩陣，使這個(gè)子矩陣中的元素和最大。其中，A的子矩陣指在A中行和列均連續(xù)的一塊。輸入格式輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示矩陣A的行數(shù)和列數(shù)。接下來(lái)n行，每行m個(gè)整數(shù)，表示矩陣A。輸出格式輸出一行，包含一個(gè)整數(shù)，表示A中最大的子矩陣中的元素和。樣例輸入3 3-1 -4 33 4 -1-5 -2 8樣例輸出10樣例說(shuō)明取最后一列，和為10。數(shù)據(jù)規(guī)模和約定對(duì)于50%的數(shù)據(jù)，1=n, m=50；對(duì)于100%的數(shù)據(jù)，1=n, m=500，A中每個(gè)元素的絕對(duì)值不超過(guò)5000。10. 歷屆試題 城市建設(shè) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述棟棟居住在一個(gè)繁華的C市中，然而，這個(gè)城市的道路大都年久失修。市長(zhǎng)準(zhǔn)備重新修一些路以方便市民，于是找到了棟棟，希望棟棟能幫助他。C市中有n個(gè)比較重要的地點(diǎn)，市長(zhǎng)希望這些地點(diǎn)重點(diǎn)被考慮?，F(xiàn)在可以修一些道路來(lái)連接其中的一些地點(diǎn)，每條道路可以連接其中的兩個(gè)地點(diǎn)。另外由于C市有一條河從中穿過(guò)，也可以在其中的一些地點(diǎn)建設(shè)碼頭，所有建了碼頭的地點(diǎn)可以通過(guò)河道連接。棟棟拿到了允許建設(shè)的道路的信息，包括每條可以建設(shè)的道路的花費(fèi)，以及哪些地點(diǎn)可以建設(shè)碼頭和建設(shè)碼頭的花費(fèi)。市長(zhǎng)希望棟棟給出一個(gè)方案，使得任意兩個(gè)地點(diǎn)能只通過(guò)新修的路或者河道互達(dá)，同時(shí)花費(fèi)盡量小。輸入格式輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示C市中重要地點(diǎn)的個(gè)數(shù)和可以建設(shè)的道路條數(shù)。所有地點(diǎn)從1到n依次編號(hào)。接下來(lái)m行，每行三個(gè)整數(shù)a, b, c，表示可以建設(shè)一條從地點(diǎn)a到地點(diǎn)b的道路，花費(fèi)為c。若c為正，表示建設(shè)是花錢(qián)的，如果c為負(fù)，則表示建設(shè)了道路后還可以賺錢(qián)（比如建設(shè)收費(fèi)道路）。接下來(lái)一行，包含n個(gè)整數(shù)w_1, w_2, , w_n。如果w_i為正數(shù)，則表示在地點(diǎn)i建設(shè)碼頭的花費(fèi)，如果w_i為-1，則表示地點(diǎn)i無(wú)法建設(shè)碼頭。輸入保證至少存在一個(gè)方法使得任意兩個(gè)地點(diǎn)能只通過(guò)新修的路或者河道互達(dá)。輸出格式輸出一行，包含一個(gè)整數(shù)，表示使得所有地點(diǎn)通過(guò)新修道路或者碼頭連接的最小花費(fèi)。如果滿足條件的情況下還能賺錢(qián)，那么你應(yīng)該輸出一個(gè)負(fù)數(shù)。樣例輸入5 51 2 41 3 -12 3 32 4 54 5 10-1 10 10 1 1樣例輸出9樣例說(shuō)明建設(shè)第2、3、4條道路，在地點(diǎn)4、5建設(shè)碼頭，總的花費(fèi)為9。數(shù)據(jù)規(guī)模和約定對(duì)于20%的數(shù)據(jù)，1=n=10，1=m=20，0=c=20，w_i=20；對(duì)于50%的數(shù)據(jù)，1=n=100，1=m=1000，-50=c=50，w_i=50；對(duì)于70%的數(shù)據(jù)，1=n=1000；對(duì)于100%的數(shù)據(jù)，1 = n = 10000，1 = m = 100000，-1000=c=1000，-1=w_i=1000，w_i0。11. 歷屆試題 郵局 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述C村住著n戶(hù)村民，由于交通閉塞，C村的村民只能通過(guò)信件與外界交流。為了方便村民們發(fā)信，C村打算在C村建設(shè)k個(gè)郵局，這樣每戶(hù)村民可以去離自己家最近的郵局發(fā)信?，F(xiàn)在給出了m個(gè)備選的郵局，請(qǐng)從中選出k個(gè)來(lái)，使得村民到自己家最近的郵局的距離和最小。其中兩點(diǎn)之間的距離定義為兩點(diǎn)之間的直線距離。輸入格式輸入的第一行包含三個(gè)整數(shù)n, m, k，分別表示村民的戶(hù)數(shù)、備選的郵局?jǐn)?shù)和要建的郵局?jǐn)?shù)。接下來(lái)n行，每行兩個(gè)整數(shù)x, y，依次表示每戶(hù)村民家的坐標(biāo)。接下來(lái)m行，每行包含兩個(gè)整數(shù)x, y，依次表示每個(gè)備選郵局的坐標(biāo)。在輸入中，村民和村民、村民和郵局、郵局和郵局的坐標(biāo)可能相同，但你應(yīng)把它們看成不同的村民或郵局。輸出格式輸出一行，包含k個(gè)整數(shù)，從小到大依次表示你選擇的備選郵局編號(hào)。（備選郵局按輸入順序由1到m編號(hào)）樣例輸入5 4 20 02 03 13 31 10 11 02 13 2樣例輸出2 4數(shù)據(jù)規(guī)模和約定對(duì)于30%的數(shù)據(jù)，1=n=10，1=m=10，1=k=5；對(duì)于60%的數(shù)據(jù)，1=m=20；對(duì)于100%的數(shù)據(jù)，1=n=50，1=m=25，1=k=10。登錄后才能查看試題。12. 歷屆試題 數(shù)字游戲 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述棟棟正在和同學(xué)們玩一個(gè)數(shù)字游戲。游戲的規(guī)則是這樣的：棟棟和同學(xué)們一共n個(gè)人圍坐在一圈。棟棟首先說(shuō)出數(shù)字1。接下來(lái)，坐在棟棟左手邊的同學(xué)要說(shuō)下一個(gè)數(shù)字2。再下面的一個(gè)同學(xué)要從上一個(gè)同學(xué)說(shuō)的數(shù)字往下數(shù)兩個(gè)數(shù)說(shuō)出來(lái)，也就是說(shuō)4。下一個(gè)同學(xué)要往下數(shù)三個(gè)數(shù)，說(shuō)7。依次類(lèi)推。為了使數(shù)字不至于太大，棟棟和同學(xué)們約定，當(dāng)在心中數(shù)到 k-1 時(shí)，下一個(gè)數(shù)字從0開(kāi)始數(shù)。例如，當(dāng)k=13時(shí)，棟棟和同學(xué)們報(bào)出的前幾個(gè)數(shù)依次為：1, 2, 4, 7, 11, 3, 9, 3, 11, 7。游戲進(jìn)行了一會(huì)兒，棟棟想知道，到目前為止，他所有說(shuō)出的數(shù)字的總和是多少。輸入格式輸入的第一行包含三個(gè)整數(shù) n,k,T，其中 n 和 k 的意義如上面所述，T 表示到目前為止棟棟一共說(shuō)出的數(shù)字個(gè)數(shù)。輸出格式輸出一行，包含一個(gè)整數(shù)，表示棟棟說(shuō)出所有數(shù)的和。樣例輸入3 13 3樣例輸出17樣例說(shuō)明棟棟說(shuō)出的數(shù)依次為1, 7, 9，和為17。數(shù)據(jù)規(guī)模和約定1 n,k,T 1,000,000；13. 歷屆試題 國(guó)王的煩惱 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述C國(guó)由n個(gè)小島組成，為了方便小島之間聯(lián)絡(luò)，C國(guó)在小島間建立了m座大橋，每座大橋連接兩座小島。兩個(gè)小島間可能存在多座橋連接。然而，由于海水沖刷，有一些大橋面臨著不能使用的危險(xiǎn)。如果兩個(gè)小島間的所有大橋都不能使用，則這兩座小島就不能直接到達(dá)了。然而，只要這兩座小島的居民能通過(guò)其他的橋或者其他的小島互相到達(dá)，他們就會(huì)安然無(wú)事。但是，如果前一天兩個(gè)小島之間還有方法可以到達(dá)，后一天卻不能到達(dá)了，居民們就會(huì)一起抗議?，F(xiàn)在C國(guó)的國(guó)王已經(jīng)知道了每座橋能使用的天數(shù)，超過(guò)這個(gè)天數(shù)就不能使用了。現(xiàn)在他想知道居民們會(huì)有多少天進(jìn)行抗議。輸入格式輸入的第一行包含兩個(gè)整數(shù)n, m，分別表示小島的個(gè)數(shù)和橋的數(shù)量。接下來(lái)m行，每行三個(gè)整數(shù)a, b, t，分別表示該座橋連接a號(hào)和b號(hào)兩個(gè)小島，能使用t天。小島的編號(hào)從1開(kāi)始遞增。輸出格式輸出一個(gè)整數(shù)，表示居民們會(huì)抗議的天數(shù)。樣例輸入4 41 2 21 3 22 3 13 4 3樣例輸出2樣例說(shuō)明第一天后2和3之間的橋不能使用，不影響。第二天后1和2之間，以及1和3之間的橋不能使用，居民們會(huì)抗議。第三天后3和4之間的橋不能使用，居民們會(huì)抗議。數(shù)據(jù)規(guī)模和約定對(duì)于30%的數(shù)據(jù)，1=n=20，1=m=100；對(duì)于50%的數(shù)據(jù)，1=n=500，1=m=10000；對(duì)于100%的數(shù)據(jù)，1=n=10000，1=m=100000，1=a, b=n， 1=t=100000。14. 歷屆試題 公式求值 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述輸入n, m, k，輸出下面公式的值。其中C_nm是組合數(shù)，表示在n個(gè)人的集合中選出m個(gè)人組成一個(gè)集合的方案數(shù)。組合數(shù)的計(jì)算公式如下。輸入格式輸入的第一行包含一個(gè)整數(shù)n；第二行包含一個(gè)整數(shù)m，第三行包含一個(gè)整數(shù)k。輸出格式計(jì)算上面公式的值，由于答案非常大，請(qǐng)輸出這個(gè)值除以999101的余數(shù)。樣例輸入313樣例輸出162樣例輸入201010樣例輸出359316數(shù)據(jù)規(guī)模和約定對(duì)于10%的數(shù)據(jù)，n10，k3；對(duì)于20%的數(shù)據(jù)，n20，k3；對(duì)于30%的數(shù)據(jù)，n1000，k5；對(duì)于40%的數(shù)據(jù)，n107，k10；對(duì)于60%的數(shù)據(jù)，n1015，k 100；對(duì)于70%的數(shù)據(jù)，n10100，k200；對(duì)于80%的數(shù)據(jù)，n10500，k 500；對(duì)于100%的數(shù)據(jù)，n在十進(jìn)制下不超過(guò)1000位，即1nxi。輸出格式輸出一個(gè)實(shí)數(shù)，四舍五入保留兩個(gè)小數(shù)，表示車(chē)輪軸經(jīng)過(guò)的總長(zhǎng)度。你的結(jié)果必須和參考答案一模一樣才能得分。數(shù)據(jù)保證答案精確值的小數(shù)點(diǎn)后第三位不是4或5。樣例輸入4 1.500.00 0.002.00 0.004.00 -1.006.00 -1.00樣例輸出6.22樣例說(shuō)明這個(gè)樣例對(duì)應(yīng)第一個(gè)圖。樣例輸入6 1.000.00 0.003.00 0.005.00 -3.006.00 2.007.00 -1.0010.00 -1.00樣例輸出15.20樣例說(shuō)明這個(gè)樣例對(duì)應(yīng)第二個(gè)圖數(shù)據(jù)規(guī)模和約定對(duì)于20%的數(shù)據(jù)，n=4；對(duì)于40%的數(shù)據(jù)，n10；對(duì)于100%的數(shù)據(jù)，4n100，0.5r20.0，xi 2000.0，-2000.0yi 2000.0。17. 歷屆試題 約數(shù)倍數(shù)選卡片 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述閑暇時(shí)，福爾摩斯和華生玩一個(gè)游戲：在N張卡片上寫(xiě)有N個(gè)整數(shù)。兩人輪流拿走一張卡片。要求下一個(gè)人拿的數(shù)字一定是前一個(gè)人拿的數(shù)字的約數(shù)或倍數(shù)。例如，某次福爾摩斯拿走的卡片上寫(xiě)著數(shù)字“6”，則接下來(lái)華生可以拿的數(shù)字包括：1，2，3, 6，12，18，24 .當(dāng)輪到某一方拿卡片時(shí)，沒(méi)有滿足要求的卡片可選，則該方為輸方。請(qǐng)你利用計(jì)算機(jī)的優(yōu)勢(shì)計(jì)算一下，在已知所有卡片上的數(shù)字和可選哪些數(shù)字的條件下，怎樣選擇才能保證必勝！當(dāng)選多個(gè)數(shù)字都可以必勝時(shí)，輸出其中最小的數(shù)字。如果無(wú)論如何都會(huì)輸，則輸出-1。輸入格式輸入數(shù)據(jù)為2行。第一行是若干空格分開(kāi)的整數(shù)（每個(gè)整數(shù)介于1100間），表示當(dāng)前剩余的所有卡片。第二行也是若干空格分開(kāi)的整數(shù)，表示可以選的數(shù)字。當(dāng)然，第二行的數(shù)字必須完全包含在第一行的數(shù)字中。輸出格式程序則輸出必勝的招法！樣例輸入2 3 63 6樣例輸出3樣例輸入1 2 2 3 3 4 53 4 5樣例輸出418. 歷屆試題 農(nóng)場(chǎng)陽(yáng)光 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述X星球十分特殊，它的自轉(zhuǎn)速度與公轉(zhuǎn)速度相同，所以陽(yáng)光總是以固定的角度照射。最近，X星球?yàn)榘l(fā)展星際旅游業(yè)，把空間位置出租給Y國(guó)游客來(lái)曬太陽(yáng)。每個(gè)租位是漂浮在空中的圓盤(pán)形彩云（圓盤(pán)與地面平行）。當(dāng)然，這會(huì)遮擋住部分陽(yáng)光，被遮擋的土地植物無(wú)法生長(zhǎng)。本題的任務(wù)是計(jì)算某個(gè)農(nóng)場(chǎng)宜于作物生長(zhǎng)的土地面積有多大。輸入格式輸入數(shù)據(jù)的第一行包含兩個(gè)整數(shù)a, b，表示某農(nóng)場(chǎng)的長(zhǎng)和寬分別是a和b，此時(shí)，該農(nóng)場(chǎng)的范圍是由坐標(biāo)(0, 0, 0), (a, 0, 0), (a, b, 0), (0, b, 0)圍成的矩形區(qū)域。第二行包含一個(gè)實(shí)數(shù)g，表示陽(yáng)光照射的角度。簡(jiǎn)單起見(jiàn)，我們假設(shè)陽(yáng)光光線是垂直于農(nóng)場(chǎng)的寬的，此時(shí)正好和農(nóng)場(chǎng)的長(zhǎng)的夾角是g度，此時(shí)，空間中的一點(diǎn)(x, y, z)在地面的投影點(diǎn)應(yīng)該是(x + z * ctg(g度), y, 0)，其中ctg(g度)表示g度對(duì)應(yīng)的余切值。第三行包含一個(gè)非負(fù)整數(shù)n，表示空中租位個(gè)數(shù)。接下來(lái) n 行，描述每個(gè)租位。其中第i行包含4個(gè)整數(shù)xi, yi, zi, ri，表示第i個(gè)租位彩云的圓心在(xi, yi, zi)位置，圓半徑為ri。輸出格式要求輸出一個(gè)實(shí)數(shù)，四舍五入保留兩位有效數(shù)字，表示農(nóng)場(chǎng)里能長(zhǎng)莊稼的土地的面積。樣例輸入10 1090.015 5 10 5樣例輸出21.46樣例輸入8 890.014 4 10 5樣例輸出1.81樣例輸入20 1045.025 0 5 58 6 14 6樣例輸出130.15登錄后才能查看試題。19. 歷屆試題 格子刷油漆 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述X國(guó)的一段古城墻的頂端可以看成 2*N個(gè)格子組成的矩形（如下圖所示），現(xiàn)需要把這些格子刷上保護(hù)漆。你可以從任意一個(gè)格子刷起，刷完一格，可以移動(dòng)到和它相鄰的格子（對(duì)角相鄰也算數(shù)），但不能移動(dòng)到較遠(yuǎn)的格子（因?yàn)橛推嵛锤刹荒懿龋。┍热纾篴 d b c e f 就是合格的刷漆順序。c e f d a b 是另一種合適的方案。當(dāng)已知 N 時(shí)，求總的方案數(shù)。當(dāng)N較大時(shí)，結(jié)果會(huì)迅速增大，請(qǐng)把結(jié)果對(duì) 1000000007 (十億零七) 取模。輸入格式輸入數(shù)據(jù)為一個(gè)正整數(shù)（不大于1000）輸出格式輸出數(shù)據(jù)為一個(gè)正整數(shù)。樣例輸入2樣例輸出24樣例輸入3樣例輸出96樣例輸入22樣例輸出35963589720. 歷屆試題 高僧斗法 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述古時(shí)喪葬活動(dòng)中經(jīng)常請(qǐng)高僧做法事。儀式結(jié)束后，有時(shí)會(huì)有“高僧斗法”的趣味節(jié)目，以舒緩壓抑的氣氛。節(jié)目大略步驟為：先用糧食（一般是稻米）在地上“畫(huà)”出若干級(jí)臺(tái)階（表示N級(jí)浮屠）。又有若干小和尚隨機(jī)地“站”在某個(gè)臺(tái)階上。最高一級(jí)臺(tái)階必須站人，其它任意。(如圖1所示)兩位參加游戲的法師分別指揮某個(gè)小和尚向上走任意多級(jí)的臺(tái)階，但會(huì)被站在高級(jí)臺(tái)階上的小和尚阻擋，不能越過(guò)。兩個(gè)小和尚也不能站在同一臺(tái)階，也不能向低級(jí)臺(tái)階移動(dòng)。兩法師輪流發(fā)出指令，最后所有小和尚必然會(huì)都擠在高段臺(tái)階，再也不能向上移動(dòng)。輪到哪個(gè)法師指揮時(shí)無(wú)法繼續(xù)移動(dòng)，則游戲結(jié)束，該法師認(rèn)輸。對(duì)于已知的臺(tái)階數(shù)和小和尚的分布位置，請(qǐng)你計(jì)算先發(fā)指令的法師該如何決策才能保證勝出。輸入格式輸入數(shù)據(jù)為一行用空格分開(kāi)的N個(gè)整數(shù)，表示小和尚的位置。臺(tái)階序號(hào)從1算起，所以最后一個(gè)小和尚的位置即是臺(tái)階的總數(shù)。（N100, 臺(tái)階總數(shù) 2 - 3 - 1 是允許的1 - 2 - 1 - 2 或者 1 - 2 - 3 - 2 都是非法的。輸入格式輸入數(shù)據(jù)的第一行為兩個(gè)整數(shù)N M，分別表示節(jié)點(diǎn)個(gè)數(shù)和連接線路的條數(shù)(1=N=10000; 0=M=100000)。接下去有M行，每行為兩個(gè)整數(shù) u 和 v，表示節(jié)點(diǎn)u 和 v 聯(lián)通(1=u,v=N , u!=v)。輸入數(shù)據(jù)保證任意兩點(diǎn)最多只有一條邊連接，并且沒(méi)有自己連自己的邊，即不存在重邊和自環(huán)。輸出格式輸出一個(gè)整數(shù)，表示滿足要求的路徑條數(shù)。 樣例輸入13 31 22 31 3 樣例輸出16 樣例輸入24 41 22 33 11 4 樣例輸出210 22. 歷屆試題 危險(xiǎn)系數(shù) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述抗日戰(zhàn)爭(zhēng)時(shí)期，冀中平原的地道戰(zhàn)曾發(fā)揮重要作用。地道的多個(gè)站點(diǎn)間有通道連接，形成了龐大的網(wǎng)絡(luò)。但也有隱患，當(dāng)敵人發(fā)現(xiàn)了某個(gè)站點(diǎn)后，其它站點(diǎn)間可能因此會(huì)失去聯(lián)系。我們來(lái)定義一個(gè)危險(xiǎn)系數(shù)DF(x,y)：對(duì)于兩個(gè)站點(diǎn)x和y (x != y), 如果能找到一個(gè)站點(diǎn)z，當(dāng)z被敵人破壞后，x和y不連通，那么我們稱(chēng)z為關(guān)于x,y的關(guān)鍵點(diǎn)。相應(yīng)的，對(duì)于任意一對(duì)站點(diǎn)x和y，危險(xiǎn)系數(shù)DF(x,y)就表示為這兩點(diǎn)之間的關(guān)鍵點(diǎn)個(gè)數(shù)。本題的任務(wù)是：已知網(wǎng)絡(luò)結(jié)構(gòu)，求兩站點(diǎn)之間的危險(xiǎn)系數(shù)。輸入格式輸入數(shù)據(jù)第一行包含2個(gè)整數(shù)n(2 = n = 1000), m(0 = m = 2000),分別代表站點(diǎn)數(shù)，通道數(shù)；接下來(lái)m行，每行兩個(gè)整數(shù) u,v (1 = u, v = n; u != v)代表一條通道；最后1行，兩個(gè)數(shù)u,v，代表詢(xún)問(wèn)兩點(diǎn)之間的危險(xiǎn)系數(shù)DF(u, v)。輸出格式一個(gè)整數(shù)，如果詢(xún)問(wèn)的兩點(diǎn)不連通則輸出-1. 樣例輸入7 61 32 33 43 54 55 61 6 樣例輸出2 23. 歷屆試題 橫向打印二叉樹(shù) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述二叉樹(shù)可以用于排序。其原理很簡(jiǎn)單：對(duì)于一個(gè)排序二叉樹(shù)添加新節(jié)點(diǎn)時(shí)，先與根節(jié)點(diǎn)比較，若小則交給左子樹(shù)繼續(xù)處理，否則交給右子樹(shù)。當(dāng)遇到空子樹(shù)時(shí)，則把該節(jié)點(diǎn)放入那個(gè)位置。 比如，10 8 5 7 12 4 的輸入順序，應(yīng)該建成二叉樹(shù)如下圖所示，其中.表示空白。.|-1210-|.|-8-|.|.|-7.|-5-|.|-4 本題目要求：根據(jù)已知的數(shù)字，建立排序二叉樹(shù)，并在標(biāo)準(zhǔn)輸出中橫向打印該二叉樹(shù)。 輸入格式輸入數(shù)據(jù)為一行空格分開(kāi)的N個(gè)整數(shù)。 N100，每個(gè)數(shù)字不超過(guò)10000。輸入數(shù)據(jù)中沒(méi)有重復(fù)的數(shù)字。 輸出格式輸出該排序二叉樹(shù)的橫向表示。為了便于評(píng)卷程序比對(duì)空格的數(shù)目，請(qǐng)把空格用句點(diǎn)代替：樣例輸入110 5 20 樣例輸出1.|-2010-|.|-5 樣例輸入25 10 20 8 4 7 樣例輸出2.|-20.|-10-|.|.|-8-|.|.|-75-|.|-4 24. 歷屆試題 幸運(yùn)數(shù) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述幸運(yùn)數(shù)是波蘭數(shù)學(xué)家烏拉姆命名的。它采用與生成素?cái)?shù)類(lèi)似的“篩法”生成。 首先從1開(kāi)始寫(xiě)出自然數(shù)1,2,3,4,5,6,.1 就是第一個(gè)幸運(yùn)數(shù)。我們從2這個(gè)數(shù)開(kāi)始。把所有序號(hào)能被2整除的項(xiàng)刪除，變?yōu)椋? _ 3 _ 5 _ 7 _ 9 .把它們縮緊，重新記序，為：1 3 5 7 9 . 。這時(shí)，3為第2個(gè)幸運(yùn)數(shù)，然后把所有能被3整除的序號(hào)位置的數(shù)刪去。注意，是序號(hào)位置，不是那個(gè)數(shù)本身能否被3整除! 刪除的應(yīng)該是5，11, 17, .此時(shí)7為第3個(gè)幸運(yùn)數(shù)，然后再刪去序號(hào)位置能被7整除的(19,39,.)最后剩下的序列類(lèi)似：1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, .輸入格式輸入兩個(gè)正整數(shù)m n, 用空格分開(kāi) (m n 1000*1000) 輸出格式程序輸出 位于m和n之間的幸運(yùn)數(shù)的個(gè)數(shù)（不包含m和n）。 樣例輸入11 20 樣例輸出15 樣例輸入230 69 樣例輸出28 25. 歷屆試題 大臣的旅費(fèi) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述很久以前，T王國(guó)空前繁榮。為了更好地管理國(guó)家，王國(guó)修建了大量的快速路，用于連接首都和王國(guó)內(nèi)的各大城市。為節(jié)省經(jīng)費(fèi)，T國(guó)的大臣們經(jīng)過(guò)思考，制定了一套優(yōu)秀的修建方案，使得任何一個(gè)大城市都能從首都直接或者通過(guò)其他大城市間接到達(dá)。同時(shí)，如果不重復(fù)經(jīng)過(guò)大城市，從首都到達(dá)每個(gè)大城市的方案都是唯一的。J是T國(guó)重要大臣，他巡查于各大城市之間，體察民情。所以，從一個(gè)城市馬不停蹄地到另一個(gè)城市成了J最常做的事情。他有一個(gè)錢(qián)袋，用于存放往來(lái)城市間的路費(fèi)。聰明的J發(fā)現(xiàn)，如果不在某個(gè)城市停下來(lái)修整，在連續(xù)行進(jìn)過(guò)程中，他所花的路費(fèi)與他已走過(guò)的距離有關(guān)，在走第x千米到第x+1千米這一千米中（x是整數(shù)），他花費(fèi)的路費(fèi)是x+10這么多。也就是說(shuō)走1千米花費(fèi)11，走2千米要花費(fèi)23。J大臣想知道：他從某一個(gè)城市出發(fā)，中間不休息，到達(dá)另一個(gè)城市，所有可能花費(fèi)的路費(fèi)中最多是多少呢？輸入格式輸入的第一行包含一個(gè)整數(shù)n，表示包括首都在內(nèi)的T王國(guó)的城市數(shù)城市從1開(kāi)始依次編號(hào)，1號(hào)城市為首都。接下來(lái)n-1行，描述T國(guó)的高速路（T國(guó)的高速路一定是n-1條）每行三個(gè)整數(shù)Pi, Qi, Di，表示城市Pi和城市Qi之間有一條高速路，長(zhǎng)度為Di千米。輸出格式輸出一個(gè)整數(shù)，表示大臣J最多花費(fèi)的路費(fèi)是多少。樣例輸入151 2 21 3 12 4 52 5 4樣例輸出1135 輸出格式大臣J從城市4到城市5要花費(fèi)135的路費(fèi)。登錄后才能查看試題。26. 歷屆試題 買(mǎi)不到的數(shù)目 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述小明開(kāi)了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣(mài)。小朋友來(lái)買(mǎi)糖的時(shí)候，他就用這兩種包裝來(lái)組合。當(dāng)然有些糖果數(shù)目是無(wú)法組合出來(lái)的，比如要買(mǎi) 10 顆糖。你可以用計(jì)算機(jī)測(cè)試一下，在這種包裝情況下，最大不能買(mǎi)到的數(shù)量是17。大于17的任何數(shù)字都可以用4和7組合出來(lái)。本題的要求就是在已知兩個(gè)包裝的數(shù)量時(shí)，求最大不能組合出的數(shù)字。輸入格式兩個(gè)正整數(shù)，表示每種包裝中糖的顆數(shù)(都不多于1000)輸出格式一個(gè)正整數(shù)，表示最大不能買(mǎi)到的糖數(shù)樣例輸入14 7樣例輸出117 樣例輸入23 5樣例輸出27 27. 歷屆試題 連號(hào)區(qū)間數(shù) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述小明這些天一直在思考這樣一個(gè)奇怪而有趣的問(wèn)題：在1N的某個(gè)全排列中有多少個(gè)連號(hào)區(qū)間呢？這里所說(shuō)的連號(hào)區(qū)間的定義是：如果區(qū)間L, R 里的所有元素（即此排列的第L個(gè)到第R個(gè)元素）遞增排序后能得到一個(gè)長(zhǎng)度為R-L+1的“連續(xù)”數(shù)列，則稱(chēng)這個(gè)區(qū)間連號(hào)區(qū)間。當(dāng)N很小的時(shí)候，小明可以很快地算出答案，但是當(dāng)N變大的時(shí)候，問(wèn)題就不是那么簡(jiǎn)單了，現(xiàn)在小明需要你的幫助。輸入格式第一行是一個(gè)正整數(shù)N (1 = N = 50000), 表示全排列的規(guī)模。第二行是N個(gè)不同的數(shù)字Pi(1 = Pi = N)， 表示這N個(gè)數(shù)字的某一全排列。輸出格式輸出一個(gè)整數(shù)，表示不同連號(hào)區(qū)間的數(shù)目。樣例輸入143 2 4 1樣例輸出17 樣例輸入253 4 2 5 1樣例輸出29 28. 歷屆試題 翻硬幣 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述小明正在玩一個(gè)“翻硬幣”的游戲。桌上放著排成一排的若干硬幣。我們用 * 表示正面，用 o 表示反面（是小寫(xiě)字母，不是零）。比如，可能情形是：*oo*oooo如果同時(shí)翻轉(zhuǎn)左邊的兩個(gè)硬幣，則變?yōu)椋簅ooo*oooo現(xiàn)在小明的問(wèn)題是：如果已知了初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)，每次只能同時(shí)翻轉(zhuǎn)相鄰的兩個(gè)硬幣,那么對(duì)特定的局面，最少要翻動(dòng)多少次呢？我們約定：把翻動(dòng)相鄰的兩個(gè)硬幣叫做一步操作，那么要求： 輸入格式兩行等長(zhǎng)的字符串，分別表示初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)。每行的長(zhǎng)度1000輸出格式一個(gè)整數(shù)，表示最小操作步數(shù)。樣例輸入1*o*o*樣例輸出15 樣例輸入2*o*o*o*o*o*o*樣例輸出21 登錄后才能查看試題。29. 歷屆試題 錯(cuò)誤票據(jù) 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB錦囊1錦囊2錦囊3問(wèn)題描述某涉密單位下發(fā)了某種票據(jù)，并要在年終全部收回。每張票據(jù)有唯一的ID號(hào)。全年所有票據(jù)的ID號(hào)是連續(xù)的，但I(xiàn)D的開(kāi)始數(shù)碼是隨機(jī)選定的。因?yàn)楣ぷ魅藛T疏忽，在錄入ID號(hào)的時(shí)候發(fā)生了一處錯(cuò)誤，造成了某個(gè)ID斷號(hào)，另外一個(gè)ID重號(hào)。你的任務(wù)是通過(guò)編程，找出斷號(hào)的ID和重號(hào)的ID。假設(shè)斷號(hào)不可能發(fā)生在最大和最小號(hào)。輸入格式要求程序首先輸入一個(gè)整數(shù)N(N100)表示后面數(shù)據(jù)行數(shù)。接著讀入N行數(shù)據(jù)。每行數(shù)據(jù)長(zhǎng)度不等，是用空格分開(kāi)的若干個(gè)（不大于100個(gè)）正整數(shù)（不大于100000），請(qǐng)注意行內(nèi)和行末可能有多余的空格，你的程序需要能處理這些空格。每個(gè)整數(shù)代表一個(gè)ID號(hào)。輸出格式要求程序輸出1行，含兩個(gè)整數(shù)m n，用空格分隔。其中，m表示斷號(hào)ID，n表示重號(hào)ID樣例輸入125 6 8 11 9 10 12 9樣例輸出17 9樣例輸入26164 178 108 109 180 155 141 159 104 182 179 118 137 184 115 124 125 129 168 196172 189 127 107 112 192 103 131 133 169 158 128 102 110 148 139 157 140 195 197185 152 135 106 123 173 122 136 174 191 145 116 151 143 175 120 161 134 162 190149 138 142 146 199 126 165 156 153 193 144 166 170 121 171 132