【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解

03-11 阅读 0评论

参加了两届蓝桥杯以及做过了往年的真题我的直观感受是蓝桥杯不再那么“暴力”了，而是逐渐趋向DP和搜素图论方面了。下面是第十四届蓝桥杯省赛C/C++ B组真题及题解，希望对阅读的你有所帮助。

$【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解,【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第1张$

（图片来源网络，侵删）

目录

题目
- 试题A：日期统计
- 试题B：01 串的熵
- 试题C：冶炼金属
- 试题D：飞机降落
- 试题E：接龙数列
- 试题F：岛屿个数
- 试题G：子串简写
- 试题H：整数删除
- 试题I：景区导游
- 试题J：砍树
- 答案
- - A题答案:
  - B题答案:
  - C题答案:
  - D题答案:
  - E题答案:
  - F题答案:
  - G题答案:
  - H题答案:
  - I题答案:
  - J题答案:
    题目
    
    试题A：日期统计
    
    【问题描述】
    小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。数组中的元素从左至右如下所示：
    5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2 7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1 0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
    现在他想要从这个数组中寻找一些满足以下条件的子序列：
    1. 子序列的长度为 8；
    2. 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且
      要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。
      yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只
      $【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解,【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第2张$
      （图片来源网络，侵删）
      有一位时需要一个前导零补充。
      请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。
      对于相同的日期你只需要统计一次即可。
    【答案提交】
    这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
    个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
    
    试题B：01 串的熵
    
    $【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解,【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,使用,我们,方法,第4张$
    （图片来源网络，侵删）
    
    试题C：冶炼金属
    
    【问题描述】
    小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个
    炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金
    属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法
    继续冶炼。
    现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次
    投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立
    的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。
    根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是
    多少，题目保证评测数据不存在无解的情况。
    【输入格式】
    第一行一个整数 N，表示冶炼记录的数目。
    接下来输入 N 行，每行两个整数 A、B，含义如题目所述。
    【输出格式】
    输出两个整数，分别表示 V 可能的最小值和最大值，中间用空格分开。
    【样例输入】
    3
    75 3
    53 2
    59 2
    【样例输出】
    20 25
    
    试题D：飞机降落
    
    【问题描述】
    N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻
    到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早
    可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li
    个单位时间。
    一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不
    能在前一架飞机完成降落前开始降落。
    请你判断 N 架飞机是否可以全部安全降落。
    【输入格式】
    输入包含多组数据。
    第一行包含一个整数 T，代表测试数据的组数。
    对于每组数据，第一行包含一个整数 N。
    以下 N 行，每行包含三个整数：Ti，Di 和 Li。
    【输出格式】
    对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
    【样例输入】
    2
    3
    0 100 10
    10 10 10
    0 2 20
    3
    0 10 20
    10 10 20
    20 10 20
    【样例输出】
    YES
    NO
    【样例说明】
    对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降
    落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机
    于 30 时刻开始降落，40 时刻完成降落。
    对于第二组数据，无论如何安排，都会有飞机不能及时降落。
    【评测用例规模与约定】
    对于 30% 的数据，N ≤ 2。
    对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti, Di, Li ≤ 10
    
    试题E：接龙数列
    
    【问题描述】
    对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且
    仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
    例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56
    的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
    现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少
    个数，可以使剩下的序列是接龙序列？
    【输入格式】
    第一行包含一个整数 N。
    第二行包含 N 个整数 A1, A2, . . . , AN。
    【输出格式】
    一个整数代表答案。
    【样例输入】
    5
    11 121 22 12 2023
    【样例输出】
    1
    【样例说明】
    删除 22，剩余 11, 121, 12, 2023 是接龙数列。
    【评测用例规模与约定】
    对于 20% 的数据，1 ≤ N ≤ 20。
    对于 50% 的数据，1 ≤ N ≤ 10000。
    对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。
    
    试题F：岛屿个数
    
    【问题描述】
    小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符
    ‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，
    每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
    在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得
    他们的坐标能够组成一个这样的排列：(x0, y0),(x1, y1), . . . ,(xk−1, yk−1)，
    其中(x(i+1)%k, y(i+1)%k) 是由 (xi, yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ k − 1)，
    此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于
    这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子
    岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。
    请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。
    【输入格式】
    第一行一个整数 T，表示有 T 组测试数据。
    接下来输入 T 组数据。对于每组数据，第一行包含两个用空格分隔的整数
    M、N 表示地图大小；接下来输入 M 行，每行包含 N 个字符，字符只可能是
    ‘0’ 或 ‘1’。
    【输出格式】
    对于每组数据，输出一行，包含一个整数表示答案。
    【样例输入】
    
    2
    5 5
    01111
    11001
    10101
    10001
    11111
    5 6
    111111
    100001
    010101
    100001
    111111
    【样例输出】
    1
    3
    【样例说明】
    对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：
    01111
    11001
    10201
    10001
    11111
    岛屿 2 在岛屿 1 的 “环” 内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。
    对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：
    111111
    100001
    020301
    100001
    111111
    注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有
    “环”。
    【评测用例规模与约定】
    对于 30% 的评测用例，1 ≤ M, N ≤ 10。
    对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。
    
    试题G：子串简写
    
    【问题描述】
    程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首
    尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
    在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法
    （长度小于 K 的字符串不配使用这种简写）。
    给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头
    c2 结尾的子串可以采用这种简写？
    【输入格式】
    第一行包含一个整数 K。
    第二行包含一个字符串 S 和两个字符 c1 和 c2。
    【输出格式】
    一个整数代表答案。
    【样例输入】
    4
    abababdb a b
    【样例输出】
    6
    【样例说明】
    符合条件的子串如下所示，中括号内是该子串：
    [abab]abdb
    [ababab]db
    [abababdb]
    ab[abab]db
    ab[ababdb]
    abab[abdb]
    【评测用例规模与约定】
    对于 20% 的数据，2 ≤ K ≤ |S | ≤ 10000。
    对于 100% 的数据，2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都
    是小写字母。
    |S | 代表字符串 S 的长度
    
    试题H：整数删除
    
    【问题描述】
    给定一个长度为 N 的整数数列：A1, A2, . . . , AN。你要重复以下操作 K 次：
    每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其
    删除。并把与它相邻的整数加上被删除的数值。
    输出 K 次操作后的序列。
    【输入格式】
    第一行包含两个整数 N 和 K。
    第二行包含 N 个整数，A1, A2, A3, . . . , AN。
    【输出格式】
    输出 N − K 个整数，中间用一个空格隔开，代表 K 次操作后的序列。
    【样例输入】
    5 3
    1 4 2 8 7
    【样例输出】
    17 7
    【样例说明】
    数列变化如下，中括号里的数是当次操作中被选择的数：
    [1] 4 2 8 7
    5 [2] 8 7
    [7] 10 7
    17 7
    【评测用例规模与约定】
    对于 20% 的数据，1 ≤ K
    对于 100% 的数据，1 ≤ K
    试题I：景区导游
    
    【问题描述】
    某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆
    渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，
    需要花费一定的时间。
    小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个
    景点：A1, A2, . . . , AK。今天由于时间原因，小明决定跳过其中一个景点，只带游
    客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会
    按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。
    请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景
    点之间的摆渡车上？
    【输入格式】
    第一行包含 2 个整数 N 和 K。
    以下 N − 1 行，每行包含 3 个整数 u, v 和 t，代表景点 u 和 v 之间有摆渡
    车线路，花费 t 个单位时间。
    最后一行包含 K 个整数 A1, A2, . . . , AK 代表原定游览线路。
    【输出格式】
    输出 K 个整数，其中第 i 个代表跳过 Ai 之后，花费在摆渡车上的时间。
    【样例输入】
    6 4
    1 2 1
    1 3 1
    3 4 2
    3 5 2
    4 6 3
    2 6 5 1
    【样例输出】
    10 7 13 14
    【样例说明】
    原路线是 2 → 6 → 5 → 1。
    当跳过 2 时，路线是 6 → 5 → 1，其中 6 → 5 花费时间 3 + 2 + 2 = 7，
    5 → 1 花费时间 2 + 1 = 3，总时间花费 10。
    当跳过 6 时，路线是 2 → 5 → 1，其中 2 → 5 花费时间 1 + 1 + 2 = 4，
    5 → 1 花费时间 2 + 1 = 3，总时间花费 7。
    当跳过 5 时，路线是 2 → 6 → 1，其中 2 → 6 花费时间 1 + 1 + 2 + 3 = 7，
    6 → 1 花费时间 3 + 2 + 1 = 6，总时间花费 13。
    当跳过 1 时，路线时 2 → 6 → 5，其中 2 → 6 花费时间 1 + 1 + 2 + 3 = 7，
    6 → 5 花费时间 3 + 2 + 2 = 7，总时间花费 14。
    【评测用例规模与约定】
    对于 20% 的数据，2 ≤ K ≤ N ≤ 102。
    对于 40% 的数据，2 ≤ K ≤ N ≤ 104。
    对于 100% 的数据，2 ≤ K ≤ N ≤ 105，1 ≤ u, v, Ai ≤ N，1 ≤ t ≤ 105。保证
    Ai 两两不同。
    
    试题J：砍树
    
    【问题描述】
    给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
    . . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai , bj(1 ≤ i, j ≤ m)。
    小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai
    , bi) 满足 ai
    和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开
    始），否则输出 -1。
    【输入格式】
    输入共 n + m 行，第一行为两个正整数 n，m。
    后面 n − 1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。
    后面 m 行，每行两个正整数 ai，bi。
    【输出格式】
    一行一个整数，表示答案，如有多个答案，输出编号最大的一个。
    【样例输入】
    6 2
    1 2
    2 3
    4 3
    2 5
    6 5
    3 6
    4 5
    【样例输出】
    4
    【样例说明】
    断开第 2 条边后形成两个连通块：{3, 4}，{1, 2, 5, 6}，满足 3 和 6 不连通，4
    和 5 不连通。
    断开第 4 条边后形成两个连通块：{1, 2, 3, 4}，{5, 6}，同样满足 3 和 6 不连
    通，4 和 5 不连通。
    4 编号更大，因此答案为 4。
    【评测用例规模与约定】
    对于 30% 的数据，保证 1
    对于 100% 的数据，保证 1
    答案
    
    A题答案:
    
    因为是填空题，所以可以写一个纯暴力的代码在自己的编译器里跑
    
    235
    
    B题答案:
    
    我们假设0出现了x次，1出现了y次
    可以发现H(S)的值就是等于
    这里x+y=n，题目中n=23333333，所以y=23333333-x，
    带入公式中之后将x从0~23333333遍历，在自己的编译器中跑出来答案之后可以得到答案
    如果答案大于23333333/2，记得把答案更新为23333333-ans，因为0出现的次数小于1的次数。
    
    11027421
    
    C题答案:
    
    75 / 3 = 25
    53 / 2 = 26
    59 / 2 = 29
    75 / (3+1) = 18
    53 / (2+1) = 17
    59 / (2+1) = 19
    
    由题意可以知道，Vmax就是对所有的A/B取最小
    Vmin则是我们对所有的A/（B+1）取最大之后因为是边界取不到，所以+1就是Vmin
