0


第十四届蓝桥杯第三期模拟赛 C/C++ B组 原题与详解

作者:@Ggggggtm

寄语:与其忙着诉苦,不如低头赶路,奋路前行,终将遇到一番好风景

一、填空题

1、1 找最小全字母十六进制数

1、1、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:请找到一个大于 2022 的最小数,这个数转换成十六进制之后,所有的数位(不含前导 0)都为字母(A 到 F)。请将这个数的十进制形式作为答案提交。

1、1、2 题解关键思路与解答

在填空题中,我们需要注意的是能省时间就省时间,有时候是没有必要写出一个完全计算该题的代码。 例如本题,我们先看2022的十六进制:

题目要求所有的数位(不含前导 0)都为字母(A 到 F),那么就是aaa了。直接出答案为:2730。当然,我们也可以写出解题代码。关键就是判断这个数%16是否在10和15之间即可。我们看代码:

bool check_vaild(int x) 
{
    while (x) 
    {
        if (x % 16 >= 10 && x % 16 <= 15)
            ;//当满足条件,我们什么也不用做,继续循环即可
        else 
        {
            return false;
        }
        x /= 16;
    }
    return true;
}

int main() 
{
    for (int i = 2023; ; i++) 
    {
        if (check_vaild(i)) 
        {
            cout << i << "\n";
            break; //找到就停止即可
        }
    }

    return 0;
}

1、2 给列命名

1、2、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:在 Excel 中,列的名称使用英文字母的组合。前 26 列用一个字母,依次为 A 到 Z,接下来 26*26 列使用两个字母的组合,依次为 AA 到 ZZ。请问第 2022 列的名称是什么?

1、2、2 题解关键思路与解答

我们先判断需要几个字母。2626 < 2022 <262626,很显然我们需要三个字母来表示。我们可以直接算出来答案的。2022-6-2626-2626=644(**第一次减26是减去的一个字符的,第二次减去2626是减去两个字母的,第三次减去2626是减去三个字母中第一个字母为A的情况,也就是到三个字母中第一个字母为B的情况**),当我们再减去2626时,发现结果为-32,我们再往回数32个即可。答案即为:BYT。这道题我们暴力枚举也可。在考试中,能够想到的解决方法即为最优解决方法,尤其是填空题,不必太过追求算法效率。我们看代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int get(int x, int y, int z) 
{
    return x * 26 * 26 + y * 26 + z;
}

string str(int x, int y, int z) 
{
    string s;
    s += 'A' + x - 1;  //转换为字符形式
    s += 'A' + y - 1;
    s += 'A' + z - 1;
    return s;
}

int main() {
    int n = 2022;

    for (int i = 1; i <= 26; i++)
        for (int j = 1; j <= 26; j++)
            for (int k = 1; k <= 26; k++)
                if (get(i, j, k) == n) 
                {
                    cout << str(i, j, k);
                    return 0;
                }

    return 0;
}

1、3 日期相等

1、3、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:对于一个日期,我们可以计算出年份的各个数位上的数字之和,也可以分别计算月和日的各位数字之和。请问从 1900 年 1 月 1 日至 9999 年 12 月 31 日,总共有多少天,年份的数位数字之和等于月的数位数字之和加日的数位数字之和。例如,2022年11月13日满足要求,因为 2+0+2+2=(1+1)+(1+3) 。请提交满足条件的日期的总数量。

1、3、2 题解关键思路与解答

本题答案为:70910。

该题要去看每个年份的年月日,似乎好像有点麻烦。我们不如把1900 年 1 月 1 日至 9999 年 12 月 31 日的日期转换为8位数的数字,再去枚举19000101到99991213之间的每个数字。我们需要先判断该数字是否为合法日期,再去判断年份的数位数字之和是否等于月的数位数字之和加日的数位数字之和。这样做下来似乎并不麻烦,我们看代码。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
int res;

