【蓝桥杯】分享一下省四选手的暴力做法（C/C++）

博主： Fivk
发布时间：2022 年 04 月 09 日
1532 次浏览
428字数
分类： C/C++ 代码笔记

### 试题 A: 九进制转十进制

##### 【问题描述】

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

##### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

这个没什么说的看代码：

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
	int ans = 2*9*9*9 + 2*9 + 2;
	cout << ans << endl << endl;

// 验证 
	while (ans) {
		cout << ans % 9;
		ans /= 9;
	}
	return 0;
}
```

1478
</div>

### 试题 B: 顺子日期

##### 【问题描述】

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

##### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

> 这个题枚举即可

```cpp
#include <bits/stdc++.h>
using namespace std;

int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int ans;

bool check2(string s) {
	int len = s.length();
	for (int i = 2; i < len; i ++) {
		if (s[i - 2] + 1 == s[i - 1] && s[i - 1] + 1 == s[i]) {
			return true;
		}
	}
	return false;
}

bool check(int yy, int dd) {
	if (dd > a[yy]) {
		return false;
	} else {
		return true;
	}
}

int main() {
	string str = "2022";
	string data = "";
	for (int yy = 1; yy <= 12; yy ++) {
		for (int dd = 1; dd <= 31; dd ++) {
			if (check(yy, dd)) {
				data = "";
				char ch;
				ch = '0' + yy / 10;
				data += ch;
				ch = '0' + (yy % 10);
				data += ch;

ch = '0' + dd / 10;
				data += ch;

ch = '0' + (dd % 10);
				data += ch;

if (check2(str + data)) {
					cout << str + data << endl;
					ans ++;
				}
			}
		}
	}
	cout << ans;

return 0;
}
```

输出：

![](https://blog.fivk.cn/usr/uploads/2022/04/168502641.png)

### 试题 C: 刷题统计

##### 【问题描述】

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

##### 【输入格式】

输入一行包含三个整数 a, b 和 n.
【输出格式】
输出一个整数代表天数。

##### 【样例输入】

```in
10 20 99
```

##### 【样例输出】

```out
8
```

##### 【评测用例规模与约定】

对于 50% 的评测用例，$1 ≤ a, b, n ≤ 10^6$
对于 100% 的评测用例，$1 ≤ a, b, n ≤ 10^{18}$

> 模拟

```cpp
#include <iostream>
using namespace std;

typedef long long ll;

ll a, b, n;

int main() {
	cin >> a >> b >> n;
	ll t = a * 5 + b * 2; // 一周的数量 
	ll c = n / t;	// 共可以多少周
	ll ans = c * 7;	// 记录天数
	ll res = c * t;	// 记录数量

if (res < n) {
		for (int i = 1; res < n && i <= 7; i ++) {
			if (i <= 5) res += a;
			else res += b;
			ans ++;
		}
	}

cout << ans;

return 0;
}
```

### 试题 D: 修剪灌木

##### 【问题描述】

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

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

##### 【输入格式】

一个正整数 N ，含义如题面所述。
【输出格式】
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。

##### 【样例输入】

```in
3
```

##### 【样例输出】

```out
4
2
4
```

##### 【评测用例规模与约定】

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

> 暴力

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e4 + 10;
int n;
long long h[N], m[N];

int main() {
	scanf("%d", &n);

for (int k = 1; k <= 2; k ++) {
		// 从左到右 
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				h[j] ++;
				if (h[j] > m[j]) m[j] = h[j];
			}
			h[i] = 0;
		}

// 从右到左 
		for (int i = n - 1; i >= 2; i --) {
			for (int j = 1; j <= n; j ++) {
				h[j] ++;
				if (h[j] > m[j]) m[j] = h[j];
			}
			h[i] = 0;
		}
	}

for (int i = 1; i <= n; i ++) {
		printf("%lld\n", m[i]);
	}

return 0;
}
```

### 试题 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 的结果。

##### 【样例输入】

```in
11
3
10 4 0
3
1 2 0
```

##### 【样例输出】

```out
94
```

##### 【样例说明】

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

##### 【评测用例规模与约定】

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

