第五屆藍橋杯大賽軟件類C++B組全國總決賽真題VIP

1、2014年決賽C/C+本科B組1 .結果填空（滿分10分）標題：年齡巧合小明和他的表弟一起去看電影，有人問他們的年齡。小明說：今年是我們的幸運年啊。我出生年份的四位數(shù)字加起來剛好是我的年齡。表弟的也是如此。已知今年是2014年,并且，小明說的年齡指的是周歲。請推斷并填寫出小明的出生年份。這是一個4位整數(shù)，請通過瀏覽器提交答案，不要填寫任何多余的內容（比如，他表弟的出生年份，或是他們的年齡等等）2 .結果填空（滿分25分）標題：出棧次序X星球特別講究秩序，所有道路都是單行線。一個甲殼蟲車隊，共16輛車，按照編號先后發(fā)車，夾在其它車流中，緩緩前行。路邊有個死胡同，只能容一輛車通過，是臨時的檢查站，

2、如圖【p1.png】所示。X星球太死板，要求每輛路過的車必須進入檢查站，也可能不檢查就放行，也可能仔細檢查。如果車輛進入檢查站和離開的次序可以任意交錯。那么，該車隊再次上路后，可能的次序有多少種？為了方便起見，假設檢查站可容納任意數(shù)量的汽車。顯然，如果車隊只有1輛車，可能次序1種；2輛車可能次序2種；3輛車可能次序5種?，F(xiàn)在足足有16輛車啊，親！需要你計算出可能次序的數(shù)目。這是一個整數(shù)，請通過瀏覽器提交答案，不要填寫任何多余的內容（比如說明性文字）。OOO死胡同檢查站單行車道車隊示意圖3 .代碼填空(滿分35分)標題：信號匹配從X星球接收了一個數(shù)字信號序列?，F(xiàn)有一個已知的樣板序列。需要在信號序

3、列中查找它首次出現(xiàn)的位置。這類似于串的匹配操作。如果信號序列較長，樣板序列中重復數(shù)字較多，就應當注意比較的策略了?？梢苑抡沾腒MPW法，進行無回溯的匹配。這種匹配方法的關鍵是構造next數(shù)組。nexti表示第i項比較失配時，樣板序列向右滑動，需要重新比較的項的序號。如果為-1,表示母序列可以進入失配位置的下一個位置進行新的比較。下面的代碼實現(xiàn)了這個功能，請仔細閱讀源碼，推斷劃線位置缺失的代碼。/生成next數(shù)組int*make_next(intpa口，intpn)int*next=(int*)malloc(sizeof(int)*pn);next0=-1;intj=0;intk=-1;whi

4、le(j<pn-1)if(k=-1|paj=pak)j+;k+;nextj=k;elsek=nextk;returnnext;/da中搜索pa,da的長度為an,pa的長度為pnintfind(intda口，intan,intpa口，intpn)intrst=-1;int*next=make_next(pa,pn);inti=0;/da中的指針intj=0;/pa中的指針intn=0;while(i<an)n+;if(dai=paj|j=-1)i+;j+;else;/填空位置if(j=pn)rst=i-pn;break;free(next);returnrst;intmain()i

5、ntda121,2,1,12121,121,121,12121,121,121,1,12123;intpa=1,2,1,1,2,1,1,1,2;intn=find(da,sizeof(da)/sizeof(int),pa,sizeof(pa)/sizeof(int);printf("%dn",n);return0;注意：通過瀏覽器提交答案。只填寫缺少的內容，不要填寫任何多余的內容（例如：說明性文字或已有符號）4 .程序設計(滿分50分)標題：生物芯片X博士正在研究一種生物芯片，其邏輯密集度、容量都遠遠高于普通的半導體芯片。博士在芯片中設計了n個微型光源，每個光源操作一次就會

6、改變其狀態(tài)，即：點亮轉為關閉，或關閉轉為點亮。這些光源的編號從1到n,開始的時候所有光源都是關閉的。博士計劃在芯片上執(zhí)行如下動作：所有編號為2的倍數(shù)的光源操作一次，也就是把2468.等序號光源打開所有編號為3的倍數(shù)的光源操作一次，也就是對369.等序號光源操作，注意此時6號光源又關閉了。所有編號為4的倍數(shù)的光源操作一次。直到編號為n的倍數(shù)的光源操作一次。X博士想知道：經過這些操作后，某個區(qū)間中的哪些光源是點亮的?！据斎敫袷健?個用空格分開的整數(shù)：NLR(L<R<N<10A15)N表示光源數(shù)，L表示區(qū)間的左邊界,R表示區(qū)間的右邊界?！据敵龈袷健枯敵?個整數(shù)，表示經過所有操作后，

7、L,R區(qū)間中有多少個光源是點亮的。例如：輸入：5 23程序應該輸出：2再例如：輸入：1036程序應該輸出：3資源約定：峰值內存消耗<256MCPU消耗<1000ms請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入”的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意：main函數(shù)需要返回0注意：只使用ANSIC/ANSIC+標準，不要調用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。注意：所有依賴的函數(shù)必須明確地在源文件中#include<xxx>,不能通過工程設置而省略常用頭文件。提交時，注意選擇所期望的編譯器類型。5.程序設計(滿分80分)標題：Log

8、大俠atm參加了速算訓練班，經過刻苦修煉，對以2為底的對數(shù)算得飛快，人稱Log大俠。一天，Log大俠的好友drd有一些整數(shù)序列需要變換，Log大俠正好施展法力.變換的規(guī)則是：對其某個子序列的每個整數(shù)變?yōu)椋簂og_2(x)+1其中表示向下取整，就是對每個數(shù)字求以2為底的對數(shù)，然后取下整。例如對序列342操作一次后，這個序列會變成232。drd需要知道，每次這樣操作后，序列的和是多少。【輸入格式】第一行兩個正整數(shù)nm。第二行n個數(shù)，表示整數(shù)序列，都是正數(shù)。接下來m行，每行兩個數(shù)LR表示atm這次操作的是區(qū)間L,R,數(shù)列序號從1開始?！据敵龈袷健枯敵鰉行，依次表示atm每做完一個操作后，整個序列的和