int days[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
bool check_vaild(int year,int month,int day)
{
    if (month == 0 || month > 12)
        return false;

    if (day == 0)
        return false;
    if (month != 2)
    {
        if (day > days[month])
            return false;
    }
    else
    {
        int leap = year % 400 == 0 || year % 4 == 0 && year % 100;

        if (day > days[month] + leap)
            return false;
    }

    return true;
}

int main()
{
    for (int i = 19000101; i <= 99991213; i++)
    {
        int year = i / 10000;
        int month = i % 10000 / 100;
        int day = i % 100;

        if (check_vaild(year, month, day))
        {
            int x=0, y=0, z=0;
            for (int i = 0; i < 4; i++)
            {
                x += year % 10;
                year /= 10;
            }

            while (month)
            {
                y += month % 10;
                month /= 10;
            }

            while(day)
            {
                z += day % 10;
                day /= 10;
            }

            if (x == y + z)
                res++;
        }
    }
    cout<<res;
    return 0;
}

1、4 乘积方案数

1、4、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:小蓝有 30 个数,分别为:99, 22, 51, 63, 72, 61, 20, 88, 40, 21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53, 64, 9, 28, 84, 34, 96, 52, 82, 51, 77 。小蓝可以在这些数中取出两个序号不同的数,共有 30*29/2=435 种取法。请问这 435 种取法中,有多少种取法取出的两个数的乘积大于等于 2022 。

1、4、2 题解关键思路与解答

本题答案为:189。

我们这个题应该没有什么好说的,直接暴力枚举即可。我们直接看代码:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int nums[31] = { 0, 99, 22, 51, 63, 72, 61, 20, 88, 40,
                21, 63, 30, 11, 18, 99, 12, 93, 16, 7, 53,
                64, 9, 28, 84, 34, 96, 52, 82, 51, 77 };

int main() {

    int res = 0;

    for (int i = 1; i <= 30; i++)
        for (int j = i + 1; j <= 30; j++) {
            if (nums[i] * nums[j] >= 2022) {
                res++;
            }
        }

    cout << res;
    return 0;
}

1、5 最大连通块

1、5、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:

110010000011111110101001001001101010111011011011101001111110
010000000001010001101100000010010110001111100010101100011110
001011101000100011111111111010000010010101010111001000010100
101100001101011101101011011001000110111111010000000110110000
010101100100010000111000100111100110001110111101010011001011
010011011010011110111101111001001001010111110001101000100011
101001011000110100001101011000000110110110100100110111101011
101111000000101000111001100010110000100110001001000101011001
001110111010001011110000001111100001010101001110011010101110
001010101000110001011111001010111111100110000011011111101010
011111100011001110100101001011110011000101011000100111001011
011010001101011110011011111010111110010100101000110111010110
001110000111100100101110001011101010001100010111110111011011
111100001000001100010110101100111001001111100100110000001101
001110010000000111011110000011000010101000111000000110101101
100100011101011111001101001010011111110010111101000010000111
110010100110101100001101111101010011000110101100000110001010
110101101100001110000100010001001010100010110100100001000011
100100000100001101010101001101000101101000000101111110001010
101101011010101000111110110000110100000010011111111100110010
101111000100000100011000010001011111001010010001010110001010
001010001110101010000100010011101001010101101101010111100101
001111110000101100010111111100000100101010000001011101100001
101011110010000010010110000100001010011111100011011000110010
011110010100011101100101111101000001011100001011010001110011
000101000101000010010010110111000010101111001101100110011100
100011100110011111000110011001111100001110110111001001000111
111011000110001000110111011001011110010010010110101000011111
011110011110110110011011001011010000100100101010110000010011
010011110011100101010101111010001001001111101111101110011101

小蓝有一个 30 行 60 列的数字矩阵,矩阵中的每个数都是 0 或 1 。如果从一个标为 1 的位置可以通过上下左右走到另一个标为 1 的位置,则称两个位置连通。与某一个标为 1 的位置连通的所有位置(包括自己)组成一个连通分块。请问矩阵中最大的连通分块有多大?

1、5、2 题解关键思路与解答

本题的答案为:148。

当遇到一个坐标可以影响到该坐标的上下左右四个坐标时,我们可以用下面方法来进行求取上下左右的各个坐标:

本题的方法就是暴搜,不断更新最大值即可,我们结合代码一起理解一下:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 35, M = 65;

int n = 30, m = 60;
char arr[N][M];

int dx[4] = { -1, 1, 0, 0 }, dy[4] = { 0, 0, -1, 1 };

int dfs(int x, int y) 
{
    int cnt = 1;
    arr[x][y] = '0';

    for (int i = 0; i < 4; i++) 
    {
        int a = x + dx[i], b = y + dy[i];
        if (a <= n && a >= 1 && b <= m && b >= 1 && arr[a][b] == '1') 
        {
            cnt += dfs(a, b);
        }
    }

    return cnt;
}

int main() 
{

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (arr[i][j] == '1')
                res = max(res, dfs(i, j));

    cout << res << "\n";
    return 0;

}

二、编程题

2、1 求星期几

2、1、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:给定一天是一周中的哪天,请问 n 天后是一周中的哪天?输入第一行包含一个整数 w,表示给定的天是一周中的哪天,w 为 1 到 6 分别表示周一到周六,w 为 7 表示周日。第二行包含一个整数 n。输出一行包含一个整数,表示 n 天后是一周中的哪天,1 到 6 分别表示周一到周六,7 表示周日。对于所有评测用例,1 <= n <= 1000000。

2、1、2 题解关键思路与解答

该题我可称它为“签到题”,分时一定要拿下,否则会吃大亏。我们直接看代码。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

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

    if ((w + n) % 7 == 0)
        cout << '7' << endl;
    else
        cout << (w + n) % 7 << endl;

    return 0;
}

