2022 蓝桥杯省赛 C++ B组 解题代码

第十三届蓝桥杯省赛C++ B组题解

前言: 本题解不保证代码正确, 主要提供一种博主在比赛过程中的做题思路, 仅供参考. 如果您对本文有什么看法, 欢迎大佬们评论区交流.

本文首发于 2022.4.9

试题 A: 九进制转十进制

解题思路

我们可以通过进制转换的通俗写法, 把

    (
   
   
    2022
   
   
    
     )
    
    
     9
    
   
  
  
   (2022)_9
  
 
(2022)9​ 转化成10进制.

或者, 直接计算

    2
   
   
    ∗
   
   
    
     9
    
    
     0
    
   
   
    +
   
   
    2
   
   
    ∗
   
   
    
     9
    
    
     1
    
   
   
    +
   
   
    0
   
   
    ∗
   
   
    
     9
    
    
     2
    
   
   
    +
   
   
    2
   
   
    ∗
   
   
    
     9
    
    
     3
    
   
  
  
   2 * 9^0 + 2 * 9^1 + 0 * 9^2 + 2 * 9^3
  
 
2∗90+2∗91+0∗92+2∗93 填空.

参考答案:

1478

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;intmain(){int x =2022;int res =0, base =1;do{
        res += x %10* base;
        x /=10;
        base *=9;}while(x);printf("%d\n", res);/** 或者直接计算
    int qaq = 2 + 2 * 9 + 2 * 9 * 9 * 9;
    cout << qaq << endl;
    */return0;}

试题 B: 顺子日期

解题思路

直接暴力枚举所有情况即可.

我的做法可能稍微有些复杂, 思路就是转化成

yyyymmdd

的字符串, 然后判断是否存在顺子.

此处可以动脑, 例如字符串不用以"1"的形式存储, 年份"2022"无意义 等等等…

参考答案:

14

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;int month[]={0,31,28,31,30,31,30,31,31,30,31,30,31};

string fact(int x){
    string s;do{
        s +='0'+ x %10;
        x /=10;}while(x);reverse(s.begin(), s.end());if(s.size()==1) s ="0"+ s;return s;}booljudge(const string& s){int len =0, last =-2;for(int i =0; i < s.size();++i){int op = s[i]-'0';
        op == last +1?++len : len =1;

        last = op;if(len ==3)return1;}return0;}intmain(){int res =0;rep(m,12){rep(d, month[m]){
            string s ="2022"+fact(m)+fact(d);if(judge(s)) res++,printf("%s\n", s.c_str());}}

    cout << res << endl;return0;}

试题 C: 刷题统计

解题思路

我们很容易发现这个题考查了周期性.

每周做的题目数量:

 week = 5a + 2b

, 因此我们可以通过

    n
   
   
    u
   
   
    m
   
   
    =
   
   
    ⌊
   
   
    
     n
    
    
     
      w
     
     
      e
     
     
      e
     
     
      k
     
    
   
   
    ⌋
   
  
  
   num = \lfloor \frac{n}{week} \rfloor
  
 
num=⌊weekn​⌋来计算出答案包含

 
  
   
    n
   
   
    u
   
   
    m
   
  
  
   num
  
 
num个**整周**.然后再暴力最后一周的情况即可.

特别需要注意的是, 本题需要用

long long

,

ll

最大值可以大概认为是

     9
    
    
     ∗
    
    
     1
    
    
     
      0
     
     
      18
     
    
   
   
    9 * 10^{18}
   
  
 9∗1018, 因此
 
  
   
    
     w
    
    
     e
    
    
     e
    
    
     k
    
   
   
    week
   
  
 week并不会导致溢出.

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;intmain(){
    ll a, b, n; cin >> a >> b >> n;

    ll week =5* a +2* b;

    ll res = n / week *7;
    n %= week;rep(i,5)if(n >0) n -= a, res++;rep(i,2)if(n >0) n -= b, res++;

    cout << res << endl;return0;}

试题 D: 修剪灌木

解题思路

这题读完之后, 很容易能感觉到最优解是存在一个最小循环节的.

通常这种题我们保险起见可以进行如下模拟:

左 -> 右 -> 左 -> 右

这样理论上一定已经包含一个最小循环节了.

但是上述写法比较复杂, 我写完后发现了规律. 我们发现答案是具有对称性的.

