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

1、2014 年蓝桥杯(第 5 届)预赛本科 B 组真题解析啤酒和饮料啤酒每罐 2.3 元，饮料每罐 1.9 元。小明买了若干啤酒和饮料，一共花了 82.3 元。 我们还知道他买的啤酒比饮料的数量少，请你计算他买了几罐啤酒。 注意：答案是一个整数。请通过浏览器提交答案。不要书写任何多余的内容(例如：写了饮料的数量，添加说明文字等) 。(1) 答案。11( 2)编程思路。把啤酒、饮料的单价和总共花的钱都乘上10，转换为整数。然后用循环对啤酒的罐数b(1b<823/23)和饮料的罐数 c(1c<823/19 )进行穷举，找出满足要求的啤酒罐数b。(3)源程序。#include <st

2、dio.h>int main()int b,c;for (b=1;b<35;b+)for (c=1;c<45;c+)if(823=b*23+c*19) &&(b<c)printf("%dn",b);return 0;(4)用单重循环完成穷举。 实际上，也可以只对啤酒的罐数进行穷举。#include <stdio.h>int main()int b,cSum;for (b=1;b<35;b+)cSum=823-23*b;if (cSum%19=0 && cSum/19>b)printf("

3、;%dn",b); return 0;切面条一根高筋拉面，中间切一刀，可以得到2 根面条。如果先对折 1 次，中间切一刀，可以得到 3 根面条。 如果连续对折 2 次，中间切一刀，可以得到 5 根面条。 那么，连续对折 10 次，中间切一刀，会得到多少面条呢？ 答案是个整数，请通过浏览器提交答案。不要填写任何多余的内容。（1）答案。1025（ 2）编程思路。由题目可知，对折 0 次切一刀得到 2 根，对折 1 次切一刀得到 3 根，对折 2 次切一刀 得到 5 根。自己再尝试对折 3 次切一刀，发现可以得到 9 根。设 Fi 表示对折 i 次后中间切一刀得到的面条根数，则有 Fi=2

4、*Fi -1-1（ i1）。（3）源程序。#include <stdio.h>int main（）int f11=2,3,5;for （int i=3;i<=10;i+） fi=2*fi -1-1; printf（"%dn",f10）; return 0;李白打酒话说大诗人李白，一生好饮。幸好他从不开车。 一天，他提着酒壶，从家里出来，酒壶中有酒2 斗。他边走边唱：无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。这一路上，他一共遇到店 5次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒 喝光了。请你计算李白遇到店和花的次序， 可以把遇店记为 a，遇

5、花记为 b。则：babaabbabbabbbb 就是合理的次序。 像这样的答案一共有多少呢？请你计算出所有可能方案的个数 （包含题目 给出的）。注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。 （1）答案。14( 2)编程思路。采用递归的方法生成 15 位二进制数的排列，对每一种排列进行判断，看是否满足要求 遇到店 5 次、酒正好喝完、最后一次遇到的是花) ，满足条件输出对应字符串即可。(3)源程序。#include <stdio.h>int cnt=0;void dfs(int *a,int k)if (k=15)int alcohol,drinkery,i;al

6、cohol=2; drinkery=0;for (i=0;i<15;i+)if (ai=0) alcohol=2*alcohol; drinkery+;elsealcohol - ;if (alcohol=0 && drinkery=5 && a14=1)for (i=0;i<15;i+)if (ai=0) printf("a");else printf("b");printf("n");cnt+;return;ak=0;dfs(a,k+1);ak=1;dfs(a,k+1);int main

7、()int a15;dfs(a,0);printf("Count=%dn",cnt);return 0;( 4)程序优化。上面的程序中用二进制数 0表示遇到店， 1 表示遇到花。实际上，可以直接定义一个字 符数组 char a16 ，该数组的元素 a0a14 直接用字符' a'或'b' 赋值， a15赋结束符' 0'。另外，通过递归产生 15 位二进制数的排列，共 215=32768 种情况，也就是上面的程序 搜索判断了 32768 种情况。实际上， 由于满足问题的解是遇店 5次，因此在某一搜索过程中 遇店达到 6 次，肯定不

8、是问题的解，无需继续进行，可以实施剪枝。为了实施剪枝，需要在递归时记录酒的斗数和遇店的次数，可以改写函数为void dfs(char *a,int k,int alcohol,int drinkery) ，其中 alcohol 记录酒壶里酒的斗数， drinkery 记录遇店的次数。剪枝优化后的源程序如下：#include <stdio.h>int cnt=0;void dfs(char *a,int k,int alcohol,int drinkery)if (k=15)if (alcohol=0 && drinkery=5 && a14='

