2018藍(lán)橋杯試題

1、精選文檔2018藍(lán)橋杯C語(yǔ)言b組國(guó)賽真題 1.標(biāo)題：換零鈔x星球的鈔票的面額只有：100元，5元，2元，1元，共4種。小明去x星旅游，他手里只有2張100元的x星幣，太不便利，恰好路過(guò)x星銀行就去換零錢。小明有點(diǎn)強(qiáng)迫癥，他堅(jiān)持要求200元換出的零鈔中2元的張數(shù)剛好是1元的張數(shù)的10倍，剩下的當(dāng)然都是5元面額的。銀行的工作人員有點(diǎn)犯難，你能掛念算出：在滿足小明要求的前提下，最少要換給他多少?gòu)堚n票嗎？（5元，2元，1元面額的必需都有，不能是0）留意，需要提交的是一個(gè)整數(shù)，不要填寫任何多余的內(nèi)容。手算都可以。下面是代碼，答案741. #include<iostream> 2.

2、using namespace std;3. int main()4. for(int i=1;i<40;i+)5. for(int j=1;j<200;j+)6. if(5*i+2*10*j+1*j=200)7. cout<<"5*"<<i<<"+2*"<<10*j<<"+1*"<<j<<"="<<5*i+2*10*j+1*j<<"(一共"<<i+10*j+j&l

3、t;<"張)"<<endl;8. 9. 10. return 0;11. 12. 2.標(biāo)題：激光樣式x星球的盛大節(jié)日為增加氣氛，用30臺(tái)機(jī)光器一字排開(kāi)，向太空中打出光柱。安裝調(diào)試的時(shí)候才發(fā)覺(jué)，不知什么緣由，相鄰的兩臺(tái)激光器不能同時(shí)打開(kāi)！國(guó)王很想知道，在目前這種bug存在的狀況下，一共能打出多少種激光效果？明顯，假如只有3臺(tái)機(jī)器，一共可以成5種樣式，即：全都關(guān)上（sorry, 此時(shí)無(wú)聲勝有聲，這也算一種）開(kāi)一臺(tái)，共3種開(kāi)兩臺(tái)，只1種30臺(tái)就不好算了，國(guó)王只好請(qǐng)你幫忙了。要求提交一個(gè)整數(shù)，表示30臺(tái)激光器能形成的樣式種數(shù)。留意，只提交一個(gè)整數(shù)，不要填

4、寫任何多余的內(nèi)容。思路很簡(jiǎn)潔，暴力搜尋，30個(gè)燈光從左到右，從左邊第一個(gè)開(kāi)頭，第一個(gè)可以開(kāi)關(guān)，其次個(gè)要依據(jù)左邊的燈光是否開(kāi)啟來(lái)取值，以此類推。 答案21783091. #include<iostream> 2. #include<string.h> 3. using namespace std;4. int ans = 0;5. int x31;/0代表關(guān)，1代表開(kāi) 6. 7. void dfs(int index)8. if(index = 30)9. ans+;10. return;11. 12. if(index = 0 | xindex-1 = 0) /第一個(gè)燈

