2022年蓝桥杯：第十三届蓝桥杯大赛软件赛省赛（全部正解做法&代码 C/C++ B组）

文章目录

• • 试题 A: 九进制转十进制
  • • 问题描述
    • 问题答案
  • 试题 B: 顺子日期
  • • 问题描述
    • 问题答案
  • 试题 C: 刷题统计
  • • 问题描述
    • 问题答案(正解)
  • 试题 D: 修剪灌木
  • • 问题描述
    • 问题答案(正解)
  • 试题 E: X 进制减法
  • • 问题描述
    • 问题答案(正解)
  • 试题 F: 统计子矩阵
  • • 问题描述
    • 问题答案(暴力百分之70&正解)
  • 试题 G: 积木画
  • • 问题描述
    • 问题答案(状态压缩DP未滚动数组版本&滚动数组优化DP&优化矩阵快速幂（没写）)都可以过
  • 试题 H: 扫雷
  • • 问题描述
    • 问题答案(暴力骗分&正解)
  • 试题 I: 李白打酒加强版
  • • 问题描述
    • 问题答案(暴力百分之40 & 正解)
  • 试题 J: 砍竹子(暴力百分之20 & 堆优化 & 性质方法（最快）正解)
  • • 问题描述
    • 问题答案

试题 A: 九进制转十进制

问题描述

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

问题答案

答案为： 1478

试题 B: 顺子日期

问题描述

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

问题答案

答案为：4 或者是 14 （我填的是4以为不包含012这种情况）

试题 C: 刷题统计

问题描述

【问题描述】
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天
做 a 道题目，周六和周日每天做 b 道题目。请你帮小明计算，按照计划他将在
第几天实现做题数大于等于 n 题br> 【输入格式】
输入一行包含三个整数 a, b 和 n.
【输出格式】
输出一个整数代表天数。
【样例输入】
10 20 99
【样例输出】
8
【评测用例规模与约定】
对于 50% 的评测用例，1 ≤ a, b, n ≤ 106.
对于 100% 的评测用例，1 ≤ a, b, n ≤ 1018

问题答案(正解)

数据范围为1e18,所以写法首先对一周进行取余，然后再进行判断7天就可以了。

试题 D: 修剪灌木

问题描述

【问题描述】
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌
木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，
每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开
始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。
灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的
早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
【输入格式】
一个正整数 N ，含义如题面所述。
【输出格式】
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。
【样例输入】
3
【样例输出】
424
【评测用例规模与约定】
对于 30% 的数据，N ≤ 10.
对于 100% 的数据，1 < N ≤ 10000

问题答案(正解)

我采用的方法是打表找规律，模拟一下这个操作打表一下找规律。

试题 E: X 进制减法

问题描述

【问题描述】
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制，因为其每一数位的进制并不固定！例如说某
种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则
X 进制数 321 转换为十进制数为 65。
现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确
定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进
制。请你算出 A B 的结果最小可能是多少。
请注意，你需要保证 A 和 B 在 X 进制下都是合法的，即每一数位上的数
字要小于其进制。
【输入格式】
第一行一个正整数 N，含义如题面所述。
第二行一个正整数 Ma，表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各
个数位上的数字在十进制下的表示。
第四行一个正整数 Mb，表示 X 进制数 B 的位数。
第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各
个数位上的数字在十进制下的表示。
请注意，输入中的所有数字都是十进制的。
【输出格式】
输出一行一个整数，表示 X 进制数 A B 的结果的最小可能值转换为十进
制后再模 1000000007 的结果。

问题答案(正解)

本质就是贪心，从低位到高位枚举max（{a+1,b+1，2}）的进制，并把进制乘进去。
举一个例子，就是你求2的1次方到2的10次方的和一样，不过这个乘的进制不是固定的变化而已。题意比较坑，看懂了还是好理解的。