例如

n = 6

答案:

10 8 6 6 8 10

, 我们结合

n = 3

答案

4 2 4

. 经过冷静分析(一顿瞎蒙)后, 我们发现这是个等差数列, 我们按照规律模拟输出即可.

特别的, 要注意模拟方式是否需要特判

n == 1

的情况, 此时答案为:

1

.

不会有一群人都挂在这上了吧, 不会吧不会吧???

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =1E5+10;int a[N];intmain(){int n; cin >> n;if(n ==1){printf("%d\n",1);return0;}rep(i,(n +1)/2){int l = i, r = n - i +1;
        a[l]= a[r]=(n - i)*2;}rep(i, n)printf("%d\n", a[i]);return0;}

试题 E: X 进制减法

解题思路

这题… 我拿到之后看了5分钟, 愣是不敢写. 别问, 问就是没读懂.

又是经过一顿冷静分析xia bi cai之后, 明白了.

解释样例: (以下数字为10进制下的含义)

假设把

     321
    
   
   
    321
   
  
 321放入数组
 
  
   
    
     a
    
    
     [
    
    
     ]
    
   
   
    a[]
   
  
 a[], 有 
 
  
   
    
     a
    
    
     [
    
    
     0
    
    
     ]
    
    
     =
    
    
     3
    
    
     ,
    
    
     a
    
    
     [
    
    
     1
    
    
     ]
    
    
     =
    
    
     2
    
    
     ,
    
    
     a
    
    
     [
    
    
     2
    
    
     ]
    
    
     =
    
    
     1
    
   
   
    a[0] = 3, a[1] = 2, a[2] = 1
   
  
 a[0]=3,a[1]=2,a[2]=1 .

现在

     a
    
    
     [
    
    
     1
    
    
     ]
    
    
     =
    
    
     2
    
   
   
    a[1] = 2
   
  
 a[1]=2这一位为
 
  
   
    
     10
    
   
   
    10
   
  
 10进制, 其高位有
 
  
   
    
     a
    
    
     [
    
    
     0
    
    
     ]
    
    
     =
    
    
     3
    
   
   
    a[0] = 3
   
  
 a[0]=3, 说明如果不产生进位, 那么有
 
  
   
    
     a
    
    
     [
    
    
     1
    
    
     ]
    
    
     =
    
    
     3
    
    
     ∗
    
    
     10
    
    
     +
    
    
     2
    
    
     =
    
    
     32
    
   
   
    a[1] = 3 * 10 + 2 = 32
   
  
 a[1]=3∗10+2=32.

同理: 对于

     a
    
    
     [
    
    
     2
    
    
     ]
    
    
     =
    
    
     1
    
   
   
    a[2] = 1
   
  
 a[2]=1, 其高位
 
  
   
    
     a
    
    
     [
    
    
     1
    
    
     ]
    
    
     =
    
    
     32
    
   
   
    a[1] = 32
   
  
 a[1]=32(我们刚计算的), 如果不进位, 则
 
  
   
    
     a
    
    
     [
    
    
     0
    
    
     ]
    
    
     =
    
    
     32
    
    
     ∗
    
    
     2
    
    
     +
    
    
     1
    
    
     =
    
    
     65
    
   
   
    a[0] = 32 * 2 + 1 = 65
   
  
 a[0]=32∗2+1=65

能get到吗?

我们观察题目, 题目规定了

    A
   
   
    ≥
   
   
    B
   
  
  
   A \ge B
  
 
A≥B, 且问最小的

 
  
   
    A
   
   
    −
   
   
    B
   
  
  
   A - B
  
 
A−B.

那么答案一定是所有位的进制越小越好.

把

    A
   
   
    ,
   
   
    B
   
  
  
   A, B
  
 
A,B两个数**右对齐**后, **从右往左**数第

 
  
   
    i
   
  
  
   i
  
 
i位的最小进制为: 

 
  
   
    m
   
   
    a
   
   
    x
   
   
    (
   
   
    {
   
   
    A
   
   
    o
   
   
    
     p
    
    
     i
    
   
   
    +
   
   
    1
   
   
    ,
   
   
    B
   
   
    o
   
   
    
     p
    
    
     i
    
   
   
    +
   
   
    1
   
   
    ,
   
   
    2
   
   
    }
   
   
    )
   
  
  
   max(\{ Aop_i + 1, Bop_i + 1, 2 \})
  
 
