蓝桥杯模拟赛C/C++总结

填空题

A题

问题描述
一个包含有2019个结点的无向连通图,最少包含多少条边?

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数,填写多余的内容将无法得分。

题解
简单的数学小思维题，一开始看错题成最多的，后来才发现是最少的…

• 最多 2019*2018/2
• 最少 2018

此题答案为 2018

B题

问题描述
由1对括号，可以组成一种合法括号序列: ()。
由2对括号，可以组成两种合法括号序列: ()()、(())。
由4对括号组成的合法括号序列一共有多少种?

【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结
多余的内容将无法得分。

把所有的情况都列举一遍，发现一共有14种
()()()()
(())()() 、 ()(())() 、 ()()(()) 、(()()()) 、 (()())() 、 ()(()()) 、 (())(())
((()))() 、 ()((())) 、 ((())()) 、 (()(())) 、 ((()()))
(((())))
答案为14

C题

问题描述
在计算机存储中，12.5MB是多少字节?

【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数，填写多余的内容将无法得分。

1MB=1024KB；
1KB=1024B；

所以12.5MB=12.5 * 1024 * 1024=13107200B
答案为13107200

D题

问题描述
将LANQIAO中的字母重新排列，可以得到不同的单词,如LANQIAO、AILNOQ等， 注意这7个字母都要被用上，单词不一定有具体的英文意义。
请问，总共能排列如多少个不同的单词。

【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数,填写多余的内容将无法得分。

实际上就是高中所学的排列组合。
即7!=7 * 6 * 5 * 4 * 3 * 2 * 1=5040，但是需要注意A有两个，所以需要除以2
则答案为2520

编程题

E题

问题描述
给定三个整数a,b,c,如果一个整数既不是a的整数倍也不是b的整数倍还不是c的整数倍，则这个数称为反倍数。
请问在1至n中有多少个反倍数。

输入格式
输入的第一行包含一个整数n。
第二行包含三E个整数a, b, c,相邻两个数之间用-一个空格分
隔。

输出格式
输出一行包含一个整数，表示答案。

样例输入
236

样例输出
10

样例说明
以下这些数满足要求: 1, 5, 7, 11, 13, 17, 19, 23, 25, 29。
评测用例规模与约定
对于40%的评测用例，1 <= n <= 10000。
对于80%的评测用例，1 <= n <= 100000。
对于所有评测用例，1<=n<=1000000，1<=a<=n,1<=b<=n，1<=C<=n。

从1到n进行遍历，然后进行判断
直接贴代码

#include<iostream>
using namespace std;
typedef long long ll;
int main() 
{
	ll n, a, b, c;
	cin >> n;
	cin >> a >> b >> c;
	ll ans = 0;
		for (int i = 1; i <= n; ++i)//遍历
			if ((i % a) && (i % b) && (i % c))ans++;//判断
		cout << ans << endl;
	return 0;
}

F题

问题描述
给定一个单词，请使用凯撒密码将这个单词加密。
凯撒密码是一种替换加密的技术 ，单词中的所有字母都在字母表上向后偏移3位后被替换成密文。即a变为d, b变为e, … w变为z,变为a，y变为b, z变为c。
例如，lanqiao会变成odqtldr.

输入格式
输入一行，包含一个单词，单词中只包含小写英文字母。

输出格式
输出一行,表示加密后的密文。

样例输入
lanqiao

样例输出
odqtldr

评测用例规模与约定
对于所有评测用例，单词中的字母个数不超过100。

题解
题中所用的的字母为26个小写英语字母，其中a-w向后移动三位，x,y,z三个字母向前移动23位

代码

#include<iostream>
using namespace std;
int main() 
{
	char ch;
	while (cin >> ch)
	{
		if (ch >= 'a' && ch <= 'w')
			cout << char(ch + 3);
		else
			cout << char(ch - 23);
	}
	return 0;
}

G题

