2022年第十三届蓝桥杯省赛B组C++所有题解

发布时间：2023-03-08 08:30

写在前面
填空题
- 试题 A: 九进制转十进制
- 试题 B: 顺子日期
编程题
- 试题 C: 刷题统计
- 试题 D: 修剪灌木
- 试题 E: X 进制减法
- 试题 F: 统计子矩阵
- 试题 G: 积木画
- 试题 H: 扫雷
- 试题 I: 李白打酒加强版
- 试题 J: 砍竹子
写到最后

写在前面

刚打完蓝桥杯省赛B组，小还差得远呢，这跟题解中的代码除了第一题，其他的都是看y总直播时候写的
看完本篇文章觉得不错的话记得点赞，收藏⭐，还有问题也可以评论留言

填空题

试题 A: 九进制转十进制

$\"在这里插入图片描述\"$
这道题是填空题，我们只需要算2×9⁰+2×9¹+2×9³，最后等于1478。

#include

using namespace std;

int main()
{
	cout << 2+2*9+2*9*9*9;
}

试题 B: 顺子日期

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第1张图片\"$
这题题意有点问题 $\"在这里插入图片描述\"$
所以很给人误解，到底012算还是不算，在这我们不纠结题意，只看怎么解决。

#include 
#include 
#include 

using namespace std;

const int months[] = {
    0, 31, 28, 31, 30, 31,
    30, 31, 31, 30, 31, 30,
    31
};

bool check(string str)
{
    for (int i = 0; i + 2 < str.size(); i ++ )
        if (str[i + 1] == str[i] + 1 && str[i + 2] == str[i] + 2)
            return true;

    return false;
}

int main()
{
    int year = 2022, month = 1, day = 1;

    int res = 0;
    for (int i = 0; i < 365; i ++ )
    {
        char str[10];
        sprintf(str, \"%04d%02d%02d\", year, month, day);

        if (check(str))
        {
            res ++ ;
            cout << str << endl;
        }

        if ( ++ day > months[month])
        {
            day = 1;
            month ++ ;
        }
    }

    cout << res << endl;
    return 0;
}

$\"在这里插入图片描述\"$
答案：14

如果012不算，那就加一个限制条件

if (check(str)&&str[i] != 0)

#include 
#include 
#include 

using namespace std;

const int months[] = {
    0, 31, 28, 31, 30, 31,
    30, 31, 31, 30, 31, 30,
    31
};

bool check(string str)
{
    for (int i = 0; i + 2 < str.size(); i ++ )
        if (str[i + 1] == str[i] + 1 && str[i + 2] == str[i] + 2)
            return true;

    return false;
}

int main()
{
    int year = 2022, month = 1, day = 1;

    int res = 0;
    for (int i = 0; i < 365; i ++ )
    {
        char str[10];
        sprintf(str, \"%04d%02d%02d\", year, month, day);

        if (check(str)&&str[i] != 0)
        {
            res ++ ;
            cout << str << endl;
        }

        if ( ++ day > months[month])
        {
            day = 1;
            month ++ ;
        }
    }

    cout << res << endl;
    return 0;
}

$\"在这里插入图片描述\"$
最后答案就是：4

编程题

试题 C: 刷题统计

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第2张图片\"$
这题需要注意数据范围，我们得开long long

#include 
#include 
#include 

using namespace std;

typedef long long LL;

int main()
{
    LL a, b, n;

    cin >> a >> b >> n;

    LL s = 5 * a + 2 * b;
    LL res = n / s * 7;
    n %= s;

    LL d[] = {a, a, a, a, a, b, b};
    for (int i = 0; n > 0; i ++ )
    {
        n -= d[i];
        res ++ ;
    }

    cout << res << endl;
    return 0;
}

试题 D: 修剪灌木

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第3张图片\"$
这题其实是一道数学题，多写几个样例就会发现前n/2个数中第i个数＝2（n-i），然后是一个对称的。

3 4 2 4
4 6 4 4 6
5 8 6 4 6 8
6 10 8 6 6 8 10

#include 
#include 
#include 

using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i ++ )
        cout << max(i - 1, n - i) * 2 << endl;

    return 0;
}