9、。例如，輸入：335641 22 313程序應該輸出：1086【數(shù)據(jù)范圍】對于30%的數(shù)據(jù)，n,m<=10A3對于100%的數(shù)據(jù)，n,m<=10A5資源約定：峰值內存消耗<256MCPU消耗<1000ms請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入”的多余內容。所有代碼放在同一個源文件中，調試通過后，拷貝提交該源碼。注意：main函數(shù)需要返回0注意：只使用ANSIC/ANSIC+標準，不要調用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。注意：所有依賴的函數(shù)必須明確地在源文件中#include<xxx>,不能通過工程設置而省略常用頭文件。提交時，注意選擇所期望

10、的編譯器類型。6.程序設計（滿分100分）標題：殖民地帶著殖民擴張的野心，Pear和他的星際艦隊登上X星球的某平原。為了評估這塊土地的潛在價值，Pear把它劃分成了M*N格，每個格子上用一個整數(shù)（可正可負）表示它的價值。Pear要做的事很簡單一一選擇一些格子，占領這些土地，通過建立圍欄把它們和其它土地隔開。對于M*N的格子，一共有（M+1）*N+M*（N+1）條圍欄，即每個格子都有上下左右四個圍欄；不在邊界上的圍欄被相鄰的兩個格子公用。大概如下圖【p1.png】所示。圖中，藍色的一段是圍欄，屬于格子1和2;紅色的一段是圍欄，屬于格子3和4。每個格子有一個可正可負的收益，而建圍欄的代價則一定是正

11、的。你需要選擇一些格子，然后選擇一些圍欄把它們圍起來，使得所有選擇的格子和所有沒被選的格子嚴格的被隔開。選擇的格子可以不連通，也可以有“洞”，即一個連通塊中間有一些格子沒選。注意，若中間有“洞”，那么根據(jù)定義，“洞”和連通塊也必須被隔開。Pear的目標很明確，花最小的代價，獲得最大的收益?！据斎霐?shù)據(jù)】程序應當輸出輸入第一行兩個正整數(shù)MN,表示行數(shù)和列數(shù)。接下來M行，每行N個整數(shù)，構成矩陣A,Ai,j表示第i行第j列格子的價值。接下來M+1行，每行N個整數(shù)，構成矩陣B,Bi,j表示第i行第j列上方的圍欄建立代價。特別的，BM+1,j表示第M行第j列下方的圍欄建立代價。接下來M行，每行N+1個整數(shù)

12、，構成矩陣C,Ci,j表示第i行第j列左方的圍欄建立代價。特別的，Ci,N+1表示第i行第N列右方的圍欄建立代價?！据敵鰯?shù)據(jù)】一行。只有一個正整數(shù)，表示最大收益。【輸入樣例1】3365-6-11156532-8566416731123212252522261113163346312程序應當輸出：123【輸入樣例2】66722-7143-127474-1435533171-1270386640-685237850116220-66176556728-196825458305920292061831920115151031923624278161052228141512421315172328241127161213271915216211152311110209828121957162026222512302716269623870【數(shù)據(jù)范圍】對于20%勺數(shù)據(jù)，M,N<=4對于50%勺數(shù)據(jù)，M,N<=15對于100%勺數(shù)據(jù)，M,N<=200AB、C數(shù)組（所有的涉及到的格子、圍欄輸入數(shù)據(jù)）絕對值均不超過1000。根據(jù)題意,A數(shù)組可正可負，BC數(shù)組均為正整數(shù)。資源約定：峰值內存消耗<256MCPU消耗&