2022第十三届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组（题解&解析）

记录刷题的过程、感悟、题解。

希望能帮到，那些与我一同前行的，来自远方的朋友😉

大纲：

 1、九进制转十进制-（解析）-简单的进制转化问题😄

 2、顺子日期-（解析）-考察日期

 3、刷题统计-（解析）-简单的除法问题🥲，千万别暴力，会超时

 4、修剪灌木-（解析）-真·贪心，主打一个观察能力🥲or 想象力

 5、X 进制减法-（解析）-进阶一点的进制转化，需要对进制转化，有更深层次的了解。

 6、统计子矩阵-（解析）-二维前缀和+滑动窗口，如果纯前缀和打暴力（只能过70%） 

 7、积木画-（解析）-太好了，我一直以为无解，原来能用线性dp做出来，太感动了(┬┬﹏┬┬)，原来还能让人做。

 8、扫雷-（解析）-啊，这道题出乎意料的简单，出在倒数第三题，简直了😇，很多人都做不到呐。

 9、李白打酒加强版-（解析）-记忆化搜索+dfs，单纯dfs定超时。|| dp也能解决。

 10、砍竹子-（解析）-这道题真是智者见智了，八仙过海、各显神通。我用的优先队列。😉

题目：

1、九进制转十进制

问题描述

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

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

运行限制

• 最大运行时间：1s
• 最大运行内存: 512M

  本题就是一道，简单的进制转化题目

  解析：(2022)9=2*9^0+2*9^1+0*9^2+2*9^3 

  2是基数、9是进制数

  #include 
  using namespace std;
  int main(){
  	string str="2022";
  	reverse(str.begin(),str.end());
  	int sum=0;
  	for(int i=0; in;
  	int cnt = 0;
  	int sum = n/(a*5+b*2);
  	int temp = n%(a*5+b*2);
  	if(temp>bn;
  	vector B(bn,0);
  	for(int j=bn-1; j>=0; --j) cin>>B[j];
    int sum = 0;
    int X = 1;
    for(int i=0; i

  6、统计子矩阵

  问题描述

  给定一个 N×M 的矩阵 A, 请你统计有多少个子矩阵 (最小 1×1, 最大 N×M) 满足子矩阵中所有数的和不超过给定的整数 K ?

  输入格式

  第一行包含三个整数 N,M 和 K.

  之后 N 行每行包含 M 个整数, 代表矩阵 A.

  输出格式

  一个整数代表答案。

  样例输入

  3 4 10
  1 2 3 4
  5 6 7 8
  9 10 11 12
  

  样例输出

  19
  

  样例说明

  满足条件的子矩阵一共有 19 , 包含:

  大小为 1×1 的有 10 个。

  大小为 1×2 的有 3 个。

  大小为 1×3 的有 2 个。

  大小为 1×4 的有 1 个。

  大小为 2×1 的有 3 个。

  评测用例规模与约定

  对于 30% 的数据, N,M≤20.

  对于 70% 的数据, N,M≤100.

  对于 100%的数据, 1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000

  运行限制

  • 最大运行时间：1s
  • 最大运行内存: 256M

    本质上就是一道二维前缀和+滑动窗口的集合，如果只用二维前缀和的话只能过70%

    #include 
    using namespace std;
    #define int long long
    const int N = 5e2 + 5;
    int arr[N][N]; 
    int n, m, K;
    signed main() {
        // 输入矩阵的行数、列数和阈值 K
        cin >> n >> m >> K;
        // 输入矩阵元素
        for (int i = 1; i  arr[i][j];
        // 计算每行的前缀和
        for (int i = 1; i