5、光可以取0或1，當(dāng)前燈光左邊要是沒(méi)開(kāi)，那當(dāng)前燈光可以取0和1 13. for(int i=0;i<=1;i+)14. xindex = i;15. dfs(index+1);16. xindex = 0;17. 18. 19. else /左邊的燈光開(kāi)了，那當(dāng)前燈光只能關(guān)閉（取0） 20. dfs(index+1);21. 22. 23. 24. int main()25. memset(x,0,31*sizeof(int);26. dfs(0);27. cout<<ans<<endl;28. return 0;29. 3.標(biāo)題：格雷碼格雷碼是以n位的二進(jìn)制來(lái)表示

6、數(shù)。與一般的二進(jìn)制表示不同的是，它要求相鄰兩個(gè)數(shù)字只能有1個(gè)數(shù)位不同。首尾兩個(gè)數(shù)字也要求只有1位之差。有很多算法來(lái)生成格雷碼。以下是較常見(jiàn)的一種：從編碼全0開(kāi)頭生成。當(dāng)產(chǎn)生第奇數(shù)個(gè)數(shù)時(shí)，只把當(dāng)前數(shù)字最末位轉(zhuǎn)變（0變1，1變0）當(dāng)產(chǎn)生第偶數(shù)個(gè)數(shù)時(shí)，先找到最右邊的一個(gè)1，把它左邊的數(shù)字轉(zhuǎn)變。用這個(gè)規(guī)章產(chǎn)生的4位格雷碼序列如下：0000000100110010011001110101010011001101111111101010101110011000以下是實(shí)現(xiàn)代碼，認(rèn)真分析其中規(guī)律，并填寫劃線部分缺少的代碼。（答案：a(a&(-a)<<1)）1. #include <s

7、tdio.h>2. void show(int a,int n)3. int i;4. int msk = 1;5. for(i=0; i<n-1; i+) msk = msk << 1;6. for(i=0; i<n; i+)7. printf(a & msk)? "1" : "0");8. msk = msk >> 1;9. 10. printf("n");11. 12. void f(int n)13. int i;14. int num = 1;15. for(i=0; i&l

8、t;n; i+) num = num<<1;16. int a = 0;17. for(i=0; i<num; i+)18. show(a,n);19. if(i%2=0)20. a = a 1;21. 22. else23. a = _ ; /填空24. 25. 26. 27. int main()28. f(4);29. return 0;30. 請(qǐng)留意：只需要填寫劃線部分缺少的內(nèi)容，不要抄寫已有的代碼或符號(hào)。4.標(biāo)題：調(diào)手表小明買了塊高端大氣上檔次的電子手表，他正預(yù)備調(diào)時(shí)間呢。在 M78 星云，時(shí)間的計(jì)量單位和地球上不同，M78 星云的一個(gè)

9、小時(shí)有 n 分鐘。大家都知道，手表只有一個(gè)按鈕可以把當(dāng)前的數(shù)加一。在調(diào)分鐘的時(shí)候，假如當(dāng)前顯示的數(shù)是 0 ，那么按一下按鈕就會(huì)變成 1，再按一次變成 2 。假如當(dāng)前的數(shù)是 n - 1，按一次后會(huì)變成 0 。作為強(qiáng)迫癥患者，小明肯定要把手表的時(shí)間調(diào)對(duì)。假如手表上的時(shí)間比當(dāng)前時(shí)間多1，則要按 n - 1 次加一按鈕才能調(diào)回正確時(shí)間。小明想，假如手表可以再添加一個(gè)按鈕，表示把當(dāng)前的數(shù)加 k 該多好啊他想知道，假如有了這個(gè)&

10、#160;+k 按鈕，依據(jù)最優(yōu)策略按鍵，從任意一個(gè)分鐘數(shù)調(diào)到另外任意一個(gè)分鐘數(shù)最多要按多少次。留意，按 +k 按鈕時(shí)，假如加k后數(shù)字超過(guò)n-1,則會(huì)對(duì)n取模。比如，n=10, k=6 的時(shí)候，假設(shè)當(dāng)前時(shí)間是0，連按2次 +k 按鈕，則調(diào)為2。輸入格式一行兩個(gè)整數(shù) n, k ，意義如題。輸出格式一行一個(gè)整數(shù)表示：依據(jù)最優(yōu)策略按鍵，從一個(gè)時(shí)間調(diào)到另一個(gè)時(shí)間最多要按多少次。樣例輸入5 3樣例輸出2樣例解釋假如時(shí)間正確則按0次。否則要按的次數(shù)和操作系列之間的關(guān)系如下：1：+12：+1,

11、0;+13：+34：+3, +1數(shù)據(jù)范圍對(duì)于 30% 的數(shù)據(jù) 0 < k < n <= 5對(duì)于 60% 的數(shù)據(jù) 0 < k < n <= 100對(duì)于 100% 的數(shù)據(jù) 0 < k < n <= 100000資源商定：峰值內(nèi)存消耗（含虛擬機(jī)） <

12、60;256MCPU消耗  < 1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入.” 的多余內(nèi)容。留意：main函數(shù)需要返回0;只使用ANSI C/ANSI C+ 標(biāo)準(zhǔn);不要調(diào)用依靠于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。全部依靠的函數(shù)必需明確地在源文件中 #include <xxx>不能通過(guò)工程設(shè)置而省略常用頭文件。提交程序時(shí)，留意選擇所期望的語(yǔ)言類型和編譯器類型。5.標(biāo)題：搭積木小明對(duì)搭積木格外感愛(ài)好。他的積木都是同樣大小的正立方體。在搭積木時(shí)，小明選取 m

