藍橋杯題庫的歷屆真題

藍橋杯題庫的歷屆真題藍橋杯題庫的歷屆真題藍橋杯題庫的歷屆真題藍橋杯題庫的歷屆真題編制僅供參考審核批準生效日期地址：電話：傳真:郵編:歷屆試題矩陣翻硬幣

時間限制：1.0s

內存限制：256.0MB問題描述小明先把硬幣擺成了一個n行m列的矩陣。

隨后，小明對每一個硬幣分別進行一次Q操作。

對第x行第y列的硬幣進行Q操作的定義：將所有第i*x行，第j*y列的硬幣進行翻轉。

其中i和j為任意使操作可行的正整數(shù)，行號和列號都是從1開始。

當小明對所有硬幣都進行了一次Q操作后，他發(fā)現(xiàn)了一個奇跡——所有硬幣均為正面朝上。

小明想知道最開始有多少枚硬幣是反面朝上的。于是，他向他的好朋友小M尋求幫助。

聰明的小M告訴小明，只需要對所有硬幣再進行一次Q操作，即可恢復到最開始的狀態(tài)。然而小明很懶，不愿意照做。于是小明希望你給出他更好的方法。幫他計算出答案。輸入格式輸入數(shù)據(jù)包含一行，兩個正整數(shù)nm，含義見題目描述。輸出格式輸出一個正整數(shù)，表示最開始有多少枚硬幣是反面朝上的。樣例輸入23樣例輸出1數(shù)據(jù)規(guī)模和約定對于10%的數(shù)據(jù)，n、m<=10^3；

對于20%的數(shù)據(jù)，n、m<=10^7；

對于40%的數(shù)據(jù)，n、m<=10^15；

對于10%的數(shù)據(jù)，n、m<=10^1000（10的1000次方）。歷屆試題蘭頓螞蟻

時間限制：1.0s

內存限制：256.0MB問題描述

蘭頓螞蟻，是于1986年，由克里斯·蘭頓提出來的，屬于細胞自動機的一種。

平面上的正方形格子被填上黑色或白色。在其中一格正方形內有一只“螞蟻”。

螞蟻的頭部朝向為：上下左右其中一方。

螞蟻的移動規(guī)則十分簡單：

若螞蟻在黑格，右轉90度，將該格改為白格，并向前移一格；

若螞蟻在白格，左轉90度，將該格改為黑格，并向前移一格。

規(guī)則雖然簡單，螞蟻的行為卻十分復雜。剛剛開始時留下的路線都會有接近對稱，像是會重復，但不論起始狀態(tài)如何，螞蟻經過漫長的混亂活動后，會開辟出一條規(guī)則的“高速公路”。

螞蟻的路線是很難事先預測的。

你的任務是根據(jù)初始狀態(tài)，用計算機模擬蘭頓螞蟻在第n步行走后所處的位置。輸入格式輸入數(shù)據(jù)的第一行是mn兩個整數(shù)（3<m,n<100），表示正方形格子的行數(shù)和列數(shù)。

接下來是m行數(shù)據(jù)。

每行數(shù)據(jù)為n個被空格分開的數(shù)字。0表示白格，1表示黑格。

接下來是一行數(shù)據(jù)：xysk,其中xy為整數(shù)，表示螞蟻所在行號和列號（行號從上到下增長，列號從左到右增長，都是從0開始編號）。s是一個大寫字母，表示螞蟻頭的朝向，我們約定：上下左右分別用：UDLR表示。k表示螞蟻走的步數(shù)。輸出格式輸出數(shù)據(jù)為兩個空格分開的整數(shù)pq,分別表示螞蟻在k步后，所處格子的行號和列號。樣例輸入56

000000

000000

001000

000000

000000

23L5樣例輸出13樣例輸入33

000

111

111

11U6樣例輸出00歷屆試題分糖果

時間限制：1.0s

內存限制：256.0MB問題描述有n個小朋友圍坐成一圈。老師給每個小朋友隨機發(fā)偶數(shù)個糖果，然后進行下面的游戲：

每個小朋友都把自己的糖果分一半給左手邊的孩子。

一輪分糖后，擁有奇數(shù)顆糖的孩子由老師補給1個糖果，從而變成偶數(shù)。

反復進行這個游戲，直到所有小朋友的糖果數(shù)都相同為止。

你的任務是預測在已知的初始糖果情形下，老師一共需要補發(fā)多少個糖果。輸入格式程序首先讀入一個整數(shù)N(2<N<100)，表示小朋友的人數(shù)。

接著是一行用空格分開的N個偶數(shù)（每個偶數(shù)不大于1000，不小于2）輸出格式要求程序輸出一個整數(shù)，表示老師需要補發(fā)的糖果數(shù)。樣例輸入3

224樣例輸出4歷屆試題小朋友排隊

時間限制：1.0s

