第六届蓝桥杯真题解析

  1. 启明星工作室解析

目录：

  1. 奖券数目
  2. 星系炸弹
  3. 三羊献瑞
  4. 格子中输出
  5. 九数组分数
  6. 加法变乘法
  7. 牌型种数
  8. 移动距离
  9. 垒骰子
  10. 生命之树

1. 奖券数目

有些人很迷信数字，比如带“4”的数字，认为和“死”谐音，就觉得不吉利。
虽然这些说法纯属无稽之谈，但有时还要迎合大众的需求。某抽奖活动的奖券号码是5位数（10000-99999），要求其中不要出现带“4”的号码，主办单位请你计算一下，如果任何两张奖券不重号，最多可发出奖券多少张。

请提交该数字（一个整数），不要写任何多余的内容或说明性文字。

解:
思路:后四个数可选0 ~ 9除去4，共9个数，第一个数可选1 ~ 9除去4，共8个数，所有没有4的总数为：
8 9 9 9 9 = 52488

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main(){
	string s;
	int sum = 0;
	int i, j;
	for(i = 10000; i <= 99999; i++){
		s = to_string(i);
		for(j = 0; j < s.length(); j++)
			if(s[j] == '4') break;
		if(j == s.length())
			sum++;
	}
	cout << sum << endl;
	return 0;
}

答案: 52488

2. 星系炸弹

在X星系的广袤空间中漂浮着许多X星人造“炸弹”，用来作为宇宙中的路标。每个炸弹都可以设定多少天之后爆炸。比如：阿尔法炸弹2015年1月1日放置，定时为15天，则它在2015年1月16日爆炸。有一个贝塔炸弹，2014年11月9日放置，定时为1000天，请你计算它爆炸的准确日期。请填写该日期，格式为 yyyy-mm-dd 即4位年份2位月份2位日期。比如：2015-02-19 请严格按照格式书写。不能出现其它文字或符号。

解：
思路：先算完2014年的天数，11月30天，12月31天，那么还剩30 + 31 - 9 = 52天，定时变为1000 - 52 = 948天，2015为365天，2016为366天，2017为365天，算上2015和2016的，定时变为948 - 365 - 366 = 217天，2017年1~6月31,28,31,30,31,30,31共212天，定时变为217 - 212 = 5天，7月再过5天，爆炸，日期为2017-08-05

答案：2017-08-05

3. 三羊献瑞

观察下面的加法算式：

1
2
3
4
5

      祥 瑞 生 辉
  +   三 羊 献 瑞
-------------------
   三 羊 生 瑞 气

其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。

请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

解：
思路：先观察这个等式，易得’三’表示的数字为1，因为10进制进位为1，祥所代表的数必定大于７，如果为7，那么7 + 1 = 8，而’瑞’＋’羊’进位不可能为2, ‘祥’所代表的数就为8或者9，如果为８，那么发生进位，’祥’ + ‘三’ = 10,那么’羊’为0，而一个一位数加上０不可能进位，所以’祥’为９，’羊’为０，此时得到祥(9), 三(1), 羊(0),因为’瑞’ + ‘羊’(0) = 生，’瑞’ != ‘羊’，所以发生进位，’瑞’ + 1 = ‘生’, ‘生’ + ‘献’ = ‘瑞’，即’瑞’ + 1 + ‘献’ = ‘瑞’ + 10，’献’ = 9，发生冲突(祥为９)，所以’’辉’＋’瑞’必定发生进位，’献’为８，然后将’瑞’从２开始取，一个个试，’瑞’(2), ‘辉’ 取８或９，矛盾;’瑞’(3),’辉’取７或８或９,矛盾;最终，’瑞’(5),’辉’(7),’生’(4)满足,此时’祥’(9),’瑞’(5),’生’(4),’辉’(7),’三’(1),’羊’(0),’献’(8),’气’(2)

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	int a[10];
	for(int i = 0; i <= 9; i++)
		a[i] = i;
	do{
		int a0 = a[0];   //祥    
 		int a1 = a[1];   //瑞
		int a2 = a[2];   //生
		int a3 = a[3];   //辉
		int a4 = a[4];   //三
		int a5 = a[5];   //羊  
		int a6 = a[6];   //献
		int a7 = a[7];   //气
		int x1 = a0 * 1000 + a1 * 100 + a2 * 10 + a3;
		int x2 = a4 * 1000 + a5 * 100 + a6 * 10 + a1;
		int x3 = a4 * 10000 + a5 * 1000 + a2 * 100 + a1 * 10 + a7; 
		if(a0 != 0 && a4 != 0 && x1 + x2 == x3)   //最高位不能为0
			cout << a4 << a5 << a6 << a1 << endl;
	}while(next_permutation(a, a + 10));
	
	return 0;
}

