2013年預(yù)賽cb組題目及評(píng)分

1、2013 年預(yù)賽 C/C+本科 B 題目及評(píng)分1題目標(biāo)題:大數(shù)學(xué)家他的有個(gè)好：無論如何都要記。有個(gè)與眾不同的地方，他從不注明年月日，而是用一個(gè)整數(shù)代替，比如：4210后來人們知道，那個(gè)整數(shù)就是日期，它表示那一天是出生后的第幾天。這或許也是個(gè)好，它時(shí)時(shí)刻刻提醒著主人：日子又過去一天，還有多少時(shí)光可以用于浪費(fèi)呢？出生于：1777 年 4 月 30 日。在發(fā)現(xiàn)的一個(gè)重要定理的上標(biāo)注著：5343，因此可算出那天是：1791 年 12 月15 日。獲得博士學(xué)位的那天上標(biāo)著：8113請(qǐng)你算出獲得博士學(xué)位的年月日。提交的格式是：yyyy-mm-dd, 例如：1980-03-21請(qǐng)嚴(yán)格按照格式，通過瀏覽器提交

2、。注意：只提交這個(gè)日期，不要寫其它附加內(nèi)容，比如：說明性的文字。參考：1799-07-162標(biāo)題: 馬虎的算式是個(gè)急性子，上小學(xué)的時(shí)候經(jīng)常把老師寫在黑板上的題目抄錯(cuò)了。有一次，老師出的題目是：36 x 495 = ?他卻給抄成了：396 x 45 = ?但結(jié)果卻很戲劇性，他的竟然是對(duì)的！因?yàn)?36 * 495 = 396 * 45 = 17820類似這樣的巧合情況可能還有很多，比如：27 * 594 = 297 * 54假設(shè) a b c d e 代表 19 不同的 5 個(gè)數(shù)字（注意是各不相同的數(shù)字，且不含 0）能滿足形如： ab * cde = adb * ce 這樣的算式一共有多少種呢？請(qǐng)你

3、利用計(jì)算機(jī)的優(yōu)勢尋找所有的可能，并回答不同算式的種類數(shù)。滿足乘法交換律的算式計(jì)為不同的種類，所以直接通過瀏覽器提交?？隙ㄊ莻€(gè)偶數(shù)。注意：只提交一個(gè)表示最終統(tǒng)計(jì)種類數(shù)的數(shù)字，不要提交解答過程或其它多余的內(nèi)容。參考142：3題目標(biāo)題: 第 39 級(jí)臺(tái)階剛剛看完好是 39 級(jí)!第 39 級(jí)臺(tái)階，離開院的時(shí)候，他數(shù)了數(shù)禮堂前的臺(tái)階數(shù)，恰站在臺(tái)階前，他突然又想著一個(gè)問題：如果一步只能邁上 1 個(gè)或 2 個(gè)臺(tái)階。先邁左腳，然后左右交替，最后一步是邁右腳，也就是說一共要走偶數(shù)步。那么，上完 39 級(jí)臺(tái)階，有多少種不同的上法呢？請(qǐng)你利用計(jì)算機(jī)的優(yōu)勢，幫助要求提交的是一個(gè)整數(shù)。尋找。注意：不要提交解答過程，或其

4、它的輔助說明文字。參考51167078：4標(biāo)題: 黃金連分?jǐn)?shù)黃金分割數(shù) 0.61803. 是個(gè)無理數(shù)，這個(gè)常數(shù)十分重要，在許多工程問題中會(huì)出現(xiàn)。有時(shí)需要把這個(gè)數(shù)字求得很精確。對(duì)于某些精密工程，常數(shù)的精度很重要。也許你聽哈勃太空望遠(yuǎn)鏡，它首次升空后就發(fā)現(xiàn)了一處人工加工錯(cuò)誤，對(duì)那樣一個(gè)龐然大物，其實(shí)只是鏡面加工時(shí)有比頭發(fā)絲還細(xì)許多倍的一處錯(cuò)誤而已，卻使它成了“近視眼”!言歸正傳，如何求得黃金分割數(shù)的盡可能精確的值呢？有許多方法。比較簡單的一種是用連分?jǐn)?shù)：1黃金數(shù) =11 +11 +11 +1 + .這個(gè)連分?jǐn)?shù)計(jì)算的“層數(shù)”越多，它的值越接近黃金分割數(shù)。請(qǐng)你利用這一特性，求出黃金分割數(shù)的足夠精確值，

5、要求四舍五入到小數(shù)點(diǎn)后 100 位。小數(shù)點(diǎn)后 3 位的值為：0.618小數(shù)點(diǎn)后 4 位的值為：0.6180小數(shù)點(diǎn)后 5 位的值為：0.61803小數(shù)點(diǎn)后 7 位的值為：0.6180340（注意尾部的 0，不能忽略）你的任務(wù)是：寫出精確到小數(shù)點(diǎn)后 100 位精度的黃金分割值。注意：尾數(shù)的四舍五入！ 尾數(shù)是 0 也要保留！顯然是一個(gè)小數(shù)，其小數(shù)點(diǎn)后有 100 位數(shù)字，請(qǐng)通過瀏覽器直接提交該數(shù)字。注意：不要提交解答過程，或其它輔助說明類的內(nèi)容。參考0.：81890113755題目標(biāo)題：前綴判斷如下的代碼判斷 needle_start 指向的串是否為 haystack_start 指向的串的前綴，如不