內存限制：256.0MB問題描述n個小朋友站成一排。現(xiàn)在要把他們按身高從低到高的順序排列，但是每次只能交換位置相鄰的兩個小朋友。

每個小朋友都有一個不高興的程度。開始的時候，所有小朋友的不高興程度都是0。

如果某個小朋友第一次被要求交換，則他的不高興程度增加1，如果第二次要求他交換，則他的不高興程度增加2（即不高興程度為3），依次類推。當要求某個小朋友第k次交換時，他的不高興程度增加k。

請問，要讓所有小朋友按從低到高排隊，他們的不高興程度之和最小是多少。

如果有兩個小朋友身高一樣，則他們誰站在誰前面是沒有關系的。輸入格式輸入的第一行包含一個整數(shù)n，表示小朋友的個數(shù)。

第二行包含n個整數(shù)H1H2…Hn，分別表示每個小朋友的身高。輸出格式輸出一行，包含一個整數(shù)，表示小朋友的不高興程度和的最小值。樣例輸入3

321樣例輸出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。歷屆試題波動數(shù)列

時間限制：1.0s

內存限制：256.0MB問題描述觀察這個數(shù)列：

1302-11-2...

這個數(shù)列中后一項總是比前一項增加2或者減少3。

棟棟對這種數(shù)列很好奇，他想知道長度為n和為s而且后一項總是比前一項增加a或者減少b的整數(shù)數(shù)列可能有多少種呢？

輸入格式輸入的第一行包含四個整數(shù)nsab，含義如前面說述。輸出格式輸出一行，包含一個整數(shù)，表示滿足條件的方案數(shù)。由于這個數(shù)很大，請輸出方案數(shù)除以100000007的余數(shù)。樣例輸入41023樣例輸出2樣例說明這兩個數(shù)列分別是2413和741-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,b<=1,000,000。歷屆試題斐波那契

時間限制：1.0s

內存限制：256.0MB問題描述斐波那契數(shù)列大家都非常熟悉。它的定義是：

f(x)=1....(x=1,2)

f(x)=f(x-1)+f(x-2)....(x>2)

對于給定的整數(shù)n和m，我們希望求出：

f(1)+f(2)+...+f(n)的值。但這個值可能非常大，所以我們把它對f(m)取模。

公式如下

但這個數(shù)字依然很大，所以需要再對p求模。輸入格式輸入為一行用空格分開的整數(shù)nmp(0<n,m,p<10^18)輸出格式輸出為1個整數(shù)，表示答案樣例輸入235樣例輸出0樣例輸入151129樣例輸出25歷屆試題地宮取寶

時間限制：1.0s

內存限制：256.0MB問題描述X國王有一個地宮寶庫。是nxm個格子的矩陣。每個格子放一件寶貝。每個寶貝貼著價值標簽。

地宮的入口在左上角，出口在右下角。

小明被帶到地宮的入口，國王要求他只能向右或向下行走。

走過某個格子時，如果那個格子中的寶貝價值比小明手中任意寶貝價值都大，小明就可以拿起它（當然，也可以不拿）。

當小明走到出口時，如果他手中的寶貝恰好是k件，則這些寶貝就可以送給小明。

請你幫小明算一算，在給定的局面下，他有多少種不同的行動方案能獲得這k件寶貝。輸入格式輸入一行3個整數(shù)，用空格分開：nmk(1<=n,m<=50,1<=k<=12)

接下來有n行數(shù)據(jù)，每行有m個整數(shù)Ci(0<=Ci<=12)代表這個格子上的寶物的價值輸出格式要求輸出一個整數(shù)，表示正好取k個寶貝的行動方案數(shù)。該數(shù)字可能很大，輸出它對1000000007取模的結果。樣例輸入222

12

21樣例輸出2樣例輸入232

123

215樣例輸出14歷屆試題螞蟻感冒

時間限制：1.0s

內存限制：256.0MB問題描述長100厘米的細長直桿子上有n只螞蟻。它們的頭有的朝左，有的朝右。

每只螞蟻都只能沿著桿子向前爬，速度是1厘米/秒。

當兩只螞蟻碰面時，它們會同時掉頭往相反的方向爬行。

這些螞蟻中，有1只螞蟻感冒了。并且在和其它螞蟻碰面時，會把感冒傳染給碰到的螞蟻。

請你計算，當所有螞蟻都爬離桿子時，有多少只螞蟻患上了感冒。輸入格式第一行輸入一個整數(shù)n(1<n<50),表示螞蟻的總數(shù)。

接著的一行是n個用空格分開的整數(shù)Xi(-100<Xi<100),Xi的絕對值，表示螞蟻離開桿子左邊端點的距離。正值表示頭朝右，負值表示頭朝左，數(shù)據(jù)中不會出現(xiàn)0值，也不會出現(xiàn)兩只螞蟻占用同一位置。其中，第一個數(shù)據(jù)代表的螞蟻感冒了。輸出格式要求輸出1個整數(shù)，表示最后感冒螞蟻的數(shù)目。樣例輸入3