max({Aopi​+1,Bopi​+1,2}), 其中

 
  
   
    A
   
   
    o
   
   
    
     p
    
    
     i
    
   
   
    ,
   
   
    B
   
   
    o
   
   
    
     p
    
    
     i
    
   
  
  
   Aop_i, Bop_i
  
 
Aopi​,Bopi​为这位上, 

 
  
   
    A
   
   
    ,
   
   
    B
   
  
  
   A, B
  
 
A,B的数字.

右对齐解释:

例如: A = { 3, 2, 1 }, B = { 4, 0 }

则对齐后如下:

A:321
B:40
M:452// 最小进制位 

本例参考答案:

27

所以n是真的有用的吗?

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =1E5+10, mod =1000000007;int a[N], b[N];intmain(){int n; cin >> n;int la; cin >> la;rep(i, la)scanf("%d",&a[i]);int lb; cin >> lb;rep(i, lb)scanf("%d",&b[i]);int suma =0, sumb =0;rep(i, la - lb){// 之前的和是suma, 这位进制至少是max(ai + 1, 2)int low =max(a[i]+1,2);
        suma =(1ll* suma * low + a[i])% mod;}int py = la - lb;//偏移量rep(i, lb){int opa = a[i + py], opb = b[i];int low =max(opa, opb)+1;
        low =max(2, low);

        suma =(1ll* suma * low + opa)% mod;
        sumb =(1ll* sumb * low + opb)% mod;}int res =(suma - sumb + mod)% mod;
    cout << res << endl;return0;}

试题 F: 统计子矩阵

解题思路

赛场思路

这题读完, 立马想到二位前缀和不过分吧? 然后立马得到了一个

    O
   
   
    (
   
   
    
     n
    
    
     4
    
   
   
    )
   
  
  
   O(n^4)
  
 
O(n4)的做法也不过分吧?

然后我们发现复杂度爆炸, 因此考虑优化:

我们发现, 如果假设子矩阵左上角

    (
   
   
    
     x
    
    
     1
    
   
   
    ,
   
   
    
     y
    
    
     1
    
   
   
    )
   
  
  
   (x_1, y_1)
  
 
(x1​,y1​), 右下角

 
  
   
    (
   
   
    
     x
    
    
     2
    
   
   
    ,
   
   
    
     y
    
    
     2
    
   
   
    )
   
  
  
   (x_2, y_2)
  
 
(x2​,y2​), 那么我们可以枚举

 
  
   
    
     x
    
    
     1
    
   
   
    ,
   
   
    
     y
    
    
     1
    
   
   
    ,
   
   
    
     x
    
    
     2
    
   
  
  
   x_1, y_1, x_2
  
 
x1​,y1​,x2​, 然后

 
  
   
    
     y
    
    
     2
    
   
  
  
   y_2
  
 
y2​是具有单调性的, 因此优化后复杂度为: 

 
  
   
    O
   
   
    (
   
   
    
     n
    
    
     3
    
   
   
    l
   
   
    o
   
   
    g
   
   
    n
   
   
    )
   
  
  
   O(n^3logn)
  
 
O(n3logn). 虽然有些爆炸, 但是骗分足够了.

赛后被教育

这题可以通过枚举矩阵宽度来把一个二维问题, 转化成一个一维问题.

此时变成了问题所求便成了一个最大连续子段问题, 可以通过双指针来求解.

最终复杂度为:

    O
   
   
    (
   
   
    
     n
    
    
     3
    
   
   
    )
   
  
  
   O(n^3)
  
 
O(n3)

参考代码

