武工大2022蓝桥杯预选赛题解复现

第一次参加编程类的比赛，不懂规矩，没有任何技巧，赛场也犯了很多错误，但想去学习的心是非常真切的。时限内仅完成两道题目，趁学校公布了题解抓紧照猫画虎复现一遍，也顺便正式入门。

A. 还原

题目描述

寒假期间，痛恨英语的阿祥终于妥协了，他决定重新开始学习英语。但阿祥的英语实在是太差了，他得从最基础的数字开始复习。单纯的背单词也太无聊了吧，你说是不是？所以阿祥花了半天时间用小写英文（zero~nine，add, sub)写了一个超级长的英文加减法算式（当然，垃圾的阿祥不会写大于10的英文数字，全是逐字符翻译的，每个单词都用一个空格隔开），完成后他觉得非常有成就感，hh！！！

过年那天，阿祥家来了一个小屁孩，他趁阿祥上厕所的时候闯进阿祥的房间乱搞了一通。等阿祥回来的时候，他写的英文加减法算式已经面目全非了，他非常生气（_/）…。快气哭的阿祥突然发现，电脑的大写锁定一直开着，并且小屁孩保证没有删除任何一个字符，也没有按多余的空格，也就是说算式是有希望复原的。上厕所并没有让阿祥变成战神，希望你能帮他写一个复原程序，并求出算式的最终结果。（别问为啥不备份、不 Ctrl+z，他就是不会）。

注：zero、one、two、three、four、five、six、seven、eight、nine。加add，减sub。

输入描述:

一行字符串 $$s(1 ≤ len(s) < 50000)$$ ，包含除回车之外的字符，以回车结尾。（保证数字和结果在int范围内，空格隔开的子串会且只会包含一个合法单词）。

输出描述:

第一行：还原的英文加减法算式（每个单词间用空格隔开）

第二行：一个整数，表示加减法算式的结果

题解复现

  1. 字符串到数字的转换由 map 容器完成。

  2. 是否为小写字母由 islower() 函数判断。

  3. 直接使用 string 类型字符串且善用加减运算。

  4. 单行代码还是不打花括号好看。

  5. #include<bits/stdc++.h>

    ios::sync_with_stdio(false);

    cin.tie(0);

    这三句貌似打比赛常用，貌似。

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
#include<bits/stdc++.h>     //万能头文件，费时但好用
using namespace std;

int main() {
	ios::sync_with_stdio(false);   //不向C语言兼容，加速用
	cin.tie(0);                    //io不绑定，加速用
	map<string, int> num;
	num["one"] = 1; num["two"] = 2; num["three"] = 3; num["four"] = 4; num["five"] = 5;
	num["six"] = 6; num["seven"] = 7; num["eight"] = 8; num["nine"] = 9; num["zero"] = 0;
	
	string s;
	vector<string> vs;

	while (cin >> s) {
		string s2 = "";
		for (auto ch : s) if (islower(ch)) s2 += ch;
		vs.push_back(s2);
	}

	int x = 1, nmb = 0, sum = 0;
	for (auto &s0 : vs) {
		cout << s0 << " ";
		if (s0 != "add" && s0 != "sub") nmb = nmb * 10 + num[s0];
		else {
			sum += nmb * x;
			nmb = 0;
			if (s0 == "add") x = 1;
			else x = -1;
		}
	}
	if (nmb != 0) sum += nmb * x;

	cout << "\n" << sum;
	return 0;
}

B. 接雨水

题目描述

地上有一个nn 行mm 列的方格，每一个方格里面有11 个单位体积的雨水，横坐标的范围是1−n1−n ，纵坐标的范围是1−m1−m ;
现在你在(1,1)(1,1) 点开始接雨水（无论(1,1)(1,1) 这一点符不符合要求，这一个格子的雨水一定会被你接到），每次只能向上下左右方向移动一格。你只能移动到横坐标与纵坐标的数位之和在[k1,k2][k_1,k_2] 之间的格子然后接到里面的雨水。
请问你最多接到多少单位体积的雨水?
例：(123,456)(123,456) 横坐标与纵坐标的数位之和为1+2+3+4+5+6=211+2+3+4+5+6=21