5-28樣例輸出1樣例輸入5

-108-201225樣例輸出3歷屆試題最大子陣

時間限制：1.0s

內存限制：256.0MB問題描述給定一個n*m的矩陣A，求A中的一個非空子矩陣，使這個子矩陣中的元素和最大。

其中，A的子矩陣指在A中行和列均連續(xù)的一塊。輸入格式輸入的第一行包含兩個整數(shù)n,m，分別表示矩陣A的行數(shù)和列數(shù)。

接下來n行，每行m個整數(shù)，表示矩陣A。輸出格式輸出一行，包含一個整數(shù)，表示A中最大的子矩陣中的元素和。樣例輸入33

-1-43

34-1

-5-28樣例輸出10樣例說明取最后一列，和為10。數(shù)據(jù)規(guī)模和約定對于50%的數(shù)據(jù)，1<=n,m<=50；

對于100%的數(shù)據(jù)，1<=n,m<=500，A中每個元素的絕對值不超過5000。歷屆試題城市建設

時間限制：1.0s

內存限制：256.0MB問題描述棟棟居住在一個繁華的C市中，然而，這個城市的道路大都年久失修。市長準備重新修一些路以方便市民，于是找到了棟棟，希望棟棟能幫助他。

C市中有n個比較重要的地點，市長希望這些地點重點被考慮。現(xiàn)在可以修一些道路來連接其中的一些地點，每條道路可以連接其中的兩個地點。另外由于C市有一條河從中穿過，也可以在其中的一些地點建設碼頭，所有建了碼頭的地點可以通過河道連接。

棟棟拿到了允許建設的道路的信息，包括每條可以建設的道路的花費，以及哪些地點可以建設碼頭和建設碼頭的花費。

市長希望棟棟給出一個方案，使得任意兩個地點能只通過新修的路或者河道互達，同時花費盡量小。輸入格式輸入的第一行包含兩個整數(shù)n,m，分別表示C市中重要地點的個數(shù)和可以建設的道路條數(shù)。所有地點從1到n依次編號。

接下來m行，每行三個整數(shù)a,b,c，表示可以建設一條從地點a到地點b的道路，花費為c。若c為正，表示建設是花錢的，如果c為負，則表示建設了道路后還可以賺錢（比如建設收費道路）。

接下來一行，包含n個整數(shù)w_1,w_2,…,w_n。如果w_i為正數(shù)，則表示在地點i建設碼頭的花費，如果w_i為-1，則表示地點i無法建設碼頭。

輸入保證至少存在一個方法使得任意兩個地點能只通過新修的路或者河道互達。輸出格式輸出一行，包含一個整數(shù)，表示使得所有地點通過新修道路或者碼頭連接的最小花費。如果滿足條件的情況下還能賺錢，那么你應該輸出一個負數(shù)。樣例輸入55

124

13-1

233

245

4510

-1101011樣例輸出9樣例說明建設第2、3、4條道路，在地點4、5建設碼頭，總的花費為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_i≠0。歷屆試題郵局

時間限制：1.0s

內存限制：256.0MB問題描述C村住著n戶村民，由于交通閉塞，C村的村民只能通過信件與外界交流。為了方便村民們發(fā)信，C村打算在C村建設k個郵局，這樣每戶村民可以去離自己家最近的郵局發(fā)信。

現(xiàn)在給出了m個備選的郵局，請從中選出k個來，使得村民到自己家最近的郵局的距離和最小。其中兩點之間的距離定義為兩點之間的直線距離。輸入格式輸入的第一行包含三個整數(shù)n,m,k，分別表示村民的戶數(shù)、備選的郵局數(shù)和要建的郵局數(shù)。

接下來n行，每行兩個整數(shù)x,y，依次表示每戶村民家的坐標。

接下來m行，每行包含兩個整數(shù)x,y，依次表示每個備選郵局的坐標。

在輸入中，村民和村民、村民和郵局、郵局和郵局的坐標可能相同，但你應把它們看成不同的村民或郵局。輸出格式輸出一行，包含k個整數(shù)，從小到大依次表示你選擇的備選郵局編號。（備選郵局按輸入順序由1到m編號）樣例輸入542

00

20

31

33

11

01

10

21

