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

admin • 2023-04-10 21:02 • 物联网

第十四届蓝桥杯C++B组复盘

A: 日期统计（5分）
- 问题描述
- 思路
B: 01 串的熵（5分）
- 问题描述
- 思路
C: 冶炼金属（10分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
D: 飞机降落（10分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
E: 接龙数列（15分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
F: 岛屿个数（15分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
G: 子串简写（20分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
H: 整数删除（20分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
I: 景区导游（25分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路
J: 砍树（25分）
- 问题描述
- 输入格式
- 输出格式
- 样例输入
- 样例输出
- 样例说明
- 评测用例规模与约定
- 思路

这届蓝桥杯跟上届蓝桥杯一样，只有2个填空题，8个编程的大题。本届蓝桥杯我愿称之为~~四小时怒开九道题~~ 。难度跟上届相比，没有那么多思维题，反倒板子题多了，不知道其他组是不是也是这样。

A: 日期统计（5分）

问题描述

小蓝现在有一个长度为

100

$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

现在他想要从这个数组中寻找一些满足以下条件的子序列：

子序列的长度为8；
这个子序列可以按照下标顺序组成一个yyyymmdd 格式的日期，并且要求这个日期是2023 年中的某一天的日期，例如20230902，20231223。yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
请你帮小蓝计算下按上述条件一共能找到多少个不同的2023 年的日期。
对于相同的日期你只需要统计一次即可。

思路

从前到后观察可以发现能凑出来2023的并不多，因此可以直接用for跑暴力。结果是235

B: 01 串的熵（5分）

问题描述

对于一个长度为

$n$ 的

$01$ 串

S = x_1x_2x_3...x_n

$S = x_{1} x_{2} x_{3} ... x_{n}$ ，香农信息熵的定义为

(

)

−

∑

(

)

log

⁡

(

)

H(S)=-sum^n_1p(x_i)log_2(p(x_i))

$H (S) = - \sum_{1 n} p (x_{i}) lo g_{2} (p (x_{i}))$ ，其中

(

)

(

)

p(0), p(1)

$p (0), p (1)$ 表示在这个

$01$ 串中

$0$ 和

$1$ 出现的占比。比如，对于

100

S = 100

$S = 100$ 来说，信息熵

(

)

−

log

⁡

(

)

−

log

⁡

(

)

−

log

⁡

(

)

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) = - \frac{1}{3} lo g_{2} (\frac{1}{3}) - \frac{2}{3} lo g_{2} (\frac{2}{3}) - \frac{2}{3} lo g_{2} (\frac{2}{3}) = 1.3083$ 。对于一个长度为

23333333

$23333333$ 的

$01$ 串，如果其信息熵为

11625907.5798

$11625907.5798$ ，且

$0$ 出现次数比

$1$ 少，那么这个

$01$ 串中

$0$ 出现了多少次？

思路

枚举一下0的个数，计算的时候要开double保证精度。结果是11027421

C: 冶炼金属（10分）

问题描述

小蓝有一个神奇的炉子用于将普通金属

$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

样例说明

当

V = 20

$V = 20$ 时，有：

⌊

⌋

lfloor frac{75}{20}=3 rfloor

$⌊ \frac{75}{20} = 3 ⌋$ ，

⌊

⌋

lfloor frac{53}{20}=2 rfloor

$⌊ \frac{53}{20} = 2 ⌋$ ，

⌊

⌋

lfloor frac{59}{20}=2 rfloor

$⌊ \frac{59}{20} = 2 ⌋$ 可以看到符合所有冶炼记录。
当

V = 25

$V = 25$ 时，有：

⌊

⌋

lfloor frac{75}{25}=3 rfloor

$⌊ \frac{75}{25} = 3 ⌋$ ，

⌊

⌋

lfloor frac{53}{25}=2 rfloor

$⌊ \frac{53}{25} = 2 ⌋$ ，

⌊

⌋

lfloor frac{59}{25}=2 rfloor

$⌊ \frac{59}{25} = 2 ⌋$ 可以看到符合所有冶炼记录。
且再也找不到比

$20$ 更小或者比

$25$ 更大的符合条件的

$V$ 值了。

评测用例规模与约定

对于

30%

$30%$ 的评测用例，

≤

1 ≤ N ≤ 10^2

$1 \leq N \leq 1 0^{2}$ 。
对于

60%

$60%$ 的评测用例，

≤

1 ≤ N ≤ 10^3

$1 \leq N \leq 1 0^{3}$ 。
对于

