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星銀行就去換零錢(qián)。小明有點(diǎn)強(qiáng)迫癥，他堅(jiān)持要求200元換出的零鈔中2元的張數(shù)剛好是1元的張數(shù)的10倍，剩下的當(dāng)然都是5元面額的。銀行的工作人員有點(diǎn)為難，你能幫助算出：在滿(mǎn)足小明要求的前提下，最少要換給他多少?gòu)堚n票嗎？（5元，2元，1元面額的必須都有，不能是0）注意，需要提交的是一個(gè)整數(shù)，不要填寫(xiě)任何多余的內(nèi)容。手算都可以。下面是代碼，答案741. #include 2. using namespace std;3. int

2、 main()4. for(int i=1;i40;i+)5. for(int j=1;j200;j+)6. if(5*i+2*10*j+1*j=200)7. cout5*i+2*10*j+1*j=5*i+2*10*j+1*j(一共i+10*j+j張)endl;8. 9. 10. return 0;11. 12. 2.標(biāo)題：激光樣式x星球的盛大節(jié)日為增加氣氛，用30臺(tái)機(jī)光器一字排開(kāi)，向太空中打出光柱。安裝調(diào)試的時(shí)候才發(fā)現(xiàn)，不知什么原因，相鄰的兩臺(tái)激光器不能同時(shí)打開(kāi)！國(guó)王很想知道，在目前這種bug存在的情況下，一共能打出多少種激光效果？顯然，如果只有3臺(tái)機(jī)器，一共可以成5種樣式，即：全都關(guān)上（s

3、orry,此時(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ù)，不要填寫(xiě)任何多余的內(nèi)容。思路很簡(jiǎn)單，暴力搜索，30個(gè)燈光從左到右，從左邊第一個(gè)開(kāi)始，第一個(gè)可以開(kāi)關(guān)，第二個(gè)要根據(jù)左邊的燈光是否開(kāi)啟來(lái)取值，以此類(lèi)推。 答案21783091. #include 2. #include 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

4、. ans+;10. return;11. 12. if(index = 0 | xindex-1 = 0) /第一個(gè)燈光可以取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. coutansendl

5、;28. return 0;29. 3.標(biāo)題：格雷碼格雷碼是以n位的二進(jìn)制來(lái)表示數(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ù)字最末位改變（0變1，1變0）當(dāng)產(chǎn)生第偶數(shù)個(gè)數(shù)時(shí)，先找到最右邊的一個(gè)1，把它左邊的數(shù)字改變。用這個(gè)規(guī)則產(chǎn)生的4位格雷碼序列如下：0000000100110010011001110101010011001101111111101010101110011000以下是實(shí)現(xiàn)代碼，仔細(xì)分析其中邏輯，并填寫(xiě)劃線(xiàn)部分缺少的代碼。（答案：

6、a(a&(-a)1)）1. #include 2. void show(int a,int n)3. int i;4. int msk = 1;5. for(i=0; in-1; i+) msk = msk 1;6. for(i=0; i 1;9. 10. printf(n);11. 12. void f(int n)13. int i;14. int num = 1;15. for(i=0; in; i+) num = num1;16. int a = 0;17. for(i=0; inum; i+)18. show(a,n);19. if(i%2=0)20. a = a 1;21. 22.

7、 else23. a = _ ; /填空24. 25. 26. 27. int main()28. f(4);29. return 0;30. 請(qǐng)注意：只需要填寫(xiě)劃線(xiàn)部分缺少的內(nèi)容，不要抄寫(xiě)已有的代碼或符號(hào)。4.標(biāo)題：調(diào)手表小明買(mǎi)了塊高端大氣上檔次的電子手表，他正準(zhǔn)備調(diào)時(shí)間呢。在M78星云，時(shí)間的計(jì)量單位和地球上不同，M78星云的一個(gè)小時(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，則要按

8、n-1次加一按鈕才能調(diào)回正確時(shí)間。小明想，如果手表可以再添加一個(gè)按鈕，表示把當(dāng)前的數(shù)加k該多好啊他想知道，如果有了這個(gè)+k按鈕，按照最優(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ù)表示：按照最優(yōu)策略按鍵，從一個(gè)時(shí)間調(diào)到另一個(gè)時(shí)間最多要按多少次。樣例輸入53樣例輸出2樣例解釋如果時(shí)間正確則按0次。否則要按的次數(shù)和操作系列之間的關(guān)系如下：1：+12：+1,+13：+34：+3,+1數(shù)據(jù)范

9、圍對(duì)于30%的數(shù)據(jù)0kn=5對(duì)于60%的數(shù)據(jù)0kn=100對(duì)于100%的數(shù)據(jù)0kn=100000資源約定：峰值內(nèi)存消耗（含虛擬機(jī)）256MCPU消耗1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入.”的多余內(nèi)容。注意：main函數(shù)需要返回0;只使用ANSIC/ANSIC+標(biāo)準(zhǔn);不要調(diào)用依賴(lài)于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。所有依賴(lài)的函數(shù)必須明確地在源文件中#include不能通過(guò)工程設(shè)置而省略常用頭文件。提交程序時(shí)，注意選擇所期望的語(yǔ)言類(lèi)型和編譯器類(lèi)型。5.標(biāo)題：搭積木小明對(duì)搭積木非常感興趣。他的積木都是同樣大小的正立方體。在搭積木時(shí)，小明選取m塊積木作為地基，將他們?cè)谧雷由弦蛔?/p>

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

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

12、00，m=100。資源約定：峰值內(nèi)存消耗（含虛擬機(jī)）256MCPU消耗1000ms請(qǐng)嚴(yán)格按要求輸出，不要畫(huà)蛇添足地打印類(lèi)似：“請(qǐng)您輸入.”的多余內(nèi)容。注意：main函數(shù)需要返回0;只使用ANSIC/ANSIC+標(biāo)準(zhǔn);不要調(diào)用依賴(lài)于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。所有依賴(lài)的函數(shù)必須明確地在源文件中#include不能通過(guò)工程設(shè)置而省略常用頭文件。提交程序時(shí)，注意選擇所期望的語(yǔ)言類(lèi)型和編譯器類(lèi)型。6.標(biāo)題：矩陣求和經(jīng)過(guò)重重筆試面試的考驗(yàn)，小明成功進(jìn)入Macrohard公司工作。今天小明的任務(wù)是填滿(mǎn)這么一張表：表有n行n列，行和列的編號(hào)都從1算起。其中第i行第j個(gè)元素的值是gcd(i,j)的平方，gcd表示最大公約數(shù)，以下是這個(gè)表的前四行的前四列：11111414119114116小明突然冒出一個(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ì)于1