> 理解x进制是怎么回事就好了，用到了贪心和前缀乘积

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n;
int ma, mb, mc;
int a[N], b[N], c[N], Max[N];
long long A, B;

void re(int *arr, int n) {
	// 反转
	n ++;
	int len = n / 2;
	for (int i = 1; i <= len; i ++) {
		int temp = arr[i];
		arr[i] = arr[n - i];
		arr[n - i] = temp;
	} 
}

int main() {
	scanf("%d", &n);

// 输入a 
	scanf("%d", &ma);
	for (int i = 1; i <= ma; i ++) {
		scanf("%d", &a[i]);
	}
	re(a, ma);

// 输入b 
	scanf("%d", &mb);
	for (int i = 1; i <= mb; i ++) {
		scanf("%d", &b[i]);
	}
	re(b, mb);

// 得到进位（贪心）
	int len = max(ma, mb);
	for (int i = 1; i <= len; i ++) {
		Max[i] = max(a[i], b[i]) + 1;
		if (Max[i] < 2) Max[i] = 2;
	}

puts("\n\n");
	for (int i = 1; i <= ma; i ++) printf("%d ", a[i]);
	puts("\n\n");
	for (int i = 1; i <= mb; i ++) printf("%d ", b[i]);
	puts("\n\n");
	for (int i = 1; i <= len; i ++) printf("%d ", Max[i]);
	puts("\n\n");

// 得到进位权
	Max[0] = 2;
	for (int i = 2; i <= len; i ++) {
		long long w = ((long long)Max[i] * (long long)Max[i - 1]) % 1000000007;
		Max[i] = (int)w;
	}

// 相减
	for (int i = 1; i <= len; i ++) {
		c[i] = a[i] - b[i];
	}

long long ans = 0;

// 计算进位
	for (int i = 1; i <= len; i ++) {
		ans = (ans + (c[i] * Max[i - 1]) % 1000000007) % 1000000007;
	}

printf("%lld", ans);
	 
	return 0;
}
```

### 试题 F: 统计子矩阵

##### 【问题描述】

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

##### 【输入格式】

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

##### 【输出格式】

一个整数代表答案。

##### 【样例输入】

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

##### 【样例输出】

```out
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 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

> 这个题我用到了二维前缀和+暴力

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 1e3 + 10;
int n, m;
ll s[N][N];
ll res, ans, k;

ll Sum(int i, int j, int u, int v) {
	ll s1 = s[u][v];
	ll s2 = s[i - 1][v];
	ll s3 = s[u][j - 1];
	ll s4 = s[i - 1][j - 1];
	return s1 - s2 - s3 + s4;
}

int main() {
	scanf("%d %d %lld", &n, &m, &k);
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			scanf("%lld", &s[i][j]);
		}
	}

// 二维前缀和
	 for (int i = 1; i <= n; i ++) {
	 	for (int j = 1; j <= m; j ++) {
	 		s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + s[i][j];
	 	}
	 }

// 枚举每一个单元矩阵大小 
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			for (int u = i; u <= n; u ++) {
				for (int v = j; v <= m; v ++) {
					res = Sum(i, j, u, v);
					if (res <= k) ans ++;
				}
			}
		}
	}

printf("%lld", ans);

return 0;
}
```

### 试题 G: 积木画

##### 【问题描述】

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

![](https://blog.fivk.cn/usr/uploads/2022/04/658281113.png)

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

##### 【输入格式】

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

##### 【输出格式】

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

```in
3
```

【样例输出】

```out
5
```

##### 【样例说明】

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

![](https://blog.fivk.cn/usr/uploads/2022/04/2246368115.png)

##### 【评测用例规模与约定】

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

> 这个题不太会乱猜规律，猜不到乱写了

当时的代码：

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

int n;
long long ans;

int main() {
	scanf("%d", &n);
	if (n == 1) printf("1");
	else if (n == 2) printf("2");
	else {
		ans = 2;
		for (int i = 3; i <= n; i ++) {
			ans = (ans * ans + 1) % 1000000007;
		}
		printf("%lld", ans);
	}
	return 0;
}
```

### 试题 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，表示一个排雷火箭的信息。

##### 【输出格式】

输出一个整数表示答案。

##### 【样例输入】

