2014年蓝桥杯(第5届)预赛本科B组C语言真题解析

2014年蓝桥杯(第5届)预赛本科 B组真题解析啤酒和饮料啤酒每罐2.3元，饮料每罐 1.9元。小明买了若干啤酒和饮料，一共花了82.3元。我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。注意：答案是一个整数。请通过浏览器提交答案。不要书写任何多余的内容(例如：写了饮料的数量，添加说明文字等)。(1)答案。11(2)编程思路。把啤酒、饮料的单价和总共花的钱都乘上10，转换为整数。然后用循环对啤酒的罐数b(1wb<823/23)和饮料的罐数 c(1Wc<823/19)进行穷举，找出满足要求的啤酒罐数 b。(3)源程序。#include<stdio.h>intmain(){intb,c;for(b=1;b<35;b++)for(c=1;c<45;c++){if((823==b*23+c*19)&&(b<c))printf("%d\n",b);}return0;}(4)用单重循环完成穷举。实际上，也可以只对啤酒的罐数进行穷举。#include<stdio.h>intmain(){intb,cSum;for(b=1;b<35;b++){cSum=823-23*b;if(cSum%19==0&&cSum/19>b)printf("%d\n",b);}return0;切面条一根高筋拉面，中间切一刀，可以得到2根面条。如果先对折 1次，中间切一刀，可以得到3根面条。如果连续对折 2次，中间切一刀，可以得到5根面条。那么，连续对折 10次，中间切一刀，会得到多少面条呢？答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。（1）答案。1025（2）编程思路。由题目可知，对折 0次切一刀得到2根，对折1次切一刀得到3根，对折2次切一刀得到5根。自己再尝试对折 3次切一刀，发现可以得到9根。设F[i]表示对折i次后中间切一刀得到的面条根数，则有F[i]=2*F[i-1]-1 （i>1）o（3）源程序。#include<stdio.h>intmain（）{intf[11]={2,3,5};for（inti=3;i<=10;i++）{f[i]=2*f[i-1]-1;}printf（"%d\n",f[10]）;return0;}李白打酒话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒 2斗。他边走边唱：无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。这一路上，他一共遇到店 5次，遇到花 10次，已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白遇到店和花的次序，可以把遇店记为 a，遇花记为b。则：babaabbabbabbbb就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。（1）答案。14(2)编程思路。采用递归的方法生成 15位二进制数的排列，对每一种排列进行判断，看是否满足要求5次、酒正好喝完、最后一次遇到的是花)，满足条件输出对应字符串即可。(3)源程序。#include<stdio.h>intcnt=0;voiddfs(int*a,intk){if(k==15){intalcohol,drinkery,i;alcohol=2;drinkery=0;for(i=0;i<15;i++)if(a[i]==0){alcohol=2*alcohol;drinkery++;}elsealcohol--;if(alcohol==0&&drinkery==5&&a[14]==1){for(i=0;i<15;i++)if(a[i]==0)printf("a");elseprintf("b");printf("\n");cnt++;}return;}a[k]=0;dfs(a,k+1);a[k]=1;dfs(a,k+1);}intmain(){inta[15];dfs(a,0);printf("Count=%d\n",cnt);return0;}(4)程序优化。上面的程序中用二进制数 0表示遇到店，1表示遇到花。实际上，可以直接定义一个字符数组chara[16],该数组白^元素a[0卜a[14]直接用字符‘a'或‘b'赋值，a[15]赋结束符’\0’。另外，通过递归产生 15位二进制数的排列，共 215=32768种情况，也就是上面的程序搜索判断了32768种情况。实际上，由于满足问题的解是遇店 5次，因此在某一搜索过程中遇店达到6次，肯定不是问题的解，无需继续进行，可以实施剪枝。为了实施剪枝，需要在递归时记录酒的斗数和遇店的次数，可以改写函数为voiddfs(char*a,intk,intalcohol,intdrinkery)，其中alcohol记录酒壶里酒的斗数，drinkery记录遇店的次数。剪枝优化后的源程序如下：#include<stdio.h>intcnt=0;voiddfs(char*a,intk,intalcohol,intdrinkery){if(k==15){if(alcohol==0&&drinkery==5&&a[14]=='b'){printf("%s\n",a);cnt++;}return;}if(drinkery<=5&&alcohol!=0)//剪枝{a[k]='a';dfs(a,k+1,2*alcohol,drinkery+1);a[k]='b';dfs(a,k+1,alcohol-1,drinkery);}}intmain(){chara[16];a[15]='\0';dfs(a,0,2,0);printf("Count=%d\n",cnt);return0;}史丰收速算史丰收速算法的革命性贡献是：从高位算起，预测进位。不需要九九表，彻底颠覆了传统手算!速算的核心基础是：1位数乘以多位数的乘法。其中，乘以7是最复杂的，就以它为例。因为，1/7是个循环小数：0.142857...，如果多位数超过 142857...，就要进 1同理，2/7,3/7,...6/7也都是类似的循环小数，多位数超过 n/7，就要进n下面的程序模拟了史丰收速算法中乘以7的运算过程。乘以7的个位规律是：偶数乘以 2，奇数乘以 2再加 5，都只取个位。乘以7的进位规律是：TOC\o"1-5"\h\z满 142857... 进 1,满 285714... 进 2,满 428571... 进 3,满 571428... 进 4,满 714285... 进 5,满 857142... 进 6请分析程序流程，填写划线部分缺少的代码。//计算个位intge_wei(inta){if(a%2==0)return(a*2)%10;elsereturn(a*2+5)%10;}//计算进位intjin_wei(char*p){char*level[]={"142857","285714","428571","571428","714285","857142"};charbuf[7];buf[6]='\0';strncpy(buf,p,6);inti;for(i=5;i>=0;i--){intr=strcmp(level[i],buf);if(r<0)returni+1;while(r==0){p+=6;strncpy(buf,p,6);r=strcmp(level[i],buf);if(r<0)returni+1; ; //填空}}return0;}//多位数乘以7voidf(char*s){inthead=jin_wei(s);if(head>0)printf("%d",head);char*p=s;while(*p){inta=(*p-'0');intx=(ge_wei(a)+jin_wei(p+1))%10;printf("%d",x);p++;}printf("\n");}intmain(){f("428571428571");f("34553834937543");return0;}注意：通过浏览器提交答案。只填写缺少的内容，不要填写任何多余的内容(例如：说明性文字)(1)参考答案。if(r>0)returni(2)解析。leve[i]就相当于满 leve[i]进i+1，因为填空所在的那段是判断条件为r==0的循环，所以是在当前buff段与某个leve相等的情况下，看下一个 buff段进位多少，那么r<0就是进位i+1，r>0就是进位i，r==0就继续看下一段 buff。打印图形小明在X星球的城堡中发现了如下图形和文字:小明开动脑筋，编写了如下的程序，实现该图形的打印。#defineN70voidf(chara口[N],intrank,introw,intcol){if(rank==1){a[row][col]='*';return;}intw=1;inti;for(i=0;i<rank-1;i++)w*=2; ;f(a,rank-1,row+w/2,col);f(a,rank-1,row+w/2,col+w);}intmain(){chara[N][N];inti,j;for(i=0;i<N;i++)for(j=0;j<N;j++)a[i][j]='';f(a,6,0,0);for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%c",a[i][j]);printf("\n");return0;}请仔细分析程序逻辑，填写缺失代码部分。通过浏览器提交答案。 注意不要填写题目中已有的代码。 也不要写任何多余内容 (比如说明性的文字)(1)参考答案。f(a,rank-1,row,col+w/2);奇怪的分式上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：1/4乘以8/5小明居然把分子拼接在一起，分母拼接在一起，答案是： 18/45(参见图l.png)老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！对于分子、分母都是 1~9中的一位数的情况，还有哪些算式可以这样计算呢？请写出所有不同算式的个数(包括题中举例的) 。显然，交换分子分母后，例如：4/1乘以5/8是满足要求的，这算做不同的算式。但对于分子分母相同的情况， 2/2乘以3/3这样的类型太多了，不在计数之列！注意：答案是个整数(考虑对称性，肯定是偶数)。请通过浏览器提交。不要书写多余的内容。(1)答案。14(2)编程思路。将分式符号化为：a/bxc/d=(10a+c)/(10b+d)对a、b、c、d在1~9之间取值穷举即可。穷举时，a!=b且c!=d。(3)源程序。#include<stdio.h>intmain(){intcnt=0;for(inta=1;a<=9;a++){for(intb=1;b<=9;b++){if(b==a)continue;for(intc=1;c<=9;c++){for(intd=1;d<=9;d++)if(d==c)continue;if(a*c*(b*10+d)==b*d*(a*10+c))cnt++;}}}}printf("%d\n",cnt);return0;}六角填数如图【l.png】所示六角形中，填入 1~12的数字。使得每条直线上的数字之和都相同。图中，已经替你填好了 3个数字，请你计算星号位置所代表的数字是多少？请通过浏览器提交答案，不要填写多余的内容。(1)答案。10(2)编程思路。定义一个数组inta[13],其中a[1卜a[12]这12个元素分别从上到下，自左向右的12个圆圈。可采用递归的方法生成由 1~12这12个数字组成的无重复数字的全排列。生成1~12不同的12个数字存储到数组中后，检测6条直线上的四个数字之和是否全相等，如果全相等，是一组解，输出并计数。(3)源程序。#include<stdio.h>inta[13];intvis[13];intcnt=0;voiddfs(intx){if(x==12){intt[6];t[0]=a[1]+a[3]+a[6]+a[8];t[1]=a[1]+a[4]+a[7]+a[11];t[2]=a[2]+a[3]+a[4]+a[5];t[3]=a[2]+a[6]+a[9]+a[12];t[4]=a[8]+a[9]+a[10]+a[11];t[5]=a[12]+a[10]+a[7]+a[5];for(inti=1;i<6;++i){if(t[i]!=t[i-1])return;}cnt++;printf("No%d\n",cnt);printf("%12d\n",a[1]);printf("%3d%6d%6d%6d\n",a[2],a[3],a[4],a[5]);printf("%6d%12d\n",a[6],a[7]);printf("%3d%6d%6d%6d\n",a[8],a[9],a[10],a[11]);printf("%12d\n\n",a[12]);return;}for(inti=1;i<13;++i){if(!vis[i]){vis[i]=1;a[x]=i;dfs(x+1);vis[i]=0;}}}intmain(){for(inti=1;i<=12;i++)vis[i]=0;vis[1]=1;a[1]=1;vis[8]=1;a[2]=8;vis[3]=1;a[12]=3;dfs(3);printf("Count=%d\n",cnt);return0;}蚂蚁感冒长100厘米的细长直杆子上有 n只蚂蚁。它们的头有的朝左，有的朝右。每只蚂蚁都只能沿着杆子向前爬，速度是 1厘米 /秒。当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。这些蚂蚁中，有1只蚂蚁感冒了。并且在和其它蚂蚁碰面时，会把感冒传染给碰到的蚂蚁。请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。【数据格式】第一行输入一个整数n（1<n<50）,表示蚂蚁的总数。接着的一行是 n个用空格分开的整数 Xi（-100<Xi<100）,Xi的绝对值，表示蚂蚁离开杆子左边端点的距离。正值表示头朝右，负值表示头朝左，数据中不会出现 0值，也不会出现两只蚂蚁占用同一位置。其中，第一个数据代表的蚂蚁感冒了。要求输出1个整数，表示最后感冒蚂蚁的数目。例如，输入：35-28程序应输出：1再例如，输入：5-108-201225程序应输出：3（1）编程思路。首先，两只蚂蚁相遇各自反向可以看作是两只蚂蚁分别穿过对方继续前进。这样处理的话就简单多了。感冒蚂蚁不管初始方向朝哪一边，它右边的蚂蚁只要向左走就可能碰撞感染（特殊情况除外），同样，它左边的蚂蚁只要朝右边走也可能被感染。假如感冒蚂蚁开始时向左行，则会感染它左边所有向右行的蚂蚁（因为相遇后它穿过对方继续向左行碰到向右行的蚂蚁感染它们）；相遇被感染的第1只蚂蚁也穿过继续向右行，感染所有它右边向左行的蚂蚁。感冒蚂蚁开始时向右行情况类似。这样，最后感冒的蚂蚁的数量为：感冒蚂蚁左边蚂蚁向右走的数量 +右边蚂蚁向左走的数量 +感冒蚂蚁本身特殊情况是，当感冒蚂蚁向左爬的时候，如果感冒蚂蚁左边没有向右爬行的蚂蚁，那么不管感冒蚂蚁右边有多少向左爬行的，因爬行的速度相同感冒蚂蚁不会遇到向右爬的蚂蚁进行感染，因此右边的蚂蚁也永远不可能被感染。同样的，当感冒蚂蚁向右爬的时候，如果感冒蚂蚁右边没有向左爬行的蚂蚁，那么同样感冒蚂蚁左边的蚂蚁也永远不可能被感染。(2)源程序。#include<stdio.h>intabs(intx){returnx>=0?x:-x;}intmain(){intant[51];intn,i;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&ant[i]);intleft=0,right=0;for(i=1;i<n;i++){if(ant[i]<0&&abs(ant[i])>abs(ant[0]))left++; //感冒蚂蚁右边且向左走的if(ant[i]>0&&abs(ant[i])<abs(ant[0]))right++; //感冒蚂蚁左边且向右走的}if((ant[0]<0&&right==0)||(ant[0]>0&&left==0))printf("1\n");elseprintf("%d\n",left+right+1);return0;}地宫取宝X国王有一个地宫宝库。是 nxm个格子的矩阵。每个格子放一件宝贝。每个宝贝贴着价值标签。地宫的入口在左上角，出口在右下角。小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它(当然，也可以不拿)。当小明走到出口时，如果他手中的宝贝恰好是 k件，则这些宝贝就可以送给小明。请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这k件宝贝。【数据格式】输入一行3个整数，用空格分开：nmk(1<=n,m<=50,1<=k<=12)接下来有n行数据，每行有 m个整数Ci（0<=Ci<=12）代表这个格子上的宝物的价值要求输出一个整数，表示正好取k个宝贝的行动方案数。该数字可能很大，输出它对1000000007取模的结果。例如，输入：2221221程序应该输出：2再例如，输入：232123215程序应该输出：14（1）编程思路。采用记忆化搜索完成。定义4维数组dp[51][51][15][15]。设dp[x][y][num][val]表示在坐标 （x,y）时拿了num件宝贝并且宝贝中价值最大的为val,其中IWxWn,iwywm,num的初值为0,表示还没有拿到宝贝，val的初值本来应该为-1，表示此时手上还没有宝物（因为从题目数据说明中可以TOC\o"1-5"\h\z看出宝贝的价值可以为0），为了让val初始值为0，可以将输入的宝贝的价值统一加 1，这样宝贝的最小价值为1（不是 0）。定义二维数组intmap[51][51]保存地宫各格子的宝贝价值。采用倒推法列出状态转移方程，即把后面的情况种数不断的往前更新。当map[x][y]>val时，dp[x][y][num][val]=dp[x+1][y][num+1][map[x][y]]+dp[x][y+1][num+1][map[x][y]]+dp[x+1][y][num][val]+dp[x][y+1][num][val] ；当map[x][y]<=val时，dp[x][y][num][val]=dp[x+1][y][num][val]+dp[x][y+1][num][val]。在通过DFS搜索方式求数组dp的各元素值时，由于数组元素值dp[x][y][num][val]跟位置（x,y）、宝贝个数以及当前最大的宝贝价值有关，当重复遍历这个结点时，若dp[x][y][num][val]的值已经计算出来了，则直接应用无需重复递归计算。为此，定义数组dp的全部元素的初始值为-1。若计算时需要用到dp[x][y][num][val]，此时dp[x][y][num][val]！=-1，则无需重复调用，直接应用计算好的dp[x][y][num][val]元素值。之所以初值定义为-1，是考虑到若路径不存在的情况（此时方案数应为0）。（2）源程序。#include<stdio.h>#include<string.h>#defineMOD1000000007longlongdp[51][51][15][15];intmap[51][51];intn,m,k;voiddfs（intx,inty,intnum,intval）{if(dp[x][y][num][val]!= -1)return;dp[x][y][num][val]=0;if(x==n&&y==m&&num==k){dp[x][y][num][val]=1;return;}if(map[x][y]>val&&num<k){dfs(x,y,num+1,map[x][y]);dp[x][y][num][val]+=dp[x][y][num+1][map[x][y]];dp[x][y][num][val]%=MOD;}if(x<n)//向下走{dfs(x+1,y,num,val);dp[x][y][num][val]+=dp[x+1][y][num][val];dp[x][y][num][val]%=MOD;}if(y<m)//向右走{dfs(x,y+1,num,val);dp[x][y][num][val]+=dp[x][y+1][num][val];dp[x][y][num][val]%=MOD;}}intmain(){scanf("%d%d%d",&n,&m,&k);for(inti=1;i<=n;i++){for(intj=1;j<=m;j++){scanf("%d",&map[i][j]);map[i][j]++;}}memset(dp,-1,sizeof(dp));dfs(1,1,0,0);printf("%d\n",dp[1][1][0][0]);return0;

