2022年第十三届蓝桥杯省赛C/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;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cout << max(i, n - i - 1) * 2 << endl;
}
return 0;
}
试题 E: X 进制减法（数学）
【样例输入】
11
3
10 4 0
3
1 2 0
【样例输出】
94
比赛时看了一个小时，读不懂题 orz…
这题十分的抽象，很难理解
这里先说明一下问题描述中的 321 是如何转换为 65 的
由题：个位是 2 进制，十位是 10 进制，百位是 8 进制。
题目第一行就说了：进制规定了数字在数位上逢几进一。意思是：个位每数 2 个，十位进 1，十位每数 10 个，百位进 1。
首先定义结果 sum = 0
① 看个位：个位为 1，那么只需数一次即可到 1，然后让结果加上 1，即 sum += 1
② 看十位：十位为 2，因为个位是二进制，所以十位要到 2 的话，就需要经过这样的变换：00 -> 01 -> 10 -> 11 -> 20。可以看出：十位每加 1，个位就需要变换 2 次，所以要使十位变成 2，则一共需要变换 2（十位的值） * 2（个位的进制） 次。然后让结果再加上它，即 sum += 2 * 2
③ 看百位：百位为 3，根据十位的分析，同理得：要使百位变成 3，则需要变换 3（百位的值） * 10（十位的进制） * 2（个位的进制）次。然后让结果再加上它，即 sum += 3 * 10 * 2
综上：321 转换为了 sum = 1 + 2 * 2 + 3 * 10 * 2 = 65
公式：
A = ( a[n - 1] * X[n - 2] * X[n - 3] * … * X[0] ) + ( a[n - 2] * X[n - 3] * X[n - 4] * … * X[0] ) + … + a[0]
B = ( b[n - 1] * X[n - 2] * X[n - 3] * … * X[0] ) + ( b[n - 2] * X[n - 3] * X[n - 4] * … * X[0] ) + … + b[0]
A - B = (( a[n - 1] - b[n - 1] ) * X[n - 2] * X[n - 3] * … * X[0] ) + (( a[n - 2] - b[n - 2] ) * X[n - 3] * X[n - 4] * … * X[0] ) + ( a[0] - b[0] )
优化：（秦九韶算法）
设 d[n - 1] = a[n - 1] - b[n - 1]
A - B = ((( d[n - 1] * X[n - 2] + d[n - 2] ) * X[n - 3] + d[n - 3] ) * X[n - 4] + … d[0] ) …
代码：
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 100;
int a[maxn];
int b[maxn];
int main() {
int n, m1, m2, m;
scanf("%d", &n);
scanf("%d", &m1);
// 逆序来存，确保让个位对齐，多余位置的值都是 0
for (int i = m1 - 1; i >= 0; i--) {
scanf("%d", &a[i]);
}
scanf("%d", &m2);
for (int i = m2 - 1; i >= 0; i--) {
scanf("%d", &b[i]);
}
m = max(m1, m2);
int res = 0;
for (int i = m - 1; i >= 0; i--) {
res = (res * max({ 2, a[i] + 1, b[i] + 1 }) % MOD + a[i] - b[i]) % MOD;
}
printf("%d\n", res);
return 0;
}
试题 F: 统计子矩阵（前缀和 + 双指针）
【样例输入】
3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】
19
注意 k 已经超了 int 范围（虽然我到不了那就已经超时了，但还是要注意的） 看错了看错了，k 的值是 2.5 * 10 ^ 8，而 int 的范围是 -21 4748 3648 ～ 21 4748 3647 (21 * 10 ^ 8)
方法①：前缀和 + 双指针
首先求出每一列的前缀和，然后利用双指针将若干行切割开
#include <iostream>
using namespace std;
const int maxn = 505;
int s[maxn][maxn];
int main() {
memset(s, 0, sizeof(s));
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j];
}
}
int res = 0;
// 上下边界
for (int up = 1; up <= n; up++) {
for (int down = up; down <= n; down++) {
int sum = 0;
// 左右边界
for (int left = 1, right = 1; right <= m; right++) {
sum += s[down][right] - s[up - 1][right];
while (sum > k) {
sum -= s[down][left] - s[up - 1][left];
left++;
}
res += right - left + 1;
}
}
}
printf("%d\n", res);
return 0;
}
方法②：暴力（过30%数据，比赛时不会做直接暴力 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: 扫雷（BFS）
【样例输入】
2 1
2 2 4
4 4 2
0 0 5
【样例输出】
2
赛前半小时又专门看了眼 BFS，用上了！
陷阱①：一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
陷阱②：有 m 个排雷火箭，但只要求在最后输出一个整数表示答案（我比赛时就输出了 m 次答案…）
#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 cnt = 0;
for (int i = 0; i < m; i++) {
point p;
cin >> p.x >> p.y >> p.r;
// 我比赛时输出了 m 次结果，裂开了
// int cnt = 0;
cnt += bfs(p, n);
// cout << cnt << endl;
}
cout << cnt << endl;
return 0;
}
试题 I: 李白打酒加强版（三维DP / 回溯）
【样例输入】
5 10
【样例输出】
14
泪目了，写题解发现 我 竟 然 忘记取模了忘记取模了忘记取模了5555555555
大家一定要记得取模！！！
做法一：三维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;
}
做法二：回溯法（比赛时用的方法）
年前和年后都练了一段时间的回溯，觉得特别有意思。
赛前半小时还专门看了一眼！！然后考试最后半个小时花了 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;
}
试题 J: 砍竹子
【样例输入】
6
2 1 4 2 6 7
【样例输出】
5
还剩最后十分钟，没时间做了，看了眼题也确实不会做。
总结
① 注意题目要求，记得取模！
② 注意范围，可能要用 long long
③ 不要在一道题卡太长时间，比如我在 E 题卡了一个小时都没看懂题，就应该早早换题，最后换换思路再回来看或许反而能看懂了
