第七届蓝桥杯省赛B组试题.doc

（1）煤球数目有一堆煤球，堆成三角棱锥形。具体：第一层放1个，第二层3个（排列成三角形），第三层6个（排列成三角形），第四层10个（排列成三角形），.如果一共有100层，共有多少个煤球？题解：纯粹的数学题而已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，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了236根蜡烛。请问，他从多少岁开始过生日party的？请填写他开始过生日party的年龄数。题解：暴力枚举。第一重循环枚举刚开始过生日时候的岁数。第二重循环是枚举现在的岁数第三重循环就是将刚开始过生日的岁数和现在的岁数加起来。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) printf(start : %d end : %dn,start,end); （3） B DEFA + + = 10 C GHI（如果显示有问题，可以参见【图1.jpg】）这个算式中AI代表19的数字，不同的字母代表不同的数字。比如：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 visit10,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 /coutb a num1 num2 num3endl; if(num1*num3*b+num2*b+num3*a=10*num3*b) 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); coutsum; return 0;（4）快速排序排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。其思想是：先选一个“标尺”，用它把整个队列过一遍筛子，以保证：其左边的元素都不大于它，其右边的元素都不小于它。这样，排序问题就被分割为两个子区间。再分别对子区间排序就可以了。这样，排序问题就被分割为两个子区间。再分别对子区间排序就可以了。下面的代码是一种实现，请分析并填写划线部分缺少的代码。#include 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(ir & a+ix);/一样的，一直左移直到小于x时if(i=j) break;/如果一直移动到了相交的区间，说明这个区间内都是由小到大的，就直接退拉！不用交换啦！swap(a,i,j);/有的话呢，就交换，这样保证了左小右大。_;return j;void quicksort(int a, int p, int r)if(pr)int q = partition(a,p,r);quicksort(a,p,q-1);quicksort(a,q+1,r);int main()int i;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; iN; i+) printf(%d , ai);printf(n);return 0;题解：快速排序。这里是单步快排。就是将一堆数按照某个数作为基准数分成左右两堆swap(a,p,j)，因为这时候的j是已经不大于了x的，p这个位置要放该区间的最小值，j满足，换过去。（5）抽签X星球要派出一个5人组成的观察团前往W星。其中：A国最多可以派出4人。B国最多可以派出2人。C国最多可以派出2人。.那么最终派往W星的观察团会有多少种国别的不同组合呢？下面的程序解决了这个问题。数组a 中既是每个国家可以派出的最多的名额。程序执行结果为：DEFFFCEFFFCDFFFCDEFFCCFFFCCEFFCCDFFCCDEFBEFFFBDFFFBDEFFBCFFFBCEFFBCDFFBCDEF.(以下省略，总共101行)#include #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(%sn,b);return;for(i=0; i=ak; i+)for(j=0; ji; 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;仔细阅读代码，填写划线部分缺少的内容。注意：不要填写任何已有内容或说明性文字。题解：这个题目是这样的，对于f(int a,int k,int m,char b)。a 是每个国家的最多指派人数,k表示当前是哪个国家,m表示还需要派送几个人(可以为负数).b表示已经派送的人的字符串。所以这个题目在递归中间的的 第一个循环表示从0ai中让i国选择指派人数，内循环只是向b记录的过程。所以答案是f(a,k+1,m-i,b). 因为这里i = j .应该 f(a,k+1,m-j,b)也可以。（6）方格填数如下的10个格子（如果显示有问题，也可以参看【图1.jpg】）填入09的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。题解:1580深搜+回溯，填完之后在判断是否可以。#include#includeintflag34;/表示哪些可以填数intmpt34;/填数boolvisit10;intans=0;voidinit()/初始化inti,j;for(i=0;i3;i+)for(j=0;j4;j+)flagij=1;flag00=0;flag23=0;voidSolve()intdir82=0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1;intbook=true;for(inti=0;i3;i+)for(intj=0;j4;j+)/判断每个数周围是否满足if(flagij=0)continue;for(intk=0;k8;k+)intx,y;x=i+dirk0;y=j+dirk1;if(x=3|y=4|flagxy=0)continue;if(abs(mptxy-mptij)=1)book=false;if(book)ans+;voiddfs(intindex)intx,y;x=index/4;y=index%4;if(x=3)Solve();return;if(flagxy)for(inti=0;i10;i+)if(!visiti)visiti=true;mptxy=i;dfs(index+1);visiti=false;elsedfs(index+1);intmain()init();dfs(0);printf(%dn,ans);return0;（7）剪邮票如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.jpg】，【图3.jpg】中，粉红色所示部分就是合格的剪取。请你计算，一共有多少种不同的剪取方法。请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。题解:这个题目跟上一道题目类似，看来这一届的深搜很火啊。跟上面一样的套路。#include#includeintmpt34;intmpt_visit34;intnum6;inthave13;intvisit13;intans=0;intCount=0;voidinit()intk=1;for(inti=0;i3;i+)for(intj=0;j4;j+)mptij=k;k+;intdir42=0,1,0,-1,-1,0,1,0;/判断五个数是否能连在一起voiddfs_find(intx,inty)for(inti=0;i4;i+)inttx,ty;tx=x+diri0;ty=y+diri1;if(tx=3|ty=4)continue;if(havempttxty=0|mpt_visittxty)continue;mpt_visittxty=1;Count+;dfs_find(tx,ty);voidSolve()inti;memset(have,0,sizeof(have);memset(mpt_visit,0,sizeof(mpt_visit);for(i=1;i6;i+)havenumi=1;for(i=0;i12;i+)intx,y;x=i/4;y=i%4;if(havemptxy)Count=1;mpt_visitxy=1;dfs_find(x,y);break;if(Count=5)ans+;/创建5个数的组合voiddfs_creat(intindex)if(index=6)Solve();return;for(inti=numindex-1+1;i13;i+)if(!visiti)visiti=true;numindex=i;dfs_creat(index+1);visiti=false;intmain()init();dfs_creat(1);printf(%dn,ans);return0;（8）四平方和四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去，就正好可以表示为4个数的平方和。比如：5 = 02 + 02 + 12 + 227 = 12 + 12 + 12 + 22（符号表示乘方的意思）对于一个给定的正整数，可能存在多种平方和的表示法。要求你对4个数排序：0 = a = b = c = d并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法程序输入为一个正整数N (N5000000)要求输出4个非负整数，按从小到大排序，中间用空格分开例如，输入：5则程序应该输出：0 0 1 2再例如，输入：12则程序应该输出：0 2 2 2再例如，输入：773535则程序应该输出：1 1 267 838资源约定：峰值内存消耗 256MCPU消耗 3000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入.” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C+ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include ， 不能通过工程设置而省略题解：一道水题。水的不能在水。从样例就可以看出来它找的顺序了。直接对你输入的数字开根号，然后一个一个往下缩，直到下一个数要大于第一个数就停。然后对剩下的开根号，一直开完就好了，另外一个快速的方法。用网上的。先把两个平方数能相加的到的数字球出来然后记录。这样我们第三层循环就可以先判断再循环了。intmpt5000010=0;/mpti=1表示i能够用两个完全平方数相加而得。intn;voidinit()for(inti=0;i*i=n;i+)for(intj=0;j*j=n;j+)if(i*i+j*j=n)mpti*i+j*j=1;intmain()intflag=false;scanf(%d,&n);init();for(inti=0;i*i=n;i+)for(intj=0;j*j=n;j+)if(mptn-i*i-j*j=0)continue;/如果剩下的差用两个完全平方数不能组合出来就不继续for(intk=0;k*k=n;k+)inttemp=n-i*i-j*j-k*k;doublel=sqrt(double)temp);if(l=(int)l)printf(%d%d%d%dn,i,j,k,(int)l);flag=true;break;if(flag)break;if(flag)break;return0;（9）交换瓶子有N个瓶子，编号 1 N，放在架子上。比如有5个瓶子：2 1 3 5 4要求每次拿起2个瓶子，交换它们的位置。经过若干次后，使得