```
#include 
using namespace std;
int n;
int vis;
int vis1;
int Vmin = 999999999;
int Vmax = 0;
int main()
{
    cin >> n;
    for (int i = 1; i 
        int x, y;
        cin > x >> y;
        int vis = x / y;
        if (vis  Vmax)
            Vmax = vis1;
    }
    cout 
	int T;
	cinT;
	while(T--)
	{
		int n;
		cin>n;
		for(int i=1;i>t[i]>>d[i]>>l[i];
		for(int i=1;i
			int now=0;
			for(int i=1;i
				if(now
   cin  n;
   for (int i = 1; i 
       cin  s;
       int x = s[0] - '0';
       int y = s[s.size()-1] - '0';
       dp[y] = max(dp[y], dp[x] + 1);
   }
   int vis = 0;
   for (int i = 0; i = 0 && tx 
                if (g[tx][ty] == '0') {
                    g[tx][ty] = '2';
                    q.push({tx, ty});
                }
            }
        }
    }
}
void bfs2(int x, int y) {
    queuex, y});
    while (!q.empty()) {
        point now = q.front();
        q.pop();
        for (int i = 0; i > m >> n;
        memset(g, '0', sizeof(g));
        ans = 0;
        for (int i = 1; i 
            for (int j = 1; j 
                cin  g[i][j];
            }
        }
        bfs1();
        for (int i = 1; i 
            for (int j = 1; j 
                if (g[i][j] == '1') {
                    ans++;
                    bfs2(i, j);
                }
            }
        }
        cout 
    cin  k  s >> c1 >> c2;
    int len = s.size();
    s = " " + s;
    for (int i = len; i >= 1; i--) {
        f[i] = f[i + 1];
        if (s[i] == c2) f[i] = f[i + 1] + 1;
    }
    for (int i = 1; i + k - 1 
        if (s[i] == c1) ans += f[i + k - 1];
    }
    cout 
    r[l[x]] = r[x], l[r[x]] = l[x];
    v[l[x]] += v[x], v[r[x]] += v[x];
}
int main () {
    int n, k; cin  n >> k;
    //最小堆， 堆中的元素是{权值， 结点下标}
    priority_queue h;
    //输入并构造双向链表
    r[0] = 1, l[n + 1] = n;
    for (int i = 1; i > v[i], l[i] = i - 1, r[i] = i + 1, h.push({v[i], i});
    while (k --) {
        auto p = h.top(); h.pop();
        //如果v发生变化， 则目前的元素不一定是最小值， 需要重新放入堆中
        if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++;
        else del(p.second);
    }
    //输出链表剩余的元素
    int head = r[0];
    while (head != n + 1) {
        cout 
    dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa;
    for (int i = 1; (1 
        if (p.first == fa) continue;
        dfs(p.first, u, d + p.second);
    }
}
//求a和b的lca
int lca(int a, int b) {
    if (dep[a]  n >> k;
    for (int i = 1; i > u >> v >> t;
        g[u].push_back({v, t}), g[v].push_back({u, t});
    }
    vector a(k);
    for (auto &x : a) cin >> x;
    dfs(1, 0, 0);
    //求出原本整条路径的和
    ll sum = 0;
    for (int i = 1; i  n >> m;
  for (int i = 1; i > a >> b;
    g[a].push_back({b, i}), g[b].push_back({a, i});
  }
  init(1, 0);
  for (int i = 0; i > a >> b;
    add(a, b);
  }
  dfs(1, 0);
  int res = -1;
  for (int i = 1; i  res)) res = w[i];
  cout 
```

相关阅读：

1、已解决javax.xml.datatype.DatatypeConfigurationException异常的正确解决方法，亲测有效！！！

2、Java 面试题篇 Sleep()方法与Wait() 方法的区别

3、Android Studio音乐播放器（使用sqlite创建数据库）

4、Windows下载安装配置并使用Redis（保姆级教程）

5、Java的日期类常用方法

免责声明

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

发表评论取消回复

评论列表（暂无评论，人围观）

还没有评论，来说两句吧...

目录[+]