devbox
Monodyee
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

2022年第十三届蓝桥杯大赛C/C++ 大学 B 组个人题解_2022年有几个顺子日期

作者：Monodyee | 2024-04-08 22:32:36

赞

踩

2022年有几个顺子日期

填空题

A: 九进制转十进制

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

答案
1478

  • 1
代码
#include<iostream>
#include<cmath>
#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;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

B: 顺子日期

小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日 期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺 子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期。

答案
14

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

程序题

C: 刷题统计

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在 第几天实现做题数大于等于 n 题？

输入格式

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

输出格式

输出一个整数代表天数。

【样例输入】
10 20 99 

  • 1
【样例输出】
8

  • 1
【评测用例规模与约定】

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

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

代码
#include<iostream>
#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;
}

  • 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

D: 修剪灌木

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

有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始， 每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。

灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的 早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。

【输入格式】

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

【输出格式】

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

【样例输入】
3

  • 1
【样例输出】
 4 2 4 

  • 1
【评测用例规模与约定】

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

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

思路

找规律

代码
#include<iostream>
#include<stack>
#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;
}

  • 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

E: X进制减法

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

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

现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A − B 的结果最小可能是多少。

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

【输入格式】

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

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

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

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

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

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

【输出格式】

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

【样例输入】
11
3
10 4 0
3
1 2 0

  • 1
  • 2
  • 3
  • 4
  • 5
【样例输出】
94

  • 1
【样例说明】

当进制为：最低位 2 进制，第二数位 5 进制，第三数位 11 进制时，减法 得到的差最小。此时 A 在十进制下是 108，B 在十进制下是 14，差值是 94。

【评测用例规模与约定】

对于 30% 的数据，N ≤ 10; Ma, Mb ≤ 8.

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

思路

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

代码
#include<iostream>
#include<cmath>
#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;
}

  • 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

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

  • 1
  • 2
  • 3
  • 4
【样例输出】
19

  • 1
【样例说明】

满足条件的子矩阵一共有 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 ≤ Aij ≤ 1000; 1 ≤ K ≤ 250000000

思路：

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

代码
#include<iostream>
#include<vector>
#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;
}

  • 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

G: 积木画

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

在这里插入图片描述

同时，小明有一块面积大小为 2 × N 的画布，画布由 2 × N 个 1 × 1 区域构 成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式？ 积木可以任意旋转，且画布的方向固定。

【输入格式】

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

【输出格式】

输出一个整数表示答案。由于答案可能很大，所以输出其对 1000000007 取 模后的值

【样例输入】
3

  • 1
【样例输出】
5

  • 1
【样例说明】

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

在这里插入图片描述

【评测用例规模与约定】

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

思路

dp[i] [k] i为第i列的情况，k为0时表示此列上填下空，为1时表示此列上空下填，为2时表示此列上下都填充。

则第i列的0可以由第i - 1列上空下填加上一块横块得到，可由第i - 1列全空（也就是i-2全满）加上一块到着的L得到。

第i列的1与0相似的方法由第i - 1列上填下空，第i - 1列全空得到。

第i列的2可由 i - 1列全满加上一块竖块得到，可由i - 2列加上两块横块得到，可由i - 1列上填下空和上空下填加一块L得到。

