第七屆藍(lán)橋杯省賽B組試題

1、（1）煤球數(shù)目有一堆煤球，堆成三角棱錐形。具體：第一層放1個，第二層3個（排列成三角形），第三層6個（排列成三角形），第四層10個（排列成三角形），.如果一共有100層，共有多少個煤球？題解：純粹的數(shù)學(xué)題而已int a101 =0; for(int i = 1 ; i < 101 ; i +) ai = ai-1 + i; int ans = 0; for(int j = 1 ; j < 101 ; j +) ans += aj; printf("%dn",ans); （2）生日蠟燭某君從某年開始每年都舉辦一次生日party，并且每次都要吹熄與年齡相同根數(shù)的蠟燭

2、。現(xiàn)在算起來，他一共吹熄了236根蠟燭。請問，他從多少歲開始過生日party的？請?zhí)顚懰_始過生日party的年齡數(shù)。題解：暴力枚舉。第一重循環(huán)枚舉剛開始過生日時候的歲數(shù)。第二重循環(huán)是枚舉現(xiàn)在的歲數(shù)第三重循環(huán)就是將剛開始過生日的歲數(shù)和現(xiàn)在的歲數(shù)加起來。int start,end; for(start = 1 ; start < 236 ; start +) for( end = start ; end < 236 ; end + ) int sum = 0; for(int i = start; i <= end; i +) sum += i; if( sum = 236)

3、printf("start : %d end : %dn",start,end); （3） B DEFA + + = 10 C GHI（如果顯示有問題，可以參見【圖1.jpg】）這個算式中AI代表19的數(shù)字，不同的字母代表不同的數(shù)字。比如：6+8/3+952/714 就是一種解法，5+3/1+972/486 是另一種解法。這個算式一共有多少種解法？/29題解：DFS+回溯由于計算機中5/2會等于2，而且如果打算采用精度方面的處理的話，會很麻煩，而且很容易錯。所以，把這些式子全部變成乘法形式就好了。A*C*GHI+B*GHI+DEF*C=10*C*GHI代碼:int visi

4、t10,num10;int sum=0;void dfs(int n) if(n=10) int b=num7*100+num8*10+num9; /GHI int a=num4*100+num5*10+num6; /DEF /cout<<b<<' '<<a<<' '<<num1<<' '<<num2<<' '<<num3<<endl; if(num1*num3*b+num2*b+num3*a=10*num3*b

5、) sum+; /cout<<"*"<<endl; return ; for(int i=1;i<=9;+i) if(!visiti) visiti=1; numn=i; dfs(n+1); visiti=0; numn=0; int main() memset(num,0,sizeof(num); memset(visit,0,sizeof(visit); dfs(1); cout<<sum; return 0;（4）快速排序排序在各種場合經(jīng)常被用到?？焖倥判蚴鞘殖Ｓ玫母咝实乃惴?。其思想是：先選一個“標(biāo)尺”，用它把整個隊列過一

6、遍篩子，以保證：其左邊的元素都不大于它，其右邊的元素都不小于它。這樣，排序問題就被分割為兩個子區(qū)間。再分別對子區(qū)間排序就可以了。這樣，排序問題就被分割為兩個子區(qū)間。再分別對子區(qū)間排序就可以了。下面的代碼是一種實現(xiàn)，請分析并填寫劃線部分缺少的代碼。#include <stdio.h>void swap(int a, int i, int j)int t = ai;ai = aj;aj = t;int partition(int a, int p, int r)int i = p;int j = r + 1;int x = ap;while(1)while(i<r &&a

7、mp; a+i<x);/由于要按照從小到大排序，就i一直向右移動直到大于x值位置while(a-j>x);/一樣的，一直左移直到小于x時if(i>=j) break;/如果一直移動到了相交的區(qū)間，說明這個區(qū)間內(nèi)都是由小到大的，就直接退拉！不用交換啦！swap(a,i,j);/有的話呢，就交換，這樣保證了左小右大。_;return j;void quicksort(int a, int p, int r)if(p<r)int q = partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);int main()int i

8、;int a = 5,13,6,24,2,8,19,27,6,12,1,17;int N = 12;quicksort(a, 0, N-1);for(i=0; i<N; i+) printf("%d ", ai);printf("n");return 0;題解：快速排序。這里是單步快排。就是將一堆數(shù)按照某個數(shù)作為基準(zhǔn)數(shù)分成左右兩堆swap(a,p,j)，因為這時候的j是已經(jīng)不大于了x的，p這個位置要放該區(qū)間的最小值，j滿足，換過去。（5）抽簽X星球要派出一個5人組成的觀察團前往W星。其中：A國最多可以派出4人。B國最多可以派出2人。C國最多可以派出

