<>2022第十三届蓝桥杯省赛C++B组个人题解

<>试题 A: 九进制转十进制

#include <iostream> #include <cmath> using namespace std; int main() { cout <<
2 * pow(9, 0) + 2 * pow(9, 1) + 0 * pow(9, 2) + 2 * pow(9, 3) << endl; return
0; }

<>试题 B: 顺子日期

20220123 20220321 20221123 20221230 20221231

20220123 20221123 20221230 20221231

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

orz

<>试题 C: 刷题统计

<>【样例输入】
10 20 99
<>【样例输出】
8

#include <iostream> using namespace std; int main() { int cnt = 1; long long
n; int a, b; cin >> a >> b >> n; long long sum = 0; while (sum < n) { if (cnt %
7 == 0 || cnt % 7 == 6) { sum += b; } else { sum += a; } cnt++; } //

#include <iostream> using namespace std; int main() { long long a, b, n; cin
>> a >> b >> n; int week = 5 * a + 2 * b; long long ans = n / week * 7; n %=
week; int sum = 0; for (int i = 1; i <= 7 && sum < n; i++) { if (i % 7 == 6 ||
i % 7 == 0) { sum += b; } else { sum += a; } ans++; } cout << ans << endl;
return 0; }
<>试题 D: 修剪灌木

<>【样例输入】
3
<>【样例输出】
4 2 4

// 暴力代码：来回走两次。注意回的时候要把两个边界去掉。 #include <iostream> #include <cstring> using
namespace std; const int maxn = 1e4 + 100; int a[maxn]; int maxHeight[maxn];
int main() { int n; while (cin >> n) { memset(a, 0, sizeof(a));
memset(maxHeight, 0, sizeof(maxHeight)); // 来回走两次 for (int today = 0; today <
n; today++) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] > maxHeight[i]) {
maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for (int today = n -
2; today > 0; today--) { for (int i = 0; i < n; i++) { a[i]++; if (a[i] >
maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } } } for
(int today = 0; today < n; today++) { for (int i = 0; i < n; i++) { a[i]++; if
(a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) { a[i] = 0; } }
} for (int today = n - 2; today > 0; today--) { for (int i = 0; i < n; i++) {
a[i]++; if (a[i] > maxHeight[i]) { maxHeight[i] = a[i]; } if (i == today) {
a[i] = 0; } } } for (int i = 0; i < n; i++) { cout << maxHeight[i] << " "; }
cout << endl << endl; } return 0; }

#include <iostream> using namespace std; const int maxn = 1e4 + 10; int
ans[maxn]; int main() { int n; cin >> n; for (int i = 0; i < n / 2; i++) {
ans[i] = ans[n - i - 1] = (n - i - 1) * 2; } // 奇数情况单独处理 ans[n / 2] = n / 2 *
2; for (int i = 0; i < n; i++) { cout << ans[i] << endl; } return 0; }
<>试题 E: X 进制减法

<>【样例输入】
11 3 10 4 0 3 1 2 0
<>【样例输出】
94

<>试题 F: 统计子矩阵

<>【样例输入】
3 4 10 1 2 3 4 5 6 7 8 9 10 11 12
<>【样例输出】
19

(21*10^8)

#include <iostream> using namespace std; int mat[550][550]; int main() { int
n, m; long long k; cin >> n >> m >> k; for (int i = 1; i <= n; i++) { for (int
j = 1; j <= m; j++) { cin >> mat[i][j]; } } long long sum = 0; long long cnt =
0; for (int h1 = 1; h1 <= n; h1++) { for (int h2 = h1; h2 <= n; h2++) { for
(int l1 = 1; l1 <= m; l1++) { for (int l2 = l1; l2 <= m; l2++) { sum = 0; for
(int h = h1; h <= h2; h++) { for (int l = l1; l <= l2; l++) { sum += mat[h][l];
} } if (sum <= k) { cnt++; } } } } } cout << cnt << endl; return 0; }
<>试题 G: 积木画

<>【样例输入】
3
<>【样例输出】
5

（是的，比如说，我倒数第二题就忘记取模了。。。。。

dp[n] 可以通过 dp[n - 1] 加上普通的一列得到

dp[n] 可以通过 dp[n - 2] 加上两块横的得到

dp[n] 可以通过 dp[n - 3] 加上两个三角形的堆起来得到，但要注意的是，这两个三角形的堆叠方式有两种，所以要加上两倍的 dp[n - 3]

dp[n]可以通过 dp[n - 4]