答案：1085

4. 格子中输出

StringInGrid函数会在一个指定大小的格子中打印指定的字符串。
要求字符串在水平、垂直两个方向上都居中。
如果字符串太长，就截断。
如果不能恰好居中，可以稍稍偏左或者偏上一点。

下面的程序实现这个逻辑，请填写划线部分缺少的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <stdio.h>
#include <string.h>

void StringInGrid(int width, int height, const char* s)
{
	int i,k;
	char buf[1000];
	strcpy(buf, s);
	if(strlen(s)>width-2) buf[width-2]=0;
	
	printf("+");
	for(i=0;i<width-2;i++) printf("-");
	printf("+\n");
	
	for(k=1; k<(height-1)/2;k++){
		printf("|");
		for(i=0;i<width-2;i++) printf(" ");
		printf("|\n");
	}
	
	printf("|");
	
	printf("%*s%s%*s",_____________________________________________);  //填空
	          
	printf("|\n");
	
	for(k=(height-1)/2+1; k<height-1; k++){
		printf("|");
		for(i=0;i<width-2;i++) printf(" ");
		printf("|\n");
	}	
	
	printf("+");
	for(i=0;i<width-2;i++) printf("-");
	printf("+\n");	
}

int main()
{
	StringInGrid(20,6,"abcd1234");
	return 0;
}

1
2
3
4
5
6
7
对于题目中数据，应该输出：
+------------------+
|                  |
|     abcd1234     |
|                  |
|                  |
+------------------+

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

解：
思路：观察代码(或者先将要填的地方注释，然后运行一遍程序)结果为

1
2
3
4
5
6
+------------------+
|                  |
||
|                  |
|                  |
+------------------+,

1
2
3
4
5
6
7
8
9
发现要填的地方其实是要在恰当的地方输出这个这个字符，框框之类的已经帮我们写好了，
观察printf("%*s%s%*s",  ),首先要了解%*s是什么，这个printf("%*s", 10, s) 意思是输出字符串s，
但至少占10个位置，不足的在字符串s左边补空格，这里等同于printf("%10s", s)  这样就明白了，
%s应该是要输出字符串，%*s是要输出空格，多少空格呢，若要让字符串居中，那么空格个数为
(width - strlen(s) - 2) / 2, 左右两边空格一样，那么就先算出总共有多少空格然后除以２就ｏｋ，所以结果就是
printf("%*s%s%*s", (width - strlen(s) - 2) / 2, buf, (width - strlen(s) - 1) / 2); 
这里中间为buf,因为题目中说明了超出界限的字符串要去掉，而代码中有buf[width - 2] = 0这个操作，
说明输出的是ｂｕｆ,这里需要注意奇偶性问题，如果width为奇数，那么就要多一个空格，
所以后面的宽度需要加上１再除２,即奇数多１，补上1再除２，就添了１，偶数＋1，除２，1 / 2值为０。

答案：(width - strlen(s) - 2) / 2, buf, (width - strlen(s) - 1) / 2

5. 九数组分数

1,2,3…9 这九个数字组成一个分数，其值恰好为1/3，如何组法？

下面的程序实现了该功能，请填写划线部分缺失的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>

