第十四届蓝桥杯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个编程的大题。本届蓝桥杯我愿称之为四小时怒开九道题 。难度跟上届相比，没有那么多思维题，反倒板子题多了，不知道其他组是不是也是这样。
博客地址：https://blog.csdn.net/m0_46326495/article/details/130043563
A: 日期统计（5分）
问题描述
小蓝现在有一个长度为 的数组，数组中的每个元素的值都在
到
的范围之内。数组中的元素从左至右如下所示：
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 年的日期。
对于相同的日期你只需要统计一次即可。
思路
纯暴力的话就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分）
问题描述
对于一个长度为 的
串
，香农信息熵的定义为
，其中
表示在这个
串中
和
出现的占比。比如，对于
来说，信息熵
。对于一个长度为
的
串，如果其信息熵为
，且
出现次数比
少，那么这个
串中
出现了多少次？
思路
枚举一下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分）
问题描述
小蓝有一个神奇的炉子用于将普通金属 冶炼成为一种特殊金属
。这个炉子有一个称作转换率的属性
，
是一个正整数，这意味着消耗
个普通金属
恰好可以冶炼出一个特殊金属
，当普通金属
的数目不足
时，无法继续冶炼。
现在给出了 条冶炼记录，每条记录中包含两个整数
和
，这表示本次投入了
个普通金属
，最终冶炼出了
个特殊金属
。每条记录都是独立的，这意味着上一次没消耗完的普通金属
不会累加到下一次的冶炼当中。
根据这 条冶炼记录，请你推测出转换率
的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数，表示冶炼记录的数目。
接下来输入 行，每行两个整数
、
，含义如题目所述。
输出格式
输出两个整数，分别表示 可能的最小值和最大值，中间用空格分开。
样例输入
3
75 3
53 2
59 2
样例输出
20 25
样例说明
当 时，有：
，
，
可以看到符合所有冶炼记录。
当 时，有：
，
，
可以看到符合所有冶炼记录。
且再也找不到比 更小或者比
更大的符合条件的
值了。
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
。
对于 的评测用例，
，
。
思路
感觉是个数学题，算一下即可。
#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分）
问题描述
架飞机准备降落到某个只有一条跑道的机场。其中第
架飞机在
时刻到达机场上空，到达时它的剩余油料还可以继续盘旋
个单位时间，即它最早可以于
时刻开始降落，最晚可以于
时刻开始降落。降落过程需要
个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数，代表测试数据的组数。
对于每组数据，第一行包含一个整数。
以下 行，每行包含三个整数：
，
和
。
输出格式
对于每组数据，输出 或者
，代表是否可以全部安全降落。
样例输入
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
样例输出
YES
NO
样例说明
对于第一组数据，可以安排第 架飞机于
时刻开始降落，
时刻完成降落。安排第
架飞机于
时刻开始降落，
时刻完成降落。安排第
架飞机于
时刻开始降落，
时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
，
，
。
思路
本来以为要贪心然后排序去做，手推了几个发现贪心不对，重新看了眼数据范围，发现是个纯暴力的题？
#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分）
问题描述
对于一个长度为 的整数数列：
，我们称之为接龙数列当且仅当
的首位数字恰好等于
的末位数字
。
例如 是接龙数列；
不是接龙数列，因为
的首位数字不等于
的末位数字。所有长度为
的整数数列都是接龙数列。
现在给定一个长度为 的数列
，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数。
第二行包含 个整数
。
输出格式
一个整数代表答案
样例输入
5
11 121 22 12 2023
样例输出
1
样例说明
删除，剩余
是接龙数列。
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
。
对于 的评测用例，
，
。所有
保证不包含前导
。
思路
动态规划，定义为用到第
个，结尾为
最少要删掉的元素数量
#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分）
问题描述
小蓝得到了一副大小为 的格子地图，可以将其视作一个只包含字符
（代表海水）和
（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的
相连接而形成。
在岛屿 所占据的格子中，如果可以从中选出
个不同的格子，使得他们的坐标能够组成一个这样的排列：
，其中
是由
通过上/下/左/右移动一次得来的
，此时这
个格子就构成了一个“环”。如果另一个岛屿
所占据的格子全部位于这个“环” 内部，此时我们将岛屿
视作是岛屿
的子岛屿。若
是
的子岛屿，
又是
的子岛屿，那
也是
的子岛屿。
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。
输入格式
第一行一个整数，表示有
组测试数据。
接下来输入 组数据。对于每组数据，第一行包含两个用空格分隔的整数
、
表示地图大小；接下来输入
行，每行包含
个字符，字符只可能是
或
。
输出格式
对于每组数据，输出一行，包含一个整数表示答案。
样例输入
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
样例输出
1
3
样例说明
对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：
01111
11001
10201
10001
11111
岛屿 在岛屿
的“环” 内部，所以岛屿
是岛屿
的子岛屿，答案为
。
对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：
111111
100001
020301
100001
111111
注意岛屿 并不是岛屿
或者岛屿
的子岛屿，因为岛屿
和岛屿
中均没有“环”。
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
。
思路
这个题蛮有意思的，如果不考虑子岛屿的话，基本上是白送分题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 等。
在本题中，我们规定长度大于等于 的字符串都可以采用这种简写方法（长度小于
的字符串不配使用这种简写）。
给定一个字符串 和两个字符
和
，请你计算
有多少个以
开头
结尾的子串可以采用这种简写？
输入格式
第一行包含一个整数。
第二行包含一个字符串 和两个字符
和
。
输出格式
一个整数代表答案。
样例输入
4
abababdb a b
样例输出
6
样例说明
符合条件的子串如下所示，中括号内是该子串：
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
。
只包含小写字母。
和
都是小写字母。
代表字符串
的长度。
思路
感觉也算个数学思维题，感觉跟前缀和有点像。
#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分）
问题描述
给定一个长度为 的整数数列：
。你要重复以下操作
次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出次操作后的序列。
输入格式
第一行包含两个整数 和
。
第二行包含 个整数，
。
输出格式
输出 个整数，中间用一个空格隔开，代表
次操作后的序列。
样例输入
5 3
1 4 2 8 7
样例输出
17 7
样例说明
数列变化如下，中括号里的数是当次操作中被选择的数：
[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
，
。
思路
堆+链表。因为需要频繁删除元素，故考虑使用链表，又因为需要找最小，因此可以使用堆解决。这题最大会爆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分）
问题描述
某景区一共有 个景点，编号
到
。景点之间共有
条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 个景点：
。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中
个景点。具体来说，如果小明选择跳过
，那么他会按顺序带游客游览
。
请你对任意一个，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？
输入格式
第一行包含 个整数
和
。
以下 行，每行包含
个整数
和
，代表景点
和
之间有摆渡车线路，花费
个单位时间。
最后一行包含 个整数
代表原定游览线路。
输出格式
输出 个整数，其中第
个代表跳过
之后，花费在摆渡车上的时间。
样例输入
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
样例说明
原路线是。
当跳过 时，路线是
，其中
花费时间
，
花费时间
，总时间花费
。
当跳过 时，路线是
，其中
花费时间
，
花费时间
，总时间花费
。
当跳过 时，路线是
，其中
花费时间
，
花费时间
，总时间花费
。
当跳过 时，路线时
，其中
花费时间
，
花费时间
，总时间花费
。
评测用例规模与约定
对于 的数据，
。
对于 的数据，
。
对于 的数据，
，
。保证
两两不同。
思路
一眼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分）
问题描述
给定一棵由 个结点组成的树以及
个不重复的无序数对
，其中
互不相同，
互不相同，
。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 满足
不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从
开始），否则输出
。
输入格式
输入共 行，第一行为两个正整数
，
。
后面 行，每行两个正整数
表示第
条边的两个端点。
后面 行，每行两个正整数
。
输出格式
一行一个整数，表示答案，如有多个答案，输出编号最大的一个。
样例输入
6 2
1 2
2 3
4 3
2 5
6 5
3 6
4 5
样例输出
4
样例说明
断开第 条边后形成两个连通块：
，满足
和
不连通，
和
不连通。
断开第 条边后形成两个连通块：
，同样满足
和6 不连通，
和
不连通。
编号更大，因此答案为
。
评测用例规模与约定
对于 的评测用例，
。
对于 的评测用例，
，
。
思路
感觉这题输出格式写的有问题，只砍断一条边，并且多个答案只输出最大的，那应该输出只有一个数，为啥一行一个整数…没懂。
解法的话应该是树上边差分的板子题。对于每个 满足
不连通，则断开的边一定在
和
上。相当于对上面区间贡献度+1，因此贡献度和为
的边为最后的解，如果不存在则无解。
#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;
}
版权声明：本文为博主作者：上山打老虎D原创文章，版权归属原作者，如果侵权，请联系我们删除！
原文链接：https://blog.csdn.net/m0_46326495/article/details/130043563
