蓝桥杯小练

试题练习
字数统计: 1.2k   |   阅读时长≈ 5 分钟

　　记录“蓝桥杯”等赛事的练习，包括真题以及小练等。

1.计算器模拟

1.1 问题描述

　　模拟程序型计算器，依次输入指令，可能包含的指令有 　　　1.数字：'NUM X'，X为一个只包含大写字母和数字的字符串，表示一个当前进制的数 　　　2.运算指令：'ADD','SUB','MUL','DIV','MOD'，分别表示加减乘，除法取商，除法取余 　　　3.进制转换指令：'CHANGE K'，将当前进制转换为K进制(2≤K≤36) 　　　4.输出指令：'EQUAL'，以当前进制输出结果 　　　5.重置指令：'CLEAR'，清除当前数字 　　指令按照以下规则给出： 　　　数字，运算指令不会连续给出，进制转换指令，输出指令，重置指令有可能连续给出 　　　运算指令后出现的第一个数字，表示参与运算的数字。且在该运算指令和该数字中间不会出现运算指令和输出指令 　　　重置指令后出现的第一个数字，表示基础值。且在重置指令和第一个数字中间不会出现运算指令和输出指令 　　　进制转换指令可能出现在任何地方 　　运算过程中中间变量均为非负整数，且小于2^63。 　　以大写的'A'~'Z'表示10~35 　　输入格式 　　　第1行：1个n，表示指令数量 　　　第2..n+1行：每行给出一条指令。指令序列一定以'CLEAR'作为开始，并且满足指令规则 　　输出格式 　　　依次给出每一次'EQUAL'得到的结果 　　样例输入 　　　7 　　　CLEAR 　　　NUM 1024 　　　CHANGE 2 　　　ADD 　　　NUM 100000 　　　CHANGE 8 　　　EQUAL 　　样例输出 　　　2040

1.2 问题分析

　　由于输入为字符串类型，因此需要将字符串类型的“数字”转化为真实的N进制数方能进行运算。机器将N进制数自动转化为二进制进行运算并得到相应的结果。
　　这里我们考虑首先将NUM指令后，也即参与运算的字符数转化为十进制进行运算。在读取到EQUAL指令时再将十进制转化为相应的进制数回显。此外，使用res寄存结果，num变量存储操作数。

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
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
69
70
71
72
73
74
75
76
77
#include<iostream>  
#include<algorithm>  
#include<string>  
#include<cctype>  
using namespace std;

long long toNumber(string strNum, int radix) {
	long long flagNum = 0;
	int len = strNum.length();
	//转换为radix进制数
	for (int i = 0; i < len; i++) {
		if (isupper(strNum[i]))
			//当读取到大写字母时
			//注意(strNum - 'A' + 10)以及(strNum - '0')均可补齐差值部分
			flagNum = (strNum[i] - 'A' + 10) + flagNum * radix;
		else
			flagNum = (strNum[i] - '0') + flagNum * radix;
	}
	return flagNum;
}

string toString(long long num, int radix) {
	if (num == 0)  return "0";
	long long temp;
	string flag;
	while (num) {
		temp = num % radix;
		if (temp > 10)
			//意味着需要用字母表示对应进制数的数位
			flag.push_back(temp + 'A' - 10);
		else
			flag.push_back(temp + '0');
		num /= radix;
	}
	reverse(flag.begin(), flag.end());	//由于flag.push_back()将字符串倒置放入，这里需要将其倒序
	return flag;
}

int main(int argc, char* argv[]) {
	int n;		//命令行数
	int radix = 10;	//默认使用10进制进行中介运算
	int p = 0;	//用于操作判断
	int clear = 1;	//用于判断CLEAR指令状态
	string ord, input_strNum;	//定义指令以及输入的字符数字
	long long res = 0, num;
	cin >> n;
	while (n--) {
		cin >> ord;
		if (!ord.compare("NUM")) {
			if (clear) {
				cin >> input_strNum;
					res = toNumber(input_strNum, radix);
					clear = 0;
			}
			else {
				cin >> input_strNum;
					num = toNumber(input_strNum, radix);
			}
			if (p) {
				if (p == 1)  res += num;
				else if (p == 2)  res -= num;
				else if (p == 3)  res *= num;
				else if (p == 4)  res /= num;
				else if (p == 5)  res %= num;
				p = 0;
			}
		}
		else if (!ord.compare("CHANGE"))  cin >> radix;
		else if (!ord.compare("EQUAL"))  cout << toString(res, radix) << endl;
		else if (!ord.compare("ADD"))  p = 1;
		else if (!ord.compare("SUB"))  p = 2;
		else if (!ord.compare("MUL"))  p = 3;
		else if (!ord.compare("DIV"))  p = 4;
		else if (!ord.compare("MOD"))  p = 5;
	}
	return 0;
}

