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

A: 日期统计（5分）

问题描述

小蓝现在有一个长度为$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 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。
   请你帮小蓝计算下按上述条件一共能找到多少个不同的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;
}

B: 01 串的熵（5分）

问题描述

对于一个长度为$n$ 的$01$ 串 S = x 1 x 2 x 3 . . . x n S = x_1x_2x_3...x_n S=x1​x2​x3​...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)=−∑1n​p(xi​)log2​(p(xi​))，其中$p(0),p(1)$ 表示在这个$01$ 串中$0$ 和$1$ 出现的占比。比如，对于$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)=−31​log2​(31​)−32​log2​(32​)−32​log2​(32​)=1.3083。对于一个长度为$23333333$ 的$01$ 串，如果其信息熵为$11625907.5798$，且$0$ 出现次数比$1$ 少，那么这个$01$ 串中$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;
}

二分：

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

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$ 时，有： ⌊ 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$ 时，有： ⌊ 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$ 更小或者比$25$ 更大的符合条件的$V$ 值了。

评测用例规模与约定

对于$30\%$ 的评测用例， 1 ≤ N ≤ 1 0 2 1 ≤ N ≤ 10^2 1≤N≤102。
对于$60\%$ 的评测用例， 1 ≤ N ≤ 1 0 3 1 ≤ N ≤ 10^3 1≤N≤103。
对于$100\%$ 的评测用例， 1 ≤ N ≤ 1 0 4 1 ≤ N ≤ 10^4 1≤N≤104， 1 ≤ B ≤ A ≤ 1 0 9 1 ≤ B ≤ A ≤ 10^9 1≤B≤A≤109。

思路

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

#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 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$ 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。
第一行包含一个整数$T$，代表测试数据的组数。
对于每组数据，第一行包含一个整数$N$。
以下$N$ 行，每行包含三个整数： T i T_i Ti​， D i D_i Di​ 和 L i L_i 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\le 2$。
对于$100\%$ 的评测用例，$1\le T\le 10$，$1\le N\le 10$， 0 ≤ T i , D i , L i ≤ 1 0 5 0 ≤ T_i, D_i, L_i ≤ 10^5 0≤Ti​,Di​,Li​≤105。

思路

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

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

E: 接龙数列（15分）

问题描述

对于一个长度为$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} Ai−1​ 的末位数字$(2\le i\le K)$。

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

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

输入格式

第一行包含一个整数$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$，剩余$11,121,12,2023$ 是接龙数列。

评测用例规模与约定

对于$30\%$ 的评测用例，$1\le N\le 20$。
对于$50\%$ 的评测用例， 1 ≤ N ≤ 1 0 4 1 ≤ N ≤ 10^4 1≤N≤104。
对于$100\%$ 的评测用例， 1 ≤ N ≤ 1 0 5 1 ≤ N ≤ 10^5 1≤N≤105， 1 ≤ A i ≤ 1 0 9 1 ≤ A_i ≤ 10^9 1≤Ai​≤109。所有 A i A_i Ai​ 保证不包含前导$0$。

思路

动态规划，定义$dp[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\times N$ 的格子地图，可以将其视作一个只包含字符$‘0’$（代表海水）和$‘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}) (x0​,y0​),(x1​,y1​),...,(xk−1​,yk−1​)，其中 ( 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\le i\le 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\le M,N\le 10$。
对于$100\%$ 的评测用例，$1\le T\le 10,1\le M,N\le 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 c1​ 和 c 2 c_2 c2​，请你计算$S$ 有多少个以 c 1 c_1 c1​ 开头 c 2 c_2 c2​ 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数$K$。
第二行包含一个字符串$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\%$ 的评测用例，$2\le K\le |S|\le 10000$。
对于$100\%$ 的评测用例， 2 ≤ K ≤ ∣ S ∣ ≤ 5 × 1 0 5 2 ≤ K ≤ |S | ≤ 5 × 10^5 2≤K≤∣S∣≤5×105。$S$ 只包含小写字母。 c 1 c_1 c1​ 和 c 2 c_2 c2​ 都是小写字母。
$|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 A1​,A2​,...,AN​。你要重复以下操作$K$ 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出$K$次操作后的序列。

输入格式

第一行包含两个整数$N$ 和$K$。
第二行包含$N$ 个整数， A 1 , A 2 , A 3 , . . . , A N A_1, A_2, A_3, ..., A_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 ≤ N ≤ 1 0 4 1 ≤K ≤N ≤ 10^4 1≤K≤N≤104。
对于$100\%$ 的评测用例， 1 ≤ K ≤ N ≤ 5 × 1 0 5 1 ≤K ≤N ≤ 5 ×10^5 1≤K≤N≤5×105， 0 ≤ A i ≤ 1 0 8 0 ≤ A_i ≤ 10^8 0≤Ai​≤108。

思路

堆+链表。因为需要频繁删除元素，故考虑使用链表，又因为需要找最小，因此可以使用堆解决。这题最大会爆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;
}

