前言

这是一篇 2023 年第十四届蓝桥杯省赛 C/C++ B 组题解。本人蒟蒻 ACMer，最近发现时隔两周的蓝桥杯省赛还没有一篇题解，火速补了题来写份题解。最后再顺便写一下心得吧。

A 题：日期统计

这题方法应该很多，没有和别人讨论想法。我的解法思路是：先 load 函数生成所有这一年的合法日期，然后枚举所有可以从数据中拿到的八位日期，检查它是否在合法日期的集合中。

这里枚举到四位，即年份的时候要判断一下，不然可能数据太多要跑很久。

注意要去重！不知道有多少冤大头痛失这 5 分。（原题里特意加粗了不重复）

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
// 日期统计
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5+5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;

// 235

set<int> S;  // 记录一年中合法的日期
set<int> M;  // 记录出现的日期，自带去重

// 生成数据
int mon[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
void load() {
    for (int i = 1; i <= 12; i++) {
        for (int j = 1; j <= mon[i-1]; j++) {
            S.insert(2023 * 10000 + i * 100 + j);
        }
    }
}

void solve() {
    const int n = 100;
    int a[256];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << ' ';
    }
    cout << endl;
    for (int _1 = 0; _1 < n; _1++) {
        for (int _2 = _1 + 1; _2 < n; _2++) {
            for (int _3 = _2 + 1; _3 < n; _3++) {
                for (int _4 = _3 + 1; _4 < n; _4++) {
                    int x = 0;
                    x = x * 10 + a[_1];
                    x = x * 10 + a[_2];
                    x = x * 10 + a[_3];
                    x = x * 10 + a[_4];
                    if (x != 2023) continue;  // 这里先判断一下合法，否则程序可能跑不动
                    for (int _5 = _4 + 1; _5 < n; _5++) {
                        for (int _6 = _5 + 1; _6 < n; _6++) {
                            for (int _7 = _6 + 1; _7 < n; _7++) {
                                for (int _8 = _7 + 1; _8 < n; _8++) {
                                    int x = 0;
                                    x = x * 10 + a[_1];
                                    x = x * 10 + a[_2];
                                    x = x * 10 + a[_3];
                                    x = x * 10 + a[_4];
                                    x = x * 10 + a[_5];
                                    x = x * 10 + a[_6];
                                    x = x * 10 + a[_7];
                                    x = x * 10 + a[_8];
                                    // 如果这个日期是这年的合法日期
                                    if (S.count(x)) {
                                        M.insert(x);
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << M.size() << endl;
}

int32_t main() {
    // 该文件是复制下来的题目给的数据
    freopen("A.txt", "r", stdin);

    load();
    cout << S.size() << endl;
    solve();

    return 0;
}

B 题：01 串的熵

题目提供了一个表达式： H(s)=−∑1np(xi)log⁡2(p(xi))H(s) = -\sum_1^n p(x_i) \log_2(p(x_i)) 其中，s 表示一个 01 字符串，p(xi)p(x_i) 表示符号 xix_i 在字符串中的占比。那么简单化简一下这个式子，我们用 x 表示 s 中 0 的个数，用 y 表示 s 中 1 的个数，n 表示 s 的长度，因为是 01 字符串，有 n = x + y。 H(s)=−(x2nlog⁡2xn+y2nlog⁡2yn)H(s) = -\left(\frac{x^2}{n}\log_2\frac{x}{n} + \frac{y^2}{n}\log_2\frac{y}{n}\right) 题目告诉你 n = 23333333 以及 H(s) 的值，求 x 和 y。

首先你要知道计算机一秒大概可以完成 1e8 次简单运算（这个运算挺简单了吧），那么很简单我们枚举 x 去拟合 H(s) 即可。

1
2
// 11027421
// 赛时用 python 跑的，不重写了。

C 题：冶炼金属

题意是有一种商品，花 x 元钱可以买 y 个该商品。给你多组这样的 x 和 y ，请你确认这个商品的价格区间。

如果给你一对 x 和 y ，那么它确定的价格区间就是 [  ⌊xy+1⌋+1, ⌊xy⌋  ]\left[~~\lfloor{\frac{x}{y+1}}\rfloor+1,~\lfloor\frac{x}{y}\rfloor~~\right] ，然后取所有区间的并即可。

注意不是 [  ⌈xy+1⌉, ⌊xy⌋  ]\left[~~\lceil{\frac{x}{y+1}}\rceil,~\lfloor\frac{x}{y}\rfloor~~\right] ，这里提供错误数据 24 3 ，正确价格区间为 [7, 8]。我一个队友 S 这了，我赛时也考虑了这个问题。

这道题还可以二分去找合法的价格区间，我另一个队友是这么做的，虽然有点蠢，但至少避免了推错式子，不作扩展。为什么有人叫我前面将的这种做法为数论分块，我不是很理解，这更像一道 “聪明题” 。

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
// 冶炼金属
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    int min_ = -INF - 1, max_ = INF;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        min_ = max(min_, x / (y + 1) + 1);  // 求左边界的并
        max_ = min(max_, x / y);            // 求右边界的并
    }
    cout << min_ << " " << max_ << endl;
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    solve();

    return 0;
}

D 题：飞机降落

注意看数据范围是 n = 10 ，自信贪心的可以好好反思一下自己了，如果真能写评论区留言。

最基本的爆搜，不需要剪枝，时间复杂度 n!n! ，看代码注释。

也可以使用 状压dp ，时间复杂度 n⋅2nn\cdot2^n 。如果数据是 n = 15 那这就是正解了。

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
// 飞机降落
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 15;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;

struct Air {
    // 最早降落时间, 最迟降落时间, 降落过程耗时
    int st, ed, len;
} air[MAX];

int n;
bool vis[MAX];
bool dfs(int x, int pos) {
    if (x >= n) return true;
    for (int i = 0; i < n; i++) {
        // 如果 i 没有用过，且 i 最迟降落时间在前者的完成这个降落流程之后
        if (not vis[i] and pos <= air[i].ed) {  
            vis[i] = true;
            // 在条件允许的情况下后者尽早降落为后者提供，要两类讨论，这里算有一点点贪心
            bool tmp = dfs(x+1, max(air[i].st, pos) + air[i].len);  
            vis[i] = false;
            if (tmp) return true;
        }
    }
    return false;
}

void solve() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> air[i].st >> air[i].ed >> air[i].len;
        air[i].ed += air[i].st;
    }
    bool res = dfs(0, 0);
    if (res) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

E 题：接龙序列

这是一道普通的 dp ，时间复杂度可以是 Θ(nlog⁡10A)\Theta(n\log_{10}A) 或者 Θ(10nlog⁡10A)\Theta(10n\log_{10}A) ，我这里写的是 Θ(n)\Theta(n) 的。

数字接龙的条件是前某个数字的最后一位与这个数字的第一位相同，那么我们使用 dp[i][j] 表示到第 i 位时，前 i 位中的接龙序列以数字 j 结尾的最大长度，设第 i 个数字的首位为 head[i]，末位为 tail[i]，则状态转移方程为：

dp[i][j]={max(dp[i−1][j], dp[i−1][head[i]]+1)ifj=tail[i]dp[i−1][j]elsedp[i][j] = \left\{ \begin{array}{l} max(dp[i-1][j],~dp[i-1][head[i]] + 1) & if & j=tail[i] \\ \\ dp[i-1][j] & else\\ \end{array} \right.

考虑到前 i 位的数据不会再次被使用，并且状态转移中有大量的拷贝，这里做了内存优化，同时时间也下降了十倍。（已经够过题了，这是次要的）

dp[tail[i]]=max(dp[i−1][tail[j]], dp[i−1][head[i]]+1) dp[tail[i]] = max(dp[i-1][tail[j]],~dp[i-1][head[i]] + 1) 

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
// 接龙序列
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;

int res[10] = {0};

void solve() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int tail = x % 10;  // 计算末尾
        int head;
        while (x) {
            head = x % 10;
            x /= 10;
        }  // 计算首位
        res[tail] = max(res[tail], res[head] + 1);  // 状态转移方程
    }
    int max_ = 0;
    for (int i = 0; i < 10; i++) {
        max_ = max(max_, res[i]);  // 获取最长接龙序列
    } 
    cout << n - max_ << endl;
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    solve();

    return 0;
}

F 题：岛屿个数

在和队友交流过程中，大概认为这道题是思维量最大的一道题了，因为你会发现再往后面的题都比较板子。

题目将地图分为 海域 和 岛屿 ，其中陆地又被区分为 内岛 和 外岛 ，题目对于 内岛 的定义是被任意的 岛屿 所围成的环的内部，然后求 外岛 的数量。

但是如果你像题意那样理解 内岛 实现就比较复杂了，转换为 外岛 是其周围的 海域 有任何一块是 外海 的 岛屿 ，所谓 外海 是可以连通到地图外的 海域 。如此理解。我们只要预处理出所有 外海 ，再处理 岛屿 即可。这里用广搜写的。

时间复杂度 Θ(nm)\Theta(nm) ，如果写蠢了 Θ(n2m2)\Theta(n^2m^2) 也可以过，没有卡时间。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
// 岛屿个数
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 55;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;

char map_[MAX][MAX];              // 地图
bool track[MAX][MAX] = {false};   // 访问标记
bool outsea[MAX][MAX] = {false};  // 外海标记
struct XY {
    int x, y;
} nxt[] = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
    {1, 1},
    {-1, 1},
    {1, -1},
    {-1, -1},
};

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> map_[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            track[i][j] = false;
            outsea[i][j] = false;
        }
    }
    // 预处理外海
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map_[i][j] == '1' or track[i][j]) continue;
            bool yep = false;
            queue<XY> que, arr;
            track[i][j] = true;
            que.push({i, j});
            arr.push({i, j});  // 记录搜索到的所有海域
            while (not que.empty()) {
                XY pos = que.front();
                que.pop();
                // 注意：海域搜索可以往八个方向走，陆地搜索只能朝四个方向
                for (int i = 0; i < 8; i++) {
                    XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};
                    if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {
                        if (map_[nw.x][nw.y] == '0' and track[nw.x][nw.y] == false) {
                            track[nw.x][nw.y] = true;
                            que.push(nw);
                            arr.push(nw);
                        }
                    } else {
                        yep = true;  // 如果有一次搜索到地图外，标记此次搜索的所有区域为外海
                    }
                }
            }
            if (yep) {
                while (not arr.empty()) {
                    XY pos = arr.front();
                    arr.pop();
                    outsea[pos.x][pos.y] = true;  // 标记搜索到的海域为外海
                }
            }
        }
    }

    // 别忘了清空访问标记
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            track[i][j] = false;
        }
    }
    // 处理岛屿
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map_[i][j] == '0' or track[i][j]) continue;
            bool yep = false;
            queue<XY> que;
            track[i][j] = true;
            que.push({i, j});
            while (not que.empty()) {
                XY pos = que.front();
                que.pop();
                for (int i = 0; i < 4; i++) {
                    XY nw = {pos.x + nxt[i].x, pos.y + nxt[i].y};
                    if (0 <= nw.x and nw.x < n and 0 <= nw.y and nw.y < m) {
                        if (map_[nw.x][nw.y] == '1') {
                            if (track[nw.x][nw.y] == false) {
                                track[nw.x][nw.y] = true;
                                que.push(nw);
                            }
                        } else {
                            if (outsea[nw.x][nw.y]) {
                                yep = true;  // 搜索到外海为外岛
                            }
                        }
                    } else {
                        yep = true;  // 搜索到边界外为外岛
                    }
                }
            }
            if (yep) {
                cnt++;  // 外岛计数
            }
        }
    }
    cout << cnt << endl;
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