100

100%

$100%$ 的评测用例，

≤

1 ≤ N ≤ 10^4

$1 \leq N \leq 1 0^{4}$ ，

≤

1 ≤ B ≤ A ≤ 10^9

$1 \leq B \leq A \leq 1 0^{9}$ 。

思路

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

#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;
}

D: 飞机降落（10分）

问题描述

$N$ 架飞机准备降落到某个只有一条跑道的机场。其中第

$i$ 架飞机在

T_i

$T_{i}$ 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋

D_i

$D_{i}$ 个单位时间，即它最早可以于

T_i

$T_{i}$ 时刻开始降落，最晚可以于

T_i+ D_i

$T_{i} + D_{i}$ 时刻开始降落。降落过程需要

L_i

$L_{i}$ 个单位时间。

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

请你判断

$N$ 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。
第一行包含一个整数

$T$ ，代表测试数据的组数。
对于每组数据，第一行包含一个整数

$N$ 。
以下

$N$ 行，每行包含三个整数：

T_i

$T_{i}$ ，

D_i

$D_{i}$ 和

L_i

$L_{i}$ 。

输出格式

对于每组数据，输出

YES

$Y ES$ 或者

$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%

$30%$ 的评测用例，

≤

N ≤ 2

$N \leq 2$ 。
对于

100

100%

$100%$ 的评测用例，

≤

1 ≤ T ≤ 10

$1 \leq T \leq 10$ ，

≤

1 ≤ N ≤ 10

$1 \leq N \leq 10$ ，

≤

0 ≤ T_i, D_i, L_i ≤ 10^5

$0 \leq T_{i}, D_{i}, L_{i} \leq 1 0^{5}$ 。

思路

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

#include<iostream>
#include<algorithm>

using namespace std;

const int maxn = 1e4 + 10;

int t[maxn], d[maxn], l[maxn];
int p[20];

int main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> t[i] >> d[i] >> l[i];
        for (int i = 1; i <= n; i++) p[i] = i;
        bool ans = false;
        do {
            int temp = 0;
            bool flag = true;
            for (int w = 1; w <= n; w++) {
                int i = p[w];
                temp = max(temp, t[i]);
                if (temp > t[i] + d[i]) {
                    flag = false;
                    break;
                }
                temp += l[i];
            }
            if (flag) {
                ans = true;
                break;
            }
        } while (next_permutation(p + 1, p + 1 + n));
        if (ans)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

E: 接龙数列（15分）

问题描述

对于一个长度为

$K$ 的整数数列：

A_1, A_2,..., A_K

$A_{1}, A_{2}, ..., A_{K}$ ，我们称之为接龙数列当且仅当

A_i

$A_{i}$ 的首位数字恰好等于

−

A_{i−1}

$A_{i - 1}$ 的末位数字

(

≤

)

(2 ≤ i ≤ K)

$(2 \leq i \leq K)$ 。

例如

12, 23, 35, 56, 61, 11

$12, 23, 35, 56, 61, 11$ 是接龙数列；

12, 23, 34, 56

$12, 23, 34, 56$ 不是接龙数列，因为

$56$ 的首位数字不等于

$34$ 的末位数字。所有长度为

$1$ 的整数数列都是接龙数列。

现在给定一个长度为

$N$ 的数列

A_1, A_2,..., A_N

$A_{1}, A_{2}, ..., A_{N}$ ，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数

$N$ 。
第二行包含

$N$ 个整数

A_1, A_2, ... ,A_N

$A_{1}, A_{2}, ..., A_{N}$ 。

输出格式

一个整数代表答案

样例输入

5
11 121 22 12 2023

样例输出

1

样例说明

删除

$22$ ，剩余

121

2023

11, 121, 12, 2023

$11, 121, 12, 2023$ 是接龙数列。

评测用例规模与约定

对于

30%

$30%$ 的评测用例，

≤

1 ≤ N ≤ 20

$1 \leq N \leq 20$ 。
对于

50%

$50%$ 的评测用例，

≤

1 ≤ N ≤ 10^4

$1 \leq N \leq 1 0^{4}$ 。
对于

100

100%

$100%$ 的评测用例，

≤

1 ≤ N ≤ 10^5

$1 \leq N \leq 1 0^{5}$ ，

≤

1 ≤ A_i ≤ 10^9

$1 \leq A_{i} \leq 1 0^{9}$ 。所有

A_i

$A_{i}$ 保证不包含前导

$0$ 。