I: 景区导游（25分）

问题描述

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

小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中$K$ 个景点： A 1 , A 2 , . . . , A K A_1, A_2, ... , A_K A1​,A2​,...,AK​。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中$K-1$ 个景点。具体来说，如果小明选择跳过 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​,...,Ai−1​,Ai+1​,...,AK​(1≤i≤K)。

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

输入格式

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

输出格式

输出$K$ 个整数，其中第$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\to 6\to 5\to 1$。
当跳过$2$ 时，路线是$6\to 5\to 1$，其中$6\to 5$ 花费时间$3+2+2=7$，$5\to 1$ 花费时间$2+1=3$，总时间花费$10$。
当跳过$6$ 时，路线是$2\to 5\to 1$，其中$2\to 5$ 花费时间$1+1+2=4$，$5\to 1$ 花费时间$2+1=3$，总时间花费$7$。
当跳过$5$ 时，路线是$2\to 6\to 1$，其中$2\to 6$ 花费时间$1+1+2+3=7$，$6\to 1$ 花费时间$3+2+1=6$，总时间花费$13$。
当跳过$1$ 时，路线时$2\to 6\to 5$，其中$2\to 6$ 花费时间$1+1+2+3=7$，$6\to 5$ 花费时间$3+2+2=7$，总时间花费$14$。

评测用例规模与约定

对于$20\%$ 的数据， 2 ≤ K ≤ N ≤ 1 0 2 2 ≤ K ≤ N ≤ 10^2 2≤K≤N≤102。
对于$40\%$ 的数据， 2 ≤ K ≤ N ≤ 1 0 4 2 ≤ K ≤ N ≤ 10^4 2≤K≤N≤104。
对于$100\%$ 的数据， 2 ≤ K ≤ N ≤ 1 0 5 ， 1 ≤ u , v , A i ≤ N 2 ≤ K ≤ N ≤ 10^5，1 ≤ u, v, A_i ≤ N 2≤K≤N≤105，1≤u,v,Ai​≤N， 1 ≤ t ≤ 1 0 5 1 ≤ t ≤ 10^5 1≤t≤105。保证 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;
}

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) (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​(1≤i,j≤m)。

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

输入格式

输入共$n+m$ 行，第一行为两个正整数$n$，$m$。
后面$n-1$ 行，每行两个正整数 x i ， y i x_i，y_i xi​，yi​ 表示第$i$ 条边的两个端点。
后面$m$ 行，每行两个正整数 a i ， b i a_i，b_i 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, 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\\} {1,2,3,4}，{5,6}，同样满足$3$ 和6 不连通，$4$ 和$5$ 不连通。
$4$ 编号更大，因此答案为$4$。

评测用例规模与约定

对于$30\%$ 的评测用例， 1 ≤ N ≤ 1 0 3 1 ≤ N ≤ 10^3 1≤N≤103。
对于$100\%$ 的评测用例， 1 ≤ N ≤ 1 0 5 1 ≤ N ≤ 10^5 1≤N≤105， 1 ≤ m ≤ n 2 1 ≤ m ≤ \\frac{n}{2} 1≤m≤2n​。

思路

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

解法的话应该是树上边差分的板子题。对于每个 ( a i , b i ) (a_i, b_i) (ai​,bi​) 满足 a i 和 b i a_i和b_i ai​和bi​ 不连通，则断开的边一定在 a i → L C A ( a i , b i ) a_i → LCA(a_i,b_i) ai​→LCA(ai​,bi​)和 b i → L C A ( a i , b i ) b_i → LCA(a_i,b_i) bi​→LCA(ai​,bi​)上。相当于对上面区间贡献度+1，因此贡献度和为$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;
}