9、;b')printf("%sn",a);cnt+;return;if (drinkery<=5 && alcohol!=0)/ 剪枝ak='a' dfs(a,k+1,2*alcohol,drinkery+1); ak='b'dfs(a,k+1,alcohol -1,drinkery);int main()char a16;a15='0'dfs(a,0,2,0);printf("Count=%dn",cnt);return 0;史丰收速算史丰收速算法的革命性贡献是： 从高位算起，

10、 预测进位。 不需要九九表，彻底颠覆了传统手算 !速算的核心基础是： 1 位数乘以多位数的乘法。 其中，乘以 7 是最复杂的，就以它为例。142857.，就要进 1n/7 ，就要进 n都只取个位。因为， 1/7 是个循环小数： 0.142857.，如果多位数超过 同理， 2/7, 3/7, . 6/7 也都是类似的循环小数，多位数超过 下面的程序模拟了史丰收速算法中乘以 7 的运算过程。 乘以 7 的个位规律是：偶数乘以 2，奇数乘以 2 再加 5 乘以 7 的进位规律是： 满 142857. 进 1, 满 285714. 进 2, 满 428571. 进 3, 满 571428. 进 4,

11、满 714285. 进 5, 满 857142. 进 6 请分析程序流程，填写划线部分缺少的代码。/计算个位int ge_wei(int a)if(a % 2 = 0)return (a * 2) % 10;elsereturn (a * 2 + 5) % 10;/计算进位int jin_wei(char* p)char* level = "142857", "285714", "428571", "571428", "714285", "857142"char buf7;

12、buf6 = '0' strncpy(buf,p,6);int i;for(i=5; i>=0; i -)int r = strcmp(leveli, buf); if(r<0) return i+1; while(r=0)p += 6; strncpy(buf,p,6); r = strcmp(leveli, buf); if(r<0) return i+1; ; / 填空 return 0;/多位数乘以 7void f(char* s)int head = jin_wei(s);if(head > 0) printf("%d",

13、head);char* p = s;while(*p)int a = (*p -'0');int x = (ge_wei(a) + jin_wei(p+1) % 10;printf("%d",x);p+;printf("n");int main()f("428571428571"); f("34553834937543"); return 0; 注意：通过浏览器提交答案。只填写缺少的内容，不要填写任何多余的内容(例如：说 明性文字)(1)参考答案。if(r>0) return i(2) 解析。

14、levei 就相当于满 levei 进 i+1 ，因为填空所在的那段是判断条件为r=0 的循环，所以是在当前 buff 段与某个 leve 相等的情况下，看下一个 buff 段进位多少，那么 r<0 就是进位 i+1 ， r>0 就是进位 i，r=0 就继续看下一段 buff 。打印图形小明在 X 星球的城堡中发现了如下图形和文字：小明开动脑筋，编写了如下的程序，实现该图形的打印。#define N 70void f(char aN, int rank, int row, int col) if(rank=1) arowcol = '*'return;int w =

15、 1;int i;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);int main()char aNN; int i,j;for(i=0;i<N;i+) for(j=0;j<N;j+) aij = ' 'f(a,6,0,0);for(i=0; i<N; i+)for(j=0; j<N; j+) printf("%c",aij); printf("n");return 0; 请仔细

16、分析程序逻辑，填写缺失代码部分。通过浏览器提交答案。 注意不要填写题目中已有的代码。 也不要写任何多余内容 （比如 说明性的文字）（1）参考答案。f（a, rank- 1, row, col+w/2）;奇怪的分式上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：1/4 乘以 8/5小明居然把分子拼接在一起，分母拼接在一起，答案是： 18/45 （参见图 1.png）老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！ 对于分子、分母都是 19 中的一位数的情况，还有哪些算式可以这样计算呢？ 请写出所有不同算式的个数（包括题中举例的） 。显然，交换分子分母后，例如： 4/1 乘以

