2020 蓝桥杯模拟省赛模拟赛题目及代码记录，若有错误欢迎指正！
因为赛后没分数啥的也不知道哪道题对哪道题不对，只能靠做的时候的感觉所以可能会有疏漏。

# 1. 填空题

易知为 2018 在这里插入图片描述

# 2. 填空题

因为有两个字母重复，所以答案为 7！/ 2 = 2520 在这里插入图片描述

# 3. 填空题

4 对括号，可以枚举共有 14 种情况，也可以递归
在这里插入图片描述

	#include <iostream>
	#include <vector>
	using namespace std;
	typedef long long ll;
	ll n,ans,total;//total 表示要排的几对括号
	vector<char> v;
	void Permu(int sum,int l,int r) {// 剩余待排列括号数已经排好的括号数
	if(l < r) return; // 先排左括号再排右括号，且右括号一定是与左括号匹配的
	// 所以左括号只能 >= 右括号
	if(sum == 0) {
	ans++;
	vector<char>::iterator it;
	for(it = v.begin(); it != v.end(); it++) {
	cout << *it;
	}
	cout << endl;
	}
	if(l < total) {
	v.push_back('(');
	Permu(sum-1,l+1,r);
	v.pop_back();
	}
	if(r < total) {
	v.push_back(')');
	Permu(sum-1,l,r+1);
	v.pop_back();
	}
	}
	int main() {
	cin >> total;
	Permu(total*2,0,0);
	cout << ans << endl;
	return 0;
	}

在这里插入图片描述

# 4. 填空题

送分，12.5 10241024 = 13107200
4对括号，可以枚举共有14种情况，也可以递归

# 5. 编程题

字符串处理，防止溢出对 26 取余就好
在这里插入图片描述

	#include <iostream>
	#include <string>
	#define div 1000000007
	typedef long long ll;
	const int maxn = 100;
	using namespace std;
	string s;
	int main() {
	cin >> s;
	int len = s.length();
	for (int i = 0; i < len; i++) {
	s[i] = 'a' + (s[i]-'a'+3)%26;
	}
	cout << s << endl;
	return 0;
	}

# 6. 编程题

O (n) 复杂度应该能过所有样例…… 大概
在这里插入图片描述

	#include <iostream>
	#include <string>
	#define div 1000000007
	typedef long long ll;
	const int maxn = 1000000;
	using namespace std;
	ll n, a, b, c, ans;
	int main() {
	cin >> n;
	cin >> a >> b >> c;
	for (int i = 1; i <= n; i++) {
	if(i % a != 0 && i % b != 0 && i % c != 0) {
	ans++;
	}
	}
	cout << ans << endl;
	return 0;
	}

# 7. 编程题

跟校内模拟赛那道题挺像，用了记忆化递归，样例能过，且速度应该能过 80%，如有逻辑漏洞还请指正。

问题描述
如果一个序列的奇数项都比前一项大，偶数项都比前一项小，则称为一个摆动序列。即 a [2i]<a [2i-1], a [2i+1]>a [2i]。
小明想知道，长度为 m，每个数都是 1 到 n 之间的正整数的摆动序列一共有多少个。
输入格式
输入一行包含两个整数 m，n。
输出格式
输出一个整数，表示答案。答案可能很大，请输出答案除以 10000 的余数。
样例输入
3 4
样例输出
14
样例说明
以下是符合要求的摆动序列：
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
评测用例规模与约定
对于 20% 的评测用例，1 <= n, m <= 5；
对于 50% 的评测用例，1 <= n, m <= 10；
对于 80% 的评测用例，1 <= n, m <= 100；
对于所有评测用例，1 <= n, m <= 1000。

	#include <iostream>
	#include <cstring>
	#define div 10000
	typedef long long ll;
	const int maxn = 1000000;
	using namespace std;
	int n, m;
	ll ans;
	int rem[101][101][101];
	ll dfs(int m,int l, int r){
	// 长度为 m，每个数都是 l 到 r 之间的正整数的摆动序列一共有多少个
	if(rem[m][l][r] != -1) return rem[m][l][r];
	if(l > r) {
	rem[m][l][r] = 0;
	return rem[m][l][r];
	} else if(l == r) {
	rem[m][l][r] = 1;
	return rem[m][l][r];
	} else if(m == 1) {
	rem[m][l][r] = r-l+1;
	return rem[m][l][r];
	}

	if(m % 2 == 0) {// 偶数项都比前一项小则前一项只能在 i~r
	for(int i = l; i <= r; i++) {
	ans = (ans + dfs(m-1,i+1,r)) % div;
	}
	} else {// 奇数项都比前一项大则前一项只能在 l~i
	for(int i = l; i <= r; i++) {
	ans = (ans + dfs(m-1,l,i-1)) % div;
	}
	}
	rem[m][l][r] = ans%div;
	return rem[m][l][r];
	}
	int main() {
	memset(rem,-1,sizeof(rem));
	cin >> m >> n;
	cout << dfs(m,1,n) << endl;
	return 0;
	}