32樣例輸出24數(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。歷屆試題數(shù)字游戲

時間限制：1.0s

內存限制：256.0MB問題描述棟棟正在和同學們玩一個數(shù)字游戲。

游戲的規(guī)則是這樣的：棟棟和同學們一共n個人圍坐在一圈。棟棟首先說出數(shù)字1。接下來，坐在棟棟左手邊的同學要說下一個數(shù)字2。再下面的一個同學要從上一個同學說的數(shù)字往下數(shù)兩個數(shù)說出來，也就是說4。下一個同學要往下數(shù)三個數(shù)，說7。依次類推。

為了使數(shù)字不至于太大，棟棟和同學們約定，當在心中數(shù)到k-1時，下一個數(shù)字從0開始數(shù)。例如，當k=13時，棟棟和同學們報出的前幾個數(shù)依次為：

1,2,4,7,11,3,9,3,11,7。

游戲進行了一會兒，棟棟想知道，到目前為止，他所有說出的數(shù)字的總和是多少。輸入格式輸入的第一行包含三個整數(shù)n,k,T，其中n和k的意義如上面所述，T表示到目前為止棟棟一共說出的數(shù)字個數(shù)。輸出格式輸出一行，包含一個整數(shù)，表示棟棟說出所有數(shù)的和。樣例輸入3133樣例輸出17樣例說明棟棟說出的數(shù)依次為1,7,9，和為17。數(shù)據(jù)規(guī)模和約定1<n,k,T<1,000,000；歷屆試題國王的煩惱

時間限制：1.0s

內存限制：256.0MB問題描述C國由n個小島組成，為了方便小島之間聯(lián)絡，C國在小島間建立了m座大橋，每座大橋連接兩座小島。兩個小島間可能存在多座橋連接。然而，由于海水沖刷，有一些大橋面臨著不能使用的危險。

如果兩個小島間的所有大橋都不能使用，則這兩座小島就不能直接到達了。然而，只要這兩座小島的居民能通過其他的橋或者其他的小島互相到達，他們就會安然無事。但是，如果前一天兩個小島之間還有方法可以到達，后一天卻不能到達了，居民們就會一起抗議。

現(xiàn)在C國的國王已經知道了每座橋能使用的天數(shù)，超過這個天數(shù)就不能使用了?，F(xiàn)在他想知道居民們會有多少天進行抗議。輸入格式輸入的第一行包含兩個整數(shù)n,m，分別表示小島的個數(shù)和橋的數(shù)量。

接下來m行，每行三個整數(shù)a,b,t，分別表示該座橋連接a號和b號兩個小島，能使用t天。小島的編號從1開始遞增。輸出格式輸出一個整數(shù)，表示居民們會抗議的天數(shù)。樣例輸入44

122

132

231

343樣例輸出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。歷屆試題公式求值

時間限制：1.0s

內存限制：256.0MB問題描述輸入n,m,k，輸出下面公式的值。

其中C_n^m是組合數(shù)，表示在n個人的集合中選出m個人組成一個集合的方案數(shù)。組合數(shù)的計算公式如下。輸入格式輸入的第一行包含一個整數(shù)n；第二行包含一個整數(shù)m，第三行包含一個整數(shù)k。輸出格式計算上面公式的值，由于答案非常大，請輸出這個值除以999101的余數(shù)。樣例輸入3

1

3樣例輸出162樣例輸入20

10

10樣例輸出359316數(shù)據(jù)規(guī)模和約定對于10%的數(shù)據(jù)，n≤10，k≤3；

對于20%的數(shù)據(jù)，n≤20，k≤3；

對于30%的數(shù)據(jù)，n≤1000，k≤5；

對于40%的數(shù)據(jù)，n≤10^7，k≤10；

對于60%的數(shù)據(jù)，n≤10^15，k≤100；

對于70%的數(shù)據(jù)，n≤10^100，k≤200；

對于80%的數(shù)據(jù)，n≤10^500，k≤500；

對于100%的數(shù)據(jù)，n在十進制下不超過1000位，即1≤n<10^1000，1≤k≤1000，同時0≤m≤n，k≤n。提示999101是一個質數(shù)；

當n位數(shù)比較多時，絕大多數(shù)情況下答案都是0，但評測的時候會選取一些答案不是0的數(shù)據(jù)；歷屆試題九宮重排

時間限制：1.0s

內存限制：256.0MB問題描述如下面第一個圖的九宮格中，放著1~8的數(shù)字卡片，還有一個格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。經過若干次移動，可以形成第二個圖所示的局面。

我們把第一個圖的局面記為：12345678.

把第二個圖的局面記為：123.46758

顯然是按從上到下，從左到右的順序記錄數(shù)字，空格記為句點。

本題目的任務是已知九宮的初態(tài)和終態(tài)，求最少經過多少步的移動可以到達。如果無論多少步都無法到達，則輸出-1。輸入格式輸入第一行包含九宮的初態(tài)，第二行包含九宮的終態(tài)。輸出格式輸出最少的步數(shù)，如果不存在方案，則輸出-1。樣例輸入12345678.

123.46758樣例輸出3樣例輸入13524678.

46758123.樣例輸出22歷屆試題車輪軸跡

時間限制：1.0s

內存限制：256.0MB問題描述棟棟每天騎自行車回家需要經過一條狹長的林蔭道。道路由于年久失修，變得非常不平整。雖然棟棟每次都很顛簸，但他仍把騎車經過林蔭道當成一種樂趣。

由于顛簸，棟棟騎車回家的路徑是一條上下起伏的曲線，棟棟想知道，他回家的這條曲線的長度究竟是多長呢？更準確的，棟棟想知道從林蔭道的起點到林蔭道的終點，他的車前輪的軸（圓心）經過的路徑的長度。

棟棟對路面進行了測量。他把道路簡化成一條條長短不等的直線段，這些直線段首尾相連，且位于同一平面內。并在該平面內建立了一個直角坐標系，把所有線段的端點坐標都計算好。

假設棟棟的自行車在行進的過程中前輪一直是貼著路面前進的。

上圖給出了一個簡單的路面的例子，其中藍色實線為路面，紅色虛線為車輪軸經過的路徑。在這個例子中，棟棟的前輪軸從A點出發(fā)，水平走到B點，然后繞著地面的F點到C點（繞出一個圓弧），再沿直線下坡到D點，最后水平走到E點，在這個圖中地面的坐標依次為：(0,0),(2,0),(4,-1),(6,-1)，前輪半徑為1.50，前輪軸前進的距離依次為：

AB=2.0000；弧長BC=0.6955；CD=1.8820；DE=1.6459。

總長度為6.2233。

下圖給出了一個較為復雜的路面的例子，在這個例子中，車輪在第一個下坡還沒下完時（D點）就開始上坡了，之后在坡的頂點要從E繞一個較大的圓弧到F點。這個圖中前輪的半徑為1，每一段的長度依次為：

AB=3.0000；弧長BC=0.9828；CD=1.1913；DE=2.6848；弧長EF=2.6224；FG=2.4415；GH=2.2792。

總長度為15.2021。

現(xiàn)在給出了車輪的半徑和路面的描述，請求出車輪軸軌跡的總長度。輸入格式輸入的第一行包含一個整數(shù)n和一個實數(shù)r，用一個空格分隔，表示描述路面的坐標點數(shù)和車輪的半徑。

接下來n行，每個包含兩個實數(shù)，其中第i行的兩個實數(shù)x[i],y[i]表示描述路面的第i個點的坐標。

路面定義為所有路面坐標點順次連接起來的折線。給定的路面的一定滿足以下性質：

*第一個坐標點一定是(0,0)；

*第一個點和第二個點的縱坐標相同；

*倒數(shù)第一個點和倒數(shù)第二個點的縱坐標相同；

*第一個點和第二個點的距離不少于車輪半徑；

*倒數(shù)第一個點和倒數(shù)第二個點的的距離不少于車輪半徑；

*后一個坐標點的橫坐標大于前一個坐標點的橫坐標，即對于所有的i，x[i+1]>x[i]。輸出格式輸出一個實數(shù)，四舍五入保留兩個小數(shù)，表示車輪軸經過的總長度。

你的結果必須和參考答案一模一樣才能得分。數(shù)據(jù)保證答案精確值的小數(shù)點后第三位不是4或5。樣例輸入41.50

0.000.00

2.000.00

4.00-1.00

6.00-1.00樣例輸出6.22樣例說明這個樣例對應第一個圖。樣例輸入61.00

0.000.00

3.000.00

5.00-3.00

6.002.00

7.00-1.00

10.00-1.00樣例輸出15.20樣例說明這個樣例對應第二個圖數(shù)據(jù)規(guī)模和約定對于20%的數(shù)據(jù)，n=4；

對于40%的數(shù)據(jù)，n≤10；

對于100%的數(shù)據(jù)，4≤n≤100，0.5≤r≤20.0，x[i]≤2000.0，-2000.0≤y[i]≤2000.0。歷屆試題約數(shù)倍數(shù)選卡片

時間限制：1.0s

內存限制：256.0MB問題描述閑暇時，福爾摩斯和華生玩一個游戲：

在N張卡片上寫有N個整數(shù)。兩人輪流拿走一張卡片。要求下一個人拿的數(shù)字一定是前一個人拿的數(shù)字的約數(shù)或倍數(shù)。例如，某次福爾摩斯拿走的卡片上寫著數(shù)字“6”，則接下來華生可以拿的數(shù)字包括：

1，2，3,6，12，18，24....

當輪到某一方拿卡片時，沒有滿足要求的卡片可選，則該方為輸方。

請你利用計算機的優(yōu)勢計算一下，在已知所有卡片上的數(shù)字和可選哪些數(shù)字的條件下，怎樣選擇才能保證必勝！

當選多個數(shù)字都可以必勝時，輸出其中最小的數(shù)字。如果無論如何都會輸，則輸出-1。輸入格式輸入數(shù)據(jù)為2行。第一行是若干空格分開的整數(shù)（每個整數(shù)介于1~100間），表示當前剩余的所有卡片。

第二行也是若干空格分開的整數(shù)，表示可以選的數(shù)字。當然，第二行的數(shù)字必須完全包含在第一行的數(shù)字中。輸出格式程序則輸出必勝的招法??！樣例輸入236

36樣例輸出3樣例輸入1223345

345樣例輸出4歷屆試題農場陽光

時間限制：1.0s

內存限制：256.0MB問題描述X星球十分特殊，它的自轉速度與公轉速度相同，所以陽光總是以固定的角度照射。

最近，X星球為發(fā)展星際旅游業(yè)，把空間位置出租給Y國游客來曬太陽。每個租位是漂浮在空中的圓盤形彩云（圓盤與地面平行）。當然，這會遮擋住部分陽光，被遮擋的土地植物無法生長。

本題的任務是計算某個農場宜于作物生長的土地面積有多大。輸入格式輸入數(shù)據(jù)的第一行包含兩個整數(shù)a,b，表示某農場的長和寬分別是a和b，此時，該農場的范圍是由坐標(0,0,0),(a,0,0),(a,b,0),(0,b,0)圍成的矩形區(qū)域。

第二行包含一個實數(shù)g，表示陽光照射的角度。簡單起見，我們假設陽光光線是垂直于農場的寬的，此時正好和農場的長的夾角是g度，此時，空間中的一點(x,y,z)在地面的投影點應該是(x+z*ctg(g度),y,0)，其中ctg(g度)表示g度對應的余切值。

第三行包含一個非負整數(shù)n，表示空中租位個數(shù)。

接下來n行，描述每個租位。其中第i行包含4個整數(shù)xi,yi,zi,ri，表示第i個租位彩云的圓心在(xi,yi,zi)位置，圓半徑為ri。輸出格式要求輸出一個實數(shù)，四舍五入保留兩位有效數(shù)字，表示農場里能長莊稼的土地的面積。樣例輸入1010

90.0

1

55105樣例輸出21.46樣例輸入88

90.0

1

44105樣例輸出1.81樣例輸入2010

45.0

2

5055

86146樣例輸出130.15歷屆試題格子刷油漆

時間限制：1.0s

內存限制：256.0MB問題描述X國的一段古城墻的頂端可以看成2*N個格子組成的矩形（如下圖所示），現(xiàn)需要把這些格子刷上保護漆。

你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數(shù)），但不能移動到較遠的格子（因為油漆未干不能踩?。?/p>

比如：adbcef就是合格的刷漆順序。

cefdab是另一種合適的方案。

當已知N時，求總的方案數(shù)。當N較大時，結果會迅速增大，請把結果對1000000007(十億零七)取模。輸入格式輸入數(shù)據(jù)為一個正整數(shù)（不大于1000）輸出格式輸出數(shù)據(jù)為一個正整數(shù)。樣例輸入2樣例輸出24樣例輸入3樣例輸出96樣例輸入22樣例輸出359635897歷屆試題高僧斗法

時間限制：1.0s

內存限制：256.0MB問題描述古時喪葬活動中經常請高僧做法事。儀式結束后，有時會有“高僧斗法”的趣味節(jié)目，以舒緩壓抑的氣氛。

節(jié)目大略步驟為：先用糧食（一般是稻米）在地上“畫”出若干級臺階（表示N級浮屠）。又有若干小和尚隨機地“站”在某個臺階上。最高一級臺階必須站人，其它任意。(如圖1所示)

兩位參加游戲的法師分別指揮某個小和尚向上走任意多級的臺階，但會被站在高級臺階上的小和尚阻擋，不能越過。兩個小和尚也不能站在同一臺階，也不能向低級臺階移動。

兩法師輪流發(fā)出指令，最后所有小和尚必然會都擠在高段臺階，再也不能向上移動。輪到哪個法師指揮時無法繼續(xù)移動，則游戲結束，該法師認輸。

對于已知的臺階數(shù)和小和尚的分布位置，請你計算先發(fā)指令的法師該如何決策才能保證勝出。輸入格式輸入數(shù)據(jù)為一行用空格分開的N個整數(shù)，表示小和尚的位置。臺階序號從1算起，所以最后一個小和尚的位置即是臺階的總數(shù)。（N<100,臺階總數(shù)<1000）輸出格式輸出為一行用空格分開的兩個整數(shù):AB,表示把A位置的小和尚移動到B位置。若有多個解，輸出A值較小的解，若無解則輸出-1。樣例輸入159樣例輸出14樣例輸入15810樣例輸出13歷屆試題網絡尋路

時間限制：1.0s

內存限制：256.0MB問題描述X國的一個網絡使用若干條線路連接若干個節(jié)點。節(jié)點間的通信是雙向的。某重要數(shù)據(jù)包，為了安全起見，必須恰好被轉發(fā)兩次到達目的地。該包可能在任意一個節(jié)點產生，我們需要知道該網絡中一共有多少種不同的轉發(fā)路徑。源地址和目標地址可以相同，但中間節(jié)點必須不同。如下圖所示的網絡。1->2->3->1是允許的1->2->1->2或者1->2->3->2都是非法的。輸入格式輸入數(shù)據(jù)的第一行為兩個整數(shù)NM，分別表示節(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ù)。樣例輸入133

12

23

13樣例輸出16樣例輸入244

12

23

31

14樣例輸出210歷屆試題危險系數(shù)

時間限制：1.0s

內存限制：256.0MB問題描述抗日戰(zhàn)爭時期，冀中平原的地道戰(zhàn)曾發(fā)揮重要作用。地道的多個站點間有通道連接，形成了龐大的網絡。但也有隱患，當敵人發(fā)現(xiàn)了某個站點后，其它站點間可能因此會失去聯(lián)系。我們來定義一個危險系數(shù)DF(x,y)：對于兩個站點x和y(x!=y),如果能找到一個站點z，當z被敵人破壞后，x和y不連通，那么我們稱z為關于x,y的關鍵點。相應的，對于任意一對站點x和y，危險系數(shù)DF(x,y)就表示為這兩點之間的關鍵點個數(shù)。本題的任務是：已知網絡結構，求兩站點之間的危險系數(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.樣例輸入76

13

23

34

35

45

56

16樣例輸出2歷屆試題橫向打印二叉樹

時間限制：1.0s

內存限制：256.0MB問題描述二叉樹可以用于排序。其原理很簡單：對于一個排序二叉樹添加新節(jié)點時，先與根節(jié)點比較，若小則交給左子樹繼續(xù)處理，否則交給右子樹。當遇到空子樹時，則把該節(jié)點放入那個位置。比如，10857124的輸入順序，應該建成二叉樹如下圖所示，其中.表示空白。...|-12

10-|

...|-8-|

.......|...|-7

.......|-5-|

...........|-4本題目要求：根據(jù)已知的數(shù)字，建立排序二叉樹，并在標準輸出中橫向打印該二叉樹。輸入格式輸入數(shù)據(jù)為一行空格分開的N個整數(shù)。N<100，每個數(shù)字不超過10000。輸入數(shù)據(jù)中沒有重復的數(shù)字。輸出格式輸出該排序二叉樹的橫向表示。為了便于評卷程序比對空格的數(shù)目，請把空格用句點代替：樣例輸入110520樣例輸出1...|-20

10-|

...|-5樣例輸入251020847樣例輸出2.......|-20

..|-10-|

..|....|-8-|

..|........|-7

5-|

..|-4歷屆試題幸運數(shù)

時間限制：1.0s

內存限制：256.0MB問題描述幸運數(shù)是波蘭數(shù)學家烏拉姆命名的。它采用與生成素數(shù)類似的“篩法”生成。首先從1開始寫出自然數(shù)1,2,3,4,5,6,....1就是第一個幸運數(shù)。我們從2這個數(shù)開始。把所有序號能被2整除的項刪除，變?yōu)椋?_3_5_7_9....把它們縮緊，重新記序，為：13579....。這時，3為第2個幸運數(shù)，然后把所有能被3整除的序號位置的數(shù)刪去。注意，是序號位置，不是那個數(shù)本身能否被3整除!!刪除的應該是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ù)mn,用空格分開(m<n<1000*1000)輸出格式程序輸出位于m和n之間的幸運數(shù)的個數(shù)（不包含m和n）。樣例輸入1120樣例輸出15樣例輸入23069樣例輸出28歷屆試題大臣的旅費

