2022年蓝桥杯第十三届CC++大学B组真题及代码

目录

1A：九进制转十进制

2B：顺子日期（存在争议）

3C：刷题统计

解析代码（模拟）

4D：修剪灌木

解析代码（找规律）

5E：X进制减法

解析代码1（模拟）

解析代码2（数学）

6F：统计子矩阵

解析代码（二维前缀和+双指针）

7G：积木画

解析代码（dp+滚动数组）

8H：扫雷

解析代码（待续）

9I：李白打酒加强版

解析代码1（dp）

解析代码2（dp）

10J：砍竹子

 解析代码（待续）

---

1A：九进制转十进制

问题描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

九进制正整数 (2022)转换成十进制等于多少？

运行限制

• 最大运行时间：1s

• 最大运行内存: 512M

#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{// 请在此输入您的代码printf("%d",2+2*9+0+2*9*9*9); // 1478return 0;
}

---

2B：顺子日期（存在争议）

问题描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456 等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如 20220123 就是一个顺子日期，因为它出现了一个顺子：123； 而 20221023 则不是一个顺子日期，它一个顺子也没有。小明想知道在整个 2022 年份中，一共有多少个顺子日期?

运行限制

• 最大运行时间：1s

• 最大运行内存: 256M

#include <stdio.h>
#include <stdlib.h>int main(int argc, char *argv[])
{//直接手算，注意题中第三行，如果012不算就是4个，但答案是14//1230  1231//1123//1012//这些月份都没有：09  08 07 06 05 04 03 02//0120 0121 0122 0123 0124 0125 0126 0127 0128 0129printf("14");return 0;
}

---

3C：刷题统计

问题描述

小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 a 道题目, 周六和周日每天做 b 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 n 题?

输入格式

输入一行包含三个整数 a,b 和 n.

输出格式

输出一个整数代表天数。

样例输入

10 20 99

样例输出

8

运行限制

• 最大运行时间：1s

• 最大运行内存: 256M

---

解析代码（模拟）

//#include <bits/stdc++.h>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int a, b, n, i, week, day;cin >> a >> b >> n;week = n / (a * 5 + b * 2);day = week * 7;n -= (a * 5 + b * 2) * week;for (i = 1; i <= 5; ++i){if (n > 0){n -= a;day++;}}for (i = 1; i <= 2; ++i){if (n > 0){n -= b;day++;}}cout << day << endl;return 0;
}

---

4D：修剪灌木

---

解析代码（找规律）

        解决本题的关键是判断每棵灌木最高的高度，简单地思考不难发现该高度与该点距离左、右侧边界的距离相关。定义左侧边界距离为 i  - 1 ，则右侧边界可计算出为：n − i 。

//#include <bits/stdc++.h>
#include <iostream>
#define endl '\n'
#define int long long
using namespace std;signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n = 0;cin >> n;for (int i = 1; i <= n; ++i){cout << max(i - 1, n - i) * 2 << endl;}return 0;
}

---

5E：X进制减法

        很多同学不会做这道题是因为题目的意思没有理清楚。其实题目的要求很简单：给定了两个整数 A,B，这两个数每一位上可以是任意进制，但是A，B相同位上进制规则相同。举个例子：

• 若 X，Y，Z 分别代表 5,6,2 进制，则 A = 4*6*2 + 2*6 + 1 ,B = 3*6*2 + 5*6 + 0
• 如 X，Y，Z 分别代表 6,7,3 进制，则 A = 4*7*3 + 2*7 + 1 ,B = 3*7*3 + 5*7 + 0

无论每一位进制为何值，都需要满足：

• 进制数要大于改位的最大值
• 进制数的最小值为 2

满足上述要求的每一位进制所得到的数：A，B ，题目要求获取 A - B 的最小值。

---

解析代码1（模拟）

每一位最小可能得结果：max(a[i] ,b[i]) + 1（再和2取一下max，因为最小为二进制）

