2022年第十三届蓝桥杯大赛CC++ 大学 B 组个人题解

填空题 A: 九进制转十进制

九进制正整数 (2022)₉转换成十进制等于多少？

答案

1478

代码

#include
#include
#define endl '\n'
#define pii pair<int, int>
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int maxn = 1e5 + 5;
int arr[maxn];
void solve() {
	cout << pow(9, 3) * 2 + pow(9, 2) * 0 + pow(9, 1) * 2 + 2 << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

B: 顺子日期

小明特别喜欢顺子。

顺子指的就是连续的三个数字：123、456 等。

顺子日 期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺 子的日期。

例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。

小明想知道在整个 2022 年份中，一共有多少个顺子日期。

答案

14

20220120
20220121
20220122
20220123
20220124
20220125
20220126
20220127
20220128
20220129
20221012
20221123
20221230
20221231

程序题 C: 刷题统计

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。

他计划周一至周五每天 做 a 道题目，周六和周日每天做 b 道题目。

请你帮小明计算，按照计划他将在 第几天实现做题数大于等于 n 题？

输入格式

输入一行包含三个整数 a, b 和 n

输出格式

输出一个整数代表天数。

【样例输入】

10 20 99 

【样例输出】

8

【评测用例规模与约定】

对于 50% 的评测用例，1 ≤ a, b, n ≤ 10⁶ .

对于 100% 的评测用例，1 ≤ a, b, n ≤ 10¹⁸ .

代码

#include
#define endl '\n'
#define pii pair<int, int>
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int maxn = 1e5 + 5;
int arr[maxn];
void solve() {
	long long a, b, n;
	cin >> a >> b >> n;
	long long ans = 0, week = ((a * 5) + (b * 2));
	ans += (n / week) * 7;
	n %= week;
	for (int i = 0; i < 5; i++) {
		if (n > 0) {
			n -= a;
			ans++;
		}
		else {
			cout << ans << endl;
			return;
		}
	}
	for (int i = 0; i < 2; i++) {
		if (n > 0) {
			n -= b;
			ans++;
		}
		else {
			cout << ans << endl;
			return;
		}
	}
	cout << ans << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

D: 修剪灌木

爱丽丝要完成一项修剪灌木的工作。

有 N 棵灌木整齐的从左到右排成一排。

爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。

爱丽丝修剪灌木的顺序是从最左侧的灌木开始， 每天向右修剪一棵灌木。

当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。

直到修剪了最左的灌木后再次调转方向。

然后如此循环往复。

灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。

在第一天的 早晨，所有灌木的高度都是 0 厘米。

爱丽丝想知道每棵灌木最高长到多高。

【输入格式】

一个正整数 N ，含义如题面所述。

【输出格式】

输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。

【样例输入】

3

【样例输出】

 4 2 4 

【评测用例规模与约定】

对于 30% 的数据，N ≤ 10.

对于 100% 的数据，1 < N ≤ 10000.

思路

找规律

代码

#include
#include
#define endl '\n'
#define pii pair<int, int>
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int maxn = 1e5 + 5;
int arr[maxn];
void solve() {
	int n; cin >> n;
	int cnt = (n + 1) / 2;
	stack<int> si;
	for (int i = 1; i <= cnt; i++) {
		int temp = 2 * (n - i);
		cout << temp << endl;
		si.push(temp);
	}
	if (n & 1)si.pop();
	while (!si.empty()) {
		cout << si.top() << endl;
		si.pop();
	}
}
int main() {
	ios, tie;
	solve();
	return 0;
}

E: X进制减法

进制规定了数字在数位上逢几进一。

X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则 X 进制数 321 转换为十进制数为 65。

现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。

请你算出 A − B 的结果最小可能是多少。

请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数字要小于其进制。

【输入格式】

第一行一个正整数 N，含义如题面所述。

第二行一个正整数 M_a，表示 X 进制数 A 的位数。

第三行 M_a 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各 个数位上的数字在十进制下的表示。

第四行一个正整数 M_b，表示 X 进制数 B 的位数。

第五行 M_b 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各 个数位上的数字在十进制下的表示。

请注意，输入中的所有数字都是十进制的。

【输出格式】

输出一行一个整数，表示 X 进制数 A − B 的结果的最小可能值转换为十进 制后再模 1000000007 的结果。

【样例输入】

11
3
10 4 0
3
1 2 0

【样例输出】

94

【样例说明】

当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法 得到的差最小。

此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。

【评测用例规模与约定】

对于 30% 的数据，N ≤ 10; M_a, M_b ≤ 8.

对于 100% 的数据，2 ≤ N ≤ 1000; 1 ≤ M_a, M_b ≤ 100000; A ≥ B

思路

对于A，B两个数，当每一位上的进制足够小时，A与B也会最小，则A - B得到的数也最小

代码

#include
#include
#define endl '\n'
#define pii pair<int, int>
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int mod = 1000000007;
const int maxn = 1e5 + 5;
int arr[3][maxn], M[2];
int MAX[maxn];//在该位上最大的进制
long long num[maxn];
void solve() {
	int n; cin >> n;
	for (int i = 0; i < 2; i++) {
		cin >> M[i];
		int j = 0;
		if (i) j = M[0] - M[1];//使进制对齐
		for (j; j < M[0]; j++) {
			cin >> arr[i][j];
			MAX[j] = max(MAX[j], 1);//当出现0时也认为是2进制
			MAX[j] = max(MAX[j], arr[i][j]);
		}
	}
	num[M[0]] = 1;
	for (int i = M[0] - 1; i >= 0; i--) {
		num[i] = num[i + 1] * (MAX[i] + 1);
		num[i] %= mod;
	}
	//两数相减
	for (int i = M[0] - 1; i >= 0; i--) {
		if (arr[0][i] < arr[1][i]) {
			arr[0][i - 1]--;
			arr[0][i] += MAX[i] + 1;
		}
		arr[2][i] = arr[0][i] - arr[1][i];
	}	
	//转为10进制
	long long ans = 0;
	for (int i = 0; i < M[0]; i++) {
		ans += arr[2][i] * num[i + 1];
		ans %= mod;
	}
	cout << ans << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

F: 统计子矩阵

给定一个 N × M 的矩阵 A，请你统计有多少个子矩阵 (最小 1 × 1，最大 N × M) 满足子矩阵中所有数的和不超过给定的整数 K?

【输入格式】

第一行包含三个整数 N, M 和 K. 之后 N 行每行包含 M 个整数，代表矩阵 A.

【输出格式】

一个整数代表答案。

【样例输入】

3 4 10
1 2 3 4
5 6 7 8
9 10 11 12

【样例输出】

19

【样例说明】

满足条件的子矩阵一共有 19，包含：

大小为 1 × 1 的有 10 个。

大小为 1 × 2 的有 3 个。

大小为 1 × 3 的有 2 个。

大小为 1 × 4 的有 1 个。

大小为 2 × 1 的有 3 个。

【评测用例规模与约定】

对于 30% 的数据，N, M ≤ 20.

对于 70% 的数据，N, M ≤ 100.

对于 100% 的数据，1 ≤ N, M ≤ 500; 0 ≤ A_ij ≤ 1000; 1 ≤ K ≤ 250000000

思路：

二位前缀和预处理，我们先设定l，r为矩阵的左右边界，然后在用双指针确定矩阵的上下边界，维护一个满足区间

代码

#include
#include
#define endl '\n'
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int maxn = 505;
long long maze[maxn][maxn], n, m, k;
long long pre[maxn][maxn], ans = 0;
void solve() {
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> maze[i][j];
			pre[i][j] = pre[i][j - 1] + maze[i][j];
		}
	}
	//枚举矩阵左右两边
	for (int l = 1; l <= m; l++) {
		for (int r = l; r <= m; r++) {
			long long sum = 0;
			//i为矩阵上边界，j为矩阵下边界，当矩阵满足条件j向后走，不满足时i向后走维护一个满足区间
			for (int i = 1, j = 1; j <= n; j++) {
				sum += pre[j][r] - pre[j][l - 1];
				while (i <= n && sum > k) {
					sum -= pre[i][r] - pre[i][l - 1];
					i++;
				}
				ans += j - i + 1;
			}
		}
	}
	cout << ans << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

G: 积木画

小明最近迷上了积木画，有这么两种类型的积木，分别为 I 型（大小为 2 个单位面积）和 L 型（大小为 3 个单位面积）：

同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构 成。

小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？ 积木可以任意旋转，且画布的方向固定。

【输入格式】

输入一个整数 N，表示画布大小。

【输出格式】

输出一个整数表示答案。

由于答案可能很大，所以输出其对 1000000007 取 模后的值

【样例输入】

3

【样例输出】

5

【样例说明】

五种情况如下图所示，颜色只是为了标识不同的积木：

【评测用例规模与约定】

对于所有测试用例，1 ≤ N ≤ 10000000.

思路

当n为1时只有一种摆法，n为2时只有两种摆法，n为3时有五种摆法。

即dp[1] = 1,dp[2] = 2,dp[3] = 5;

dp[n] 为：

dp[n - 1]加上一列得到

dp[n - 2]加上两块横着的得到，这里不算两块竖着的，会和n - 1重复

dp[n - 3]加上两块L型得到，L型摆法有两种

所以：dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3] * 2

代码

#include
#include
#define endl '\n'
#define pii pair<int, int>
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int mod = 1000000007;
const int maxn = 1e7 + 5;
int dp[maxn];
void solve() {
	int n; cin >> n;
	dp[1] = 1, dp[2] = 2, dp[3] = 5;
	for (int i = 4; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] ;
		dp[i] %= mod;
	}
	cout << dp[n] << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

H: 扫雷

小明最近迷上了一款名为《扫雷》的游戏。

其中有一个关卡的任务如下， 在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (x_i , y_i ,r_i) 表示在坐标 (x_i , y_i) 处 存在一个炸雷，它的爆炸范围是以半径为 r_i 的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。

玩家可以发射 m 个排雷火 箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (x_j , y_j ,r_j) 表 示这个排雷火箭将会在 (x_j , y_j) 处爆炸，它的爆炸范围是以半径为 r_j 的一个圆， 在其爆炸范围内的炸雷会被引爆。

同时，当炸雷被引爆时，在其爆炸范围内的 炸雷也会被引爆。

现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。

一个点处可以存在多个 炸雷和排雷火箭。

当炸雷位于爆炸范围的边界上时也会被引爆。

【输入格式】

输入的第一行包含两个整数 n、m.

接下来的 n 行，每行三个整数 xi , yi ,ri，表示一个炸雷的信息。

再接下来的 m 行，每行三个整数 xj , yj ,rj，表示一个排雷火箭的信息。

【输出格式】

输出一个整数表示答案。

【样例输入】

2 1
2 2 4
4 4 2
0 0 5

【样例输出】

2

【样例说明】

示例图如下，排雷火箭 1 覆盖了炸雷 1，所以炸雷 1 被排除；炸雷 1 又覆 盖了炸雷 2，所以炸雷 2 也被排除。

【评测用例规模与约定】

对于 40% 的评测用例：0 ≤ x, y ≤ 10⁹ , 0 ≤ n, m ≤ 10³ , 1 ≤ r ≤ 10.

对于 100% 的评测用例：0 ≤ x, y ≤ 10⁹ , 0 ≤ n, m ≤ 5 × 10⁴ , 1 ≤ r ≤ 10.

思路

我的想法是将这些炸雷看成一个节点，如果这个炸雷的爆炸范围能波及到其他炸雷，也就是说这个节点能通向其他节点，位于同一点的炸雷可以看作一个炸雷，记录最大的爆炸半径就行了，那么这就变成了一个BFS了，但是我没有想到好的建图方法，用的暴力建图，只能过一半样例

代码

#include
#include
#include
#include
#include
#include
#include
#define endl '\n'
#define pii pair<int, int>
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int maxn = 5e4 + 5;
int Rad[maxn];//每个节点的最大爆炸范围
int Num[maxn];//记录该节点有几个炸雷
bool Vis[maxn];//记录该节点的炸雷是否爆炸
map<pii, int> mpii;//给每一个节点的炸雷定义一个下标
vector<pii> vpii[maxn];//邻接矩阵存图
queue<pii> q;
int ans = 0;
double Dis(pii a, pii b) {
	return sqrt(pow(abs(a.first - b.first), 2) + pow(abs(a.second - b.second), 2));
}
void Bfs() {
	while (!q.empty()) {
		pii tp = q.front(); q.pop();
		int dex = mpii[tp];
		int len = vpii[dex].size();
		for (int i = 0; i < len; i++) {
			int to = mpii[vpii[dex][i]];
			if (!Vis[to]) {
				q.push(vpii[dex][i]);
				ans += Num[to];
				Vis[to] = true;
			}
		}
	}
}
void solve() {
	int n, m; cin >> n >> m;
	int node = 0;
	for (int i = 1; i <= n; i++) {
		pii pot; cin >> pot.first >> pot.second;
		if (!mpii[pot])mpii[pot] = ++node;
		Vis[mpii[pot]] = false;
		Num[mpii[pot]]++;
		int r; cin >> r;
		Rad[mpii[pot]] = max(r, Rad[mpii[pot]]);
	}
	//暴力建图
	for (auto i = mpii.begin(); i != mpii.end(); i++) {
		for (auto j = i++; j != mpii.end(); j++) {
			double D = Dis(i->first, j->first);
			if (Rad[i->second] >= D)vpii[i->second].push_back(j->first);
			if (Rad[j->second] >= D)vpii[j->second].push_back(i->first);
		}
	}
	for (int i = 1; i <= m; i++) {
		pii pot; cin >> pot.first >> pot.second;
		int r; cin >> r;
		for (auto it = mpii.begin(); it != mpii.end(); it++) {
			if (Vis[it->second])continue;
			double D = Dis(pot, it->first);
			if (r >= D) {
				q.push(it->first);
				Vis[it->second] = true;
				ans += Num[it->second];
			}
		}
	}
	Bfs();
	cout << ans << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

I: 李白打酒加强版

话说大诗人李白，一生好饮。

幸好他从不开车。

一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。

他边走边唱：

无事街上走，提壶去打酒。

逢店加一倍，遇花喝一斗。

这一路上，他一共遇到店 N 次，遇到花 M 次。

已知最后一次遇到的是花， 他正好把酒喝光了。

请你计算李白这一路遇到店和花的顺序，有多少种不同的可能？

注意：壶里没酒 ( 0 斗) 时遇店是合法的，加倍后还是没酒；但是没酒时遇花是不合法的。

【输入格式】

第一行包含两个整数 N 和 M.

【输出格式】

输出一个整数表示答案。

由于答案可能很大，输出模 1000000007 的结果。

【样例输入】

5 10

【样例输出】

14

【样例说明】

如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100

【评测用例规模与约定】

对于 40% 的评测用例：1 ≤ N, M ≤ 10。

对于 100% 的评测用例：1 ≤ N, M ≤ 100。

思路

三维dp，dp[i] [j] [k]表示遇到i次店，j次花，酒为k斗的方案数。

输出遇到m-1次花，n次酒店且酒的数量刚好为一斗，即可保证最后一次能遇到花且喝完酒。

代码

#include
#define endl '\n'
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int mod = 1000000007;
const int maxn = 105;
int dp[maxn][maxn][maxn << 1];
void solve() {
	int n, m; cin >> n >> m;
	dp[0][0][2] = 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= 205; k++) {
				if (!(k & 1) && i)dp[i][j][k] += dp[i - 1][j][k >> 1];
				if (j)dp[i][j][k] += dp[i][j - 1][k + 1];
				dp[i][j][k] %= mod;
			}
		}
	}
	cout << dp[n][m - 1][1] << endl;
}
int main() {
	ios, tie;
	solve();
	return 0;
}

J: 砍竹子

这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的 高度为 h_i .

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。

魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以 把这一段竹子的高度都变为 ⌊   ⌊   H 2 ⌋ + 1 ⌋ \lfloor\ \sqrt {\lfloor\ \frac{H}{2} \rfloor + 1} \rfloor ⌊ ⌊ 2H​⌋+1 ​⌋，其中 ⌊x⌋ 表示对 x 向下取整。

小明想 知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

【输入格式】

第一行为一个正整数 n，表示竹子的棵数。

第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。

【输出格式】

一个整数表示答案。

【样例输入】

6
2 1 4 2 6 7

【样例输出】

5

【样例说明】

其中一种方案：

 2 1 4 2 6 7

→ 2 1 4 2 6 2 

→ 2 1 4 2 2 2 

→ 2 1 1 2 2 2 

→ 1 1 1 2 2 2 

→ 1 1 1 1 1 1 

共需要 5 步完成

【评测用例规模与约定】

对于 20% 的数据，保证 n ≤ 1000, h_i ≤ 10⁶。

对于 100% 的数据，保证 n ≤ 2 × 10⁵ , h_i ≤ 10¹⁸。

思路

不会

待补充…