```in
2 1
2 2 4
4 4 2
0 0 5
```

##### 【样例输出】

```out
2
```

##### 【样例说明】

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

![](https://blog.fivk.cn/usr/uploads/2022/04/3538998980.png)

##### 【评测用例规模与约定】

对于 40% 的评测用例：$0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 10^3, 1 ≤ r ≤ 10$.
对于 100% 的评测用例：$0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 5 × 10^4, 1 ≤ r ≤ 10.$

> 这个题纯暴力

```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 5e4 + 10;
int n, m;
long long ans;

struct node {
	int x, y, r;
	vector<int> child;
	int cnt = 0;
} a[N];
bool b[N];

void add(int i, int j) {
	// 计算圆心距 
	double L =  sqrt(pow(a[i].x - a[j].x, 2) + pow(a[i].y - a[j].y, 2));
	if (a[i].r > L) a[i].child.push_back(j);
	if (a[j].r > L) a[j].child.push_back(i);
}

long long dfs(int index) {
	long long res = 1;
	for (int i:a[index].child) {
		if (!b[i]) {
			b[i] = true;
			res = res + dfs(i);
		}
	}
	return res;
}

long long check(int x, int y, int r) {
	memset(b, 0, sizeof b);
	long long res = 0;
	for (int i = 1; i <= n; i ++) {
		// 计算圆心距 
		double L =  sqrt(pow(a[i].x - x, 2) + pow(a[i].y - y, 2));
		if (r > L && !b[i]) {
			b[i] = true;
			res = res + dfs(i); 
		}
	}
	return res;
}

int main() {
	scanf("%d %d", &n, &m);

int x, y, r;
	for (int i = 1; i <= n; i ++) {
		scanf("%d %d %d", &x, &y, &r);
		a[i].x = x;
		a[i].y = y;
		a[i].r = r;
	}

for (int i = 1; i <= n; i ++) {
		for (int j = 1; i <= n; i ++) {
			if (i != j) add(i, j);
		}
	}

for (int i = 1; i <= m; i ++) {
		scanf("%d %d %d", &x, &y, &r);
		ans = ans + check(x, y, r);
	}
	printf("%lld", ans);

return 0;
}
```

##### 试题 I: 李白打酒加强版

【问题描述】
话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

> 无事街上走，提壶去打酒。
> 逢店加一倍，遇花喝一斗。

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

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

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

##### 【输入格式】

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

##### 【输出格式】

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

##### 【样例输入】

```in
5 10
```

##### 【样例输出】

```out
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。

> 额，直接dfs暴力好吧qvq

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

int n, m;
long long ans = 0;

void dfs(int n, int m, int x) {
	if (n == 0 && m == 0 && x == 1) {
		ans = (ans + 1) % 1000000007;
		return;
	} else if (n == 0 && m == 0) {
		return;
	}

// 遇到花 
	if (m > 0) {
		if (x > 0) {
			dfs(n, m - 1, x - 1);
		}
	}

// 遇到店 
	if (n > 0) {
		dfs(n - 1, m, 2 * x);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	dfs(n, m - 1, 2);
	printf("%lld", ans);
	return 0;
}
```

### 试题 J: 砍竹子

##### 【问题描述】

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

他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一
段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以
把这一段竹子的高度都变为 $⌊\sqrt{\frac{H}{2}+1}⌋$其中 ⌊x⌋ 表示对 x 向下取整。小明想
知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。

##### 【输入格式】

第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
【输出格式】
一个整数表示答案。

##### 【样例输入】

```in
6
2 1 4 2 6 7
```

【样例输出】

```out
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^6$。
对于 100% 的数据，保证 $n ≤ 2 × 10^5, hi ≤ 10^{18}$。

> 这个题感觉策略不对，我用的是贪心

```cpp
#include <iostream>
#include <cstdio>
#include <cmath> 
#include <set>
#include <vector> 
#include <unordered_set>
using namespace std;

int n, t;
set<long long> v;
long long ans = 0;

int main() {

scanf("%d", &n);
	vector<unordered_set<long long>> arr(n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &t);
		v.insert(t);
	}

while (true) {
		if (v.size() == 1 && *v.begin() == 1) {
			break;
		}
		bool flag = true; 	// 判断是否砍断后有重复的合并即可 
		for (set<long long>::iterator it = v.begin(); it != v.end(); it ++) {
			long long res = *it;
			if (res == 1) continue; 
			res = sqrt(res/2 + 1);
			if (v.find(res) != v.end()) {
				// 有重复直接删除现在这个 
				v.erase(*it);
				flag = false; 
				break;
			}
		}
		if (flag) {
			// 砍掉后没有重复的，那么尝试砍掉其他的
			for (set<long long>::iterator it = v.begin(); it != v.end(); it ++) {
				long long res = *it;
				if (res > 1) {
					v.erase(res);
					res = sqrt(res/2 + 1);
					v.insert(res);
					break;
				}
			}
		}

// 判断是否与之前重复 
		int len = v.size(), index = 0;
		bool t = true;
		for (auto x:v) {
			if (arr[index].find(x) == arr[index].end()) {
				t = false;
				arr[index].insert(x);
			}
			index ++; 
		}
		if (t) ans --;
		ans ++;
	}
	ans ++;
	printf("%lld", ans);

return 0;
}
```

最后修改：2022 年 04 月 13 日

如果觉得我的文章对你有用，请随意赞赏

【蓝桥杯】分享一下省四选手的暴力做法（C/C++）

Fivk • 2022 年 04 月 09 日

### 试题 A: 九进制转十进制

##### 【问题描述】

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

##### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

这个没什么说的看代码：

```cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
	int ans = 2*9*9*9 + 2*9 + 2;
	cout << ans << endl << endl;

