很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

【蓝桥杯总决赛】第十三届蓝桥杯省赛C/C++B组个人题解_蓝桥杯十三届省赛题b组c++答案

作者：很楠不爱3 | 2024-04-25 02:15:44

踩

蓝桥杯十三届省赛题b组c++答案

2022年第十三届蓝桥杯省赛C/C++B组个人题解
试题 A: 九进制转十进制（数学）
试题 B: 顺子日期（语文）
试题 C: 刷题统计（模拟）
【样例输入】
【样例输出】
试题 D: 修剪灌木（找规律）
【样例输入】
【样例输出】
试题 E: X 进制减法（数学）
【样例输入】
【样例输出】
试题 F: 统计子矩阵（前缀和 + 双指针）
【样例输入】
【样例输出】
试题 G: 积木画（动态规划）
【样例输入】
【样例输出】
试题 H: 扫雷（BFS）
【样例输入】
【样例输出】
试题 I: 李白打酒加强版（三维DP / 回溯）
【样例输入】
【样例输出】
试题 J: 砍竹子
【样例输入】
【样例输出】
总结

试题 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 去掉

第三种答案：14
题目说的顺子是：连续的三个数字，并不是三位数。所以 012 也算是顺子。再由第二个例子 20221023 得知：210 这种逆序的不算顺子。
如果要算上 012，那么第二个例子就把 210 这种逆序的给否掉啦

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

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

我目前也不知道正确答案，只能等官方解释吧
orz

试题 C: 刷题统计（模拟）

【样例输入】

10 20 99

【样例输出】

在这里插入图片描述

陷阱：注意 a, b, n 要用 long long

#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: 修剪灌木（找规律）

【样例输入】

【样例输出】


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 进制减法（数学）

【样例输入】

【样例输出】

比赛时看了一个小时，读不懂题 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: 统计子矩阵（前缀和 + 双指针）

【样例输入】

【样例输出】

4748 3648 ～ 21 4748 3647 (21 * 10 ^ 8)

方法①：前缀和 + 双指针
首先求出每一列的前缀和，然后利用双指针将若干行切割开

#include <iostream>

#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;
}

#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];
                       }
                   }

那么又有问题了，黑客可否在服务器和公正机构之间，还有在客服端和公正机构之间做手脚尼？？

从理论是哪个来讲是可以这么做，也确实这么做了过后可以拿到密钥；

但是从实际出发，成本花销特别大，而且还是双倍，一般的黑客是做不到的，再说破解个密钥证书可能也会耗费好几年的时间，时间成本都大，所以从实际上来讲黑客不会这么做。

（网络这个东西没有绝对安全）

总结：

文章目录
前言

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/482757