小朋友排队n个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是 0。如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加（2即不高兴程度为 3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加 k。请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。【数据格式】输入的第一行包含一个整数n,表示小朋友的个数。第二行包含n个整数H1H2…Hn,分别表示每个小朋友的身高。输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。例如，输入：3321程序应该输出：9【样例说明】首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和13，总和为9。【数据规模与约定】对于对于对于对于对于对于对于对于（1）。10%的数据，30%的数据，50%的数据，100%的数据，编程思路。1<=n<=1000；1<=n<=10000；1<=n<=100000，0<=Hi<=1000000。本题的实质是求一组数据中逆序数对的个数。比如题目中的3，2，1，和3有关的逆序对为（3，2）和（3，1），和2有关的逆序对为（3，2）和（2，1），和1有关的逆序对为（3，1）和（2，1），为了完成排序，任何一个逆序对的两个元素都必须交换一次，于是可知，每个小朋友都完成了两次交换。要求一个数组元素有关的逆序对个数，就是求它之前有几个大于它的元素（设为b1），之后有几个小于它的元素（设为b2），这样每个元素的交换次数为b1+b2。根据数据规模与约定，若采用二重循环进行暴力搜索逆序对的个数，肯定会超时的。因此，采用树状数组来解决本题。树状数组实际上是由两部分组成：数据数组（设为num）和统计数组（设为C）。我们以数据数组num[3]={3,2,1}为例进行描述。树状数组的各元素初始值为 0，但由于树状数组元素下标是从 1开始的，因此将数据数组的每个元素值加 1，然后作为树状数组的下标，将数值 1存到相应的位置。从左到右依次扫描数据数组。C为：C[6] C[7] C[8]0 0 0TOC\o"1-5"\h\z1）读入 3，此时读入的数据个数为 1C为：C[6] C[7] C[8]0 0 0C[1] C[2] C[3] C[4] C[5]0 0 0 1 0可以看到sum(C[1],C[4])=1，这是小于等于 3的数字的个数，也就是说当输入第一个数3的时候没有比它小的数字存在。这时“输入数值个数 -sum(C[1],C[4])=1-1=0”，也就是说大于3的数字的个数为0，保存起来，即b[0]=0。(在这里特别注意，根据树状数组sum(C[1],C[n])算出来的数值是某个数字 n左边比它小的数字的个数。)TOC\o"1-5"\h\z2)读入 2，此时读入的数据个数为 2，树状数组 C为：C[1] C[2] C[3] C[4] C[5] C[6] C[7] C[8]……0 0 1 1 0 0 0 0可以看到sum(C[1],C[3])=1，仍然不存在比它小的数，而此时输入的数据个数为 2，2-1=1，就是说，存在一个数在 2之前并且大于 2(这个数是第 1个数3)，保存b[1]=1。3)读入1，此时读入的数据个数为 3，树状数组 C为：C[1] C[2] C[3] C[4] C[5] C[6] C[7] C[8]……0 1 1 1 0 0 0 0可以看到sum(C[1],C[2])=1，仍然不存在比它小的数，而此时输入的数据个数为 3，3-1=2，就是说，存在两个数在 1之前并且大于 1(这两个数就是 3和2