2、2 范围覆盖点数

2、2、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (0, 0), 东南角坐标为 (W, 0), 西北角坐标为 (0, H), 东北角坐标为 (W, H)。其中 W, H 都是整数。
  他在 n 个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为 R 的圆形(包括边缘)。
  为了对信号覆盖的情况进行检查,小蓝打算在区域内的所有横纵坐标为整数的点进行测试,检查信号状态。其中横坐标范围为 0 到 W,纵坐标范围为 0 到 H,总共测试 (W+1) * (H+1) 个点。
  给定信号塔的位置,请问这 (W+1)*(H+1) 个点中有多少个点被信号覆盖。

   输入第一行包含四个整数 W, H, n, R,相邻整数之间使用一个空格分隔。
    接下来 n 行,每行包含两个整数 x, y,表示一个信号塔的坐标。信号塔可能重合,表示两个信号发射器装在了同一个位置。

   输出一行包含一个整数,表示答案。

   对于所有评测用例,1 <= W, H <= 100,1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H。

2、2、2 题解关键思路与解答

本题给出的数据范围较小,我们可以直接采用暴力枚举的方法,时间复杂度度是可以通过的。我们直接枚举每个点位,看是否再信号塔的范围内。计算该点到信号塔的圆心处的距离是否小于等于半径的长度。在计算的时候不必使用sqrt函数进行开根号,直接与半径的平方进行比较即可。sqrt函数反而会损失精度,可能会造成误判。我们看代码。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 110;

int w, h, n, R;
PII a[N];

int main() 
{
    cin >> w >> h >> n >> R;

    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;

    int res = 0;
    for (int i = 0; i <= w; i++)
        for (int j = 0; j <= h; j++) 
        {
            bool flag = false;
            while(n--) 
            {
                int k = 0;
                if ((i - a[k++].x) * (i - a[k++].x) +(j - a[k++].y) * (j - a[k++].y) <= R * R) 
                {
                    flag = true;
                    break;  //当flag为true时,直接结束。也就是该点至少在一个信函探测器里面。
                }
            }

            if (flag) res++;
        }

    cout << res;
    return 0;
}

2、3 清理水草

2、3、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:小蓝有一个 n * m 大小的矩形水域,小蓝将这个水域划分为 n 行 m 列,行数从 1 到 n 标号,列数从 1 到 m 标号。每行和每列的宽度都是单位 1 。现在,这个水域长满了水草,小蓝要清理水草。每次,小蓝可以清理一块矩形的区域,从第 r1 行(含)到第 r2 行(含)的第 c1 列(含)到 c2 列(含)。经过一段时间清理后,请问还有多少地方没有被清理过。

输入第一行包含两个整数 n, m,用一个空格分隔。
第二行包含一个整数 t ,表示清理的次数。
接下来 t 行,每行四个整数 r1, c1, r2, c2,相邻整数之间用一个空格分隔,表示一次清理。请注意输入的顺序。

输出一行包含一个整数,表示没有被清理过的面积。

对于所有评测用例,1 <= r1 <= r2 <= n <= 100, 1 <= c1 <= c2 <= m <= 100, 0 <= t <= 100。

2、3、2 题解关键思路与解答

题目给出的数据范围较小,我们可以直接用暴力的方法去做。我们首先创建数组,给数组的每个值初始化成 1,然后再把清理的面积改成 0。最后把数组剩下的 1加起来即可。我们看代码。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

int r1, c1, r2, c2;
int n, m, t;

const int N = 110;

int a[N][N];

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

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            a[i][j] = 1;  //1表示未清理过
    cin >> t;
    while (t--)
    {
        cin >> r1 >> c1 >> r2 >> c2;
        for (int i = r1; i <= r2; i++)
            for (int j = c1; j <= c2; j++)
                a[i][j] = 0;  //0表示已经被清理过

    }

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res += a[i][j];

    cout << res;
    return 0;
}

2、4 最大滑雪长度