時間限制：1.0s

內存限制：256.0MB問題描述很久以前，T王國空前繁榮。為了更好地管理國家，王國修建了大量的快速路，用于連接首都和王國內的各大城市。為節(jié)省經費，T國的大臣們經過思考，制定了一套優(yōu)秀的修建方案，使得任何一個大城市都能從首都直接或者通過其他大城市間接到達。同時，如果不重復經過大城市，從首都到達每個大城市的方案都是唯一的。J是T國重要大臣，他巡查于各大城市之間，體察民情。所以，從一個城市馬不停蹄地到另一個城市成了J最常做的事情。他有一個錢袋，用于存放往來城市間的路費。聰明的J發(fā)現(xiàn)，如果不在某個城市停下來修整，在連續(xù)行進過程中，他所花的路費與他已走過的距離有關，在走第x千米到第x+1千米這一千米中（x是整數(shù)），他花費的路費是x+10這么多。也就是說走1千米花費11，走2千米要花費23。J大臣想知道：他從某一個城市出發(fā)，中間不休息，到達另一個城市，所有可能花費的路費中最多是多少呢？

輸入格式輸入的第一行包含一個整數(shù)n，表示包括首都在內的T王國的城市數(shù)城市從1開始依次編號，1號城市為首都。接下來n-1行，描述T國的高速路（T國的高速路一定是n-1條）每行三個整數(shù)Pi,Qi,Di，表示城市Pi和城市Qi之間有一條高速路，長度為Di千米。輸出格式輸出一個整數(shù)，表示大臣J最多花費的路費是多少。樣例輸入15