/* 做法一: 复杂度O(n^3logn) */#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =5E2+10;int a[N][N], s[N][N];intcalc(int x1,int y1,int x2,int y2){return s[x2][y2]- s[x2][y1 -1]- s[x1 -1][y2]+ s[x1 -1][y1 -1];}intmain(){int n, m, k; cin >> n >> m >> k;rep(i, n)rep(j, m){scanf("%d",&a[i][j]);
            s[i][j]= s[i -1][j]+ s[i][j -1]- s[i -1][j -1]+ a[i][j];}

    ll res =0;rep(x1, n)rep(y1, m){for(int x2 = x1; x2 <= n;++x2){if(calc(x1, y1, x2, y1)> k)break;int l = y1, r = m;while(l < r){int mid = l + r +1>>1;if(calc(x1, y1, x2, mid)<= k) l = mid;else r = mid -1;}

                res +=(r - y1 +1);}}

    cout << res << endl;return0;}/* 做法2: 复杂度O(n^3) */#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =5E2+10;int a[N][N], s[N][N];intcalc(int cur,int L,int R){return s[cur][R]- s[cur][L -1];}intmain(){int n, m, k; cin >> n >> m >> k;rep(i, n)rep(j, m){scanf("%d",&a[i][j]);
        s[i][j]= s[i][j -1]+ a[i][j];}int res =0;rep(L, m)for(int R = L; R <= m;++R){int top =0, down =0;for(int l =1, r =0; l <= n;++l){while(r +1<= n and down +calc(r +1, L, R)- top <= k){
                down +=calc(++r, L, R);}if(down - top <= k){
                res += r - l +1;}

            top +=calc(l, L, R);}}

    cout << res << endl;return0;}

试题 G: 积木画

解题思路

这题… 我提供个我的做题思维吧…

我并不是很擅长递推类问题, 首先删除掉了L形积木, 我发现如果只有I型积木, 答案就是个斐波那契数列. 此时我大胆猜测, 如果加上了L积木, 答案应该是可以通过类似的方式递推出来的.

最终结论为:

a[i] = a[i - 1] + a[i - 2] + 2 * a[i - 3]

.

解释: 首先我们考虑I型只需要

     2
    
    
     ∗
    
    
     2
    
   
   
    2 * 2
   
  
 2∗2的格子即可完成不同种排列组合, **L型**则需要
 
  
   
    
     3
    
    
     ∗
    
    
     2
    
   
   
    3 * 2
   
  
 3∗2.

有

     i
    
   
   
    i
   
  
 i列时, 比
 
  
   
    
     i
    
    
     −
    
    
     1
    
   
   
    i - 1
   
  
 i−1列多出了一列, 这一列我们只能**竖着放I**.

而比

     i
    
    
     −
    
    
     2
    
   
   
    i - 2
   
  
 i−2列多出了两列, 这两列我们只能**横着放I**, 否则会与
 
  
   
    
     i
    
    
     −
    
    
     1
    
   
   
    i - 1
   
  
 i−1列的情况重复.

同理, 比

     i
    
    
     −
    
    
     3
    
   
   
    i - 3
   
  
 i−3列多出了三列, 此时我们只能放**L型**, 否则同样会和前面冲突, 而对于
 
  
   
    
     3
    
    
     ∗
    
    
     2
    
   
   
    3 * 2
   
  
 3∗2的格子, 有两种放**L型**积木的方式, 因此要
 
  
   
    
     ×
    
    
     2
    
   
   
    \times 2
   
  
 ×2.

对于多出更多列的方式, 我们发现均会与之前的情况重复.

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =1E7+10, mod =1000000007;int a[N];// 当然你可以选择不开数组.intmain(){int n; cin >> n;

    a[1]=1, a[2]=2, a[3]=5;for(int i =4; i <= n;++i){
        a[i]= a[i -1];// 加一列在后面
        a[i]=(a[i]+ a[i -2])% mod;
        a[i]=(0ll+ a[i]+ a[i -3]*2)% mod;}

    cout << a[n]<< endl;return0;}

试题 H: 扫雷

解题思路

这题… 其实如果按照我的方式理解题意… 我算是暴力了一下

最终复杂度为:

    O
   
   
    (
   
   
    n
   
   
    
     r
    
    
     2
    
   
   
    l
   
   
    o
   
   
    g
   
   
    n
   
   
    )
   
  
  
   O(nr^2logn)
  
 
O(nr2logn)

其实可以通过离散化的方式删除掉后面的

    l
   
   
    o
   
   
    g
   
  
  
   log
  
 
log但是写起来太复杂了.

代码供大家参考着玩吧, 比赛时乱YY的, 不一定对.

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;typedef pair<int,int> PII;structnode{int x, y, r;node(int a,int b,int c){
        x = a, y = b, r = c;}};