#include <iostream> //  D题：X 进制减法
#include <algorithm>
#define endl '\n'
#define int long long
using namespace std;
const int mod = 1000000007;
int n, ma, mb, a[100001], b[100001];signed main()
{cin >> n;cin >> ma;for (int i = 1; i <= ma; ++i)cin >> a[i];cin >> mb;for (int i = 1; i <= mb; ++i)cin >> b[i];if (ma > mb) // 高位补0{for (int i = ma; i > ma - mb; --i)b[i] = b[i - (ma - mb)];for (int i = 1; i <= ma - mb; ++i)b[i] = 0;}int res = 0;for (int i = 1; i <= ma; ++i){res *= max(max(a[i], b[i]) + 1, (int)2);res %= mod;res += a[i] - b[i];if (res < 0)res += mod;if (res >= mod)res -= mod;}cout << res;return 0;
}

---

解析代码2（数学）

        平时X进制的数，各位数字的进制是相同的，每位数字的权重是X^n（n为该位数字后面的位数），比如二进制1000中首位的1的权重是2^3=8;但是本题各位数字进制不同，该位数字的权重其实是后面各位数字的进制的乘积。

        欲使A-B最小，只需使得各位数字取得合法范围内的最小进制即可，具体做法就是对A和B中相同数位的数字取int tmax = max(a[i], b[i])，该位的合法最小进制即为max(tmax + 1, 2)，因为最小进制不能小于2；而对于X进制的数来说，合法的最大数字是X-1，例如8进制中最大数字是7，二进制中最大数字是1。

         而求A和B的值，只需要再开一个数组存储各位数字的实际权重，再将各位数字和对应的权重相乘后相加即可。需要注意的是这个题数据比较大，需要多次取模，特别是最后计算最终结果的时候，应(A - B + mod) % mod，否则可能A本来比B大，但是取模后比B小，这样A-B可能会出现负值。

#include <iostream> //  X 进制减法
#include <algorithm>
#define endl '\n'
#define int long long
using namespace std;
const int M = 100010, N = 1010, mod = 1000000007;
int a[M], b[M], w[M];  // a[] 存储A各位数字   b[] 存储B各位数字   w[] 存储各位的进制
int n;
int Ma, Mb;
int mul[M];  // 各位数字的实际权重
int A, B;signed main()
{cin >> n;  // 最大进制cin >> Ma;for (int i = Ma; i >= 1; --i) cin >> a[i];cin >> Mb;for (int i = Mb; i >= 1; --i) cin >> b[i];int MM = max(Ma, Mb);  // A B 中最大的位数for (int i = MM;i >= 1; --i) // 确定各位进制 w[i]{int tmax = max(a[i], b[i]);w[i] = max((int)2, tmax + 1);}mul[1] = 1;for (int i = 2; i <= MM; ++i) // 计算权重mul[i] = w[i - 1] * mul[i - 1] % mod;for (int i = Ma; i >= 1; --i) // 计算AA = (A + a[i] * mul[i]) % mod;for (int i = Mb; i >= 1; --i)  // 计算BB = (B + b[i] * mul[i]) % mod;cout << (A - B + mod) % mod << endl;return 0;
}

---

6F：统计子矩阵

---

解析代码（二维前缀和+双指针）

如果直接用 前缀和 + 暴力，复杂度将是O(N^4 )，

        优化的方法是：枚举子矩阵的 左边界i 和 右边界j，用快指针lower 枚举 子矩阵的下边界，慢指针upper 维护子矩阵的上边界。

        如果得到的子矩阵的权值和 大于 k，则慢指针s 前进，而子矩阵和必将单调不增，慢指针继续前进，直到 子矩阵的和 不大于k，慢指针没必要前进了，因为该子矩阵的所有宽度为 j - i + 1 的子矩阵（总共 t - s + 1 种）一定满足要求，更新该情况对答案的贡献 t - s + 1；反之，如果慢指针s越界（s > t），则不操作，直接进入下层循环

#include <iostream>
#define endl '\n'
#define int long long
using namespace std;
const int N = 5e2 + 3;
int n, m, k;
int arr[N][N];signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin >> n >> m >> k;for (int i = 1; i <= n; ++i){for (int j = 1; j <= m; ++j) // 直接在原数组基础得到前缀和数组{cin >> arr[i][j];arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];}}int ans = 0;for (int i = 1; i <= m; ++i){for (int j = i; j <= m; ++j){for (int left = 1, right = 1; right <= n; ++right){while (left <= right && arr[right][j] - arr[left - 1][j] - arr[right][i - 1] + arr[left - 1][i - 1] > k)++left;if (left <= right)ans += right - left + 1;}}}cout << ans << '\n';return 0;
}