输入描述:

第一行输入四个数字n,m,k1,k2n,m,k_1,k_2

输出描述:

输出最多能够接到的单位体积的雨水数量

题解复现

  1. BFS（广度优先搜索算法）

    BFS并不使用经验法则算法。从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实验里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表）

    大致就是，以一个点为中心，遍历边上所有点，再将符合条件的点分别作为中心，继续相同操作。在本题中先以原点为中心将上下左右符合条件的点加入队列，每次从队首取元素同时弹出该元素，以该点为中心继续做相同操作，这样就能保证每次加入队列的元素及其前辈元素均符合条件。

  2. 队列：queue

    函数功能
    .push()加入队尾
    .pop()弹出队首
    .front()访问队首
    .back()访问队尾
    .empty()队列判空
    .size()元素个数

  3. make_pair(type, type) 函数无需参数类型即可快速创建 pair 类型数据。

  4. pair 中的两个元素分别是 first 和 second ，只需要按正常结构体的方式去访问即可。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
typedef pair<int, int> pii;

int n, m, k1, k2;
bool grid[N][N];                   //标记方格
int dx[] = { 0, 1, 0, -1 };        //控制上下左右移动
int dy[] = { 1, 0, -1, 0 };

int get(int x, int y) {            //获取数位之和
	int sum = 0;

	while (x) {
		sum += x % 10;
		x /= 10;
	}
	while (y) {
		sum += y % 10;
		y /= 10;
	}

	return sum;
}

int bfs() {
	grid[1][1] = true;
	queue<pii> q;
	q.push(make_pair(1, 1));
	int count = 1;

	while (!q.empty()) {
		pii p = q.front();       //每次循环以队首元素为中心
		q.pop();                 //及时将队首弹出

		for (int i = 0; i < 4; i++) {
			int x = p.first + dx[i];
			int y = p.second + dy[i];
			if (x <= n && x >= 1 && y <= m && y >= 1 && !grid[x][y]) {
				grid[x][y] = true;
				int num = get(x, y);
				if (num <= k2 && num >= k1) {
					q.push(make_pair(x, y));
                    //只有前辈元素在需求范围内才有机会加入队列
					count++;
				}
			}
		}
	}

	return count;
}

int main() {
	cin >> n >> m >> k1 >> k2;
	cout << bfs();
	return 0;
}

C. 24点游戏

题目描述

小碘的妹妹喜欢玩2424 点的游戏。2424 点十棋牌类益智游戏，要求四个数字运算结果等于二十四，这个游戏用扑克牌更容易来开展。拿一副牌，抽去大小王后(也可以把J/Q/K/大小王也拿去)，剩下1～101～10 这4040 张牌。任意抽取44 张牌(称为牌组)，用加、减、乘、除(可加括号)把牌面上的数算成2424 。每张牌必须用且只能用一次。如抽出的牌是3、8、8、93、8、8、9 ，那么算式为(9−8)×8×3=24(9-8)×8×3=24 。 小碘的妹妹特别厉害，每次都能很快算出来，小碘想打败她就只能先改变2424 点的规则（可能因为他不会写2424 点的程序），然后写好程序，然后输入四个数，让系统自动生成解决方案。 小碘将2424 的规则变成：让系统随机给五个数字，问是否可以让前四个数字只通过加、减变成第五个数字。

输入描述:

第一行为一个整数T(1≤T≤100)T(1≤T≤100) ，表示测试组数。
接下来的TT 行，每行包括五个整数a,b,c,d,e(1≤a,b,c,d≤100000,1≤e≤400000)a,b,c,d,e(1{\leq}a,b,c,d{\leq}100000,1{\leq}e{\leq}400000) 。

输出描述:

每组测试用例，输出一行一个整数。如果前四个数字可以变成第五个数字，输出YESYES ，否则输出NONO 。

