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

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

3、列中查找它首次出現(xiàn)的位置。這類似于串的匹配操作。如果信號(hào)序列較長(zhǎng)，樣板序列中重復(fù)數(shù)字較多，就應(yīng)當(dāng)注意比較的策略了。可以仿照串的KMPW法，進(jìn)行無(wú)回溯的匹配。這種匹配方法的關(guān)鍵是構(gòu)造next數(shù)組。nexti表示第i項(xiàng)比較失配時(shí)，樣板序列向右滑動(dòng)，需要重新比較的項(xiàng)的序號(hào)。如果為-1,表示母序列可以進(jìn)入失配位置的下一個(gè)位置進(jìn)行新的比較。下面的代碼實(shí)現(xiàn)了這個(gè)功能，請(qǐng)仔細(xì)閱讀源碼，推斷劃線位置缺失的代碼。/生成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的長(zhǎng)度為an,pa的長(zhǎng)度為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;注意：通過(guò)瀏覽器提交答案。只填寫缺少的內(nèi)容，不要填寫任何多余的內(nèi)容（例如：說(shuō)明性文字或已有符號(hào)）4 .程序設(shè)計(jì)(滿分50分)標(biāo)題：生物芯片X博士正在研究一種生物芯片，其邏輯密集度、容量都遠(yuǎn)遠(yuǎn)高于普通的半導(dǎo)體芯片。博士在芯片中設(shè)計(jì)了n個(gè)微型光源，每個(gè)光源操作一次就會(huì)

6、改變其狀態(tài)，即：點(diǎn)亮轉(zhuǎn)為關(guān)閉，或關(guān)閉轉(zhuǎn)為點(diǎn)亮。這些光源的編號(hào)從1到n,開始的時(shí)候所有光源都是關(guān)閉的。博士計(jì)劃在芯片上執(zhí)行如下動(dòng)作：所有編號(hào)為2的倍數(shù)的光源操作一次，也就是把2468.等序號(hào)光源打開所有編號(hào)為3的倍數(shù)的光源操作一次，也就是對(duì)369.等序號(hào)光源操作，注意此時(shí)6號(hào)光源又關(guān)閉了。所有編號(hào)為4的倍數(shù)的光源操作一次。直到編號(hào)為n的倍數(shù)的光源操作一次。X博士想知道：經(jīng)過(guò)這些操作后，某個(gè)區(qū)間中的哪些光源是點(diǎn)亮的。【輸入格式】3個(gè)用空格分開的整數(shù)：NLR(L<R<N<10A15)N表示光源數(shù)，L表示區(qū)間的左邊界,R表示區(qū)間的右邊界。【輸出格式】輸出1個(gè)整數(shù)，表示經(jīng)過(guò)所有操作后，

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

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

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

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

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

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