©2020-2024 ioDraw All rights reserved
<>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; }
答案：1478
<>试题 B: 顺子日期
目前有很多争议，分为 3 种答案：4，5，14
我考试时写的答案是 5
不过我观察到网友更多的答案是 4
而比赛后当天晚上的蓝桥云课说的是 14（非官方）
我来总结一下：
第一种答案：5
看题，在说明 20220123时，说它出现了一个顺子：123。
所以可以认为是只有 123 这一个顺子，而 012 是不算顺子的。
然后在说明 20221023 时又涉及到了 210 这个逆着的顺子，但它说这不是一个顺子日期。因此认为这里更明确了 0
不可以被包括进去，而逆序的可以算是顺子。
20220123 20220321 20221123 20221230 20221231
第二种答案：4
即认为 012 和逆序的顺子（如 210）都不算是顺子，因此把上面的 20220321 去掉
20220123 20221123 20221230 20221231
第三种答案：14
题目说的顺子是：连续的三个数字，并不是三位数。所以 012 也算是顺子。再由第二个例子 20221023 得知：210 这种逆序的不算顺子。
如果要算上 012，那么第二个例子就把 210 这种逆序的给否掉啦
20220120 20220121 20220122 20220123 20220124 20220125 20220126 20220127
20220128 20220129 20221012 20221123 20221230 20221231
我目前也不知道正确答案，只能等官方解释吧
orz
<>试题 C: 刷题统计
<>【样例输入】
10 20 99
<>【样例输出】
8
陷阱：注意 a, b, n 要用 long long 存
考试时写的代码：只考虑到了 n 要用 long long 存，竟然没用 long long 存 a, b，还没考虑到时间可能还会超限
#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++; } //
当超出时退出while循环，所以答案需要减一。 cout << cnt - 1 << endl; return 0; }
赛后优化代码：先取余再暴力
#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
看了一个小时，读不懂题 orz…
<>试题 F: 统计子矩阵
<>【样例输入】
3 4 10 1 2 3 4 5 6 7 8 9 10 11 12
<>【样例输出】
19
注意 k 已经超了 int 范围（虽然我到不了那就已经超时了，但还是要注意的），int 范围是 -21 4748 3648 ～ 21 4748 3647
(21*10^8)
不会做，直接暴力了，6 个 for ！
#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
陷阱：注意要取模取模取模，经常有人忘记这回事！！！
（是的，比如说，我倒数第二题就忘记取模了。。。。。
这道题足足用了我三张白纸，我从 n = 1 画到了 n = 6，写了一个小时。
我认为 dp 就是找规律，可是，该死的是我 n = 6 的时候漏画了一种情况（三列横着的摆放），导致一直找不到规律。。。
这道题的规律是，第 n 列可以通过前面的排列，再加上那几种基础的排列得到。
第一种情况：
dp[n] 可以通过 dp[n - 1] 加上普通的一列得到
第二种情况：
dp[n] 可以通过 dp[n - 2] 加上两块横的得到
第三种情况：
dp[n] 可以通过 dp[n - 3] 加上两个三角形的堆起来得到，但要注意的是，这两个三角形的堆叠方式有两种，所以要加上两倍的 dp[n - 3]
第四种情况：（我考试的时候给漏掉了555
dp[n]可以通过 dp[n - 4]
加上由左右两个各一个三角形，中间若干个横块的组合得到，同第三种情况，这个组合可以倒过来，即有两种堆叠方式，因此要加上两倍的 dp[n - 4]
综上：dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3] * 2 + dp[n - 4] * 2
#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] = (((((dp[i - 1] + dp[i - 2]) % MOD) + dp[i - 3] * 2) % MOD)
+ dp[i - 4] * 2) % MOD; } cout << dp[n] << endl; return 0; }
<>试题 H: 扫雷
<>【样例输入】
2 1 2 2 4 4 4 2 0 0 5
<>【样例输出】
2
赛前半小时又专门看了眼 BFS，用上了！
陷阱：一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
#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
来排序，因为 map 本身是有序的 bool operator < (const point& p) const { if (x == p.x) { if
(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
泪目了，写题解发现 我 竟 然 忘记取模了忘记取模了忘记取模了5555555555
大家一定要记得取模！！！
做法一：回溯法（比赛时用的方法）
年前和年后都练了一段时间的回溯，觉得特别有意思。
赛前半小时还专门看了一眼！！然后考试最后半个小时花了 20min 就写出来了。
本来一下子就写出框架了，不过太着急了，很多题目条件没看清楚，导致找了好久错误，不过还好，这题答案错了的话就是比正确答案大一些，很容易发现错误。
主要错误如下：
① 一共必须要且仅要经过 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; //
如果遇到花却没酒了，则不符合条件 if (nn > n || mm > m) return; // 如果经过了多于 N 次店、M 次花，则不符合条件 if
(temp.size() == n + m) { if (jiu == 0 && temp.back() == '0') { //
如果最后到达的是店也不符合条件 ans.push_back(temp); } return; } temp.push_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; }
做法二：三维dp（赛后学习的优化方法）
三个维度分别对应：走了多少步、经过了多少家酒馆，酒壶中还剩多少酒
在走到第 n 步时，他可能是从花走来的，也有可能是从酒馆走来的，所以要加上上一步遇到花的所有可能走法，再加上上一步遇到酒馆的所有可能走法。
#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 题卡了一个小时都没看懂题，就应该早早换题，最后换换思路再回来看或许反而能看懂了