题解复现

  1. 送分题，但是我只会暴力枚举，官方题解提供了两种解法：二进制枚举与 DFS （深度优先搜索）
  2. 二进制枚举即 0000 ~ 1111 ，0 表示减，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<bits/stdc++.h>
using namespace std;

int x;          //全局变量，不用向函数传递参数
int a[4];

bool f() {
	for (int i = 0; i < 16; i++) {
		int sum = 0;
		for (int j = 0; j < 4; j++) {
			if (i >> j & 1) sum += a[j];
			else sum -= a[j];
		}
		if (sum == x) return true;
	}
	return false;
}

int main() {
	int n;
	cin >> n;

	while (n--) {
		for (int i = 0; i < 4; i++) cin >> a[i];
		cin >> x;
		if (f()) cout << "YES" << endl;     //若用 puts() 会方便一点
		else cout << "NO" << endl;
	}

	return 0;
}
  1. DFS 类似于 BFS ，但是顾名思义，他会先沿一条线遍历到终点再返回遍历分支。
  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
#include<bits/stdc++.h>
using namespace std;

int x;
int a[4];

bool f(int n, int m) {
	if (n == 4) return m == x;
	return f(n + 1, m + a[n]) || f(n + 1, m - a[n]);
}

int main() {
	int n;
	cin >> n;

	while (n--) {
		for (int i = 0; i < 4; i++) cin >> a[i];
		cin >> x;
		if (f(0, 0)) cout << "YES" << endl;
		else cout << "NO" << endl;
	}

	return 0;
}

D. 奇怪的管子

题目描述

lxy 在生日时收到了一件特殊的礼物，这件礼物由一个奇形怪状的管子和一些盘子组成.。这个管子是由许多不同直径的圆筒（直径也可以相同）同轴连接而成.。这个管子的底部是封闭的，顶部是打开的。下图是由直径为：5cm，6cm，4cm，3cm，6cm，2cm and 3cm 的圆筒组成的管子。

图D-1

每个圆筒的高度都是相等的，玩具中所带的盘子也是一些高度和它们相同的圆筒，直径有大有小。
lxy 发明了一种游戏，把盘子从管子顶部一个接一个的扔下去，他想知道最后这些盘子落在了哪，假设盘子落下过程中圆心和管子的轴一直保持一致，比如说我们丢下去三个盘子：3cm，2cm and 5cm，下图展示了最终它们的停止位置：
图D-2
如图可以知道,盘子掉下去以后，要么被某个圆筒卡住，要么就是因为掉在了以前的一个盘子上而停住。
lxy 想知道他最后扔下去的那个盘子掉在了哪个位置，你来帮他吧。

输入描述:

第一行两个整数nn 和m(1≤n,m≤300000)m ( 1{\leq}n,m{\leq} 300 000) 表示水管包含的圆筒数以及盘子总数。
第二行给出nn 个整数r1,r2,...,rn(1≤ri≤1000000000,1≤i≤n)r_1, r_2,...,r_n ( 1 {\leq}r_i{\leq} 1 000 000 000 ,1{\leq}i{\leq}n) 表示水管从上到下所有圆筒的直径。第三行给出mm 个整数k1,k2,...,km(1≤kj≤1000000000,1≤j≤m)k_1, k_2,..., k_m ( 1{\leq} k_j{\leq} 1 000 000 000,1{\leq}j{\leq} m) 分别表示 lxy 依次扔下去的盘子直径。

输出描述:

一个整数输出最后一个盘子掉在了哪一层，如果盘子不能扔进水管,那么打印0。

题解复现

  1. 如果盘子比圆筒多，无论如何都会超出，因此可直接输出 0 结束。
  2. 如果存在比第一层宽的盘子，则无论如何都会超出，因此同样可直接输出 0 结束。
  3. 若上方圆筒比下方小，则下方圆筒直径对盘子无影响，可认为与上方等径。
  4. 盘子与圆筒逐个遍历即可，题目不涉及复杂算法，但逻辑关系较为严谨。
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
#include<bits/stdc++.h>
using namespace std;