void test(int x[])
{
	int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
	int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];
	
	if(a*3==b) printf("%d / %d\n", a, b);
}

void f(int x[], int k)
{
	int i,t;
	if(k>=9){
		test(x);
		return;
	}
	
	for(i=k; i<9; i++){
		{t=x[k]; x[k]=x[i]; x[i]=t;}
		f(x,k+1);
		_____________________________________________ // 填空处
	}
}
	
int main()
{
	int x[] = {1,2,3,4,5,6,7,8,9};
	f(x,0);	
	return 0;
}

注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。

解：
思路：观察代码，很明显地发现ｆ一个递归函数，从第一个数字开始，不断将数组数字进行交换，然后得出所有的情况，最后调用test()函数测试是否为1 / 3, 在一次递归完成后需要将数组内的数字位置还原，因而结果应该填{t=x[k]; x[k]=x[i]; x[i]=t;},也就是交换一遍之后再重复这个操作便可以还原位置

答案：{t=x[k]; x[k]=x[i]; x[i]=t;}

6. 加法变乘法

我们都知道：1+2+3+ … + 49 = 1225
现在要求你把其中两个不相邻的加号变成乘号，使得结果为2015

比如：
1+2+3+…+1011+12+…+2728+29+…+49 = 2015
就是符合要求的答案。

请你寻找另外一个可能的答案，并把位置靠前的那个乘号左边的数字提交（对于示例，就是提交10）。

注意：需要你提交的是一个整数，不要填写任何多余的内容。

解：
思路：这题首先想到的就是一个个地试，因为已经告诉了一种情况，那么，左边的数字必然>10,最右边的数字必然小于28,因为如果是<10和大于28,由于后面的数字相乘之后太大，一定是超出2015的，因而只要尝试>10&&<28以内的就ｏｋ，尝试方法举例:
若是11 12 和 26 27，那么1125 - 11 - 12 - 26 - 27 + 11 12 + 26 27, 多次尝试之后得到16 17 24 25

也可以写程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int main(){
	int a[49];
	int sum = 1225;
	for(int i = 1; i <= 49; i++)
		a[i] = i;
	int i, j, p, q;
	for(i = 1, j = i + 1; i <= 46; i++, j++)
		for(p = i + 2, q = p + 1; p <= 48; p++, q++){
			if(sum - a[i] - a[j] - a[p] - a[q] + a[i] * a[j] + a[p] * a[q] == 2015){
				cout << i << " " << j << " " << p << " " << q << endl;
			}
		}
	return 0;
}

答案：16

7. 牌型种数

小明被劫持到X赌城，被迫与其他3人玩牌。
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。
这时，小明脑子里突然冒出一个问题：
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？

请填写该整数，不要填写任何多余的内容或说明文字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;

int count = 0;   //count为情况总数

int dfs(int poker, int cnt){   //poker为点数, cnt为张数
	if(poker > 13 || cnt > 13)  //点数或者张数大于１３，返回
		return 0;
	if(cnt == 13){     //当张数满足１３时，算作一种取法
		count++;
		return 0;
	}
	for(int i = 0; i <= 4; i++)
		dfs(poker + 1, cnt + i);   //点数逐渐加１，取牌张数从０到４
	return 0;
}

int main(){
	dfs(0, 0);
	cout << count << endl;
	return 0;
}

8. 移动距离

X星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为1,2,3…
当排满一行时，从下一行相邻的楼往反方向排号。
比如：当小区排号宽度为6时，开始情形如下：

1 2 3 4 5 6
12 11 10 9 8 7
13 14 15 …..

我们的问题是：已知了两个楼号m和n，需要求出它们之间的最短移动距离（不能斜线方向移动）

输入为3个整数w m n，空格分开，都在1到10000范围内
w为排号宽度，m,n为待计算的楼号。
要求输出一个整数，表示m n 两楼间最短移动距离。

例如：
用户输入：
6 8 2
则，程序应该输出：
4