2.合根植物

2.1 问题描述

　　w星球的一个种植园，被分成 m * n 个小格子（东西方向m行，南北方向n列）。每个格子里种了一株合根植物。 　　这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。 　　如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？ 输入格式 　　第一行，两个整数m，n，用空格分开，表示格子的行数、列数（1

2.2 问题分析

　　这是典型的并查集问题，只需要集合归并后搜索即可。

2.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
32
33
34
35
36
37
#include <cstdio>
using namespace std;
const int maxn = 1e6 + 10;
int pre[maxn];

//初始化Union_Find_set并查集
void initUFset(int n) {
	for (int i = 0; i < n; i++)  pre[i] = i;
}
//查找树根
int find(int x) {
	return x == pre[x] ? x : pre[x] = find(pre[x]);
}
//联合树枝
void join(int x, int y) {
	int fx = find(x);
	int fy = find(y);
	if (fx != fy) pre[fy] = fx;
}

int main() {
	int m, n, k, x, y, total;
	scanf("%d%d%d", &m, &n, &k);
	total = m * n;
	initUFset(total);
	while (k--) {
		scanf("%d%d", &x, &y);
		join(x, y);
	}

	int ans = 0;
	for (int i = 1; i < total; i++) {
		if (find(i) == i)  ++ans;
	}
	printf("%d\n", ans);
	return 0;
}

2.4 注释

　　在Visual Studio 2019中运行代码会出现以下报错：
　　1AFmfP.jpg
　　并非代码bug，这里可考虑尝试以下方法解决编译器报错：
　　　方法一：在程序最前面（指在所有#include前的最前）加#define _CRT_SECURE_NO_DEPRECATE；
　　　方法二：在程序最前面加#define _CRT_SECURE_NO_WARNINGS；
　　　方法三：在程序最前面加#pragma warning(disable:4996)；
　　　方法四：把scanf、scanf改为scanf_s、fopen_s，具体方法请百度；
　　　方法五：无需在程序最前面加那行代码，只需在新建项目时取消勾选“SDL检查”即可；
　　　方法六：若项目已建立好，在项目属性里关闭SDL也行；
　　　方法七：在工程项目设置一下就行；将报错那个宏定义放到 项目属性 — C/C++— 预处理器 — 预处理器定义；
　　　方法八：在 项目属性 — c/c++ — 命令行 添加：/D _CRT_SECURE_NO_WARNINGS 就行了。

3.分考场

3.1 问题描述


　　n个人参加某项特殊考试。
　　为了公平，要求任何两个认识的人不能分在同一个考场。
　　求是少需要分几个考场才能满足条件。

