<>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 题卡了一个小时都没看懂题,就应该早早换题,最后换换思路再回来看或许反而能看懂了

技术
友情链接
码工具
Toolsou
API参考文档
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信