2、4、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:小蓝准备在一个空旷的场地里面滑行,这个场地的高度不一,小蓝用一个 n 行 m 列的矩阵来表示场地,矩阵中的数值表示场地的高度。
  如果小蓝在某个位置,而他上、下、左、右中有一个位置的高度(严格)低于当前的高度,小蓝就可以滑过去,滑动距离为 1 。
  如果小蓝在某个位置,而他上、下、左、右中所有位置的高度都大于等于当前的高度,小蓝的滑行就结束了。
  小蓝不能滑出矩阵所表示的场地。
  小蓝可以任意选择一个位置开始滑行,请问小蓝最多能滑行多远距离。

输入第一行包含两个整数 n, m,用一个空格分隔。
接下来 n 行,每行包含 m 个整数,相邻整数之间用一个空格分隔,依次表示每个位置的高度。

输出一行包含一个整数,表示答案。

对于 30% 评测用例,1 <= n <= 20,1 <= m <= 20,0 <= 高度 <= 100。
对于所有评测用例,1 <= n <= 100,1 <= m <= 100,0 <= 高度 <= 10000。

2、4、2 题解关键思路与解答

当遇到一个坐标可以影响到该坐标的上下左右四个坐标时,我们可以用下面方法来进行求取上下左右的各个坐标:

我们先看题目中给出的数据范围,数据范围较小,我们可以使用暴搜的方法求解。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int N = 110;

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

int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };

int dfs(int x, int y) 
{
    int res = 0;
    for (int i = 0; i < 4; i++) 
    {
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && !f[a][b] && g[x][y] > g[a][b]) 
        {
            f[a][b] = true;
            res = max(res, dfs(a, b) + 1);

            //还原现场
            f[a][b] = false;
        }
    }

    return res;
}

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

    int res = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            scanf("%d", &g[i][j]);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
        {
            f[i][j] = true;  //表示当前位置已经走过
            res = max(res, dfs(i, j));

            //还原现场
            f[i][j] = false;
        }

    cout << res + 1 << "\n";
    return 0;
}

2、5 序号最小值

2、5、1 题目描述

题目来源:第十四届蓝桥杯第三期模拟赛

题目难度:简单

题目描述:小蓝有一个序列 a[1], a[2], …, a[n]。给定一个正整数 k,请问对于每一个 1 到 n 之间的序号 i,a[i-k], a[i-k+1], …, a[i+k] 这 2k+1 个数中的最小值是多少?当某个下标超过 1 到 n 的范围时,数不存在,求最小值时只取存在的那些值。

输入的第一行包含一整数 n。
第二行包含 n 个整数,分别表示 a[1], a[2], …, a[n]。
第三行包含一个整数 k 。

输出一行,包含 n 个整数,分别表示对于每个序号求得的最小值。

对于 30% 的评测用例,1 <= n <= 1000,1 <= a[i] <= 1000。
对于 50% 的评测用例,1 <= n <= 10000,1 <= a[i] <= 10000。
对于所有评测用例,1 <= n <= 1000000,1 <= a[i] <= 1000000。

2、5、2 题解关键思路与解答

经典模板题。首先暴力是通过不了的,能通过一部分测试用例,但是并不能通过全部测试用例。我们来看代码:

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1e6 + 10, M = 20;

int n, k, t;
int q[N];
int f[N][M]; 

int query(int l, int r) 
{
    int len = log(r - l + 1) / log(2); 
    int x = f[l][len], y = f[r - (1 << len) + 1][len]; 
    return q[x] > q[y] ? y : x;
}int main() 
{
    cin >> n; 
    for (int i = 1; i <= n; i++) 
        scanf("%d", &q[i]); 

    cin >> k;

    t = log(n) / log(2); 
    for (int j = 0; j <= t; j++) 
    { 
        for (int i = 1; i + (1 << j) - 1 <= n; i++) 
        { 
            if (!j) 
                f[i][j] = i; 
            else 
            { 
                int l = f[i][j - 1], r = f[i + (1 << (j - 1))][j - 1]; 
                if (q[l] > q[r]) 
                    f[i][j] = r; 
                else 
                    f[i][j] = l; 
            } 
        } 
    }
    int l, r; 
    for (int i = 1; i <= n; i++) 
    { 
        l = max(1, i - k), r = min(n, i + k); 
        cout << q[query(l, r)] << " ";
    }
    cout << endl;
    return 0;
}

以上就是蓝桥杯第十四届第三期模拟赛所有的题目了,希望本篇文章的讲解对你有所帮助,感谢阅读ovo~

标签: 蓝桥杯 算法 c++

本文转载自: https://blog.csdn.net/weixin_67596609/article/details/129384380
版权归原作者 Ggggggtm 所有, 如有侵权,请联系我们删除。

“第十四届蓝桥杯第三期模拟赛 C/C++ B组 原题与详解”的评论:

还没有评论