再例如：
用户输入：
4 7 20
则，程序应该输出：
5

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 1000ms

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cmath>
using namespace std;

int getX(int w, int m){
	//计算所在行
	return m % w == 0 ? m / w : m / w + 1;   //如果是中间的点，因为除不尽，所以需要＋１
}

int getY(int x, int w, int m){
	if(x % 2 == 0)   //能被２整除，数字从右往左排列
//(x - 1) * w 是上面有多少数字，m - (x - 1) * w是当前的位置,然后用ｗ减去这个位置再＋１，就是当前所在列 
		return w - (m - (x - 1) * w) + 1;   
	else
		return m - (x - 1) * w;
}

int main(){
	int w, m, n;
	cin >> w >> m >> n;
	int x1, y1, x2, y2;
	x1 = getX(w, m);
	x2 = getX(w, n);
	y1 = getY(x1, w, m);
	y2 = getY(x2, w, n);
	cout << abs(x1 - x2) + abs(y1 - y2) << endl;
	return 0;
}

9. 垒骰子

赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。
经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！
我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。
假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。
atm想计算一下有多少种不同的可能的垒骰子方式。
两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。
由于方案数可能过多，请输出模 10^9 + 7 的结果。

不要小看了 atm 的骰子数量哦～

「输入格式」
第一行两个整数 n m
n表示骰子数目
接下来 m 行，每行两个整数 a b ，表示 a 和 b 数字不能紧贴在一起。

「输出格式」
一行一个数，表示答案模 10^9 + 7 的结果。

「样例输入」
2 1
1 2

「样例输出」
544

「数据范围」
对于 30% 的数据：n <= 5
对于 60% 的数据：n <= 100
对于 100% 的数据：0 < n <= 10^9, m <= 36

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 2000ms

解：
思路：矩阵X记录骰子是否选择，选择为０，不选为１，不能相贴合的面就为０，这里可以转化为顶面不满足的就为０，这样比较方便，比如1 2不能紧贴在一起，1的对面为4，2的对面为5, 那么如果1为顶面，那么下一个骰子的顶面就不能为5，这样相比前一个骰子看顶面，后一个骰子看底面的方法简单许多，然后矩阵A1 A2就计算这两个骰子的所有匹配情况，A1[i][j]表示点数为i，顶面为j的方案总数，A2就是新加入的一个骰子，比如我现在前面的骰子的匹配情况是10，那么将每一个点数所代表的方案数再和一个骰子相乘，如果该骰子为０，表示有冲突，那么相乘之后就为０，就不加入进来，如果是１，那么就加入进来，假如情况为1 2 3 1 2 1, 一个骰子为1 1 1 1 0 1, 点数为１时:1 1 + 1 1 + 1 1 + 1 1 + 1 0 + 1 1,点数为２时2 1 + 1 1 + 1 1 + 1 1 + 2 0 + 1…就和矩阵相乘是一样的，令X那么先利用矩阵快速幂求An, An = An-1 * X, A1 = E(单位矩阵), An = X ^ (n - 1), 之后再将矩阵内的值全部加起来就是顶面方案的全部情况，最后再乘以4 ^ n,因为有四个面，面可以旋转，这个用快速幂求解，避免爆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll MOD = 1000000007;

//矩阵连乘
mat mul(mat &A, mat &B){
	mat C(A.size(), vec(B[0].size()));
	for(int i = 0; i < A.size(); i++)
		for(int j = 0; j < B.size(); j++)
			for(int k = 0; k < B[0].size(); k++)
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD;
	return C;
}

//矩阵快速幂
mat fast_pow1(mat &A, int n){
	mat B(A.size(), vec(A.size()));
	for(int i = 0; i < A.size(); i++)
		B[i][i] = 1;
	while(n){
		if(n & 1)
			B = mul(B, A);
		A = mul(A, A);
		n >>= 1;
	}
	return B;
}