代码
#include<iostream>
#include<vector>
#define endl '\n'
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e7 + 5;
int dp[maxn][3];
void solve() {
	int n; cin >> n;
	dp[0][2] = 1, dp[1][2] = 1;
	for (int i = 2; i <= n; i++) {
		(dp[i][0] += dp[i - 1][1] + dp[i - 2][2]) %= mod;
		(dp[i][1] += dp[i - 1][0] + dp[i - 2][2]) %= mod;
		(dp[i][2] += (dp[i - 1][2] + dp[i - 2][2]) % mod + (dp[i - 1][0] + dp[i - 1][1]) % mod) %= mod;
	}
	cout << dp[n][2] << endl;
}
int main() {
	ios, tie;
	solve();
	return 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

H: 扫雷

小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下， 在一个二维平面上放置着 n 个炸雷，第 i 个炸雷 (xi , yi ,ri) 表示在坐标 (xi , yi) 处 存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。

为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射 m 个排雷火 箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj , yj ,rj) 表 示这个排雷火箭将会在 (xj , yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆， 在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的 炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？

你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个 炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。

【输入格式】

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

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

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

【输出格式】

输出一个整数表示答案。

【样例输入】
2 1
2 2 4
4 4 2
0 0 5

  • 1
  • 2
  • 3
  • 4
【样例输出】
2

  • 1
【样例说明】

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

在这里插入图片描述

【评测用例规模与约定】

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

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

思路

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

代码
#include<iostream>
#include<cstring>
#include<utility>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#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, node = 0, n, m, r;
double D;
inline double Dis(pii a, pii b) {
	int x = abs(a.first - b.first), y = abs(a.second - b.second);
	return sqrt(x * x + y * y);
}
void bfs() {
	int dex, len, to;
	pii tp;
	while (!q.empty()) {
		tp = q.front(); q.pop();
		dex = mpii[tp], len = vpii[dex].size();
		for (int i = 0; i < len; i++) {
			if (!Vis[mpii[vpii[dex][i]]]) {
				to = mpii[vpii[dex][i]];
				q.push(vpii[dex][i]);
				ans += Num[to];
				Vis[to] = true;
			}
		}
	}
}
void solve() {
	cin >> n >> m;
	pii pot, temp;
	for (int i = 0; i < n; i++) {
		cin >> pot.first >> pot.second >> r;
		//合并同坐标点
		if (!mpii[pot]) {
			mpii[pot] = ++node;
			Vis[mpii[pot]] = false;
		}
		++Num[mpii[pot]];
		Rad[mpii[pot]] = max(r, Rad[mpii[pot]]);
	}
	//建图
	for (auto it = mpii.begin(); it != mpii.end(); it++) {
		for (int i = it->first.first - Rad[it->second]; i <= it->first.first + Rad[it->second]; i++) {
			for (int j = it->first.second - Rad[it->second]; j <= it->first.second + Rad[it->second]; j++) {
				//检测该点是否存在
				temp.first = i, temp.second = j;
				if (mpii.find(temp) != mpii.end() && it->first != temp) {
					D = Dis(it->first, temp);
					if (Rad[it->second] < D)continue;
					vpii[it->second].push_back(temp);
				}
			}
		}
	}
	//引爆
	while (m--) {
		cin >> pot.first >> pot.second >> r;
		for (int i = pot.first - r; i <= pot.first + r; i++) {
			for (int j = pot.second - r, dex; j <= pot.second + r; j++) {
				//检测该点是否存在
				temp.first = i, temp.second = j;
				if (mpii.find(temp) != mpii.end() && !Vis[mpii[temp]]) {
					dex = mpii[temp];
					D = Dis(pot, temp);
					if (r < D)continue;
					q.push(temp);
					Vis[dex] = true;
					ans += Num[dex];
				}
			}
		}
	}
	bfs();
	cout << ans << endl;
}
int main() {
	ios, tie;
	solve();
	return 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
  • 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
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94

I: 李白打酒加强版

话说大诗人李白，一生好饮。幸好他从不开车。

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

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

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

这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花， 他正好把酒喝光了。

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

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

【输入格式】

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

【输出格式】

输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。

【样例输入】
5 10

  • 1
【样例输出】
14

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

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
【评测用例规模与约定】

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

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

思路

三维dp，dp[i] [j] [k]表示遇到i次店，j次花，酒为k斗的方案数。输出遇到m-1次花，n次酒店且酒的数量刚好为一斗，即可保证最后一次能遇到花且喝完酒。

代码
#include<iostream>
#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;
}

  • 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

J: 砍竹子

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

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 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

  • 1
  • 2
【样例输出】
5

  • 1
【样例说明】
其中一种方案：

 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 步完成

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
【评测用例规模与约定】

对于 20% 的数据，保证 n ≤ 1000, hi ≤ 106。

对于 100% 的数据，保证 n ≤ 2 × 105 , hi ≤ 1018。

思路

贪心，每次将进来的树封装进优先队列，依次取出最高的树，然后查看是否有与其高度相同并且相邻的树，有则合并为一棵树，使用魔法后再次扔进优先队列，直到队列最高树为1。

代码
#include<iostream>
#include<queue>
#include<cmath>
#define endl '\n'
#define ios ios::sync_with_stdio(false)
#define tie cin.tie(NULL),cout.tie(NULL)
using namespace std;
class Node {
public:
	long long l, r, h;
	Node(long long l, long long r, long long h) {
		this->l = l, this->r = r, this->h = h;
	}
    //高度越高越优先,左端点越小越优先
	inline friend bool operator< (const Node& a, const Node& b) {
		if (a.h == b.h)return a.l > b.l;
		else return a.h < b.h;
	}
};
priority_queue<Node> pq;
void solve() {
	int n; cin >> n;
	for (long long i = 1, temp; i <= n; i++) {
		cin >> temp;
		pq.push(Node(i, i, temp));
	}
	int ans = 0;
	while (!pq.empty()) {
		Node tp = pq.top(); pq.pop();
		if (tp.h == 1)break;
		while (!pq.empty()) {
			Node nxt = pq.top();
			//合并相同高度并且相邻的树
			if (nxt.h == tp.h && nxt.l == tp.r + 1) {
				tp.r = nxt.r; pq.pop();
			}
			else break;
		}
		tp.h = (long long)sqrt((tp.h >> 1) + 1);
		pq.push(tp);
		ans++;
	}
	cout << ans << endl;
}
int main() {
	ios, tie;
	solve();
	return 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
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

待补充…

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Monodyee/article/detail/388636
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号