// 验证 
	while (ans) {
		cout << ans % 9;
		ans /= 9;
	}
	return 0;
}
```

1478
</div>

### 试题 B: 顺子日期

##### 【问题描述】

##### 【答案提交】

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

> 这个题枚举即可

```cpp
#include <bits/stdc++.h>
using namespace std;

int a[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int ans;

bool check2(string s) {
	int len = s.length();
	for (int i = 2; i < len; i ++) {
		if (s[i - 2] + 1 == s[i - 1] && s[i - 1] + 1 == s[i]) {
			return true;
		}
	}
	return false;
}

bool check(int yy, int dd) {
	if (dd > a[yy]) {
		return false;
	} else {
		return true;
	}
}

ch = '0' + dd / 10;
				data += ch;

ch = '0' + (dd % 10);
				data += ch;

if (check2(str + data)) {
					cout << str + data << endl;
					ans ++;
				}
			}
		}
	}
	cout << ans;

return 0;
}
```

输出：

![](https://blog.fivk.cn/usr/uploads/2022/04/168502641.png)

### 试题 C: 刷题统计

##### 【问题描述】

##### 【输入格式】

输入一行包含三个整数 a, b 和 n.
【输出格式】
输出一个整数代表天数。

##### 【样例输入】

```in
10 20 99
```

##### 【样例输出】

```out
8
```

##### 【评测用例规模与约定】

对于 50% 的评测用例，$1 ≤ a, b, n ≤ 10^6$
对于 100% 的评测用例，$1 ≤ a, b, n ≤ 10^{18}$

> 模拟

```cpp
#include <iostream>
using namespace std;

typedef long long ll;

ll a, b, n;

int main() {
	cin >> a >> b >> n;
	ll t = a * 5 + b * 2; // 一周的数量 
	ll c = n / t;	// 共可以多少周
	ll ans = c * 7;	// 记录天数
	ll res = c * t;	// 记录数量

if (res < n) {
		for (int i = 1; res < n && i <= 7; i ++) {
			if (i <= 5) res += a;
			else res += b;
			ans ++;
		}
	}

cout << ans;

return 0;
}
```

### 试题 D: 修剪灌木

##### 【问题描述】

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

##### 【输入格式】

一个正整数 N ，含义如题面所述。
【输出格式】
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。

##### 【样例输入】

```in
3
```

##### 【样例输出】

```out
4
2
4
```

##### 【评测用例规模与约定】

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

> 暴力

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 1e4 + 10;
int n;
long long h[N], m[N];

int main() {
	scanf("%d", &n);

for (int k = 1; k <= 2; k ++) {
		// 从左到右 
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				h[j] ++;
				if (h[j] > m[j]) m[j] = h[j];
			}
			h[i] = 0;
		}

// 从右到左 
		for (int i = n - 1; i >= 2; i --) {
			for (int j = 1; j <= n; j ++) {
				h[j] ++;
				if (h[j] > m[j]) m[j] = h[j];
			}
			h[i] = 0;
		}
	}

for (int i = 1; i <= n; i ++) {
		printf("%lld\n", m[i]);
	}

return 0;
}
```