122

131

245

254樣例輸出1135輸出格式大臣J從城市4到城市5要花費135的路費。歷屆試題買不到的數(shù)目

時間限制：1.0s

內存限制：256.0MB問題描述小明開了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣。小朋友來買糖的時候，他就用這兩種包裝來組合。當然有些糖果數(shù)目是無法組合出來的，比如要買10顆糖。你可以用計算機測試一下，在這種包裝情況下，最大不能買到的數(shù)量是17。大于17的任何數(shù)字都可以用4和7組合出來。本題的要求就是在已知兩個包裝的數(shù)量時，求最大不能組合出的數(shù)字。輸入格式兩個正整數(shù)，表示每種包裝中糖的顆數(shù)(都不多于1000)輸出格式一個正整數(shù)，表示最大不能買到的糖數(shù)樣例輸入147樣例輸出117樣例輸入235樣例輸出27歷屆試題連號區(qū)間數(shù)

時間限制：1.0s

內存限制：256.0MB問題描述小明這些天一直在思考這樣一個奇怪而有趣的問題：在1~N的某個全排列中有多少個連號區(qū)間呢？這里所說的連號區(qū)間的定義是：

如果區(qū)間[L,R]里的所有元素（即此排列的第L個到第R個元素）遞增排序后能得到一個長度為R-L+1的“連續(xù)”數(shù)列，則稱這個區(qū)間連號區(qū)間。當N很小的時候，小明可以很快地算出答案，但是當N變大的時候，問題就不是那么簡單了，現(xiàn)在小明需要你的幫助。輸入格式第一行是一個正整數(shù)N(1<=N<=50000),表示全排列的規(guī)模。第二行是N個不同的數(shù)字Pi(1<=Pi<=N)，表示這N個數(shù)字的某一全排列。輸出格式輸出一個整數(shù)，表示不同連號區(qū)間的數(shù)目。樣例輸入14