9、2人。.那么最終派往W星的觀察團會有多少種國別的不同組合呢？下面的程序解決了這個問題。數(shù)組a 中既是每個國家可以派出的最多的名額。程序執(zhí)行結(jié)果為：DEFFFCEFFFCDFFFCDEFFCCFFFCCEFFCCDFFCCDEFBEFFFBDFFFBDEFFBCFFFBCEFFBCDFFBCDEF.(以下省略，總共101行)#include <stdio.h>#define N 6#define M 5#define BUF 1024void f(int a, int k, int m, char b)int i,j;if(k=N) bM = 0;if(m=0) printf(&qu

10、ot;%sn",b);return;for(i=0; i<=ak; i+)for(j=0; j<i; j+) bM-m+j = k+'A'_; /填空位置int main()int aN = 4,2,2,1,1,3;char bBUF;f(a,0,M,b);return 0;仔細(xì)閱讀代碼，填寫劃線部分缺少的內(nèi)容。注意：不要填寫任何已有內(nèi)容或說明性文字。題解：這個題目是這樣的，對于f(int a,int k,int m,char b)。a 是每個國家的最多指派人數(shù),k表示當(dāng)前是哪個國家,m表示還需要派送幾個人(可以為負(fù)數(shù)).b表示已經(jīng)派送的人的字符串。所以這

11、個題目在遞歸中間的的 第一個循環(huán)表示從0ai中讓i國選擇指派人數(shù)，內(nèi)循環(huán)只是向b記錄的過程。所以答案是f(a,k+1,m-i,b). 因為這里i = j .應(yīng)該 f(a,k+1,m-j,b)也可以。（6）方格填數(shù)如下的10個格子（如果顯示有問題，也可以參看【圖1.jpg】）填入09的數(shù)字。要求：連續(xù)的兩個數(shù)字不能相鄰。（左右、上下、對角都算相鄰）一共有多少種可能的填數(shù)方案？請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。注意：你提交的應(yīng)該是一個整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。題解:1580深搜+回溯，填完之后在判斷是否可以。#include <stdio.h>  

12、#include <math.h>  int flag34; /表示哪些可以填數(shù)  int mpt34; /填數(shù)  bool visit10;  int ans = 0;  void init()   /初始化        int i,j;  &

13、#160;   for(i = 0  i < 3  i +)          for(j = 0  j < 4  j +)             

14、; flagij = 1;      flag00 = 0;      flag23 = 0;      void Solve()        int dir82 =  0,1,0,-1,1,0,-1,0,1,1,1,

15、-1,-1,1,-1,-1;      int book = true;      for(int i = 0  i < 3  i +)                for(int&

16、#160;j = 0  j < 4; j +)                        /判斷每個數(shù)周圍是否滿足             

17、 if(flagij = 0)continue;              for( int k = 0  k < 8  k +)               &#

18、160;                int x,y;                  x = i + dirk0;       

19、60;          y = j + dirk1;                  if(x < 0 | x >= 3 | y < 0 |

20、0;y >= 4 | flagxy = 0) continue;                  if(abs(mptxy - mptij) = 1)  book = false;       

21、;                             if(book) ans +;        void dfs(int index)    

22、;    int x,y;      x = index / 4;      y = index % 4;      if( x = 3)          &

23、#160;     Solve();          return;            if(flagxy)                for(int 

24、;i = 0  i < 10  i +)                        if(!visiti)             

25、;                   visiti = true;                  mptxy = i;     

26、60;            dfs(index+1);                  visiti = false;             &

27、#160;                      else                dfs(index+1);        &#

28、160; int main()        init();      dfs(0);      printf("%dn",ans);      return 0;    （7）剪郵票如【圖1.jpg】, 有12張連在一起的12生肖的郵票?，F(xiàn)在你要從

29、中剪下5張來，要求必須是連著的。（僅僅連接一個角不算相連）比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。請你計算，一共有多少種不同的剪取方法。請?zhí)顚懕硎痉桨笖?shù)目的整數(shù)。注意：你提交的應(yīng)該是一個整數(shù)，不要填寫任何多余的內(nèi)容或說明性文字。題解:這個題目跟上一道題目類似，看來這一屆的深搜很火啊。跟上面一樣的套路。#include <stdio.h>  #include <string.h>  int mpt34;  int mpt_visit34;&