G 题：子串简写

计数有多少个子串满足以 c1 开头、c2 结尾、长度大于等于 k 。

双指针二分，一个指针遍历，一个指针二分。题目要求以 c1 开头、以 c2 结尾，那么就用两个数组分别记录 c1 和 c2 出现的位置，一个指针遍历 c1 位置序列，一个指针在 c2 位置序列二分大于等于当前长度加 k 后第一个 c2 出现的位置，从这个位置往后都是有效贡献。时间复杂度 Θ(nlogn)\Theta(nlogn) 。

同样是双指针，类似的记录两个序列： c1 位置序列， c2 位置序列。慢指针遍历 c1 位置序列，快指针在 c1 与 c2 的距离不足 k 时向后移动，指到足够或越界，记录每次贡献。时间复杂度 Θ(n)\Theta(n) 。

这道题虽然数据是 n = 5e5 但是二分还是跑的过的，因为二分的常数非常的优秀，这里是我赛时首先想到的第一种解法。

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
// 子串简写
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
#ifdef _DEBUG
#pragma GCC optimize(2)
#endif
using namespace std;
const int MAX = 5e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;

int aa[MAX], cnt_aa = 0;
int bb[MAX], cnt_bb = 0;

// binary_search 二分查找
int bs(int x) {
    int l = 0, r = cnt_bb - 1;
    while (l <= r) {
        int mid = l + r >> 1;
        if (bb[mid] < x) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

void solve() {
    int k;
    cin >> k;
    string s;
    cin >> s;
    int n = s.size();
    char a, b;
    cin >> a >> b;
    for (int i = 0; i < n; i++) {
        if (s[i] == a) {
            aa[cnt_aa++] = i;  // 转储 c1 位置序列
        }
        if (s[i] == b) {
            bb[cnt_bb++] = i;  // 转储 c2 位置序列
        }
    }
    int res = 0;
    for (int i = 0; i < cnt_aa; i++) {
        res += cnt_bb - bs(aa[i] + k - 1);  // 记录有效贡献
    }
    cout << res << endl;
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    solve();

    return 0;
}

H 题：整数删除

使用优先队列维护找到最小删除数，并且使用类似链表的结构记录数的前驱与后继。

如果想到这些，那么问题就变成了一个流程的模拟了，我在代码里多打了一些注释。

我不知道命题组怎么想的 n = 5e5 的数据给了 1s 的时间，后面的 I 题 n = 1e5 的数据给了 5s 的时间。如果使用 STL 优先队列，由于常数问题我测试了民间数据 TLE 了，听了别人的写法大多都是使用优先队列的。实测手写 堆 或 线段树 不会 TLE ，这样卡常？莫非是有更优秀的解法？评论区留言。（下面的代码使用手写堆的）

不管怎么看后面 I 题的常数不会与 H 题有这么大的差距。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
// 整数删除
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
#ifdef _DEBUG
// #pragma GCC optimize(2)
#endif
using namespace std;
const int MAX = 5e5 + 5;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9 + 7;
int a[MAX];
int left_[MAX], right_[MAX];  // 仿链表结构

using pii = pair<int, int>;

// 小顶堆, 手写堆方法与 prority_queue 相仿，可跳至 第121行 void solve();
namespace heap {

pii heap[MAX << 1];  // 堆 (树状数组)
int a2h[MAX << 1];   // 数组索引 -> 堆索引
int h2a[MAX << 1];   // 堆索引 -> 数组索引
int total = 0;       // 总节点 (含已 pop 节点)
int siz = 0;         // 堆大小

// C 风格比较函数
bool cmp(pii x, pii y) { return x > y; }

// 维护映射的交换
void swap_(int u, int v) {
    swap(a2h[h2a[u]], a2h[h2a[v]]);
    swap(h2a[u], a2h[v]);
    swap(heap[u], heap[v]);
    if (u == siz) {
        a2h[h2a[u]] = -1;
        h2a[u] = -1;
    }
    if (v == siz) {
        a2h[h2a[v]] = -1;
        h2a[v] = -1;
    }
}

// 向上维护
void up(int node) {
    while (node and cmp(heap[(node - 1) / 2], heap[node])) {
        swap_(node, (node - 1) / 2);
        node = (node - 1) / 2;
    }
}

// 向下维护
void down(int node) {
    int parent = node;         // 父节点下标
    int child = 2 * node + 1;  // 子节点下标
    while (child < siz) {
        // 判断子节点哪个大, 大的与父节点比较
        if (child + 1 < siz and cmp(heap[child], heap[child + 1]))
            child++;
        if (cmp(heap[parent], heap[child]))  // 判断父节点是否小于子节点
        {
            swap_(parent, child);  // 交换父节点和子节点
            parent = child;        // 子节点下标 赋给 父节点下标
        }
        child = child * 2 + 1;  // 换行, 比较下面的父节点和子节点
    }
}

// 线性初始化堆
void build(int n) {
    total = siz = n;
    for (int i = 0; i < siz; i++) {
        a2h[i] = i;
        h2a[i] = i;
    }
    for (int i = siz / 2 - 1; i >= 0; i--)
        // 必须自下而上
        down(i);
}

// 插入节点
void push(pii x) {
    heap[siz] = x;
    a2h[total] = siz;
    h2a[siz] = total;
    up(siz);
    total++;
    siz++;
}

// 返回顶值
pii top() { return heap[0]; }

// 删除顶点
pii pop() {
    siz--;
    swap_(0, siz);
    down(0);
    return heap[siz];
}

// 修改第 u 个插入的节点
void modify_by_address(int u, pii x) {
    int v = a2h[u];
    heap[v] = x;
    down(v);
    up(v);
}

// 删除第 u 个插入的节点. 返回: 布尔型: 节点在堆中
void pop_by_address(int u) {
    int v = a2h[u];
    siz--;
    swap_(v, siz);
    down(v);
    up(v);
}

}  // namespace heap

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) {
        if (i > 0)
            left_[i] = i - 1; // 初始 i 的前驱 i - 1 
        else
            left_[i] = -1;  // 没有前驱的特殊标记
        if (i < n - 1)
            right_[i] = i + 1;  // 初始 i 的后继 i + 1
        else
            right_[i] = -1;
        heap::push({a[i], i});  // 放入堆中
    }
    int cnt = 0;
    while (cnt < k) {
        pii p = heap::pop();  // 取出最小的数
        int idx = p.second, x = p.first;  // idx 为数的索引，x 为这个数
        if (a[idx] != x) continue;  // 过滤脏数据
        // 如果有前驱
        if (left_[idx] >= 0) {
            a[left_[idx]] += x;  // 贡献给前驱
            heap::push({a[left_[idx]], left_[idx]});  // 加入修改后数据，原数据变为脏数据，延迟过滤
            right_[left_[idx]] = right_[idx]; // 更新前驱的后继
        }
        // 如果有后继
        if (right_[idx] >= 0) {
            a[right_[idx]] += x; // 贡献给后继
            heap::push({a[right_[idx]], right_[idx]});  // 加入修改后数据，原数据变为脏数据，延迟过滤
            left_[right_[idx]] = left_[idx]; // 更新后继的前驱
        }
        // 标记为无效
        a[idx] = -1;
        cnt++;
    }
    // 输出
    for (int i = 0; i < n; i++)
        if (a[i] >= 0)
            cout << a[i] << ' ';
    cout << endl;
}