---

7G：积木画

---

解析代码（dp+滚动数组）

#include <iostream> //  G题：积木画
#include <cstring>
#define endl '\n'
using namespace std;
#define int long long
const int mod = 1000000007;
int n, v[2][2], dp[2][2];
// 数组第1维表示上一行有没有积木，第二维表示下一行有没有积木，0是没有，1是有
inline void add(int& x, int y)
{x += y;x %= mod;
}signed main()
{cin >> n; // 用例：3dp[0][0] = 1;for (int i = 1; i <= n; ++i) // i表示第i列，{memset(v, 0, sizeof(v));add(v[0][0], dp[0][0]); // 00 能转变为的情况add(v[1][1], dp[0][0]);add(v[0][1], dp[0][0]);add(v[1][0], dp[0][0]);add(v[0][1], dp[1][0]); // 10 能转变为的情况add(v[1][1], dp[1][0]);add(v[1][0], dp[0][1]); // 01 能转变为的情况add(v[1][1], dp[0][1]);add(v[0][0], dp[1][1]); // 11 能转变为的情况memcpy(dp, v, sizeof(dp)); // 把dp给v}cout << dp[0][0];return 0;
}

---

8H：扫雷

---

解析代码（待续）

（待续）

---

9I：李白打酒加强版

---

解析代码1（dp）

状态表示：本题的解法是动态规划，定义三维数组 dp存储状态，d p [ i ] [ j ] [ k ]表示路上遇到了 i 次店，j 次花后，酒壶中酒剩余 k 斗的方法数。

初始化：初始情况李白没有遇到店、花，初始状态下酒壶中有 2 斗，因此定义 dp [ 0 ] [ 0 ] [ 2 ] = 1 为初始状态。

状态转移方程：

• 如果当前状态遇到一次店，即 i > 0且剩余酒的数量应该是之前的两倍，即 k % 2 == 0，此时 dp [ i ] [ j ] [ k ] + = dp [ i − 1 ] [ j ] [ k / 2 ] 
• 如果当前状态遇到一次花，即 j > 0，此时 dp [ i ] [ j ] [ k ] + = dp [ i ] [ j − 1 ] [ k + 1 ]，k+1 表示酒被喝掉了一斗。

返回值：因为最后一次遇到的一定是花且剩余酒的数量为 0 ，不妨将状态转换为：共遇到 n次店，m − 1次花且剩余酒的数量为 1，这样返回 dp [ n ] [ m − 1 ] [ 1 ]就是题目所求。

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int mod = 1000000007;
const int M = 110;
int dp[M * 2][M][M];signed main()
{memset(dp, 0, sizeof dp); // 0 表示花 1 表示店dp[0][0][2] = 1;int n, m;cin >> n >> m;for (int i = 0; i <= n; ++i){for (int j = 0; j <= m; ++j){for (int k = 0; k <= 101; ++k){if (i == 0 && j == 0)continue;if (i > 0 && !(k & 1)) // 店dp[i][j][k] += dp[i - 1][j][k / 2];if (j > 0) // 花dp[i][j][k] += dp[i][j - 1][k + 1];dp[i][j][k] %= mod;}}}cout << dp[n][m - 1][1];
}

---

解析代码2（dp）

#include <iostream>
#include <cstring>
#define endl '\n'
using namespace std;
const int mod = 1000000007;
const int M = 110;
int dp[M * 2][M][M];
inline void add(int& x, int y)
{x += y;x %= mod;
}signed main()
{// 第一维是遇到的建筑(店/花)，第二维是店，第三维是剩余的酒memset(dp, 0, sizeof dp);dp[0][0][2] = 1;int n, m;cin >> n >> m;for (int i = 1; i <= n + m; ++i) // 第i建筑{for (int j = 0; j <= n; ++j) // 第j个店，i-j 个花{for (int k = 0; k <= m + 1; ++k) // 还有k壶酒{if(dp[i - 1][j][k] != 0){if (j < n)add(dp[i][j + 1][min(k * 2, m + 1)], dp[i - 1][j][k]);if (i - 1 - j < m && k != 0)add(dp[i][j][k - 1], dp[i - 1][j][k]);}}}}cout << dp[n + m - 1][n][1];return 0;
}

---

10J：砍竹子

---

 解析代码（待续）

（待续）