# 8. 编程题

螺旋矩阵，知道最大走多少步就好办了，顺序是右、下、左、上这样

问题描述
对于一个 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 列的元素的值。
样例输入
4 5
2 2
样例输出
15
评测用例规模与约定
对于 30% 的评测用例，2 <= n, m <= 20。
对于 70% 的评测用例，2 <= n, m <= 100。
对于所有评测用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m。

	#include <iostream>
	#include <cstring>
	#define div 10000
	typedef long long ll;
	const int maxn = 1000000;
	using namespace std;
	int n, m;
	int k = 1;
	int a[105][105];
	int main() {
	cin >> n >> m;
	int all = n*m;
	int r=1, c=1;// 行列
	a[r][c] = k;
	while(k < all) {// 进行上下左右的判断
	while(c+1 <= m && !a[r][c+1]) {// 当右边没走过且未出界时向右走
	a[r][++c] = ++k;
	}
	while(r+1 <= n && !a[r+1][c]) {// 当下边没走过且未出界时向下走
	a[++r][c] = ++k;
	}
	while(c-1 >= 1 && !a[r][c-1]) {// 当左边没走过且未出界时向左走
	a[r][--c] = ++k;
	}
	while(r-1 >= 1 && !a[r-1][c]) {// 当上边没走过且未出界时向上走
	a[--r][c] = ++k;
	}
	}
	cin >> r >> c;
	cout << a[r][c] << endl;
	return 0;
	}

# 9. 编程题

暂未解决

问题描述
小明和朋友们一起去郊外植树，他们带了一些在自己实验室精心研究出的小树苗。
小明和朋友们一共有 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。

# 10. 编程题

其实就是最小生成树，现学了 Prim 算法，在最后几分钟才交的卷，样例能过，有没有 bug 暂未测出

问题描述
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。

	#include <iostream>
	#include <cstring>
	#include <cmath>
	#define div 10000
	typedef long long ll;
	const int maxn = 1000;
	const int INF = 0x3f3f3f;
	using namespace std;
	int n, m;
	struct Village{
	int x,y,h;
	} v[maxn];
	double edge[maxn][maxn];
	int fa[maxn];//fa [i] 表示已加入的 V 中里该点最近的点编号
	int vis[maxn];// 该点是否已访问过
	double dist[maxn];
	double ans;
	//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)。
	void init() {
	for(int i = 2; i <= n; i++) {
	dist[i] = edge[1][i];
	}
	fa[1] = -1;
	vis[1] = 1;//// 收录初始点 1
	}
	double Prim() {
	init();
	for(int i = 2; i <= n; i++) {
	int min = INF;
	int v = -1;
	for(int j = 2; j <= n; j++) {
	if(!vis[j] && dist[j] < min) {
	min = dist[j];
	v = j;
	}
	}
	if(v != -1) {// 找到了最小的～收入 V
	vis[v] = 1;
	ans += dist[v];
	for(int j = 2;j <= n; j++) {// 更新距离 dist
	if(!vis[j] && edge[v][j] < dist[j]) {
	dist[j] = edge[v][j];
	fa[j] = v;
	}
	}
	}
	}
	return ans;
	}
	int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
	cin >> v[i].x >> v[i].y >> v[i].h;
	}
	for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= n; j++) {
	if(i == j) continue;
	double d = sqrt((v[i].x-v[j].x)(v[i].x-v[j].x)+(v[i].y-v[j].y)(v[i].y-v[j].y))
	+(v[i].h-v[j].h)*(v[i].h-v[j].h);
	edge[i][j] = edge[j][i] = d;
	}
	}
	double ans = Prim();
	printf("%.2f",ans);
	return 0;
	}

# 总结

此次模拟赛真实水平应该是 8 题上下，最后一题由于是现学的最小生成树所以并不算熟练，打算去多刷下这类题目，抓紧学习图论。

c++ 蓝桥杯数据结构