//快速幂
ll fast_pow2(ll x, ll n){
	ll res = 1;
	while(n){
		if(n & 1)
			res = res * x % MOD;
		x = x * x % MOD;
		n >>= 1;
	}
	return res;
}

int main(){
	ll n, m;
	cin >> n >> m;
	int a, b;
	mat A(6, vec(6, 1));  //６行６列，全部值初始化为１
	for(int i = 0; i < m; i++){
		cin >> a >> b;
		/** 从０开始计数,所以a - 1表示当前点,和(b + 2) % 6不相融，
		  例如1 2, a - 1 = 0, (b + 2) % 6 = 4, 0为顶面时，下一个骰子的4不能为顶面，相当于１和５,
		  当１为顶面时，２不能为底面，2为底面时，5就为顶面**/
		A[a - 1][(b + 2) % 6] = 0;  
		A[b - 1][(a + 2) % 6] = 0;  //同理5为顶面时，下一个骰子的1不能为顶面
	}
	mat C = fast_pow1(A, n - 1);   //矩阵快速幂求An = X ^ (n - 1)
	ll sum = 0;
	for(int i = 0; i < A.size(); i++)
		for(int j = 0; j < A.size(); j++)
			sum = (sum + C[i][j]) % MOD;    //求矩阵的和
	sum = sum * fast_pow2(4, n) % MOD;   //快速幂求sum * (4 ^ n),四个面，ｎ个骰子情况数为4 ^ n
	cout << sum << endl;
	return 0;
}

10. 生命之树

在X森林里，上帝创建了生命之树。

他给每棵树的每个节点（叶子也称为一个节点）上，都标了一个整数，代表这个点的和谐值。
上帝要在这棵树内选出一个非空节点集S，使得对于S中的任意两个点a,b，都存在一个点列 {a, v1, v2, …, vk, b} 使得这个点列中的每个点都是S里面的元素，且序列中相邻两个点间有一条边相连。

在这个前提下，上帝要使得S中的点所对应的整数的和尽量大。
这个最大的和就是上帝给生命之树的评分。

经过atm的努力，他已经知道了上帝给每棵树上每个节点上的整数。但是由于 atm 不擅长计算，他不知道怎样有效的求评分。他需要你为他写一个程序来计算一棵树的分数。

「输入格式」
第一行一个整数 n 表示这棵树有 n 个节点。
第二行 n 个整数，依次表示每个节点的评分。
接下来 n-1 行，每行 2 个整数 u, v，表示存在一条 u 到 v 的边。由于这是一棵树，所以是不存在环的。

「输出格式」
输出一行一个数，表示上帝给这棵树的分数。

「样例输入」
5
1 -2 -3 4 5
4 2
3 1
1 2
2 5

「样例输出」
8

「数据范围」
对于 30% 的数据，n <= 10
对于 100% 的数据，0 < n <= 10^5, 每个节点的评分的绝对值不超过 10^6 。

资源约定：
峰值内存消耗 < 256M
CPU消耗 < 3000ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAX = 1e5;

int N, dp[MAX][2];
vector<int> G[MAX];

void dfs(int v, int father){
	for(int i = 0; i < G[v].size(); i++){
		int u = G[v][i];
		if(u == father)
			continue;
		dfs(u, v);
		dp[v][0] = max(max(dp[u][0], dp[u][1]), dp[v][0]);
		if(dp[u][1] > 0)
			dp[v][1] += dp[u][1];
	}
}

int main(){
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> dp[i][1];
		dp[i][0] = -INF;
	}
	for(int i = 0; i < N - 1; i++){
		int u, v;
		cin >> u >> v;
		G[v].push_back(u);
		G[u].push_back(v);
	}
	dfs(1, -1);
	cout << max(dp[1][0], dp[1][1]) << endl;
	return 0;
}

本文标题:第六届蓝桥杯真题解析

文章作者:gydjsz

发布时间:2019-03-20, 18:53:11

最后更新:2019-03-20, 18:53:11

原始链接:https://gydjsz.github.io/2019/03/20/algorithm/lqb6/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
|