int32_t main() {
#ifdef _DEBUG
    // freopen("H.in", "r", stdin);
    // freopen("H.out", "w", stdout);
    // clock_t st = clock();
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    solve();

#ifdef _DEBUG
    // cout << "COST: " << clock() - st << endl;
#endif
    return 0;
}

I 题：景区导游

LCA 板子题，作用是找到最近公共祖先。如果不会 LCA ，建议去学，学完这道题自然就会了。

先求出不删除节点的总路程。要求去除一个节点后的最短距离只需要置换掉相邻两个最短路为一个新连接的最短路，左右边界特殊处理即可。

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
91
92
93
94
95
96
97
98
99
100
101
// 景区导游
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5+5;
const int LOG = 20;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;

// 建议直接去写板子，别看了

int lg2[MAX];
int depth[MAX];
int st[MAX][LOG];
int dis[MAX];
vector<pair<int, int>> edge[MAX];

void load_lg2() {
    lg2[0] = -1;
    for (int i = 1; i < MAX; i++) {
        lg2[i] = lg2[i / 2] + 1;
    }
}

void build(int x, int pre, int level) {
    depth[x] = level;
    st[x][0] = pre;
    for (int i = 1; i <= lg2[depth[x]]; i++) {
        st[x][i] = st[st[x][i-1]][i-1];
    }
    for (pair<int, int> p : edge[x]) {
        int y = p.first, d = p.second;
        if (y == pre) continue;
        dis[y] = dis[x] + d;
        build(y, x, level + 1);
    }
}

