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

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