问题描述
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即a[2ij<a[2i- 1], a[2i+ 1]>a[2i。小明想知道，长度为m,每个数都是1到n之间的正整数的摆动序列共有多少个。

输入格式
输入一行包含两个整数m, n。

输出格式
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。

样例输入
34

样例输出
14

题解

使用dp来进行求解。
dp[i][j]表示第i位数时，最大数为m时共有多少个。
我们每次处理都需要判断i的奇偶，然后我们为边界赋值，赋值只有1位数的时，最大数的不同时，可能的种类，初始化为dp[1][i] = n - i + 1

计算的时候先从第一行开始，为第一行进行一个初始化，初始化为下一行可以选择的值的数目，即当前所能组成的摆动数列的个数。初始化dp[1][i] = n - i + 1;
第一行中，令 d[1][j]为：第1个数选择大于等于 j的数的方案总数。
从第二行开始：奇数行中，令 d[i][j]为：第i个数选择大于等于j的数时的方案总数。偶数行中，令 d[i][j]为：第i个数选择小于等于j的数时的方案总数。

即从第二行开始，如果行数为偶数行，那么我们当前可能的数目为：dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % 10000;如果为奇数行则：dp[i][j] = (dp[i-1][j-1] + dp[i][j+1]) % 10000;。
​ 如果总的长度为奇数的话，那么就是dp[m][1],如果是偶数，则为dp[m][n]。

代码

#include <iostream>
using namespace std;
const int N = 1e3 + 10;
const int mod = 1e4;
int dp[N][N];
int main() 
{
    int m, n;
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
        dp[1][i] = n - i + 1;
    for (int i = 2; i <= m; i++)
        if (i % 2)//奇数
            for (int j = n; j >= 1; j--)
                dp[i][j] = (dp[i - 1][j - 1] + dp[i][j + 1]) % mod;
        else//偶数
            for (int j = 1; j <= n; j++)
                dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % mod;
    int ans;
    if (m % 2)//奇数
         ans = dp[m][1];
    else//偶数
         ans = dp[m][n];
    cout << ans<<endl;
    return 0;
}

H题

问题描述
对于一个n行m列的表格,我们可以使用螺旋的方式给表格依
次填上正整数，我们称填好的表格为一个螺旋矩阵。
例如，一个4行5列的螺旋矩阵如下:
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8

输入格式
输入的第一行包含两个整数n, m,分别表示螺旋矩阵的行数和列数。
第二行包含两个整数r, C,表示要求的行号和列号。

输出格式
输出一个整数，表示螺旋矩阵中第r行第c列的元素的值。

样例输入
45
22

样例输出
15

评测用例规模与约定
对于30%的评测用例，2 <= n,m <= 20。
对于70%的评测用例，2 <= n,m <= 100。
对于所有评测用例，2<=n,m<=1000,1<=r<=n,1<=C<=m。

题解
分四种情况讨论，分别为 上 下 左 右 ，再判断特殊情况，思路不难想，就是代码实现有些繁琐

代码

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e3 + 10;
int a[MAXN][MAXN] = { 0 };
int main()
{
	int m, n;
	int r, c;
	int start = 1;
	cin >> n >> m;
	cin >> r >> c;
	int count = min(n, m);//较小值 
	int i, j;
	//分层填充
	for (i = 0; i < count / 2; i++) {
		int row = n - i - 1;
		int col = m - i - 1;
		//上边
		for (j = i; j < col; j++) {
			a[i][j] = start++;
		}
		//右边
		for (j = i; j < row; j++) {
			a[j][col] = start++;
		}
		//下边
		for (j = col; j > i; j--) {
			a[row][j] = start++;
		}
		//左边
		for (j = row; j > i; j--) {
			a[j][i] = start++;
		}
	}
	if (count % 2 == 1)
	{
		if (count == n)
		{
			int row = n / 2;
			int col = m - count / 2;
			for (int k = count / 2; k < col; k++)
				a[row][k] = start++;
		}
		else
		{
			int row = n - count / 2;
			int col = m / 2;
			for (int k = count / 2; k < row; k++)
				a[k][col] = start++;
		}
	}
	cout << a[r-1][c-1] << endl;
	return 0;

}

I题

问题描述
小明和朋友们一起去郊外植树，他们带了一些在自己实验室精心研究出的小树苗。
　　小明和朋友们一共有 n 个人，他们经过精心挑选，在一块空地上每个人挑选了一个适合植树的位置，总共 n 个。他们准备把自己带的树苗都植下去。
　　然而，他们遇到了一个困难：有的树苗比较大，而有的位置挨太近，导致两棵树植下去后会撞在一起。
　　他们将树看成一个圆，圆心在他们找的位置上。如果两棵树对应的圆相交，这两棵树就不适合同时植下（相切不受影响），称为两棵树冲突。
　　小明和朋友们决定先合计合计，只将其中的一部分树植下去，保证没有互相冲突的树。他们同时希望这些树所能覆盖的面积和（圆面积和）最大。

输入格式

输入的第一行包含一个整数 n ，表示人数，即准备植树的位置数。
　　接下来 n 行，每行三个整数 x, y, r，表示一棵树在空地上的横、纵坐标和半径。

输出格式

输出一行包含一个整数，表示在不冲突下可以植树的面积和。由于每棵树的面积都是圆周率的整数倍，请输出答案除以圆周率后的值（应当是一个整数）。

样例输入

6
1 1 2
1 4 2
1 7 2
4 1 2
4 4 2
4 7 2

样例输出

12

评测用例规模与约定

对于 30% 的评测用例，1 <= n <= 10；
　　对于 60% 的评测用例，1 <= n <= 20；
　　对于所有评测用例，1 <= n <= 30，0 <= x, y <= 1000，1 <= r <= 1000。

题解
这题暂时没有好的解法，貌似是用dfs？？做不出来呀…

J题

问题描述
2015年，全中国实现了户户通电。作为一名电力建设者，小明正在帮助一带一路上的国家通电。
这一次，小明要帮助 n 个村庄通电，其中 1 号村庄正好可以建立一个发电站，所发的电足够所有村庄使用。
现在，这 n 个村庄之间都没有电线相连，小明主要要做的是架设电线连接这些村庄，使得所有村庄都直接或间接的与发电站相通。
　　小明测量了所有村庄的位置（坐标）和高度，如果要连接两个村庄，小明需要花费两个村庄之间的坐标距离加上高度差的平方，形式化描述为坐标为 (x_1, y_1) 高度为 h_1 的村庄与坐标为 (x_2, y_2) 高度为 h_2 的村庄之间连接的费用为
　　sqrt((x_1-x_2)(x_1-x_2)+(y_1-y_2)(y_1-y_2))+(h_1-h_2)*(h_1-h_2)。
　　在上式中 sqrt 表示取括号内的平方根。请注意括号的位置，高度的计算方式与横纵坐标的计算方式不同。
　　由于经费有限，请帮助小明计算他至少要花费多少费用才能使这 n 个村庄都通电。

输入格式

输入的第一行包含一个整数 n ，表示村庄的数量。
　　接下来 n 行，每个三个整数 x, y, h，分别表示一个村庄的横、纵坐标和高度，其中第一个村庄可以建立发电站。

输出格式

输出一行，包含一个实数，四舍五入保留 2 位小数，表示答案。

样例输入

4
1 1 3
9 9 7
8 8 6
4 5 4

样例输出

17.41

评测用例规模与约定

对于 30% 的评测用例，1 <= n <= 10；
　　对于 60% 的评测用例，1 <= n <= 100；
　　对于所有评测用例，1 <= n <= 1000，0 <= x, y, h <= 10000。

题解
本人比较菜，这题也不会做，如有大佬，请指教

总结

填空题比较简单，都是些简单的数学题…,编程题的前两个也比较简单，其中一个之前还做过；中间两个还勉强能做出来，螺旋矩阵 花费的时间比较多代码实现太繁琐了，还要考虑特殊情况；由于最近在学习、训练dp，自然而然地就想到用dp解决摆动矩阵 这道题目，思路有了，代码实现就比较简单；最后两道题不是我这种菜菜能解决的…,尽量弄明白了再回来补充题解，溜了溜了~~
da lao们请多指教