#include <iostream> using namespace std; const long long MOD = 1e9 + 7; const
int maxn = 1e7 + 100; long long dp[maxn]; int main() { int n; cin >> n; dp[0] =
1; dp[1] = 1; dp[2] = 2; dp[3] = 5; for (int i = 4; i <= n; i++) { //

+ dp[i - 4] * 2) % MOD; } cout << dp[n] << endl; return 0; }
<>试题 H: 扫雷

<>【样例输入】
2 1 2 2 4 4 4 2 0 0 5
<>【样例输出】
2

#include <iostream> #include <queue> #include <cmath> #include <map> using
namespace std; const int maxn = 50100; // 记录坐标和半径 int x_pos[maxn]; int
y_pos[maxn]; int radius[maxn]; bool vis[maxn]; // 用来记录这个点爆炸了没有 // 用于 bfs 的
struct，更方便处理 struct point { int x, y, r; // 将结构体放入 map 中，需要自己写一个 operator

(y == p.y) { return r < p.y; } return y < p.y; } return x < p.x; } };
map<point, int> all; double getDis(int x1, int y1, int x2, int y2) { return
sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } int bfs(point begin, int
n) { int cnt = 0; queue<point> q; q.push(begin); while (!q.empty()) { point cur
= q.front(); q.pop(); // 遍历以 2 倍半径为边长的正方形，找到其爆炸所涉及到的炸雷 for (int i = cur.y -
cur.r; i <= cur.y + cur.r; i++) { for (int j = cur.x - cur.r; j <= cur.x +
cur.r; j++) { if(getDis(j, i, cur.x, cur.y) > cur.r) { continue; } point temp;
temp.y = i, temp.x = j; for (int k = 0; k < n; k++) { if (!vis[k] && x_pos[k]
== temp.x && y_pos[k] == temp.y) { temp.r = radius[k]; q.push(temp); cnt++;
all[temp]--; vis[k] = true; // 标记为以爆炸 } } } } } return cnt; } int main() { int
n, m; cin >> n >> m; for (int i = 0; i < n; i++) { cin >> x_pos[i] >> y_pos[i]
>> radius[i]; vis[i] = false; // 初始化都还没有爆炸 } int x, y, r; for (int i = 0; i <
m; i++) { point p; cin >> p.x >> p.y >> p.r; cout << bfs(p, n) << '\n'; //
dev调试还不能用endl，否则就不能进入下一步 } return 0; }
<>试题 I: 李白打酒加强版

<>【样例输入】
5 10
<>【样例输出】
14

① 一共必须要且仅要经过 N 次店，M 次花
② 最后一次遇到的必须是花
③ 最后遇到花后，酒必须喝光
④ 在中途遇到花时，酒不能为空
#include <iostream> #include <string> #include <vector> using namespace std;
const int MOD = 1e9 + 7; void backTrack(vector<char>& temp, vector<vector<char>
>& ans, int n, int m, int nn, int mm, int jiu) { if (jiu < 0) return; //

(temp.size() == n + m) { if (jiu == 0 && temp.back() == '0') { //

backTrack(temp, ans, n, m, nn, mm + 1, jiu - 1); temp.pop_back();
temp.push_back('1'); backTrack(temp, ans, n, m, nn + 1, mm, jiu * 2);
temp.pop_back(); } int main() { int n, m; cin >> n >> m; int jiu = 2;
vector<char> temp; vector<vector<char> > ans; backTrack(temp, ans, n, m, 0, 0,
jiu); cout << ans.size() % MOD << endl; return 0; }

#include <iostream> using namespace std; const int MOD = 1e9 + 7; const int
maxn = 105; long long dp[maxn][maxn][maxn] = { 0 }; int main() { int n, m; cin
>> n >> m; // 初始化 dp dp[0][0][2] = 1; for (int i = 1; i <= n + m; i++) { for
(int j = 0; j <= i; j++) { for (int k = 0; k <= 100; k++) { // 遇到了花后抵达第 i 步
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k + 1]) % MOD; // 遇到了酒馆后抵达第 i 步 // 当
k % 2 == 0 时才有可能是从酒馆走来的，因为经过酒馆后酒就加倍了 if (j != 0 && k % 2 == 0) { dp[i][j][k] =
(dp[i][j][k] + dp[i - 1][j - 1][k / 2]) % MOD; } } } } cout << dp[n + m -
1][n][1] << endl; return 0; }
<>试题 J: 砍竹子

<>【样例输入】
6 2 1 4 2 6 7
<>【样例输出】
5

<>总结

① 注意题目要求，记得取模！
② 注意范围，可能要用 long long
③ 不要在一道题卡太长时间，比如我在 E 题卡了一个小时都没看懂题，就应该早早换题，最后换换思路再回来看或许反而能看懂了

GitHub

Gitee