map<PII, PII> mp;// { x, y } { r, num }doublegetdis(const pair<int,int>& a,const pair<int,int>& b){int x1 = a.first, y1 = a.second;int x2 = b.first, y2 = b.second;
    ll x =(x1 - x2), y =(y1 - y2);returnsqrt(x * x + y * y);}intmain(){int n, m; cin >> n >> m;rep(i, n){int x, y, r;scanf("%d %d %d",&x,&y,&r);

        PII p =make_pair(x, y);if(!mp.count(p)) mp[p]=make_pair(r,1);else{
            PII op = mp[p];
            mp[p]=make_pair(max(op.first, r), op.second +1);}}

    queue<node> q;rep(i, m){int x, y, r;scanf("%d %d %d",&x,&y,&r);
        q.push(node(x, y, r));int res =0;while(!q.empty()){
            node op = q.front(); q.pop();
            x = op.x, y = op.y, r = op.r;
            PII p =make_pair(x, y);for(int px = x - r; px <= x + r;++px){for(int py = y - r; py <= y + r;++py){
                    PII pp =make_pair(px, py);if(getdis(p, pp)> r)continue;if(!mp.count(pp))continue;
                    PII now = mp[pp];
                    mp.erase(pp);

                    q.push(node(pp.first, pp.second, now.first));
                    res += now.second;}}}printf("%d\n", res);}return0;}

试题 I: 李白打酒加强版

解题思路

这题, 读完了之后冷静分析, 发现是个dp, 然后我直接写了暴力…

但是最后做完了题, 没事干, 于是尝试着写了写… 没想到过了样例, 然后开始对拍… 没想到过了对拍…

好吧好吧, 删掉暴力, 自信交!

对于本题的讲解, 其实博主并不擅长dp, 这道题只是尝试着用我认为的dp分析方式写出来了, 就不在这里乱叨叨了.

参考代码

/* 暴力做法, 40%没问题 */#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint mod =1000000007;intmain(){int n, m; cin >> n >> m;constint B = n + m;constint TOP =1<< B;int res =0;for(int i =0; i < TOP;++i){if(i %2==1orbitset<32>(i).count()!= n)continue;

        ll now =2;for(int j = B -1; j >=0;--j){if(i >> j &1) now *=2;else now--;}if(!now) res++;}

    cout << res << endl;return0;}/* DP 100% O(n^3) 代码注释为比赛时的注释, 未修改 */#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =1E2+10, mod =1000000007;int dp[N *2][N][N];// 前i步中, 还有k个花 有j口酒的情况int n, m;intfact(){int all = n + m;

    dp[0][2][m]=1;rep(i, all){// 枚举总步数for(int j =0; j <= m;++j){// 枚举当前步数下, 还有多少口酒for(int k = j; k <= m;++k){// 枚举后续还能遇到多少个花
                dp[i][j][k]=0;

                dp[i][j][k]= dp[i -1][j +1][k +1];if(j %2==0) dp[i][j][k]=(dp[i][j][k]+ dp[i -1][j /2][k])% mod;}}}return dp[all -1][1][1];}intmain(){
    cin >> n >> m;int res =fact();
    cout << res << endl;return0;}

试题 J: 砍竹子

解题思路(本题思路纯属扯淡)

这题, 读完了好眼熟啊… 感觉某位前辈好像在冥冥之中给过我指引, 但是我好像写的并不太对…

本来尝试讲解了一下自己的思路, 发现狗屁不通!!!

所以本题看着玩吧 (摆烂.png)

参考代码

#include<bits/stdc++.h>#definerep(i, n)for(int i =1; i <=(n);++i)usingnamespace std;typedeflonglong ll;constint N =2E5+10;
ll a[N];structnode{
    ll val;int l, r;node(ll a,int b,int c){
        val = a;
        l = b, r = c;}booloperator<(const node& t)const{return val < t.val;}};

ll fact(ll x){
    x = x /2;returnsqrt(x +1);}intmain(){int n; cin >> n;rep(i, n)scanf("%lld",&a[i]);

    set<ll> st[2];

    ll res =0;rep(i, n){int id = i &1, anid = id ^1;
        st[id].clear();while(a[i]!=1){
            st[id].insert(a[i]);if(!st[anid].count(a[i])) res++;

            a[i]=fact(a[i]);}}

    cout << res << endl;return0;}

退役前: DP不会, 规律找不到.

退役后: 卧槽, 我能写出来DP了? 卧槽, 我还会递推找规律了?

END