### 试题 E: X 进制减法

##### 【问题描述】

##### 【输入格式】

##### 【输出格式】

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

##### 【样例输入】

```in
11
3
10 4 0
3
1 2 0
```

##### 【样例输出】

```out
94
```

##### 【样例说明】

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

##### 【评测用例规模与约定】

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

> 理解x进制是怎么回事就好了，用到了贪心和前缀乘积

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10;
int n;
int ma, mb, mc;
int a[N], b[N], c[N], Max[N];
long long A, B;

void re(int *arr, int n) {
	// 反转
	n ++;
	int len = n / 2;
	for (int i = 1; i <= len; i ++) {
		int temp = arr[i];
		arr[i] = arr[n - i];
		arr[n - i] = temp;
	} 
}

int main() {
	scanf("%d", &n);

// 输入a 
	scanf("%d", &ma);
	for (int i = 1; i <= ma; i ++) {
		scanf("%d", &a[i]);
	}
	re(a, ma);

// 输入b 
	scanf("%d", &mb);
	for (int i = 1; i <= mb; i ++) {
		scanf("%d", &b[i]);
	}
	re(b, mb);

// 得到进位（贪心）
	int len = max(ma, mb);
	for (int i = 1; i <= len; i ++) {
		Max[i] = max(a[i], b[i]) + 1;
		if (Max[i] < 2) Max[i] = 2;
	}

// 得到进位权
	Max[0] = 2;
	for (int i = 2; i <= len; i ++) {
		long long w = ((long long)Max[i] * (long long)Max[i - 1]) % 1000000007;
		Max[i] = (int)w;
	}

// 相减
	for (int i = 1; i <= len; i ++) {
		c[i] = a[i] - b[i];
	}

long long ans = 0;

// 计算进位
	for (int i = 1; i <= len; i ++) {
		ans = (ans + (c[i] * Max[i - 1]) % 1000000007) % 1000000007;
	}

printf("%lld", ans);
	 
	return 0;
}
```

### 试题 F: 统计子矩阵

##### 【问题描述】

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

##### 【输入格式】

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

##### 【输出格式】

一个整数代表答案。

##### 【样例输入】

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

##### 【样例输出】

```out
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 ≤ Ai j ≤ 1000; 1 ≤ K ≤ 250000000.

> 这个题我用到了二维前缀和+暴力

```cpp
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int N = 1e3 + 10;
int n, m;
ll s[N][N];
ll res, ans, k;

ll Sum(int i, int j, int u, int v) {
	ll s1 = s[u][v];
	ll s2 = s[i - 1][v];
	ll s3 = s[u][j - 1];
	ll s4 = s[i - 1][j - 1];
	return s1 - s2 - s3 + s4;
}

int main() {
	scanf("%d %d %lld", &n, &m, &k);
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= m; j ++) {
			scanf("%lld", &s[i][j]);
		}
	}

// 二维前缀和
	 for (int i = 1; i <= n; i ++) {
	 	for (int j = 1; j <= m; j ++) {
	 		s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + s[i][j];
	 	}
	 }

printf("%lld", ans);

return 0;
}
```

### 试题 G: 积木画

##### 【问题描述】

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