3241樣例輸出17樣例輸入25

34251樣例輸出29歷屆試題翻硬幣

時間限制：1.0s

內存限制：256.0MB問題描述小明正在玩一個“翻硬幣”的游戲。桌上放著排成一排的若干硬幣。我們用*表示正面，用o表示反面（是小寫字母，不是零）。比如，可能情形是：**oo***oooo如果同時翻轉左邊的兩個硬幣，則變?yōu)椋簅ooo***oooo現(xiàn)在小明的問題是：如果已知了初始狀態(tài)和要達到的目標狀態(tài)，每次只能同時翻轉相鄰的兩個硬幣,那么對特定的局面，最少要翻動多少次呢？

我們約定：把翻動相鄰的兩個硬幣叫做一步操作，那么要求：輸入格式兩行等長的字符串，分別表示初始狀態(tài)和要達到的目標狀態(tài)。每行的長度<1000輸出格式一個整數(shù)，表示最小操作步數(shù)。樣例輸入1**********

o****o****樣例輸出15樣例輸入2*o**o***o***

*o***o**o***樣例輸出21歷屆試題錯誤票據(jù)

時間限制：1.0s

內存限制：256.0MB問題描述某涉密單位下發(fā)了某種票據(jù)，并要在年終全部收回。每張票據(jù)有唯一的ID號。全年所有票據(jù)的ID號是連續(xù)的，但ID的開始數(shù)碼是隨機選定的。因為工作人員疏忽，在錄入ID號的時候發(fā)生了一處錯誤，造成了某個ID斷號，另外一個ID重號。你的任務是通過編程，找出斷號的ID和重號的ID。假設斷號不可能發(fā)生在最大和最小號。輸入格式要求程序首先輸入一個整數(shù)N(N<100)表示后面數(shù)據(jù)行數(shù)。接著讀入N行數(shù)據(jù)。每行數(shù)據(jù)長度不等，是用空格分開的若干個（不大于100個）正整數(shù)（不大于100000），請注意行內和行末可能有多余的空格，你的程序需要能處理這些空格。每個整數(shù)代表一個ID號。輸出格式要求程序輸出1行，含兩個整數(shù)mn，用空格分隔。其中，m表示斷號ID，n表示重號ID樣例輸入12

568119

10129樣例輸出179樣例輸入26

164178108109180155141159104182179118137184115124125129168196

172189127107112192103131133169158

128102110148139157140195197

185152135106123173122136174191145116151143175120161134162190

149138142146199126165156153193144166170121171132101194187188

113130176154177120117150114183186181100163160167147198111119樣例輸出2105120歷屆試題剪格子

時間限制：1.0s

內存限制：256.0MB問題描述如下圖所示，3x3的格子中填寫了一些整數(shù)。+--*--+--+

|10*1|52|

+--****--+

|20|30*1|

*******--+

|1|2|3|

+--+--+--+我們沿著圖中的星號線剪開，得到