思路

动态规划，定义

[

]

[

]

dp[i][j]

$d p [i] [j]$ 为用到第

$i$ 个，结尾为

$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;
}

F: 岛屿个数（15分）

问题描述

小蓝得到了一副大小为

M × N

$M \times N$ 的格子地图，可以将其视作一个只包含字符

‘

’

‘0’

$‘0’$ （代表海水）和

‘

’

‘1’

$‘1’$ （代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的

‘

’

‘1’

$‘1’$ 相连接而形成。

在岛屿

$A$ 所占据的格子中，如果可以从中选出

$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})$ ，其中

(

)

(

)

(x_{(i+1)%k}, y_{(i+1)%k})

$(x_{(i + 1) % k}, y_{(i + 1) % k})$ 是由

(

)

(x_i, y_i)

$(x_{i}, y_{i})$ 通过上/下/左/右移动一次得来的

(

≤

−

)

(0 ≤ i ≤ k − 1)

$(0 \leq i \leq k - 1)$ ，此时这

$k$ 个格子就构成了一个“环”。如果另一个岛屿

$B$ 所占据的格子全部位于这个“环” 内部，此时我们将岛屿

$B$ 视作是岛屿

$A$ 的子岛屿。若

$B$ 是

$A$ 的子岛屿，

$C$ 又是

$B$ 的子岛屿，那

$C$ 也是

$A$ 的子岛屿。

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

输入格式

第一行一个整数

$T$ ，表示有

$T$ 组测试数据。
接下来输入

$T$ 组数据。对于每组数据，第一行包含两个用空格分隔的整数

$M$ 、

$N$ 表示地图大小；接下来输入

$M$ 行，每行包含

$N$ 个字符，字符只可能是

‘

’

‘0’

$‘0’$ 或

‘

’

‘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$ 在岛屿

$1$ 的“环” 内部，所以岛屿

$2$ 是岛屿

$1$ 的子岛屿，答案为

$1$ 。
对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：

111111
100001
020301
100001
111111

注意岛屿

$3$ 并不是岛屿

$1$ 或者岛屿

$2$ 的子岛屿，因为岛屿

$1$ 和岛屿

$2$ 中均没有“环”。

评测用例规模与约定

对于

30%

$30%$ 的评测用例，

≤

1 ≤ M,N ≤ 10

$1 \leq M, N \leq 10$ 。
对于

100

100%

$100%$ 的评测用例，

≤

1 ≤T≤ 10, 1 ≤ M,N ≤ 50

$1 \leq T \leq 10, 1 \leq M, N \leq 50$ 。

思路

这个题蛮有意思的，如果不考虑子岛屿的话，基本上是白送分题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;
}

G: 子串简写（20分）

问题描述

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

在本题中，我们规定长度大于等于

$K$ 的字符串都可以采用这种简写方法（长度小于

$K$ 的字符串不配使用这种简写）。

给定一个字符串

$S$ 和两个字符

c_1

$c_{1}$ 和

c_2

$c_{2}$ ，请你计算

$S$ 有多少个以

c_1

$c_{1}$ 开头

c_2

$c_{2}$ 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数

$K$ 。
第二行包含一个字符串

$S$ 和两个字符

c_1

$c_{1}$ 和

c_2

$c_{2}$ 。

输出格式

一个整数代表答案。

样例输入

4
abababdb a b

样例输出

6

样例说明

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

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

评测用例规模与约定

对于

30%

$30%$ 的评测用例，

≤

∣

≤

10000

2 ≤ K ≤ |S | ≤ 10000

$2 \leq K \leq ∣ S ∣ \leq 10000$ 。
对于

100

100%

$100%$ 的评测用例，

≤

∣

≤

2 ≤ K ≤ |S | ≤ 5 × 10^5

$2 \leq K \leq ∣ S ∣ \leq 5 \times 1 0^{5}$ 。

$S$ 只包含小写字母。

c_1

$c_{1}$ 和

c_2

$c_{2}$ 都是小写字母。

∣

|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;
}

H: 整数删除（20分）

问题描述

给定一个长度为

$N$ 的整数数列：

A_1, A_2, ..., A_N

$A_{1}, A_{2}, ..., A_{N}$ 。你要重复以下操作

$K$ 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出

$K$ 次操作后的序列。

输入格式

第一行包含两个整数

$N$ 和

$K$ 。
第二行包含

$N$ 个整数，

A_1, A_2, A_3, ..., A_N