int m, n;  //n是圆筒层数，m是盘子总数
long long r[300010], k[300010];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    //实测这两句能让效率提升不少

	cin >> n >> m;

	for (int i = n; i > 0; i--) cin >> r[i];
    //便于从底端开始
	for (int i = 1; i <= m; i++) cin >> k[i];

	if (n < m) {
		cout << 0;
		return 0;
	}

	for (int i = 1; i <= m; i++)
		if (k[i] > r[n]) {
			cout << 0;
			return 0;
		}

	for (int i = n; i > 1; i--) {
		if (r[i] < r[i - 1]) r[i - 1] = r[i];
        //圆筒整形，统一向蛇精脸发展
	}

	int x = 1;
	for (int i = 1; i <= m; i++) {
		for (int j = x; j <= n; j++) {
			if (r[j] >= k[i]) {
				x = j + 1;
				break;
			}
		}
		if (x > n) {
			cout << 0;
			return 0;
		}
	}

	cout << n - x + 2;
	return 0;
}

E. ACE 的多项式

题目描述

设P(x)和Q(x)为关于x的多项式：

P(x)=∑i=0naixi,Q(x)=∑i=0mbixiP(x) = \sum_{i = 0}^{n}{a_{i}x^{i}}, Q(x) = \sum_{i = 0}^{m}{b_{i}x^{i}}

则有，将两个多项式相乘可得P(x)Q(x)=∑i=0n+m(a∗b)ixiP(x)Q(x) = \sum_{i = 0}^{n + m}{(a*b)_{i}x^{i}} 其中 * 表示卷积运算，现在给出一个整数k，ACE请你计算出(a∗b)k(a*b)_{k} ，那么由于这个数可能会很大，只需要求出其除以998244353的余数。

提示：也就是说两个多项式相乘，我们给出其xkx_{k} 的系数，那么我们就只需要 for 一遍，ans =所有(ai∗bj)(满足i+j=k)的和所有(a_{i} * b_{j})(满足i + j = k)的和 ，关于求余数，就是取模运算，ai∗bja_{i}*b_{j} 处的 * 是乘法运算。