输入格式
　　第一行，一个整数n(1

3.2 问题分析

　　采用回溯算法，每次有两种抉择，新建房间和放置入之前的某个房间（需要判断）

3.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define min(a, b) a > b ? b : a  
using namespace std;
const int N = 100 + 5;
int cnt[N];				//cnt[i]表示第i个room内人数
int relation[N][N];		//relation[i][j]表示i考生与j考生之间的关系
int room[N][N];			//room[i][j]表示第i个考场内第j个考生
int ans = 0x3f3f3f3f;	//最好情况的房间数
int n;					//参加考试的人数

void solve(int curStu, int roomNum) {	//curStu表示当前学生，roomNum表示当前考场编号
	if (roomNum > ans)  return;	//已经大于最好情况的ans个房间，剪枝
	if (curStu > n) {
		ans = min(ans, roomNum);
		return;
	}
	for (int i = 1; i <= roomNum; i++) {	//判断是否可以放入以前的考场
		bool legal = true;
		for (int j = 1, len = cnt[i]; j < len; j++) {	//判断是否和考场内的人相识
			if (relation[room[i][j]][curStu] == 1) {
				legal = false;				//有关系则跳出房间内循环，对下一房间进行判断
				break;
			}
			if (legal) {
				room[i][cnt[i]++] = curStu;	//将合法考生安放在当前考场内
				solve(curStu + 1, roomNum);	//在安排完毕上述考生后基于此房间进行下一个考生的安置
				cnt[i]--;					//若在下一考生未能安置在本房间，需要排除此考生并进入新房间
			}
		}
		//新建房间的操作
		room[roomNum + 1][cnt[roomNum + 1]++] = curStu;
		solve(curStu + 1, roomNum + 1);
		cnt[roomNum + 1]--;
	}
}

int main(int argc, char** argv) {
	int ord;
	scanf("%d%d", &n, &ord);
	while (ord--) {
		int x, y;
		scanf("%d%d", &x, &y);
		relation[x][y] = relation[y][x] = 1;
	}
	solve(1, 0);	//第一个考生必定新建房间，因此从0开始
	printf("%d\n", ans);
	return 0;
}

4.对局匹配

4.1 问题描述


　　小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是K的两名用户匹配在一起。如果两人分差小于或大于K，系统都不会将他们匹配。
　　现在小明知道这个网站总共有N名用户，以及他们的积分分别是A1, A2, … AN。
　　小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于K)？

输入格式
　　第一行包含两个个整数N和K。
　　第二行包含N个整数A1, A2, … AN。
　　对于30%的数据，1 <= N <= 10
　　对于100%的数据，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000

输出格式
　　一个整数，代表答案。

样例输入
　　10 0
　　1 4 2 8 5 7 1 4 2 8

样例输出
　　6
</font>

4.2 问题分析

　　如果把n个元素按照分数相差为k的用户分为一组，例如：
　　第一组：{0,k,2k,3k,……}，
　　第二组：{1,k+1,k+2,k+3,……}，
　　……等等

　　这样分组可以保证能各组之间不会被匹配，因为分叉不可能为k。因此可能匹配成功的玩家只可能从同组中产生，故只需在每个分组内尽量选取更多用户即可。使用cnt[score]表示分数为score的用户人数，假设现第i组有m个不同分数{x,x+k,x+2k,……,x+(m-1)k}，其中x表示该组的第一个人的积分，这里采用动态规划法来选择更多的人数。dp[j]表示前j个分数能够获得的最大用户（价值），很明显这里有两个选择：

　　1.选择j：dp[j] = dp[j-1];
　　2.不选j：dp[j] = dp[j-2] + cnt[score];

　　因此状态转义方程如下所示：
　　　　dp[i] = max{dp[i-1], dp[i-2] + cnt[score]}
　　　　其中score是此组中第i个分数值
　　需要注意的是，边界处（例如k=0）需要特殊处理

4.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
32
33
34
35
36
37
38
39
40
41
42
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
using namespace std;
int n, k;
const int maxn = 100000 + 7;
const int max_score = 100000;
int cnt[maxn];		//cnt[score]表示积分为score的人数
int temp[maxn];
int dp[maxn];

int main(int argc, char** argv) {
	while (scanf("%d%d", &n, &k) == 2) {
		memset(cnt, 0, sizeof(cnt));
		int score, ans = 0;
		for (int i = 1; i <= n; i++) {
			scanf("%d", &score);
			cnt[score]++;
		}
		if (k == 0) {		//如果分差0即可匹配
			for (int i = 0; i < max_score; i++) {
				if (cnt[i])  ans++;
			}
		}
		else {
			for (int i = 0; i < k; i++) {	//对于每积分组别
				int index = 0;
				for (int j = i; j < max_score; j += k) {
					temp[index++] = cnt[j];
				}
				dp[0] = temp[0];
				for (int j = 1; j < index; j++) {
					if (j == 1)  dp[j] = max(dp[0], temp[j]);	//边界
					else  dp[j] = max(dp[j - 1], dp[j - 2] + temp[j]);
				}
				ans += dp[index - 1];
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

　　

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2019-2024 鞠桥丹-QIAODAN JU
  • 访问人数: | 浏览次数:

请我喝杯蓝莓汁吧~

支付宝
微信