int lca(int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);
    while (depth[x] < depth[y]) {
        y = st[y][lg2[depth[y]-depth[x]]];
    }
    if (x == y) return x;
    for (int i = lg2[depth[x]]; i >= 0; i--) {
        if (st[x][i] != st[y][i]) {
            x = st[x][i];
            y = st[y][i];
        }
    }
    return st[x][0];
}

int a[MAX];
int rount[MAX];

void solve() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[u].push_back({v, w});
        edge[v].push_back({u, w});
    }
    dis[1] = 0;
    build(1, 1, 0);
    for (int i = 0; i < k; i++) {
        cin >> a[i];
    }
    int tot = 0;
    for (int i = 1; i < k; i++) {
        int f = lca(a[i-1], a[i]);
        rount[i] = dis[a[i-1]] - dis[f] + dis[a[i]] - dis[f];
        tot += rount[i];
    }
    cout << tot - rount[1] << ' ';  // 第一个
    for (int i = 1; i < k - 1; i++) {
        int f = lca(a[i-1], a[i+1]);
        // 中间置换
        cout << tot - rount[i] - rount[i+1] + dis[a[i-1]] - dis[f] + dis[a[i+1]] - dis[f] << ' ';
    }
    cout << tot - rount[k-1] << endl;  // 最后一个
    while (true) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
}   

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    load_lg2();
    solve();

    return 0;
}