试题 E: X 进制减法

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第4张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第5张图片\"$

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 100010, MOD = 1000000007;

int n, m1, m2, m;
int a[N], b[N];

int main()
{
    scanf(\"%d\", &n);
    scanf(\"%d\", &m1);
    for (int i = m1 - 1; i >= 0; i -- ) scanf(\"%d\", &a[i]);
    scanf(\"%d\", &m2);
    for (int i = m2 - 1; i >= 0; i -- ) scanf(\"%d\", &b[i]);

    int m = max(m1, m2);

    int res = 0;
    for (int i = m - 1; i >= 0; i -- )
        res = (res * (LL)max({2, a[i] + 1, b[i] + 1}) + a[i] - b[i]) % MOD;

    printf(\"%d\\n\", res);
    return 0;
}

试题 F: 统计子矩阵

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第6张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第7张图片\"$
这题需要用到前缀和，大家可以看一下我之前写过的前缀和

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 510;

int n, m, K;
int s[N][N];

int main()
{
    scanf(\"%d%d%d\", &n, &m, &K);

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            scanf(\"%d\", &s[i][j]);
            s[i][j] += s[i - 1][j];
        }

    LL res = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            for (int l = 1, r = 1, sum = 0; r <= m; r ++ )
            {
                sum += s[j][r] - s[i - 1][r];
                while (sum > K)
                {
                    sum -= s[j][l] - s[i - 1][l];
                    l ++ ;
                }
                res += r - l + 1;
            }

    printf(\"%lld\\n\", res);
    return 0;
}

试题 G: 积木画

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第8张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第9张图片\"$
这题是状态压缩DP

#include 
#include 
#include 

using namespace std;

const int N = 1e7 + 10, MOD = 1e9 + 7;

int n;
int g[4][4] = {
    {1, 1, 1, 1},
    {0, 0, 1, 1},
    {0, 1, 0, 1},
    {1, 0, 0, 0},
};
int f[2][4];

int main()
{
    scanf(\"%d\", &n);
    f[1][0] = 1;

    for (int i = 1; i <= n; i ++ )
    {
        memset(f[i + 1 & 1], 0, sizeof f[0]);
        for (int j = 0; j < 4; j ++ )
            for (int k = 0; k < 4; k ++ )
                f[i + 1 & 1][k] = (f[i + 1 & 1][k] + f[i & 1][j] * g[j][k]) % MOD;
    }

    printf(\"%d\\n\", f[n + 1 & 1][0]);
    return 0;
}

试题 H: 扫雷

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第10张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第11张图片\"$

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 50010, M = 999997;

int n, m;
struct Circle
{
    int x, y, r;
}cir[N];
LL h[M];
int id[M];
bool st[M];

LL get_key(int x, int y)
{
    return x * 1000000001ll + y;
}

int find(int x, int y)
{
    LL key = get_key(x, y);
    int t = (key % M + M) % M;

    while (h[t] != -1 && h[t] != key)
        if ( ++ t == M)
            t = 0;
    return t;
}

int sqr(int x)
{
    return x * x;
}

void dfs(int x, int y, int r)
{
    st[find(x, y)] = true;

    for (int i = x - r; i <= x + r; i ++ )
        for (int j = y - r; j <= y + r; j ++ )
            if (sqr(i - x) + sqr(j - y) <= sqr(r))
            {
                int t = find(i, j);
                if (id[t] && !st[t])
                    dfs(i, j, cir[id[t]].r);
            }
}

int main()
{
    scanf(\"%d%d\", &n, &m);

    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        int x, y, r;
        scanf(\"%d%d%d\", &x, &y, &r);
        cir[i] = {x, y, r};

        int t = find(x, y);
        if (h[t] == -1) h[t] = get_key(x, y);

        if (!id[t] || cir[id[t]].r < r)
            id[t] = i;
    }

    while (m -- )
    {
        int x, y, r;
        scanf(\"%d%d%d\", &x, &y, &r);

        for (int i = x - r; i <= x + r; i ++ )
            for (int j = y - r; j <= y + r; j ++ )
                if (sqr(i - x) + sqr(j - y) <= sqr(r))
                {
                    int t = find(i, j);
                    if (id[t] && !st[t])
                        dfs(i, j, cir[id[t]].r);
                }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (st[find(cir[i].x, cir[i].y)])
            res ++ ;

    printf(\"%d\\n\", res);
    return 0;
}

试题 I: 李白打酒加强版

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第12张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第13张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第14张图片\"$

#include 
#include 
#include 

using namespace std;

const int N = 110, MOD = 1e9 + 7;

int n, m;
int f[N][N][N];

int main()
{
    cin >> n >> m;

    f[0][0][2] = 1;
    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= m; j ++ )
            for (int k = 0; k <= m; k ++ )
            {
                int& v = f[i][j][k];
                if (i && k % 2 == 0) v = (v + f[i - 1][j][k / 2]) % MOD;
                if (j) v = (v + f[i][j - 1][k + 1]) % MOD;
            }

    cout << f[n][m - 1][1] << endl;
    return 0;
}

试题 J: 砍竹子

$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第15张图片\"$
$\"2022年第十三届蓝桥杯省赛B组C++所有题解_第16张图片\"$
O(6n)

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 200010, M = 10;

int n, m;
LL f[N][M];

int main()
{
    scanf(\"%d\", &n);
    LL stk[M];

    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        LL x;
        int top = 0;
        scanf(\"%lld\", &x);

        while (x > 1) stk[ ++ top] = x, x = sqrt(x / 2 + 1);
        res += top;
        m = max(m, top);

        for (int j = 0, k = top; k; j ++, k -- )
            f[i][j] = stk[k];
    }

    for (int i = 0; i < m; i ++ )
        for (int j = 1; j < n; j ++ )
            if (f[j][i] && f[j][i] == f[j - 1][i])
                res -- ;

    printf(\"%d\\n\", res);
    return 0;
}

优先队列解法，时间复杂度 O(6nlogn)

#include 
#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;
const int N = 200010;

int n;
LL h[N];

struct Seg
{
    int l, r;
    LL v;
    bool operator< (const Seg& S) const
    {
        if (v != S.v) return v < S.v;
        return l > S.l;
    }
};

LL f(LL x)
{
    return sqrt(x / 2 + 1);
}

int main()
{
    scanf(\"%d\", &n);
    for (int i = 0; i < n; i ++ ) scanf(\"%lld\", &h[i]);

    priority_queue<Seg> heap;

    for (int i = 0; i < n; i ++ )
    {
        int j = i + 1;
        while (j < n && h[i] == h[j]) j ++ ;
        heap.push({i, j - 1, h[i]});
        i = j - 1;
    }

    int res = 0;
    while (heap.size() > 1 || heap.top().v > 1)
    {
        auto t = heap.top();
        heap.pop();

        while (heap.size() && heap.top().v == t.v && t.r + 1 == heap.top().l)
        {
            t.r = heap.top().r;
            heap.pop();
        }
        heap.push({t.l, t.r, f(t.v)});

        if (t.v > 1) res ++ ;
    }

    printf(\"%d\\n\", res);

    return 0;
}

写到最后

最后看到这了，如果觉得自己有收获的话，可以给博主点个关注哦
觉得本篇文章不错的话记得点赞，收藏⭐，还有问题也可以评论留言
你的支持将是我继续创作的最大动力❤️❤️❤️
由于作者水平有限，如有错误和不准确之处在所难免，本人也很想知道这些错误，恳望读者批评指正！

\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0