$A_{1}, A_{2}, A_{3}, ..., A_{N}$ 。

输出格式

输出

−

N − K

$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%

$20%$ 的评测用例，

≤

1 ≤K ≤N ≤ 10^4

$1 \leq K \leq N \leq 1 0^{4}$ 。
对于

100

100%

$100%$ 的评测用例，

≤

1 ≤K ≤N ≤ 5 ×10^5

$1 \leq K \leq N \leq 5 \times 1 0^{5}$ ，

≤

0 ≤ A_i ≤ 10^8

$0 \leq A_{i} \leq 1 0^{8}$ 。

思路

没想到啥好方法，用个set维护有序性并记录相应的下标，每次取下标处理。这题最后数据范围会爆iint，需要开long long。

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

using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;

ll num[maxn];
int ls[maxn], rs[maxn];

int main() {
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    rs[0] = 1;
    set<pair<ll, int>> s;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        s.insert({num[i], i});
    }
    for (int i = 0; i <= n + 1; i++) {
        ls[i] = i - 1;
        rs[i] = i + 1;
    }
    while (k--) {
        auto cur = *s.begin();
        int cIndex = cur.second;
        int lIndex = ls[cIndex];
        int rIndex = rs[cIndex];
        s.erase(cur);
        s.erase({num[lIndex], lIndex});
        s.erase({num[rIndex], rIndex});
        num[lIndex] += num[cIndex];
        num[rIndex] += num[cIndex];
        rs[lIndex] = rIndex;
        ls[rIndex] = lIndex;
        if (lIndex > 0) s.insert({num[lIndex], lIndex});
        if (rIndex <= n) s.insert({num[rIndex], rIndex});
    }
    int cur = rs[0];
    while (cur <= n) {
        cout << num[cur] << " ";
        cur = rs[cur];
    }
    return 0;
}

I: 景区导游（25分）

问题描述

某景区一共有

$N$ 个景点，编号

$1$ 到

$N$ 。景点之间共有

−

N − 1

$N - 1$ 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中

$K$ 个景点：

A_1, A_2, ... , A_K

$A_{1}, A_{2}, ..., A_{K}$ 。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中

−

K − 1

$K - 1$ 个景点。具体来说，如果小明选择跳过

A_i

$A_{i}$ ，那么他会按顺序带游客游览

−

(

≤

)

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 \leq i \leq K)$ 。

请你对任意一个

A_i

$A_{i}$ ，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？

输入格式

第一行包含

$2$ 个整数

$N$ 和

$K$ 。
以下

−

N − 1

$N - 1$ 行，每行包含

$3$ 个整数

u, v

$u, v$ 和

$t$ ，代表景点

$u$ 和

$v$ 之间有摆渡车线路，花费

$t$ 个单位时间。
最后一行包含

$K$ 个整数

A_1, A_2,..., A_K

$A_{1}, A_{2}, ..., A_{K}$ 代表原定游览线路。

输出格式

输出

$K$ 个整数，其中第

$i$ 个代表跳过

A_i

$A_{i}$ 之后，花费在摆渡车上的时间。

样例输入

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 \to 6 \to 5 \to 1$ 。
当跳过

$2$ 时，路线是

→

6 → 5 → 1

$6 \to 5 \to 1$ ，其中

→

6 → 5

$6 \to 5$ 花费时间

3 + 2 + 2 = 7

$3 + 2 + 2 = 7$ ，

→

5 → 1

$5 \to 1$ 花费时间

2 + 1 = 3

$2 + 1 = 3$ ，总时间花费

$10$ 。
当跳过

$6$ 时，路线是

→

2 → 5 → 1

$2 \to 5 \to 1$ ，其中

→

2 → 5

$2 \to 5$ 花费时间

1 + 1 + 2 = 4

$1 + 1 + 2 = 4$ ，

→

5 → 1

$5 \to 1$ 花费时间

2 + 1 = 3

$2 + 1 = 3$ ，总时间花费

$7$ 。
当跳过

$5$ 时，路线是

→

2 → 6 → 1

$2 \to 6 \to 1$ ，其中

→

2 → 6

$2 \to 6$ 花费时间

1 + 1 + 2 + 3 = 7

$1 + 1 + 2 + 3 = 7$ ，

→

6 → 1

$6 \to 1$ 花费时间

3 + 2 + 1 = 6

$3 + 2 + 1 = 6$ ，总时间花费

$13$ 。
当跳过

$1$ 时，路线时

→

2 → 6 → 5

$2 \to 6 \to 5$ ，其中