![](https://blog.fivk.cn/usr/uploads/2022/04/658281113.png)

##### 【输入格式】

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

##### 【输出格式】

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

```in
3
```

【样例输出】

```out
5
```

##### 【样例说明】

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

![](https://blog.fivk.cn/usr/uploads/2022/04/2246368115.png)

##### 【评测用例规模与约定】

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

> 这个题不太会乱猜规律，猜不到乱写了

当时的代码：

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

int n;
long long ans;

### 试题 H: 扫雷

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

##### 【输入格式】

##### 【输出格式】

输出一个整数表示答案。

##### 【样例输入】

```in
2 1
2 2 4
4 4 2
0 0 5
```

##### 【样例输出】

```out
2
```

##### 【样例说明】

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

![](https://blog.fivk.cn/usr/uploads/2022/04/3538998980.png)

##### 【评测用例规模与约定】

对于 40% 的评测用例：$0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 10^3, 1 ≤ r ≤ 10$.
对于 100% 的评测用例：$0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 5 × 10^4, 1 ≤ r ≤ 10.$

> 这个题纯暴力

```cpp
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 5e4 + 10;
int n, m;
long long ans;

struct node {
	int x, y, r;
	vector<int> child;
	int cnt = 0;
} a[N];
bool b[N];

long long dfs(int index) {
	long long res = 1;
	for (int i:a[index].child) {
		if (!b[i]) {
			b[i] = true;
			res = res + dfs(i);
		}
	}
	return res;
}

int main() {
	scanf("%d %d", &n, &m);

int x, y, r;
	for (int i = 1; i <= n; i ++) {
		scanf("%d %d %d", &x, &y, &r);
		a[i].x = x;
		a[i].y = y;
		a[i].r = r;
	}

for (int i = 1; i <= n; i ++) {
		for (int j = 1; i <= n; i ++) {
			if (i != j) add(i, j);
		}
	}

for (int i = 1; i <= m; i ++) {
		scanf("%d %d %d", &x, &y, &r);
		ans = ans + check(x, y, r);
	}
	printf("%lld", ans);

return 0;
}
```

##### 试题 I: 李白打酒加强版

【问题描述】
话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：

> 无事街上走，提壶去打酒。
> 逢店加一倍，遇花喝一斗。

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

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

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

##### 【输入格式】

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

##### 【输出格式】

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

##### 【样例输入】

```in
5 10
```

##### 【样例输出】

```out
14
```

##### 【样例说明】

如果我们用 0 代表遇到花，1 代表遇到店，14 种顺序如下：

---

##### 【评测用例规模与约定】

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

> 额，直接dfs暴力好吧qvq

```cpp
#include <iostream>
#include <cstdio>
using namespace std;

int n, m;
long long ans = 0;

void dfs(int n, int m, int x) {
	if (n == 0 && m == 0 && x == 1) {
		ans = (ans + 1) % 1000000007;
		return;
	} else if (n == 0 && m == 0) {
		return;
	}

// 遇到花 
	if (m > 0) {
		if (x > 0) {
			dfs(n, m - 1, x - 1);
		}
	}

// 遇到店 
	if (n > 0) {
		dfs(n - 1, m, 2 * x);
	}
}

int main() {
	scanf("%d %d", &n, &m);
	dfs(n, m - 1, 2);
	printf("%lld", ans);
	return 0;
}
```

### 试题 J: 砍竹子

##### 【问题描述】

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

##### 【输入格式】

第一行为一个正整数 n，表示竹子的棵数。
第二行共 n 个空格分开的正整数 hi，表示每棵竹子的高度。
【输出格式】
一个整数表示答案。

##### 【样例输入】

```in
6
2 1 4 2 6 7
```

【样例输出】

```out
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^6$。
对于 100% 的数据，保证 $n ≤ 2 × 10^5, hi ≤ 10^{18}$。

> 这个题感觉策略不对，我用的是贪心

```cpp
#include <iostream>
#include <cstdio>
#include <cmath> 
#include <set>
#include <vector> 
#include <unordered_set>
using namespace std;

int n, t;
set<long long> v;
long long ans = 0;

int main() {

scanf("%d", &n);
	vector<unordered_set<long long>> arr(n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &t);
		v.insert(t);
	}

return 0;
}
```

【蓝桥杯】分享一下省四选手的暴力做法（C/C++）

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【数据结构】图论算法_最短路径算法

【知识总结】信息安全原理与技术-第六章

【实用软件】bandzip解压软件

【c】利用二维数组转置行列式

【开发工具】zabbix3监控工具

【蓝桥杯】分享一下省四选手的暴力做法（C/C++）