当前位置:   article > 正文

2023年第十四届蓝桥杯C++B组复盘_2023蓝桥杯c++b组

2023蓝桥杯c++b组

这届蓝桥杯跟上届蓝桥杯一样,只有2个填空题,8个编程的大题。本届蓝桥杯我愿称之为四小时怒开九道题 。难度跟上届相比,没有那么多思维题,反倒板子题多了,不知道其他组是不是也是这样。
博客地址:https://blog.csdn.net/m0_46326495/article/details/130043563

A: 日期统计(5分)

问题描述

小蓝现在有一个长度为 100 100 100 的数组,数组中的每个元素的值都在 0 0 0 9 9 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 表示天数,当月份或者天数的长度只有一位时需要一个前导零补充。
    请你帮小蓝计算下按上述条件一共能找到多少个不同的2023 年的日期。
    对于相同的日期你只需要统计一次即可。

思路

纯暴力的话就dfs,或者用8重循环。不妨再考虑下题目,由于对于相同的日期只需统计一次,因此可以查询每个2023年的日期能否由上面给的数字拼出来。这样既能有很好的效率,又能省去去重的过程。最终结果是235
具体代码如下

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

using namespace std;
const int numbers[100] = {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};
const int days[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main() {
    int ans = 0;
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= days[i]; j++) {
            string str = "2023";
            if (i < 10)str += "0";
            str += to_string(i);
            if (j < 10)str += "0";
            str += to_string(j);
            int k = 0;
            for (int l = 0; l < 100 && k < 8; l++) {
                if (numbers[l] == str[k] - '0') k++;
            }
            if (k >= 8) ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

B: 01 串的熵(5分)

问题描述

对于一个长度为 n n n 01 01 01 S = x 1 x 2 x 3 . . . x n S = x_1x_2x_3...x_n S=x1x2x3...xn,香农信息熵的定义为 H ( S ) = − ∑ 1 n p ( x i ) log ⁡ 2 ( p ( x i ) ) H(S)=-\sum^n_1p(x_i)\log_2(p(x_i)) H(S)=1np(xi)log2(p(xi)),其中 p ( 0 ) , p ( 1 ) p(0), p(1) p(0),p(1) 表示在这个 01 01 01 串中 0 0 0 1 1 1 出现的占比。比如,对于 S = 100 S = 100 S=100 来说,信息熵 H ( S ) = − 1 3 log ⁡ 2 ( 1 3 ) − 2 3 log ⁡ 2 ( 2 3 ) − 2 3 log ⁡ 2 ( 2 3 ) = 1.3083 H(S)=-\frac{1}{3}\log_2(\frac{1}{3})-\frac{2}{3}\log_2(\frac{2}{3})-\frac{2}{3}\log_2(\frac{2}{3})=1.3083 H(S)=31log2(31)32log2(32)32log2(32)=1.3083。对于一个长度为 23333333 23333333 23333333 01 01 01 串,如果其信息熵为 11625907.5798 11625907.5798 11625907.5798,且 0 0 0 出现次数比 1 1 1 少,那么这个 01 01 01 串中 0 0 0 出现了多少次?

思路

枚举一下0的个数,计算的时候要开double保证精度。结果是11027421(因为本题数据并不是很大,直接暴力枚举也可以,并不一定需要使用二分)

暴力枚举:

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

using namespace std;

const int total = 23333333;
const double H = 11625907.5798;

int main() {
    for (int i = 0; i < total / 2; i++) {
        double ans = 0;
        ans -= 1.0 * i * i / total * log2(1.0 * i / total);
        ans -= 1.0 * (total - i) * (total - i) / total * log2(1.0 * (total - i) / total);
        if (abs(ans - H) < 1e-4) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

二分:

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

using namespace std;

const int total = 23333333;
const double H = 11625907.5798;

int main() {
    int l = 0, r = total / 2;
    while (l < r) {
        int mid = (l + r) >> 1;
        double ans = 0;
        ans -= 1.0 * mid * mid / total * log2(1.0 * mid / total);
        ans -= 1.0 * (total - mid) * (total - mid) / total * log2(1.0 * (total - mid) / total);
        if (abs(ans - H) < 1e-4) {
            cout << mid << endl;
            return 0;
        }
        if (ans > H) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

C: 冶炼金属(10分)

问题描述

小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个称作转换率的属性 V V V V V V 是一个正整数,这意味着消耗 V V V 个普通金属 O O O 恰好可以冶炼出一个特殊金属 X X X,当普通金属 O O O 的数目不足 V V V 时,无法继续冶炼。

现在给出了 N N N 条冶炼记录,每条记录中包含两个整数 A A A B B B,这表示本次投入了 A A A 个普通金属 O O O,最终冶炼出了 B B B 个特殊金属 X X X。每条记录都是独立的,这意味着上一次没消耗完的普通金属 O O O 不会累加到下一次的冶炼当中。

根据这 N N N 条冶炼记录,请你推测出转换率 V V V 的最小值和最大值分别可能是多少,题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 N N N,表示冶炼记录的数目。
接下来输入 N N N 行,每行两个整数 A A A B B B,含义如题目所述。

输出格式

输出两个整数,分别表示 V V V 可能的最小值和最大值,中间用空格分开。

样例输入

3
75 3
53 2
59 2

样例输出

20 25

样例说明

V = 20 V = 20 V=20 时,有: ⌊ 75 20 = 3 ⌋ \lfloor \frac{75}{20}=3 \rfloor 2075=3 ⌊ 53 20 = 2 ⌋ \lfloor \frac{53}{20}=2 \rfloor 2053=2 ⌊ 59 20 = 2 ⌋ \lfloor \frac{59}{20}=2 \rfloor 2059=2可以看到符合所有冶炼记录。
V = 25 V = 25 V=25 时,有: ⌊ 75 25 = 3 ⌋ \lfloor \frac{75}{25}=3 \rfloor 2575=3 ⌊ 53 25 = 2 ⌋ \lfloor \frac{53}{25}=2 \rfloor 2553=2 ⌊ 59 25 = 2 ⌋ \lfloor \frac{59}{25}=2 \rfloor 2559=2可以看到符合所有冶炼记录。
且再也找不到比 20 20 20 更小或者比 25 25 25 更大的符合条件的 V V V 值了。

评测用例规模与约定

对于 30 % 30\% 30% 的评测用例, 1 ≤ N ≤ 1 0 2 1 ≤ N ≤ 10^2 1N102
对于 60 % 60\% 60% 的评测用例, 1 ≤ N ≤ 1 0 3 1 ≤ N ≤ 10^3 1N103
对于 100 % 100\% 100% 的评测用例, 1 ≤ N ≤ 1 0 4 1 ≤ N ≤ 10^4 1N104 1 ≤ B ≤ A ≤ 1 0 9 1 ≤ B ≤ A ≤ 10^9 1BA109

思路

感觉是个数学题,算一下即可。

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    int ansMin = 0, ansMax = 1e9;
    while (n--) {
        int a, b;
        cin >> a >> b;
        ansMin = max(a / (b + 1) + 1, ansMin);
        ansMax = min(a / b, ansMax);
    }
    cout << ansMin << " " << ansMax << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

D: 飞机降落(10分)

问题描述

N N N 架飞机准备降落到某个只有一条跑道的机场。其中第 i i i 架飞机在 T i T_i Ti时刻到达机场上空,到达时它的剩余油料还可以继续盘旋 D i D_i Di个单位时间,即它最早可以于 T i T_i Ti 时刻开始降落,最晚可以于 T i + D i T_i+ D_i Ti+Di 时刻开始降落。降落过程需要 L i L_i Li个单位时间。

一架飞机降落完毕时,另一架飞机可以立即在同一时刻开始降落,但是不能在前一架飞机完成降落前开始降落。

请你判断 N N N 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。
第一行包含一个整数 T T T,代表测试数据的组数。
对于每组数据,第一行包含一个整数 N N N
以下 N N N 行,每行包含三个整数: T i T_i Ti D i D_i Di L i L_i Li

输出格式

对于每组数据,输出 Y E S YES YES 或者 N O NO 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 3 3 架飞机于 0 0 0 时刻开始降落, 20 20 20 时刻完成降落。安排第 2 2 2 架飞机于 20 20 20 时刻开始降落, 30 30 30 时刻完成降落。安排第 1 1 1 架飞机于 30 30 30 时刻开始降落, 40 40 40 时刻完成降落。
对于第二组数据,无论如何安排,都会有飞机不能及时降落。

评测用例规模与约定

对于 30 % 30\% 30% 的评测用例, N ≤ 2 N ≤ 2 N2
对于 100 % 100\% 100% 的评测用例, 1 ≤ T ≤ 10 1 ≤ T ≤ 10 1T10 1 ≤ N ≤ 10 1 ≤ N ≤ 10 1N10 0 ≤ T i , D i , L i ≤ 1 0 5 0 ≤ T_i, D_i, L_i ≤ 10^5 0Ti,Di,Li105

思路

本来以为要贪心然后排序去做,手推了几个发现贪心不对,重新看了眼数据范围,发现是个纯暴力的题?

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 10;
bool st[N];
int n;
bool flag = false;
int t[N], d[N], l[N];

void dfs(int u, int last) {
    if (flag) return;
    if (u == n) {
        flag = true;
        return;
    }
    for (int i = 0; i < n; i++) {
        if (!st[i]) {
            if (t[i] + d[i] >= last) {
                st[i] = true;
                if (t[i] > last) dfs(u + 1, t[i] + l[i]);
                else dfs(u + 1, last + l[i]);
                st[i] = false;
            } else return;
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> l[i];
        for (int i = 0; i < N; i++) st[i] = false;
        flag = false;
        dfs(0, 0);
        if (flag) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

E: 接龙数列(15分)

问题描述

对于一个长度为 K K K 的整数数列: A 1 , A 2 , . . . , A K A_1, A_2,..., A_K A1,A2,...,AK,我们称之为接龙数列当且仅当 A i A_i Ai 的首位数字恰好等于 A i − 1 A_{i−1} Ai1 的末位数字 ( 2 ≤ i ≤ K ) (2 ≤ i ≤ K) (2iK)

例如 12 , 23 , 35 , 56 , 61 , 11 12, 23, 35, 56, 61, 11 12,23,35,56,61,11 是接龙数列; 12 , 23 , 34 , 56 12, 23, 34, 56 12,23,34,56 不是接龙数列,因为 56 56 56的首位数字不等于 34 34 34 的末位数字。所有长度为 1 1 1 的整数数列都是接龙数列。

现在给定一个长度为 N N N 的数列 A 1 , A 2 , . . . , A N A_1, A_2,..., A_N A1,A2,...,AN,请你计算最少从中删除多少个数,可以使剩下的序列是接龙序列?

输入格式

第一行包含一个整数 N N N
第二行包含 N N N 个整数 A 1 , A 2 , . . . , A N A_1, A_2, ... ,A_N A1,A2,...,AN

输出格式

一个整数代表答案

样例输入

5
11 121 22 12 2023

样例输出

1

样例说明

删除 22 22 22,剩余 11 , 121 , 12 , 2023 11, 121, 12, 2023 11,121,12,2023 是接龙数列。

评测用例规模与约定

对于 30 % 30\% 30% 的评测用例, 1 ≤ N ≤ 20 1 ≤ N ≤ 20 1N20
对于 50 % 50\% 50% 的评测用例, 1 ≤ N ≤ 1 0 4 1 ≤ N ≤ 10^4 1N104
对于 100 % 100\% 100% 的评测用例, 1 ≤ N ≤ 1 0 5 1 ≤ N ≤ 10^5 1N105 1 ≤ A i ≤ 1 0 9 1 ≤ A_i ≤ 10^9 1Ai109。所有 A i A_i Ai 保证不包含前导 0 0 0

思路

动态规划,定义 d p [ i ] [ j ] dp[i][j] dp[i][j]为用到第 i i i个,结尾为 j j j最少要删掉的元素数量

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5 + 10;
int dp[N][10];
int a[N];

int inline tou(int x) {
    while (x >= 10) {
        x /= 10;
    }
    return x;
}

int inline wei(int x) {
    return x % 10;
}

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < 10; j++) {
            dp[i][j] = 0x3f3f3f3f;
        }
    }
    for (int i = 1; i <= n; i++) {
        int t = tou(a[i]);
        int w = wei(a[i]);
        for (int j = 1; j <= 9; j++) dp[i][j] = dp[i - 1][j] + 1;
        dp[i][w] = min(dp[i][w], dp[i - 1][t]);
        dp[i][w] = min(dp[i][w], i - 1);
    }
    int ans = dp[n][1];
    for (int i = 2; i <= 9; i++) ans = min(ans, dp[n][i]);
    cout << ans << endl;
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

F: 岛屿个数(15分)

问题描述

小蓝得到了一副大小为 M × N M × N M×N 的格子地图,可以将其视作一个只包含字符 ‘ 0 ’ ‘0’ ‘0’(代表海水)和 ‘ 1 ’ ‘1’ ‘1’(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 ‘ 1 ’ ‘1’ ‘1’相连接而形成。

在岛屿 A A A 所占据的格子中,如果可以从中选出 k k k 个不同的格子,使得他们的坐标能够组成一个这样的排列: ( x 0 , y 0 ) , ( x 1 , y 1 ) , . . . , ( x k − 1 , y k − 1 ) (x_0, y_0), (x_1,y_1),..., (x_{k−1}, y_{k−1}) (x0,y0),(x1,y1),...,(xk1,yk1),其中 ( x ( i + 1 ) % k , y ( i + 1 ) % k ) (x_{(i+1)\%k}, y_{(i+1)\%k}) (x(i+1)%k,y(i+1)%k) 是由 ( x i , y i ) (x_i, y_i) (xi,yi) 通过上/下/左/右移动一次得来的 ( 0 ≤ i ≤ k − 1 ) (0 ≤ i ≤ k − 1) (0ik1),此时这 k k k个格子就构成了一个“环”。如果另一个岛屿 B B B 所占据的格子全部位于这个“环” 内部,此时我们将岛屿 B B B 视作是岛屿 A A A 的子岛屿。若 B B B A A A 的子岛屿, C C C 又是 B B B 的子岛屿,那 C C C 也是 A A A 的子岛屿。

请问这个地图上共有多少个岛屿?在进行统计时不需要统计子岛屿的数目。

输入格式

第一行一个整数 T T T,表示有 T T T 组测试数据。
接下来输入 T T T 组数据。对于每组数据,第一行包含两个用空格分隔的整数 M M M N N N 表示地图大小;接下来输入 M M M 行,每行包含 N N N 个字符,字符只可能是 ‘ 0 ’ ‘0’ ‘0’ ‘ 1 ’ ‘1’ ‘1’

输出格式

对于每组数据,输出一行,包含一个整数表示答案。

样例输入

2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111

样例输出

1
3

样例说明

对于第一组数据,包含两个岛屿,下面用不同的数字进行了区分:

01111
11001
10201
10001
11111

岛屿 2 2 2 在岛屿 1 1 1 的“环” 内部,所以岛屿 2 2 2 是岛屿 1 1 1 的子岛屿,答案为 1 1 1
对于第二组数据,包含三个岛屿,下面用不同的数字进行了区分:

111111
100001
020301
100001
111111

注意岛屿 3 3 3 并不是岛屿 1 1 1 或者岛屿 2 2 2 的子岛屿,因为岛屿 1 1 1 和岛屿 2 2 2 中均没有“环”。

评测用例规模与约定

对于 30 % 30\% 30% 的评测用例, 1 ≤ M , N ≤ 10 1 ≤ M,N ≤ 10 1M,N10
对于 100 % 100\% 100% 的评测用例, 1 ≤ T ≤ 10 , 1 ≤ M , N ≤ 50 1 ≤T≤ 10, 1 ≤ M,N ≤ 50 1T10,1M,N50

思路

这个题蛮有意思的,如果不考虑子岛屿的话,基本上是白送分题hhh。如果考虑子岛屿就需要判断是不是成环,以及另一个岛屿是不是在这个成环的岛屿中。不妨换个思路看,如果一个岛屿不在另一个岛屿中,则这个岛屿在有水的地方(为’0’的地方)一定是跟外界连通的(注意此处的连通包括对角线这种连通)。可以用这个思路去写代码会更简单一些。

#include<iostream>
#include<algorithm>
#include<queue>

using namespace std;
typedef long long ll;

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

int n, m;
char graph[60][60];
bool vis[60][60];

bool fill(int A, int B) {
    for (int i = 0; i <= n + 1; i++) {
        for (int j = 0; j <= m + 1; j++) {
            vis[i][j] = false;
        }
    }
    queue<pair<int, int> > q;
    q.emplace(A, B);
    vis[A][B] = true;
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx < 1 || nx > n || ny < 1 || ny > m) return true;
            if (graph[nx][ny] == '0' && !vis[nx][ny]) {
                vis[nx][ny] = true;
                q.emplace(nx, ny);
            }
        }
    }
    return false;
}

void bfs(int A, int B) {
    queue<pair<int, int> > q;
    q.emplace(A, B);
    while (!q.empty()) {
        auto cur = q.front();
        q.pop();
        int x = cur.first, y = cur.second;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && graph[nx][ny] == '1') {
                graph[nx][ny] = '0';
                q.emplace(nx, ny);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cin >> graph[i][j];
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (graph[i][j] == '1') {
                    if (!fill(i, j))
                        graph[i][j] = '0';
                }
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (graph[i][j] == '1') {
                    ans++;
                    bfs(i, j);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90

G: 子串简写(20分)

问题描述

程序猿圈子里正在流行一种很新的简写方法:对于一个字符串,只保留首尾字符,将首尾字符之间的所有字符用这部分的长度代替。例如internationalization简写成i18nKubernetes 简写成K8s, Lanqiao 简写成L5o 等。

在本题中,我们规定长度大于等于 K K K 的字符串都可以采用这种简写方法(长度小于 K K K 的字符串不配使用这种简写)。

给定一个字符串 S S S 和两个字符 c 1 c_1 c1 c 2 c_2 c2,请你计算 S S S 有多少个以 c 1 c_1 c1 开头 c 2 c_2 c2 结尾的子串可以采用这种简写?

输入格式

第一行包含一个整数 K K K
第二行包含一个字符串 S S S 和两个字符 c 1 c_1 c1 c 2 c_2 c2

输出格式

一个整数代表答案。

样例输入

4
abababdb a b

样例输出

6

样例说明

符合条件的子串如下所示,中括号内是该子串:

[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]

评测用例规模与约定

对于 30 % 30\% 30% 的评测用例, 2 ≤ K ≤ ∣ S ∣ ≤ 10000 2 ≤ K ≤ |S | ≤ 10000 2KS10000
对于 100 % 100\% 100% 的评测用例, 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 0 5 2 ≤ K ≤ |S | ≤ 5 × 10^5 2KS5×105 S S S 只包含小写字母。 c 1 c_1 c1 c 2 c_2 c2 都是小写字母。
∣ S ∣ |S | S 代表字符串 S S S 的长度。

思路

感觉也算个数学思维题,感觉跟前缀和有点像。

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;

string s;
int sum[maxn];

int main() {
    int k;
    cin >> k;
    cin >> s;
    int n = s.size();
    char a, b;
    cin >> a >> b;
    for (int i = 1; i <= n; i++) {
        if (s[i - 1] == b) sum[i] = 1;
        sum[i] += sum[i - 1];
    }
    ll ans = 0;
    for (int i = 1; i + k - 1 <= n; i++) {
        if (s[i - 1] == a) ans += sum[n] - sum[i + k - 2];
    }
    cout << ans << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32

H: 整数删除(20分)

问题描述

给定一个长度为 N N N 的整数数列: A 1 , A 2 , . . . , A N A_1, A_2, ..., A_N A1,A2,...,AN。你要重复以下操作 K K K 次:
每次选择数列中最小的整数(如果最小值不止一个,选择最靠前的),将其删除。并把与它相邻的整数加上被删除的数值。
输出 K K K次操作后的序列。

输入格式

第一行包含两个整数 N N N K K K
第二行包含 N N N 个整数, A 1 , A 2 , A 3 , . . . , A N A_1, A_2, A_3, ..., A_N A1,A2,A3,...,AN

输出格式

输出 N − K N − K NK 个整数,中间用一个空格隔开,代表 K 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 % 20\% 20% 的评测用例, 1 ≤ K ≤ N ≤ 1 0 4 1 ≤K ≤N ≤ 10^4 1KN104
对于 100 % 100\% 100% 的评测用例, 1 ≤ K ≤ N ≤ 5 × 1 0 5 1 ≤K ≤N ≤ 5 ×10^5 1KN5×105 0 ≤ A i ≤ 1 0 8 0 ≤ A_i ≤ 10^8 0Ai108

思路

堆+链表。因为需要频繁删除元素,故考虑使用链表,又因为需要找最小,因此可以使用堆解决。这题最大会爆int,因此必须开long long。

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;

const int maxn = 5e5 + 10;

ll v[maxn], l[maxn], r[maxn];

void del(ll x) {
    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<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
    r[0] = 1, l[n + 1] = n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        l[i] = i - 1;
        r[i] = i + 1;
        pq.emplace(v[i], i);
    }
    while (k--) {
        auto p = pq.top();
        pq.pop();
        if (p.first != v[p.second]) {
            pq.emplace(v[p.second], p.second);
            k++;
        } else del(p.second);
    }
    ll head = r[0];
    while (head != n + 1) {
        cout << v[head] << " ";
        head = r[head];
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42

I: 景区导游(25分)

问题描述

某景区一共有 N N N 个景点,编号 1 1 1 N N N。景点之间共有 N − 1 N − 1 N1 条双向的摆渡车线路相连,形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行,需要花费一定的时间。

小明是这个景区的资深导游,他每天都要按固定顺序带客人游览其中 K K K 个景点: A 1 , A 2 , . . . , A K A_1, A_2, ... , A_K A1,A2,...,AK。今天由于时间原因,小明决定跳过其中一个景点,只带游客按顺序游览其中 K − 1 K − 1 K1 个景点。具体来说,如果小明选择跳过 A i A_i Ai,那么他会按顺序带游客游览 A 1 , A 2 , . . . , A i − 1 , A i + 1 , . . . , A K ( 1 ≤ i ≤ K ) A_1, A_2,..., A_{i−1}, A_{i+1},..., A_K(1 ≤ i ≤ K) A1,A2,...,Ai1,Ai+1,...,AK(1iK)

请你对任意一个 A i A_i Ai,计算如果跳过这个景点,小明需要花费多少时间在景点之间的摆渡车上?

输入格式

第一行包含 2 2 2 个整数 N N N K K K
以下 N − 1 N − 1 N1 行,每行包含 3 3 3 个整数 u , v u, v u,v t t t,代表景点 u u u v v v 之间有摆渡车线路,花费 t t t 个单位时间。
最后一行包含 K K K 个整数 A 1 , A 2 , . . . , A K A_1, A_2,..., A_K A1,A2,...,AK 代表原定游览线路。

输出格式

输出 K K K 个整数,其中第 i i i 个代表跳过 A i A_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 2651
当跳过 2 2 2 时,路线是 6 → 5 → 1 6 → 5 → 1 651,其中 6 → 5 6 → 5 65 花费时间 3 + 2 + 2 = 7 3 + 2 + 2 = 7 3+2+2=7 5 → 1 5 → 1 51 花费时间 2 + 1 = 3 2 + 1 = 3 2+1=3,总时间花费 10 10 10
当跳过 6 6 6 时,路线是 2 → 5 → 1 2 → 5 → 1 251,其中 2 → 5 2 → 5 25 花费时间 1 + 1 + 2 = 4 1 + 1 + 2 = 4 1+1+2=4 5 → 1 5 → 1 51 花费时间 2 + 1 = 3 2 + 1 = 3 2+1=3,总时间花费 7 7 7
当跳过 5 5 5 时,路线是 2 → 6 → 1 2 → 6 → 1 261,其中 2 → 6 2 → 6 26 花费时间 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 = 7 1+1+2+3=7 6 → 1 6 → 1 61 花费时间 3 + 2 + 1 = 6 3 + 2 + 1 = 6 3+2+1=6,总时间花费 13 13 13
当跳过 1 1 1 时,路线时 2 → 6 → 5 2 → 6 → 5 265,其中 2 → 6 2 → 6 26 花费时间 1 + 1 + 2 + 3 = 7 1 + 1 + 2 + 3 = 7 1+1+2+3=7 6 → 5 6 → 5 65 花费时间 3 + 2 + 2 = 7 3 + 2 + 2 = 7 3+2+2=7,总时间花费 14 14 14

评测用例规模与约定

对于 20 % 20\% 20% 的数据, 2 ≤ K ≤ N ≤ 1 0 2 2 ≤ K ≤ N ≤ 10^2 2KN102
对于 40 % 40\% 40% 的数据, 2 ≤ K ≤ N ≤ 1 0 4 2 ≤ K ≤ N ≤ 10^4 2KN104
对于 100 % 100\% 100% 的数据, 2 ≤ K ≤ N ≤ 1 0 5 , 1 ≤ u , v , A i ≤ N 2 ≤ K ≤ N ≤ 10^5,1 ≤ u, v, A_i ≤ N 2KN1051u,v,AiN 1 ≤ t ≤ 1 0 5 1 ≤ t ≤ 10^5 1t105。保证 A i A_i Ai 两两不同。

思路

一眼LCA,如果用floyd过不去所有数据

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

vector<pair<int, int>> e[maxn];
ll fa[maxn], dep[maxn], son[maxn], siz[maxn], top[maxn];
ll c[maxn], suf[maxn];
ll sum[maxn];

void dfs1(ll u, ll f, ll val) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    sum[u] = val;
    for (auto x: e[u]) {
        ll v = x.first;
        if (v == f) continue;
        dfs1(v, u, val + x.second);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(ll u, ll t) {
    top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (auto x: e[u]) {
        ll v = x.first;
        if (v != son[u] && v != fa[u]) dfs2(v, v);
    }
}

ll lca(ll x, ll y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] > dep[y] ? y : x;
}

ll get(ll x, ll y) {
    if (x == 0 || y == 0) return 0;
    return sum[x] + sum[y] - 2 * sum[lca(x, y)];
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, z;
        cin >> u >> v >> z;
        e[u].emplace_back(v, z);
        e[v].emplace_back(u, z);
    }
    dfs1(1, 1, 0);
    dfs2(1, 1);
    for (int i = 1; i <= k; i++) cin >> c[i];
    for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] + get(c[i], c[i + 1]);
    ll pre = 0;
    for (int i = 1; i <= k; i++) {
        cout << pre + get(c[i - 1], c[i + 1]) + suf[i + 1] << " ";
        pre += get(c[i - 1], c[i]);
    }
    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75

J: 砍树(25分)

问题描述

给定一棵由 n n n 个结点组成的树以及 m m m 个不重复的无序数对 ( a 1 , b 1 ) , ( a 2 , b 2 ) , . . . , ( a m , b m ) (a_1, b_1), (a_2, b_2),... , (a_m, b_m) (a1,b1),(a2,b2),...,(am,bm),其中 a i a_i ai 互不相同, b i b_i bi 互不相同, a i , b j ( 1 ≤ i , j ≤ m ) a_i , b_j(1 ≤ i, j ≤ m) ai,bj(1i,jm)

小明想知道是否能够选择一条树上的边砍断,使得对于每个 ( a i , b i ) (a_i, b_i) (ai,bi) 满足 a i 和 b i a_i和b_i aibi 不连通,如果可以则输出应该断掉的边的编号(编号按输入顺序从 1 1 1 开始),否则输出 − 1 -1 1

输入格式

输入共 n + m n + m n+m 行,第一行为两个正整数 n n n m m m
后面 n − 1 n − 1 n1 行,每行两个正整数 x i , y i x_i,y_i xiyi 表示第 i i i 条边的两个端点。
后面 m m m 行,每行两个正整数 a i , b i a_i,b_i aibi

输出格式

一行一个整数,表示答案,如有多个答案,输出编号最大的一个。

样例输入

6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5

样例输出

4

样例说明

断开第 2 2 2 条边后形成两个连通块: { 3 , 4 } , { 1 , 2 , 5 , 6 } \{3, 4\},\{1, 2, 5, 6\} {3,4}{1,2,5,6},满足 3 3 3 6 6 6 不连通, 4 4 4 5 5 5 不连通。
断开第 4 4 4 条边后形成两个连通块: { 1 , 2 , 3 , 4 } , { 5 , 6 } \{1, 2, 3, 4\},\{5, 6\} {1,2,3,4}{5,6},同样满足 3 3 3 和6 不连通, 4 4 4 5 5 5 不连通。
4 4 4 编号更大,因此答案为 4 4 4

评测用例规模与约定

对于 30 % 30\% 30% 的评测用例, 1 ≤ N ≤ 1 0 3 1 ≤ N ≤ 10^3 1N103
对于 100 % 100\% 100% 的评测用例, 1 ≤ N ≤ 1 0 5 1 ≤ N ≤ 10^5 1N105 1 ≤ m ≤ n 2 1 ≤ m ≤ \frac{n}{2} 1m2n

思路

感觉这题输出格式写的有问题,只砍断一条边,并且多个答案只输出最大的,那应该输出只有一个数,为啥一行一个整数…没懂。

解法的话应该是树上边差分的板子题。对于每个 ( a i , b i ) (a_i, b_i) (ai,bi) 满足 a i 和 b i a_i和b_i aibi 不连通,则断开的边一定在 a i → L C A ( a i , b i ) a_i → LCA(a_i,b_i) aiLCA(ai,bi) b i → L C A ( a i , b i ) b_i → LCA(a_i,b_i) biLCA(ai,bi)上。相当于对上面区间贡献度+1,因此贡献度和为 m m m的边为最后的解,如果不存在则无解。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 50;

vector<int> e[maxn];
ll fa[maxn], dep[maxn], son[maxn], siz[maxn], top[maxn];
ll diff[maxn];

void dfs1(ll u, ll f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    siz[u] = 1;
    for (auto x: e[u]) {
        ll v = x;
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(ll u, ll t) {
    top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (auto x: e[u]) {
        ll v = x;
        if (v != son[u] && v != fa[u]) dfs2(v, v);
    }
}

ll lca(ll x, ll y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = fa[top[x]];
    }
    return dep[x] > dep[y] ? y : x;
}

void dfs(int x, int fx) {
    for (auto y: e[x]) {
        if (y == fx) continue;
        dfs(y, x);
        diff[x] += diff[y];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    dfs1(1, 1);
    dfs2(1, 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        diff[u]++, diff[v]++, diff[lca(u, v)] -= 2;
    }
    dfs(1, 0);
    ll ans = -1;
    for (int i = 0; i <= n; i++) if (diff[i] >= m) ans = i - 1;
    cout << ans << endl;
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/430180
推荐阅读
相关标签
  

闽ICP备14008679号