6、是，則返回 NULL。比如：abcd1234 就包含了 abc 為前綴char* prefix(char* haystack_start, char* needle_start)char* haystack = haystack_start; char* needle = needle_start; while(*haystack & *needle)if() return NULL;/填空位置if(*needle) return NULL; return haystack_start;請(qǐng)分析代碼邏輯，并推測劃線處的代碼，通過網(wǎng)頁提交。注意：僅把缺少的代碼作為，千萬不要填寫多余的代碼、符號(hào)或說

7、明文字！參考：*haystack+ != *needle+方法：用考生提交的代替程序中的 #運(yùn)行程序，比對(duì)結(jié)果為：|abcd| NO|abcd|abcd| NO|程序?yàn)椋?include char* start_with(char* haystack_start, char* needle_start)char* haystack = haystack_start; char* needle = needle_start; while(*haystack & *needle)if(#) return NULL;if(*needle) return NULL; return haystack_s

8、tart;void test(char* a, char* b)char* p = start_wiif(p=NULL),b);prf(NOn);elseprf(|%s|n, p);main()test(abcd,abc);test(abcd,acb);test(abcd,abcd);test(abcd,);test(,abc);test(,); return 0;6標(biāo)題：三部排序一般的排序有許多經(jīng)典算法，如快速排序、排序等。但實(shí)際應(yīng)用時(shí)，經(jīng)常會(huì)或多或少有一些特殊的要求。以根據(jù)實(shí)際情況建立更好的解法。比如，對(duì)一個(gè)整型數(shù)組中的數(shù)字進(jìn)行分類排序：沒必要套用那些經(jīng)典算法，可使得負(fù)數(shù)都靠左端，正數(shù)都靠

9、右端，0 在中部。注意問題的特點(diǎn)是：負(fù)數(shù)區(qū)域和正數(shù)區(qū)域內(nèi)并不要求有序?？梢岳眠@個(gè)特點(diǎn)通過 1 次線性掃描就結(jié)束戰(zhàn)斗!以下的程序?qū)崿F(xiàn)了該目標(biāo)。其中 x 指向待排序的整型數(shù)組，len 是數(shù)組的長度。void sort3p(* x,p = 0;left = 0; right = len-1;len)while(p=right) if(xp0)t = xright; xright = xp; xp = t;right-;else;/填空位置如果給定數(shù)組：25,18,-2,0,16,-5,33,21,0,19,-16,25,-3,0則排序后為：-3,-2,-16,-5,0,0,0,21,19,33,2

10、5,16,18,25請(qǐng)分析代碼邏輯，并推測劃線處的代碼，通過網(wǎng)頁提交注意：僅把缺少的代碼作為，千萬不要填寫多余的代碼、符號(hào)或說明文字！參考p+：方法：用考生提交的代替程序中的 #運(yùn)行程序，比對(duì)結(jié)果為：-1,-2,-6,-3,-5,-4,0,0,0,0,0,4,3,2,5,6,1,-1,-1,-2,-2,-3,-3,-4,-5,-4,-6,-5,-6,0,0,0,0,0,0,0,0,0,0,3,2,2,3,4,5,4,6,1,5,6,1,程序?yàn)椋?include void show(* x,i;len)for(i=0; ilen; i+)prf(%d,xi);prf(n);void sort3p

11、(* x,p = 0;left = 0; right = len-1;len)while(p=right) if(xp0)t = xright; xright = xp; xp = t;right-;/p+;else#;show(x, len);main()a = -1,0,1,-2,0,2,-3,0,0,3,-4,-5,4,-6,0,5,6;b = -1,0,-1,-2,0,-2,-3,0,0,-3,-4,-5,-4,-6,0,-5,-6;c = 1,0,1,2,0,2,3,0,0,3,4,5,4,6,0,5,6;sort3p(a,sizeof(a)/sizeof( sort3p(b,siz

12、eof(b)/sizeof(sort3p(c,sizeof(c)/sizeof();););return 0;7錯(cuò)誤票據(jù)某涉密下發(fā)了某種票據(jù)，并要在年終全部收回。每張票據(jù)有唯一的 ID 號(hào)。全年所有票據(jù)的 ID 號(hào)是連續(xù)的，但 ID 的開始數(shù)碼是隨機(jī)選定的。因?yàn)橐粋€(gè) ID 重號(hào)。疏忽，在錄入 ID 號(hào)的時(shí)候發(fā)生了一處錯(cuò)誤，造成了某個(gè) ID 斷號(hào)，另外你的任務(wù)是通過編程，找出斷號(hào)的 ID 和重號(hào)的 ID。假設(shè)斷號(hào)不可能發(fā)生在最大和最小號(hào)。要求程序首先輸入一個(gè)整數(shù)N(N100)表示后面數(shù)據(jù)行數(shù)。接著讀入N 行數(shù)據(jù)。每行數(shù)據(jù)長度不等，是用空格分開的若干個(gè)（不大于 100 個(gè)）正整數(shù)（不大于 1000