13、0;塊積木作為地基，將他們?cè)谧雷由弦蛔峙砰_(kāi)，中間不留空隙，并稱其為第0層。隨后，小明可以在上面擺放第1層，第2層，最多擺放至第n層。擺放積木必需遵循三條規(guī)章：規(guī)章1：每塊積木必需緊挨著放置在某一塊積木的正上方，與其下一層的積木對(duì)齊；規(guī)章2：同一層中的積木必需連續(xù)擺放，中間不能留有空隙；規(guī)章3：小明不寵愛(ài)的位置不能放置積木。其中，小明不寵愛(ài)的位置都被標(biāo)在了圖紙上。圖紙共有n行，從下至上的每一行分別對(duì)應(yīng)積木的第1層至第n層。每一行都有m個(gè)字符，字符可能是.或X，其中X表示這個(gè)位置是小明不寵愛(ài)的?，F(xiàn)在，小明想要知道，共有多少種放置積木的方案。他找到了參與藍(lán)橋杯的你來(lái)幫他計(jì)算這個(gè)答案。由于這個(gè)答案可能

14、很大，你只需要回答這個(gè)答案對(duì)1000000007(十億零七)取模后的結(jié)果。留意：地基上什么都不放，也算作是方案之一種?！据斎敫袷健枯斎霐?shù)據(jù)的第一行有兩個(gè)正整數(shù)n和m，表示圖紙的大小。隨后n行，每行有m個(gè)字符，用來(lái)描述圖紙 。每個(gè)字符只可能是.或X。【輸出格式】輸出一個(gè)整數(shù)，表示答案對(duì)1000000007取模后的結(jié)果?！緲永斎?】2 3.X.X.【樣例輸出1】4【樣例說(shuō)明1】成功的擺放有（其中O表示放置積木）：(1).X.X.(2).XOX.(3)O.XOX.(4).X.XO【樣例輸入2】3 3.X.X.【樣例輸出2】16【數(shù)據(jù)規(guī)模商定】對(duì)于10%的數(shù)據(jù)，n=1，

15、m<=30；對(duì)于40%的數(shù)據(jù)，n<=10，m<=30；對(duì)于100%的數(shù)據(jù)，n<=100，m<=100。資源商定：峰值內(nèi)存消耗（含虛擬機(jī)） < 256MCPU消耗  < 1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請(qǐng)您輸入.” 的多余內(nèi)容。留意：main函數(shù)需要返回0;只使用ANSI C/ANSI C+ 標(biāo)準(zhǔn);不要調(diào)用依靠于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。全部依靠的函數(shù)必需明確地在源文件中 #include <xxx>不能通

16、過(guò)工程設(shè)置而省略常用頭文件。提交程序時(shí)，留意選擇所期望的語(yǔ)言類型和編譯器類型。6.標(biāo)題：矩陣求和經(jīng)過(guò)重重筆試面試的考驗(yàn)，小明成功進(jìn)入 Macrohard 公司工作。今日小明的任務(wù)是填滿這么一張表：表有 n 行 n 列，行和列的編號(hào)都從1算起。其中第 i 行第 j 個(gè)元素的值是 gcd(i, j)的平方，gcd 表示最大公約數(shù)，以下是這個(gè)表的前四行的前四列：1  1  1  11  4&#

17、160; 1  41  1  9  11  4  1 16小明突然冒出一個(gè)驚異的想法，他想知道這張表中全部元素的和。由于表過(guò)于浩大，他期望借助計(jì)算機(jī)的力氣。輸入格式一行一個(gè)正整數(shù) n 意義見(jiàn)題。輸出格式一行一個(gè)數(shù)，表示全部元素的和。由于答案比較大，請(qǐng)輸出模 (109 + 7)(即：十億零七) 后的結(jié)果。樣例輸入4樣例輸出48數(shù)據(jù)范圍對(duì)于 30% 的數(shù)據(jù)，n <= 1000存在 10% 的數(shù)據(jù)，n = 105對(duì)于 60% 的數(shù)據(jù)，n <= 106對(duì)于 100% 的數(shù)據(jù)，n <= 107