17、5/8 是满足要求的，这算做不同的算式。 但对于分子分母相同的情况， 2/2 乘以 3/3 这样的类型太多了，不在计数之列 ! 注意：答案是个整数（考虑对称性，肯定是偶数） 。请通过浏览器提交。不要书写多余的内 容。（1）答案。14（ 2）编程思路。将分式符号化为： a/b × c/d = （10a+c）/（10b+d。） 对 a、b、c、d 在 19 之间取值穷举即可。 穷举时， a!=b 且 c!=d 。（3）源程序。#include <stdio.h>int main（）int cnt=0;for（int a=1;a<=9;a+）for（int b=1;b&l

18、t;=9;b+）if（b=a） continue; for（int c=1;c<=9;c+） for(int d=1;d<=9;d+)if(d=c) continue;if(a*c*(b*10+d)=b*d*(a*10+c) cnt+;printf("%dn",cnt);return 0;六角填数如图【 1.png 】所示六角形中，填入 112 的数字。使得每条直线上的数字之和都相同。图中，已经替你填好了 3 个数字，请你计算星号位置所代表的数字是多少？ 请通过浏览器提交答案，不要填写多余的内容。（1）答案。10（ 2）编程思路。定义一个数组 int a13 ，

19、其中 a1a12这 12个元素分别从上到下，自左向右的 12个 圆圈。可采用递归的方法生成由 112这 12个数字组成的无重复数字的全排列。生成 112 不同的 12个数字存储到数组中后，检测 6 条直线上的四个数字之和是否全 相等，如果全相等，是一组解，输出并计数。（3）源程序。#include <stdio.h>int a13;int vis13;int cnt=0;void dfs(int x)if(x = 12)int t6;t0 = a1 + a3 + a6 + a8;t1 = a1 + a4 + a7 + a11;t2 = a2 + a3 + a4 + a5;t3 =

20、a2 + a6 + a9 + a12;t4 = a8 + a9 + a10 + a11;t5 = a12 + a10 + a7 + a5;for(int i = 1; i < 6; +i)if(ti != ti -1) return ;cnt+;printf("No %dn",cnt);printf("%12dn",a1); printf("%3d%6d%6d%6dn",a2,a3,a4,a5); printf("%6d%12dn",a6,a7);printf("%3d%6d%6d%6dn"

21、;,a8,a9,a10,a11); printf("%12dnn",a12);return ;for(int i = 1;i < 13; +i)if(!visi)visi = 1; ax = i;dfs(x+1);visi = 0;int main()for (int i=1;i<=12;i+)visi=0;vis1 = 1;a1 = 1;vis8 = 1; a2 = 8;vis3 = 1;a12 =3;dfs(3);printf("Count=%dn",cnt); return 0;蚂蚁感冒长 100 厘米的细长直杆子上有 n 只蚂蚁。它们

22、的头有的朝左，有的朝右。 每只蚂蚁都只能沿着杆子向前爬，速度是1厘米 /秒。当两只蚂蚁碰面时，它们会同时掉头往相反的方向爬行。这些蚂蚁中， 有 1 只蚂蚁感冒了。 并且在和其它蚂蚁碰面时， 会把感冒传染给碰到的蚂 蚁。请你计算，当所有蚂蚁都爬离杆子时，有多少只蚂蚁患上了感冒。 【数据格式】 第一行输入一个整数 n （1 < n < 50）, 表示蚂蚁的总数。接着的一行是 n个用空格分开的整数 Xi （-100 < Xi < 100）, Xi 的绝对值，表示蚂蚁离开 杆子左边端点的距离。正值表示头朝右， 负值表示头朝左，数据中不会出现 0 值， 也不会出 现两只蚂蚁占用同

23、一位置。其中，第一个数据代表的蚂蚁感冒了。要求输出 1 个整数，表示最后感冒蚂蚁的数目。 例如，输入：35 -2 8 程序应输出：1 再例如，输入：5-10 8 -20 12 25 程序应输出：3 （ 1）编程思路。 首先， 两只蚂蚁相遇各自反向可以看作是两只蚂蚁分别穿过对方继续前进。这样处理的话就简单多了。 感冒蚂蚁不管初始方向朝哪一边， 它右边的蚂蚁只要向左走就可能碰撞感染 （特殊情况除外） ，同样，它左边的蚂蚁只要朝右边走也可能被感染。假如感冒蚂蚁开始时向左行， 则会感染它左边所有向右行的蚂蚁 （因为相遇后它穿过对 方继续向左行碰到向右行的蚂蚁感染它们） ；相遇被感染的第 1 只蚂蚁也穿

24、过继续向右行， 感染所有它右边向左行的蚂蚁。感冒蚂蚁开始时向右行情况类似。 这样，最后感冒的蚂蚁的数量为： 感冒蚂蚁左边蚂蚁向右走的数量 + 右边蚂蚁向左走的数量 + 感冒蚂蚁本身 特殊情况是， 当感冒蚂蚁向左爬的时候， 如果感冒蚂蚁左边没有向右爬行的蚂蚁， 那么 不管感冒蚂蚁右边有多少向左爬行的， 因爬行的速度相同感冒蚂蚁不会遇到向右爬的蚂蚁进行感染，因此右边的蚂蚁也永远不可能被感染。同样的， 当感冒蚂蚁向右爬的时候， 如果感冒蚂蚁右边没有向左爬行的蚂蚁， 那么同样 感冒蚂蚁左边的蚂蚁也永远不可能被感染。(2)源程序。#include <stdio.h>int abs(int x

25、)return x>=0?x: -x;int main()int ant51;int n,i;scanf("%d",&n);for (i=0;i<n;i+) scanf("%d",&anti);int left=0,right=0;for (i=1;i<n;i+)if (anti<0 && abs(anti)>abs(ant0) left+; / 感冒蚂蚁右边且向左走的 if (anti>0&&abs(anti)<abs(ant0) right+; / 感冒蚂蚁左边

26、且向右走的if (ant0<0 && right=0)| (ant0>0 && left=0) printf("1n");else printf("%dn",left+right+1);return 0;地宫取宝X 国王有一个地宫宝库。是 n x m 个格子的矩阵。每个格子放一件宝贝。每个宝贝贴 着价值标签。地宫的入口在左上角，出口在右下角。 小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时， 如果那个格子中的宝贝价值比小明手中任意宝贝价值都大， 小明就可 以拿起它(当然，也可以不拿) 。当小

27、明走到出口时，如果他手中的宝贝恰好是 k 件，则这些宝贝就可以送给小明。 请你帮小明算一算，在给定的局面下，他有多少种不同的行动方案能获得这 k 件宝贝。 【数据格式】输入一行 3 个整数，用空格分开： n m k (1<=n,m<=50, 1<=k<=12)接下来有 n 行数据，每行有 m 个整数 Ci （0<=Ci<=12） 代表这个格子上的宝物的价值 要求输出一个整数，表示正好取 k 个宝贝的行动方案数。该数字可能很大，输出它对 1000000007 取模的结果。例如，输入：2 2 21 22 1程序应该输出：2再例如，输入：2 3 21 2 32 1

28、 5程序应该输出：14（ 1）编程思路。采用记忆化搜索完成。定义 4维数组 dp51511515 。设 dpxynumval 表示在坐标 （x,y）时拿了 num 件宝 贝并且宝贝中价值最大的为 val，其中 1xn，1 y m， num的初值为 0，表示还没有拿 到宝贝， val 的初值本来应该为 -1，表示此时手上还没有宝物（因为从题目数据说明中可以 看出宝贝的价值可以为 0），为了让 val 初始值为 0，可以将输入的宝贝的价值统一加1，这样宝贝的最小价值为 1（不是 0）。定义二维数组 int map5151 保存地宫各格子的宝贝价值。 采用倒推法列出状态转移方程，即把后面的情况种数不

29、断的往前更新。 当 mapxy>val 时，dpxynumval=dpx+1ynum+1mapxy+dpxy+1num+1mapxy +dpx+1ynumval+dpxy+1numval ；当 mapxy<=val 时， dpxynumval=dpx+1ynumval+dpxy+1numval 。在通过 DFS 搜索方式求数组 dp 的各元素值时， 由于数组元素值 dpxynumval 跟位 置（x,y）、宝贝个数 以及当 前最大 的宝贝 价值有关 ，当重 复遍历这个结 点时， 若 dpxynumval 的值已经计算出来了， 则直接应用无需重复递归计算。 为此， 定义数组 dp 的

30、全部元素的初始值为 -1。若计算时需要用到 dpxynumval ，此时 dpxynumval ！ =-1，则无需重复调用， 直接应用计算好的 dpxynumval 元素值。 之所以初值定义为 -1， 是考虑到若路径不存在的情况（此时方案数应为0）。（2）源程序。#include <stdio.h>#include <string.h>#define MOD 1000000007long long dp51511515;int map5151;int n,m,k;void dfs（int x, int y, int num, int val）if (dpxynumval

31、 != -1)return;dpxynumval = 0;if (x = n && y = m && num = k)dpxynumval = 1;return;if (mapxy > val && num < k)dfs(x, y, num + 1, mapxy);dpxynumval += dpxynum + 1mapxy;dpxynumval %= MOD;if (x < n) / 向下走dfs(x + 1, y, num, val);dpxynumval += dpx + 1ynumval;dpxynumval %= M

32、OD;if (y < m) / 向右走dfs(x, y + 1, num, val);dpxynumval += dpxy + 1numval;dpxynumval %= MOD;int main()scanf("%d%d%d",&n,&m,&k);for (int i = 1; i <=n ; i+)for (int j = 1; j <= m; j+)scanf("%d",&mapij); mapij+;memset(dp, -1, sizeof(dp);dfs(1, 1, 0, 0);printf(

33、"%dn",dp1100);return 0;小朋友排队n 个小朋友站成一排。 现在要把他们按身高从低到高的顺序排列， 但是每次只能交换位 置相邻的两个小朋友。每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。如果某个小朋友第一次被要求交换， 则他的不高兴程度增加 1，如果第二次要求他交换， 则他的不高兴程度增加 2（ 即不高兴程度为 3），依次类推。当要求某个小朋友第 k 次交换时， 他的不高兴程度增加 k。请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。 如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。【数据格式】输

34、入的第一行包含一个整数 n，表示小朋友的个数。第二行包含 n 个整数 H1 H2 Hn，分别表示每个小朋友的身高。 输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。 例如，输入：33 2 1程序应该输出：9【样例说明】首先交换身高为 3 和 2 的小朋友，再交换身高为 3 和 1 的小朋友，再交换身高为 2 和 1 的小朋友，每个小朋友的不高兴程度都是3，总和为 9。【数据规模与约定】对于 10%的数据， 1<=n<=10 ；对于 30%的数据， 1<=n<=1000 ；对于 50%的数据， 1<=n<=10000 ；对于 100%的数据， 1&l

35、t;=n<=100000 ， 0<=Hi<=1000000 。（ 1）编程思路。本题的实质是求一组数据中逆序数对的个数。比如题目中的3，2，1，和 3 有关的逆序对为（3，2）和（3，1），和 2有关的逆序对为 （3，2）和（2，1），和 1有关的逆序对为 （3，1）和（ 2，1），为了完成排序，任何一个逆序对的两个元素都必须交换一次，于是可知，每 个小朋友都完成了两次交换。要求一个数组元素有关的逆序对个数，就是求它之前有几个大于它的元素（设为b1 ），之后有几个小于它的元素（设为b2），这样每个元素的交换次数为 b1+b2。根据数据规模与约定， 若采用二重循环进行暴力搜索逆

36、序对的个数， 肯定会超时的。 因 此，采用树状数组来解决本题。树状数组实际上是由两部分组成：数据数组（设为num）和统计数组（设为 C）。我们以数据数组 num3=3,2,1 为例进行描述。树状数组的各元素初始值为0，但由于树状数组元素下标是从 1 开始的，因此将数据数组的每个元素值加1，然后作为树状数组的下标，将数值 1 存到相应的位置。从左到右依次扫描数据数组。1）读入 3，此时读入的数据个数为 1，树状数组 C 为：C1C2C3C4C5C6C7C800010 0 00可以看到 sum(C1,C4)=1 ，这是小于等于 3 的数字的个数，也就是说当输入第一个数3 的时候没有比它小的数字存在

37、。这时“输入数值个数 -sum(C1,C4)=1 -1=0”，也就是说大 于 3 的数字的个数为 0，保存起来，即 b0=0 。( 在这里特别注意， 根据树状数组 sum(C1,Cn) 算出来的数值是某个数字 n 左边比它小的数字的个数。 )2) 读入 2，此时读入的数据个数为 2，树状数组 C 为：C1C2C3C4C5C6C7C800110 0 00可以看到 sum(C1,C3)=1 ，仍然不存在比它小的数， 而此时输入的数据个数为 2，2-1=1 ， 就是说，存在一个数在 2 之前并且大于 2(这个数是第 1 个数 3)，保存 b1=1 。3) 读入 1，此时读入的数据个数为 3，树状数组 C 为：C1C2C3C4C5C6C7C801110 0 00可以看到 sum(C1,C2)=1 ，仍然不存在比它小的数， 而此时输入的数据个数为 3，3-1=2 ， 就是说，存在两个数在 1 之前并且大于 1(这两个数就是 3