J 题：砍树

树上差分 板子题，主要是一种思想，没学过赛时可能也能想到。大多数 树上差分 的板子题都很有难度，因为单独的 树上差分 很难做一件事情，这道题出出来很好，很适合作为板子题，难度较低。

也要 LCA 雾…

给定一棵树，给定 m 条最短路，现在让你砍断一条边从而砍断所有这 m 条最短路。

我们只需记录每条边经过了多少次，如果有一条边经过了 m 次，那么砍断它即可。否则输出 -1。

如何在允许的时间内计数所有边经过多少次我们只需要存储差分数，最后对全树求和即可。对于边 (u, v) ，weight[u]++, weight[v]++, weight[lca(u, v)]--, weight[pre[lca(u, v)]]--; 。可以发现最后对全树求和就是我们要的边数。时间复杂度 Θ(n+mlogn)\Theta(n+mlogn) 。

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// 砍树
#include <bits/stdc++.h>
#define int int64_t
#define endl '\n'
using namespace std;
const int MAX = 1e5+5;
const int LOG = 20;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MOD = 1e9+7;

// 代码较长，建议从 solve 开始看

int lg2[MAX];
int depth[MAX];
int st[MAX][LOG]; // pre[i] 即为 st[i][0]
int weight[MAX];
vector<pair<int, int>> edge[MAX]; // pre : suf, idx

