2022第十三届蓝桥杯省赛C/C++B组 真题题解
目录
特别说明：本文章运用了万能头文件#include <bits/stdc++.h>，会降低代码的运行效率，读者可根据实际情况进行更改。不难。
A.九进制转十进制
问题描述
九进制正整数(2022)₉转换成十进制等于多少？
法一：
2 * 9^3 + 0 * 9^2 + 2 * 9^1 + 2 * 9^0=1478
此题用代码简直是在浪费时间，填空题应该本着能省则省（省时间）的原则。
哈哈哈哈哈哈，难道这不是最简单的方法吗？
#include <bits/stdc++.h>
using namespace std;
int main()
{
cout << 2 * 9^3 + 0 * 9^2 + 2 * 9^1 + 2 * 9^0;
return 0;
}法一：老老实实的转换
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int main()
{
int x = 2022;
int a = 1;
int ans = 0;
while(x) {
ans += (x % 10) * a;
a = a * 9;
x /= 10;
}
cout << ans;
return 0;
}答案：1478
B.顺子日期
问题描述
小明特别喜欢顺子。顺子指的就是连续的三个数字：123、456等。顺子日期指的就是在日期的yyyymmdd表示法中，存在任意连续的三位数是一个顺子的日期。例如20220123就是一个顺子日期，因为它出现了一个顺子：123；而20221023则不是一个顺子日期，它一个顺子也没有。小明想知道在整个2022年份中，一共有多少个顺子日期。
思路
由于只需要判断2022年这一个年份，所以，只需要手写几个日期即可。此题具有很大的争议，很多人在讨论 012 算不算顺子，因为题目里说 0123 中的顺子是 123，我是算了的，不算的话答案应该是 4。
法一：日历
年份 2022 是不变的，而且不可能搭上顺子，所以只考虑后四位即可。
可能搭上顺子的月份有：
1月：0120 ~ 0129 共 10 个，顺子是 012 (其中 0123 可以认为顺子是 123)
10月：1012，顺子是 012
11月：1123，顺子是 123
12月：1230，1231，顺子是 123
一共 14 个
法二：代码
#include <bits/stdc++.h>
using namespace std;
int a[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31};
int main() {
int ans = 0;
for(int i = 20220101; i <= 20221231; i++) {
int m = (i % 10000) / 100;
int d = (i % 100);
if(m > 12) continue;
if(d == 0 || d > a[m])continue;
string tmp = "";
int t = i;
while(t) {
int aa = t % 10;
tmp = tmp + (char)('0' + aa);
t = t / 10;
}
reverse(tmp.begin(),tmp.end());
int a1 = tmp.find("123");
int a2 = tmp.find("012");
//注释代码表示逆序也算顺子
//int a3 = tmp.find("321");
//int a4 = tmp.find("210");
//if(a1 != -1||a2 != -1||a3 != -1||a4 != -1){
if(a1 != -1||a2 != -1) {
cout<<i<<endl;
++ans;
}
}
cout<<ans<<endl;
}答案：14
C.刷题统计
问题描述
小明决定从下周一开始努力刷题准备蓝桥杯竞赛。
他计划周一至周五每天做 a 道题目，周六和周日每天做 b 道题目。
请你帮小明计算，按照计划他将在第几天实现做题数大于等于 n 题？
输入格式
输入一行包含三个整数 a,b 和 n。
输出格式
输出一个整数代表天数。
评测用例规模与约定
对于 50% 的评测用例，1≤a,b,n≤106.
对于 100% 的评测用例，1≤a,b,n≤1018.
样例输入
10 20 99
样例输出
8
思路
取余：看 1E15 的数据规模，暴力模拟的话稳稳超时，可以先算出每周可以做多少题，然后利用除法和取余，就能把取余后的做题量控制在一周内，再判断一下一周内的五天能不能做完，就比较简单了。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b, n, k;
LL ans = 0;
int main() {
cin >> a >> b >> n;
k = a * 5 + b + b;
ans += n / k * 7;
n %= k;
if (n <= a * 5) {
ans += n / a + (n % a != 0);
}
else {
n -= a * 5;
ans += 6 + (n > b);
}
cout << ans << endl;
return 0;
}
D.修剪灌木
问题描述
爱丽丝要完成一项修剪灌木的工作。
有 N 棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为 0 厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始，每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。
然后如此循环往复。灌木每天从早上到傍晚会长高 1 厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是 0 厘米。爱丽丝想知道每棵灌木最高长到多高。
输入格式
一个正整数 N，含义如题面所述。
输出格式
输出 N 行，每行一个整数，第行表示从左到右第 i 棵树最高能长到多高。
评测用例规模与约定
对于 30% 的数据，N≤10，
对于 100% 的数据，1<N≤10000。
样例输入
3
样例输出
4
2
4
评测用例规模与约定
对于 30% 的数据，N ≤ 10.
对于 100% 的数据，1< N ≤ 10000.
思路
贪心算法：注意每棵灌木在被修剪得那天还会先长高 1 厘米，然后再被修剪，对于每棵灌木，长到最高的时间段有两种可能：被剪后往右剪再拐回来，和被剪之后往左剪再拐回来，假设某个灌木左侧有 x 棵灌木，右侧有 y 棵，容易发现这颗灌木的最大高度是 max(x, y) * 2，它的左(右)侧每有一颗灌木被剪前它都会长高 1 厘米，包括它自己被剪之前。
代码
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x = max(i, n - i - 1);
cout << x * 2 << endl;
}
return 0;
}E.X进制减法
问题描述
进制规定了数字在数位上逢几进一。
X 进制是一种很神奇的进制，因为其每一数位的进制并不固定!例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X进制数 321 转换为十进制数为 65。
现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A-B 的结果最小可能是多少。
输入格式
第一行一个正整数 N，含义如题面所述。
第二行一个正整数 Ma，表示 X 进制数 A 的位数。
第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。
第四行一个正整数 M, 表示X进制数 B 的位数。
第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。
请注意，输入中的所有数字都是十进制的。
输出格式
输出一行一个整数，表示X进制数 A - B 的结果的最小可能值转换为十进制后再模1000000007的结果。
样例输入
11
3
10 4 0
3
1 2 0
样例输出
94
样例说明
当进制为:最低位2进制，第二数位5进制，第三数位11进制时,减法得到的差最小。此时A在十进制下是108，B在十进制下是 14，差值是94.
评测用例规模与约定
对于30%的数据，N≤ 10; Ma, Mb ≤ 8.
对于100%的数据，2 < N ≤ 1000; 1 ≤ Ma, Mb, ≤ 100000; A ≥ B.
思路
推出进制计算方式:每一位数字,乘以该数字数位后所有进制数,求和即为结果
欲使A-B最小，只需使得各位数字取得合法范围内的最小进制即可，具体做法就是对A和B中相同数位的数字取xmax = max(a[i], b[i])，该位的合法最小进制即为max(xmax + 1, 2)
因为最小进制不能小于2；而对于X进制的数来说，合法的最大数字是X-1，例如8进制中最大数字是7，二进制中最大数字是1。
而求A和B的值，只需要再开一个数组存储各位数字的实际权重，再将各位数字和对应的权重相乘后相加即可。
需要注意的是这个题数据比较大，需要多次取模，特别是最后计算最终结果的时候，应(A - B + mod) % mod，否则可能A本来比B大，但是取模后比B小，这样A-B可能会出现负值。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10,mod=1000000007;
ll a[N],b[N],w[N],mul[N];
ll A,B;
//a存储A各位数字,b存储B各位数字,w存储各位的进制,mul存储各位数字的实际权重
int main(){
int n,ma,mb;
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];
// 确定各位进制 w[i]
int maxx=max(ma,mb); // A B 中最大的位数
for(int i=maxx;i>=1;i--){
int tmax=max(a[i],b[i]);
w[i]=max(2,tmax + 1);
}
// 计算权重
mul[1]=1;
for(int i=2;i<=maxx;i++){
mul[i]=w[i-1]*mul[i-1]%mod;
}
// 计算A
for(int i=ma;i>=1;i--){
A=(A+a[i]*mul[i])%mod;
}
// 计算B
for(int i=mb;i>=1;i--){
B=(B+b[i]*mul[i])%mod;
}
// A - B
cout<<(A-B+mod)%mod<<endl;
return 0;
}
F.统计子矩阵
问题描述
输入格式
输出格式
样例输入
样例输出
#include<iostream>
using namespace std;
const int N = 10010;
int n,m,k,a[N][N];
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
cin>>a[i][j];
a[i][j]+=a[i-1][j];
}
}
long long ans=0,l,r;
for(int i=1;i<=n;++i){
for(int j=0;j<i;++j){
int sum=0;
for(l=1,r=1;r<=m;++r){
sum+=a[i][r]-a[j][r];
while(sum>k){
sum-=a[i][l]-a[j][l];
l++;
}
if(r>=l)ans+=r-l+1;
}
}
}
cout<<ans;
}
评测用例规模与约定
G.积木画
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
H.扫雷
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
I.李白打酒加强版
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 105;
ll mp[N][N][N];
ll dfs(int n, int m, int k) {
if (k == 0) return (m == 0 && n == 0);
if (k > m || n >= m) return 0;
if (n == 0) return k == m;
if (mp[n][m][k] != -1) return mp[n][m][k];
ll ans = dfs(n, m - 1, k - 1) + dfs(n - 1, m, k + k);
ans %= MOD;
mp[n][m][k] = ans;
return ans;
}
int main() {
memset(mp, -1, sizeof mp);
int m, n;
cin >> n >> m;
cout << dfs(n, m, 2) << endl;
return 0;
}
J.砍竹子
问题描述
输入格式
输出格式
样例输入
样例输出
评测用例规模与约定