30、#160; int num6;   int have13;  int visit13;  int ans = 0;  int Count = 0;    void init()        int k = 1;   &

31、#160;  for(int i = 0  i < 3  i +)          for(int j = 0  j < 4  j +)           

32、;             mptij = k;              k +;              int dir42 =

33、60;0,1,0,-1,-1,0,1,0;  /判斷五個數(shù)是否能連在一起  void dfs_find(int x,int y)        for(int i = 0  i < 4  i+)             &#

34、160;  int tx,ty;          tx = x + diri0;          ty = y + diri1;          if(tx <

35、0;0 | tx >= 3 | ty < 0 | ty >= 4) continue;          if(havempttxty = 0 | mpt_visittxty)continue;          

36、;mpt_visittxty = 1;          Count +;          dfs_find(tx,ty);            void Solve()     

37、60;  int i;      memset(have,0,sizeof(have);      memset(mpt_visit,0,sizeof(mpt_visit);      for(i = 1; i < 6  i +) havenumi = 1; &#

38、160;    for(i = 0  i < 12  i +)                int x,y;          x = i / 4;&#

39、160;         y = i % 4;          if(havemptxy)                       &

40、#160;Count = 1;              mpt_visitxy =1;              dfs_find(x,y);            &

41、#160; break;                      if(Count = 5)                ans +;   

42、60;        /創(chuàng)建5個數(shù)的組合  void dfs_creat(int index)        if(index = 6)                Solve();   

43、       return;            for(int i = numindex-1 + 1; i < 13  i +)             

44、60;  if(!visiti)                        visiti = true;              numindex = i

45、;              dfs_creat(index+1);              visiti = false;              

46、60;       int main()        init();      dfs_creat(1);      printf("%dn",ans);      return 0;   

47、0;（8）四平方和四平方和定理，又稱為拉格朗日定理：每個正整數(shù)都可以表示為至多4個正整數(shù)的平方和。如果把0包括進(jìn)去，就正好可以表示為4個數(shù)的平方和。比如：5 = 02 + 02 + 12 + 227 = 12 + 12 + 12 + 22（符號表示乘方的意思）對于一個給定的正整數(shù)，可能存在多種平方和的表示法。要求你對4個數(shù)排序：0 <= a <= b <= c <= d并對所有的可能表示法按 a,b,c,d 為聯(lián)合主鍵升序排列，最后輸出第一個表示法程序輸入為一個正整數(shù)N (N<5000000)要求輸出4個非負(fù)整數(shù)，按從小到大排序，中間用空格分開例如，輸入：5則程序

48、應(yīng)該輸出：0 0 1 2再例如，輸入：12則程序應(yīng)該輸出：0 2 2 2再例如，輸入：773535則程序應(yīng)該輸出：1 1 267 838資源約定：峰值內(nèi)存消耗 < 256MCPU消耗 < 3000ms請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入.” 的多余內(nèi)容。所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。注意: main函數(shù)需要返回0注意: 只使用ANSI C/ANSI C+ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。注意: 所有依賴的函數(shù)必須明確地在源文件中 #include <xxx>， 不能通過工程設(shè)置而省略題解：一道水題。水的不能在水

49、。從樣例就可以看出來它找的順序了。直接對你輸入的數(shù)字開根號，然后一個一個往下縮，直到下一個數(shù)要大于第一個數(shù)就停。然后對剩下的開根號，一直開完就好了，另外一個快速的方法。用網(wǎng)上的。先把兩個平方數(shù)能相加的到的數(shù)字球出來然后記錄。這樣我們第三層循環(huán)就可以先判斷再循環(huán)了。int mpt5000010 =0;  /mpti = 1表示i 能夠用兩個完全平方數(shù)相加而得。  int n;  void init()     

50、0;  for(int i = 0  i*i <= n  i +)          for(int j = 0  j*j <=n  j +)           &#

51、160;  if(i*i+j*j <= n) mpti*i+j*j = 1;    int main()              int flag = false;      scanf("%d",&n);

52、0;     init();      for(int i = 0  i * i <= n  i +)                for(int j = 0 &

53、#160;j * j <= n  j +)              if(mptn - i*i - j*j = 0) continue;   /如果剩下的差用兩個完全平方數(shù)不能組合出來就不繼續(xù)       

54、60;      for(int k = 0  k * k <= n  k +)                            

55、;    int temp = n - i*i - j*j - k*k;                  double l = sqrt(double) temp);                  if(l = (int)l )       &