→

2 → 6

$2 \to 6$ 花费时间

1 + 1 + 2 + 3 = 7

$1 + 1 + 2 + 3 = 7$ ，

→

6 → 5

$6 \to 5$ 花费时间

3 + 2 + 2 = 7

$3 + 2 + 2 = 7$ ，总时间花费

$14$ 。

评测用例规模与约定

对于

20%

$20%$ 的数据，

≤

2 ≤ K ≤ N ≤ 10^2

$2 \leq K \leq N \leq 1 0^{2}$ 。
对于

40%

$40%$ 的数据，

≤

2 ≤ K ≤ N ≤ 10^4

$2 \leq K \leq N \leq 1 0^{4}$ 。
对于

100

100%

$100%$ 的数据，

≤

，

≤

2 ≤ K ≤ N ≤ 10^5，1 ≤ u, v, A_i ≤ N

$2 \leq K \leq N \leq 1 0^{5} ， 1 \leq u, v, A_{i} \leq N$ ，

≤

1 ≤ t ≤ 10^5

$1 \leq t \leq 1 0^{5}$ 。保证

A_i

$A_{i}$ 两两不同。

思路

一眼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;
}

J: 砍树（25分）

问题描述

给定一棵由

$n$ 个结点组成的树以及

$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})$ ，其中

a_i

$a_{i}$ 互不相同，

b_i

$b_{i}$ 互不相同，

(

≤

)

a_i , b_j(1 ≤ i, j ≤ m)

$a_{i}, b_{j} (1 \leq i, j \leq m)$ 。

小明想知道是否能够选择一条树上的边砍断，使得对于每个

(

)

(a_i, b_i)

$(a_{i}, b_{i})$ 满足

和

a_i和b_i

$a_{i} 和 b_{i}$ 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从

$1$ 开始），否则输出

−

-1

$- 1$ 。

输入格式

输入共

n + m

$n + m$ 行，第一行为两个正整数

$n$ ，

$m$ 。
后面

−

n − 1

$n - 1$ 行，每行两个正整数

，

x_i，y_i

$x_{i} ， y_{i}$ 表示第

$i$ 条边的两个端点。
后面

$m$ 行，每行两个正整数

，

a_i，b_i

$a_{i} ， b_{i}$ 。

输出格式

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

样例输入

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, 4} ， {1, 2, 5, 6}$ ，满足

$3$ 和

$6$ 不连通，

$4$ 和

$5$ 不连通。
断开第

$4$ 条边后形成两个连通块：

{

}

，

{

}

{1, 2, 3, 4}，{5, 6}

${1, 2, 3, 4} ， {5, 6}$ ，同样满足

$3$ 和6 不连通，

$4$ 和

$5$ 不连通。

$4$ 编号更大，因此答案为

$4$ 。

评测用例规模与约定

对于

30%

$30%$ 的评测用例，

≤

1 ≤ N ≤ 10^3

$1 \leq N \leq 1 0^{3}$ 。
对于

100

100%

$100%$ 的评测用例，

≤

1 ≤ N ≤ 10^5

$1 \leq N \leq 1 0^{5}$ ，

≤

1 ≤ m ≤ frac{n}{2}

$1 \leq m \leq \frac{n}{2}$ 。

思路

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

这题也不会搞，写了个暴力交上去了。（小数据正常跑，大数据肯定超时，直接输出 -1 骗分hhh）

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

using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

vector<pair<int, int>> e[maxn];

bool vis[maxn];
int a[maxn], b[maxn];
int n, m;

bool check(int x, int y, int bi) {
    for (int i = 0; i <= n; i++) vis[i] = false;
    queue<int> q;
    q.push(x);
    vis[x] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto i: e[u]) {
            if (i.second == bi) continue;
            if (!vis[i.first]) {
                vis[i.first] = true;
                q.push(i.first);
            }
        }
    }
    return vis[y];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        e[u].emplace_back(v, i);
        e[v].emplace_back(u, i);
    }
    if (n * m > 1e8 || n * n > 1e8) {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= m; i++) cin >> a[i] >> b[i];
    int ans = -1;
    for (int i = n - 1; i >= 1; i--) {
        bool flag = true;
        for (int j = 1; j <= m; j++) {
            if (check(a[j], b[j], i)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c++动态规划数据结构算法蓝桥杯

二维码

数据库并发控制基本概念和基本技术

< <上一篇

【操作系统】面试官都爱问的进程调度算法

下一篇>>