2018藍橋杯試題

1、2018藍橋杯C語言b組國賽真題1.標(biāo)題：換零鈔x星球的鈔票的面額只有：100元，5元，2元，1元，共4種。小明去x星旅游，他手里只有2張100元的x星幣，太不方便，恰好路過x星銀行就去換零錢。小明有點強迫癥，他堅持要求200元換出的零鈔中2元的張數(shù)剛好是1元的張數(shù)的10倍，剩下的當(dāng)然都是5元面額的。銀行的工作人員有點為難，你能幫助算出：在滿足小明要求的前提下，最少要換給他多少張鈔票嗎？（5元，2元，1元面額的必須都有，不能是0）注意，需要提交的是一個整數(shù)，不要填寫任何多余的內(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臺機光器一字排開，向太空中打出光柱。安裝調(diào)試的時候才發(fā)現(xiàn)，不知什么原因，相鄰的兩臺激光器不能同時打開！國王很想知道，在目前這種bug存在的情況下，一共能打出多少種激光效果？顯然，如果只有3臺機器，一共可以成5種樣式，即：全都關(guān)上（s

3、orry,此時無聲勝有聲，這也算一種）開一臺，共3種開兩臺，只1種30臺就不好算了，國王只好請你幫忙了。要求提交一個整數(shù)，表示30臺激光器能形成的樣式種數(shù)。注意，只提交一個整數(shù)，不要填寫任何多余的內(nèi)容。思路很簡單，暴力搜索，30個燈光從左到右，從左邊第一個開始，第一個可以開關(guān)，第二個要根據(jù)左邊的燈光是否開啟來取值，以此類推。 答案21783091. #include 2. #include 3. using namespace std;4. int ans = 0;5. int x31;/0代表關(guān)，1代表開 6. 7. void dfs(int index)8. if(index = 30)9

4、. ans+;10. return;11. 12. if(index = 0 | xindex-1 = 0) /第一個燈光可以取0或1，當(dāng)前燈光左邊要是沒開，那當(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 /左邊的燈光開了，那當(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位的二進制來表示數(shù)。與普通的二進制表示不同的是，它要求相鄰兩個數(shù)字只能有1個數(shù)位不同。首尾兩個數(shù)字也要求只有1位之差。有很多算法來生成格雷碼。以下是較常見的一種：從編碼全0開始生成。當(dāng)產(chǎn)生第奇數(shù)個數(shù)時，只把當(dāng)前數(shù)字最末位改變（0變1，1變0）當(dāng)產(chǎn)生第偶數(shù)個數(shù)時，先找到最右邊的一個1，把它左邊的數(shù)字改變。用這個規(guī)則產(chǎn)生的4位格雷碼序列如下：0000000100110010011001110101010011001101111111101010101110011000以下是實現(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. 請注意：只需要填寫劃線部分缺少的內(nèi)容，不要抄寫已有的代碼或符號。4.標(biāo)題：調(diào)手表小明買了塊高端大氣上檔次的電子手表，他正準(zhǔn)備調(diào)時間呢。在M78星云，時間的計量單位和地球上不同，M78星云的一個小時有n分鐘。大家都知道，手表只有一個按鈕可以把當(dāng)前的數(shù)加一。在調(diào)分鐘的時候，如果當(dāng)前顯示的數(shù)是0，那么按一下按鈕就會變成1，再按一次變成2。如果當(dāng)前的數(shù)是n-1，按一次后會變成0。作為強迫癥患者，小明一定要把手表的時間調(diào)對。如果手表上的時間比當(dāng)前時間多1，則要按

8、n-1次加一按鈕才能調(diào)回正確時間。小明想，如果手表可以再添加一個按鈕，表示把當(dāng)前的數(shù)加k該多好啊他想知道，如果有了這個+k按鈕，按照最優(yōu)策略按鍵，從任意一個分鐘數(shù)調(diào)到另外任意一個分鐘數(shù)最多要按多少次。注意，按+k按鈕時，如果加k后數(shù)字超過n-1,則會對n取模。比如，n=10,k=6的時候，假設(shè)當(dāng)前時間是0，連按2次+k按鈕，則調(diào)為2。輸入格式一行兩個整數(shù)n,k，意義如題。輸出格式一行一個整數(shù)表示：按照最優(yōu)策略按鍵，從一個時間調(diào)到另一個時間最多要按多少次。樣例輸入53樣例輸出2樣例解釋如果時間正確則按0次。否則要按的次數(shù)和操作系列之間的關(guān)系如下：1：+12：+1,+13：+34：+3,+1數(shù)據(jù)范

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

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

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

12、00，m=100。資源約定：峰值內(nèi)存消耗（含虛擬機）256MCPU消耗1000ms請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入.”的多余內(nèi)容。注意：main函數(shù)需要返回0;只使用ANSIC/ANSIC+標(biāo)準(zhǔn);不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。所有依賴的函數(shù)必須明確地在源文件中#include不能通過工程設(shè)置而省略常用頭文件。提交程序時，注意選擇所期望的語言類型和編譯器類型。6.標(biāo)題：矩陣求和經(jīng)過重重筆試面試的考驗，小明成功進入Macrohard公司工作。今天小明的任務(wù)是填滿這么一張表：表有n行n列，行和列的編號都從1算起。其中第i行第j個元素的值是gcd(i,j)的平方，gcd表示最大公約數(shù)，以下是這個表的前四行的前四列：11111414119114116小明突然冒出一個奇怪的想法，他想知道這張表中所有元素的和。由于表過于龐大，他希望借助計算機的力量。輸入格式一行一個正整數(shù)n意義見題。輸出格式一行一個數(shù)，表示所有元素的和。由于答案比較大，請輸出模(109+7)(即：十億零七)后的結(jié)果。樣例輸入4樣例輸出48數(shù)據(jù)范圍對于30%的數(shù)據(jù)，n=1000存在10%的數(shù)據(jù)，n=105對于60%的數(shù)據(jù)，n=106對于1