13、00）每個(gè)整數(shù)代表一個(gè) ID 號(hào)。要求程序輸出 1 行，含兩個(gè)整數(shù) m n，用空格分隔。其中，m 表示斷號(hào) ID，n 表示重號(hào) ID例如：用戶輸入：25 6 8 11 910 12 9則程序輸出：7 9再例如： 用戶輸入： 6164 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 158128 102 110 148 139 157 140 195 197185 152 135 106 123 173 122 13

14、6 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 101 194 187 188113 130 176 154 177 120 117 150 114 183 186 181 100 163 160 167 147 198 111 119則程序輸出：105 120資源約定：峰值內(nèi)存消耗 64M CPU 消耗 1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入.” 的多余內(nèi)容。所有代碼放在同一個(gè)源文件中，調(diào)試

15、通過后，拷貝提交該源碼。注意: main 函數(shù)需要返回 0注意: 只使用ANSI C/ANSI C+ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。注意: 所有依賴的函數(shù)必須明確地在源文件中常用頭文件。提交時(shí)，注意選擇所期望的編譯器類型。#include，不能通過工程設(shè)置而省略使用測試用例。輸入：325 13 22 21 27 17 1912 16 26 2820 23 18 29 14 24 10 11 19結(jié)果：15 19每個(gè)用例均等分值。資源約定：峰值內(nèi)存消耗 64MCPU 消耗 1000ms8題目標(biāo)題：翻硬幣正在玩一個(gè)“翻硬幣”的。桌上放著排成一排的若干硬幣。是零）。比如，可能情形

16、是：*oo*oooo用*表示正面，用 o 表示（是小寫字母，不如果同時(shí)翻轉(zhuǎn)左邊的兩個(gè)硬幣，則變?yōu)椋簅ooo*oooo現(xiàn)在是：如果已知了初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)，每次只能同時(shí)翻轉(zhuǎn)相鄰的兩個(gè)硬幣,那么對(duì)特定的局面，最少要翻動(dòng)多少次呢？約定：把翻動(dòng)相鄰的兩個(gè)硬幣叫做一步操作，那么要求程序輸入：兩行等長的字符串，分別表示初始狀態(tài)和要達(dá)到的目標(biāo)狀態(tài)。每行的長度1000程序輸出：一個(gè)整數(shù)，表示最小操作步數(shù)例如：用戶輸入：* o*o*程序應(yīng)該輸出：5再例如： 用戶輸入：*o*o*o*o*o*o*程序應(yīng)該輸出：1資源約定：峰值內(nèi)存消耗 64M CPU 消耗 1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類

17、似：“請(qǐng)您輸入.”的多余內(nèi)容。所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。注意: main 函數(shù)需要返回 0注意: 只使用ANSI C/ANSI C+ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。注意: 所有依賴的函數(shù)必須明確地在源文件中 #include ，不能通過工程設(shè)置而省略使用測試用例。輸入：*oo*oo*oo*結(jié)果：3每個(gè)用例均等分值。資源約定：峰值內(nèi)存消耗 64M CPU 消耗 1000ms9標(biāo)題：帶分?jǐn)?shù)100 可以表示為帶分?jǐn)?shù)的形式：100 = 3 + 69258 / 714還可以表示為：100 = 82 + 3546 / 197注意特征：帶分?jǐn)?shù)中，數(shù)字 19

18、分別出現(xiàn)且只出現(xiàn)一次（不包含 0）。類似這樣的帶分?jǐn)?shù)，100 有 11 種表示法。題目要求：從標(biāo)準(zhǔn)輸入讀入一個(gè)正整數(shù)N (N1000*1000)程序輸出該數(shù)字用數(shù)碼 19 不重復(fù)不遺漏地組成帶分?jǐn)?shù)表示的全部種數(shù)。注意：不要求輸出每個(gè)表示，只統(tǒng)計(jì)有多少表示法！例如：用戶輸入：100程序輸出：11再例如： 用戶輸入： 105程序輸出：6資源約定：峰值內(nèi)存消耗 64M CPU 消耗 3000ms請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入.” 的多余內(nèi)容。所有代碼放在同一個(gè)源文件中，調(diào)試通過后，拷貝提交該源碼。注意: main 函數(shù)需要返回 0注意: 只使用ANSI C/ANSI C+ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。注意: 所有依賴的函數(shù)必須明確地在源文件中 #include ， 不能通過工程設(shè)置而省略使用測試用例。每個(gè)用例均等分值。資源約定：峰值內(nèi)存消耗 64MCPU 消耗 3000ms10標(biāo)題：連號(hào)區(qū)間數(shù)這些天一直在思考這樣一個(gè)奇怪而有趣：在 1N 的某個(gè)全排列中有多少個(gè)連號(hào)區(qū)間呢？這里所說的連號(hào)區(qū)間的定義是：如果區(qū)間L, R 里的所有元素（即此排列的