x,y两个数相加求余数就是ans = ( x +ｙ）％998244353；

x,y两个数相乘求余数就是ans = (1ll *x * y)％998244353；

乘上1ll ，防止爆int ，或者你可以使用自己的方法。

建议多取模，建议用long long .

输入描述:

第一行输入一个整数n,(1≤n≤1000000)n, ( 1 \leq n \leq 1000000 )
第二行输入n+1个整数，代表ai(0≤ai≤1e9)a_{i}( 0 \leq a_{i} \leq 1e9 )
第三行输入一个整数m,(1≤m≤1000000)m,( 1\leq m \leq 1000000 )
第四行输入m+1个整数,代表bi(0≤bi≤1e9)b_{i}(0 \leq b_{i} \leq 1e9)
第五行输入一个整数k,(0≤k≤n+m)k, (0 \leq k \leq n + m )

输出描述:

输出一个整数代表答案

题解复现

  1. 我是万万没想到这道题目被改得这么简单了。
  2. long long + for 循环遍历即可。
  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
#include<bits/stdc++.h>
using namespace std;
const int N = 2000010;  
//暂时没搞懂为什么要这么大，按题目应该1000000就够了。
using  ll = long long;
ll a[N], b[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m, k;

	cin >> n;
	for (int i = 0; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int i = 0; i <= m; i++) cin >> b[i];
	cin >> k;

	ll sum = 0;
	for (int i = 0; i <= min(n, k); i++)
		sum = (sum + (a[i] % 998244353 * b[k - i] % 998244353) % 998244353) % 998244353;
	cout << sum;
	return 0;
}

F. 异世旅行之冒险岛

题目描述

小精灵来到了异世界的冒险岛探险。冒险岛上有nn 个堡垒，编号从11 到nn ，每个堡垒都有一个藏宝盒，小精灵此次旅行正是要取得所有的藏宝盒。堡垒与堡垒之间可以互相通行，但也可能道路被巨石阻挡无法通行。堡垒与堡垒之间的道路上可能有怪物，每打败一个怪物，都需要花费小精灵11 点体力。如果小精灵想要从一个堡垒抵达另一个堡垒，那么要保证两个堡垒之间的道路不能被巨石阻挡，还要战胜这条道路上的所有怪物。小精灵体力并不是无限的，如果体力耗尽还没有取得所有的藏宝盒，那么小精灵将被困在冒险岛中。请你计算一下小精灵能不能取得所有的藏宝盒（小精灵不能透支体力与怪物作战，体力也没有恢复手段），完美地完成这次旅行。

注：小精灵可以从1号堡垒出发前往3号堡垒，花费0点体力，此时小精灵剩余体力值为1；第二次，小精灵从3号堡垒出发前往2号堡垒，花费1点体力。此时小精灵剩余体力值为0。所以，小精灵可以取得所有的藏宝盒。小精灵初始时可以在任意一个堡垒，但在之后，想要到达另一个堡垒就必须通过道路抵达。

输入描述:

第一行输入为n、m、hn、m、h 。nn 表示冒险岛上堡垒的数量，mm 表示可通行的道路数，hh 表示小精灵的初始体力值。
其中2≤n≤1e5，1≤m≤min(n∗(n−1)2，2e5)，1≤h≤1e9.2\leq n\leq 1e5，1\leq m\leq min\left( \frac{n*(n-1)}{2}，2e5 \right)，1\leq h \leq1e9.
接下来mm 行，每行三个整数u、v、wu、v、w 。表示uu 号堡垒和vv 号堡垒之间有一条可通行的道路，道路上有ww 个怪物（数据保证不会有重复的道路，并且u≠vu\ne v ）。
其中1≤u,v≤n,0≤w≤100.1\leq u,v \leq n,0\leq w \leq 100.

输出描述:

输出为单独的一行字符。
如果小精灵可以完美完成这次旅行，输出"YES"。
否则，输出“NO”。（输出不包含双引号）

题解复现

  1. 最小生成树

    边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。权值最小的生成树即最小生成树。

    最小生成树的性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。

    完成构造网的最小生成树必须解决下面两个问题：

    1. 尽可能选取权值小的边，但不能构成回路；

    2. 选取n－1条恰当的边以连通n个顶点。

    摘自 CSDN 博主@Superb_Day

  2. 并查集

    在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

    1. 查找

      1
      int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}

    2. 合并

      1
      void join(int x,int y){father[find(x)]=find(y);}

      摘自 CSDN 博主@Superb_Day

  3. Kruskal 算法

    克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用的最小边权的边（可以直接快排或者algorithm的sort）。每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通。

    摘自 CSDN 博主@Superb_Day

  4. INF=0x3f3f3f3f 常用于表示无穷大。

  5. sort(start,end,cmp)

    cmp用于规定排序的方法，可不填，默认升序。

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
#include<bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n, m, h;
int baol[100010];
struct load {
	int u, v, w;
} loads[200010];

bool f(load a, load b) { return a.w < b.w; };  //定义排序方法

int find(int x) { return baol[x] == x ? x : baol[x] = find(baol[x]); }
int kruskal() {
	int sum = 0, count = 1;
	for (int i = 0; i < n; i++) baol[i] = i;
	for (int i = 0; i < m; i++) {
		int a = loads[i].u, b = loads[i].v, c = loads[i].w;
		a = find(a);
		b = find(b);
		if (a != b) {
			baol[a] = b;
			sum += c;
			count++;
		}
	}

	if (count < n) return INF;
	return sum;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> h;
	for (int i = 0; i < m; i++) {
		cin >> loads[i].u >> loads[i].v >> loads[i].w;
	}

	sort(loads, loads + m, f);         //可使用 Lambda 表达式，如下
	//sort(loads, loads + m, [&](load a, load b) { return a.w < b.w; });
	if (kruskal() <= h) cout << "YES";
	else cout << "NO";

	return 0;
}