void load_lg2() {
    lg2[0] = -1;
    for (int i = 1; i < MAX; i++) {
        lg2[i] = lg2[i / 2] + 1;
    }
}

void build(int x, int pre, int level) {
    depth[x] = level;
    st[x][0] = pre;
    for (int i = 1; i <= lg2[depth[x]]; i++) {
        st[x][i] = st[st[x][i-1]][i-1];
    }
    for (pair<int, int> p : edge[x]) {
        int y = p.first;
        if (y == pre) continue;
        build(y, x, level + 1);
    }
}

int lca(int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);
    while (depth[x] < depth[y]) {
        y = st[y][lg2[depth[y]-depth[x]]];
    }
    if (x == y) return x;
    for (int i = lg2[depth[x]]; i >= 0; i--) {
        if (st[x][i] != st[y][i]) {
            x = st[x][i];
            y = st[y][i];
        }
    }
    return st[x][0];
}

void dfs(int x, int pre) {
    for (pair<int, int> p : edge[x]) {
        int y = p.first;
        if (y == pre) continue;
        dfs(y, x);
        weight[x] += weight[y];
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        edge[u].push_back({v, i});
        edge[v].push_back({u, i});
    }
    build(1, 0, 0);  // lca 初始化, 不能写 build(1, 1, 0)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        int f = lca(u, v);
        // 记录差分
        weight[u]++;
        weight[v]++;
        weight[f]--;
        weight[st[f][0]]--;
    }
    dfs(1, 0);
    // 输出
    int res = -1;
    for (int x = 1; x <= n; x++) {
        if (weight[x] == m) {
            for (pair<int, int> p : edge[x]) {
                int y = p.first, idx = p.second;
                if (weight[y] == m) {
                    res = max(res, idx);
                }
            }
        }
    }
    cout << res << endl;
}

int32_t main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    load_lg2();
    solve();

    return 0;
}

OK！结束。

心得体会

个人不是很喜欢这场蓝桥杯，最后两道题考得两个 LCA，在这里分配了 50 分的分值是否有失偏颇？最后两大题占据了 1/3 的分值却是两道板子题。近几年蓝桥杯的热度暴涨，出的题也是每年都不一样，从暴力杯到 dp 杯一定程度考察考生的思维能力，有些题还是挺有思维量的，今年的 LCA 杯不作评价。

A-G 题还是比较传统的并且也没有什么问题，H 题给的数据范围以及对应的时间有些问题，我当时赛时用的 set 写被卡掉可以理解，但是 5e5 的数据以及 1s 的时间数据够强可以卡掉优先队列。相反 I 题 1e5 的数据给 5s 的时间完全没有必要。

我是第一次打蓝桥杯，也是问题连连。A 题没看到 不重复 ； D 题那个自信贪心的就是我；H 题 TLE 部分点被卡常（赛时疑似按了两下 Ctrl + V 编译错误）； I 题 LCA 默好了默对了最后忘记调用了，神奇的过了样例；J 题没写来不及。

文章心得拖延了两天，我写完这篇文章的时候刚好出结果了，勉强还是拿到了 浙江省一 。