- 1NLP实践——中文指代消解方案
- 2【Python天气预报系统】又要降温，这个冬天你准备好棉衣秋裤了吗？看了不后悔系列之Python打造智能天气预报系统，爆赞。_基于python的降水量预警系统的设计与实现
- 3RabbitMQ消息队列实战（2）—— Java调用RabbitMQ的三种方式_java mq的使用
- 4tritonserver学习之六：自定义c++、python custom backend实践_triton c++
- 5Python爬虫北京二手房源数据可视化分析大屏全屏系统
- 6Bug小能手系列(python)_7: BertTokenizer报错 Connection reset by peer_can't load tokenizer for 'bert-base-uncased'. if y
- 7[论文翻译]DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning
- 8Python 人工智能实战：风格迁移_python 风格迁移
- 9Java 判断Object对象的所有属性值是否为空。_java objectutil判断全null
- 10Linux | Linux离线安装JDK_linux jdk离线安装
【备战蓝桥杯】第十四届蓝桥杯省赛C/C++ B组真题及题解_蓝桥杯真题
赞
踩
参加了两届蓝桥杯以及做过了往年的真题我的直观感受是蓝桥杯不再那么“暴力”了，而是逐渐趋向DP和搜素图论方面了。下面是第十四届蓝桥杯省赛C/C++ B组真题及题解，希望对阅读的你有所帮助。
题目
试题A：日期统计
【问题描述】
小蓝现在有一个长度为 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 年的日期。
对于相同的日期你只需要统计一次即可。
【答案提交】
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一
个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
试题B：01 串的熵
试题C：冶炼金属
【问题描述】
小蓝有一个神奇的炉子用于将普通金属 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
试题D：飞机降落
【问题描述】
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻
到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早
可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li
个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不
能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
【输入格式】
输入包含多组数据。
第一行包含一个整数 T，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N。
以下 N 行，每行包含三个整数：Ti，Di 和 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 ≤ 2。
对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti, Di, Li ≤ 10
试题E：接龙数列
【问题描述】
对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且
仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。
例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56
的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。
现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少
个数，可以使剩下的序列是接龙序列？
【输入格式】
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, . . . , AN。
【输出格式】
一个整数代表答案。
【样例输入】
5
11 121 22 12 2023
【样例输出】
1
【样例说明】
删除 22，剩余 11, 121, 12, 2023 是接龙数列。
【评测用例规模与约定】
对于 20% 的数据，1 ≤ N ≤ 20。
对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 105，1 ≤ Ai ≤ 109。所有 Ai 保证不包含前导 0。
试题F：岛屿个数
【问题描述】
小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符
‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，
每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。
在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得
他们的坐标能够组成一个这样的排列：(x0, y0),(x1, y1), . . . ,(xk−1, yk−1)，
其中(x(i+1)%k, y(i+1)%k) 是由 (xi, yi) 通过上/下/左/右移动一次得来的 (0 ≤ i ≤ 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 ≤ M, N ≤ 10。
对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。
试题G：子串简写
【问题描述】
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首
尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法
（长度小于 K 的字符串不配使用这种简写）。
给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头
c2 结尾的子串可以采用这种简写？
【输入格式】
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符 c1 和 c2。
【输出格式】
一个整数代表答案。
【样例输入】
4
abababdb a b
【样例输出】
6
【样例说明】
符合条件的子串如下所示，中括号内是该子串：
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
【评测用例规模与约定】
对于 20% 的数据，2 ≤ K ≤ |S | ≤ 10000。
对于 100% 的数据，2 ≤ K ≤ |S | ≤ 5 × 105。S 只包含小写字母。c1 和 c2 都
是小写字母。
|S | 代表字符串 S 的长度
试题H：整数删除
【问题描述】
给定一个长度为 N 的整数数列：A1, A2, . . . , AN。你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其
删除。并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
【输入格式】
第一行包含两个整数 N 和 K。
第二行包含 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 ≤ 10000。
对于 100% 的数据，1 ≤ K < N ≤ 5 × 105，0 ≤ Ai ≤ 108。
试题I：景区导游
【问题描述】
某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆
渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，
需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个
景点：A1, A2, . . . , AK。今天由于时间原因，小明决定跳过其中一个景点，只带游
客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会
按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。
请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景
点之间的摆渡车上？
【输入格式】
第一行包含 2 个整数 N 和 K。
以下 N − 1 行，每行包含 3 个整数 u, v 和 t，代表景点 u 和 v 之间有摆渡
车线路，花费 t 个单位时间。
最后一行包含 K 个整数 A1, A2, . . . , AK 代表原定游览线路。
【输出格式】
输出 K 个整数，其中第 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，其中 6 → 5 花费时间 3 + 2 + 2 = 7，
5 → 1 花费时间 2 + 1 = 3，总时间花费 10。
当跳过 6 时，路线是 2 → 5 → 1，其中 2 → 5 花费时间 1 + 1 + 2 = 4，
5 → 1 花费时间 2 + 1 = 3，总时间花费 7。
当跳过 5 时，路线是 2 → 6 → 1，其中 2 → 6 花费时间 1 + 1 + 2 + 3 = 7，
6 → 1 花费时间 3 + 2 + 1 = 6，总时间花费 13。
当跳过 1 时，路线时 2 → 6 → 5，其中 2 → 6 花费时间 1 + 1 + 2 + 3 = 7，
6 → 5 花费时间 3 + 2 + 2 = 7，总时间花费 14。
【评测用例规模与约定】
对于 20% 的数据，2 ≤ K ≤ N ≤ 102。
对于 40% 的数据，2 ≤ K ≤ N ≤ 104。
对于 100% 的数据，2 ≤ K ≤ N ≤ 105，1 ≤ u, v, Ai ≤ N，1 ≤ t ≤ 105。保证
Ai 两两不同。
试题J：砍树
【问题描述】
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),
. . . , (am, bm)，其中 ai 互不相同，bi 互不相同，ai , bj(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai
, bi) 满足 ai
和 bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开
始），否则输出 -1。
【输入格式】
输入共 n + m 行，第一行为两个正整数 n，m。
后面 n − 1 行，每行两个正整数 xi，yi 表示第 i 条边的两个端点。
后面 m 行，每行两个正整数 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 和 6 不连通，4
和 5 不连通。
断开第 4 条边后形成两个连通块：{1, 2, 3, 4}，{5, 6}，同样满足 3 和 6 不连
通，4 和 5 不连通。
4 编号更大，因此答案为 4。
【评测用例规模与约定】
对于 30% 的数据，保证 1 < n ≤ 1000。
对于 100% 的数据，保证 1 < n ≤ 105，1 ≤ m ≤ n/2。
答案
A题答案:
因为是填空题，所以可以写一个纯暴力的代码在自己的编译器里跑
235
B题答案:
我们假设0出现了x次，1出现了y次
可以发现H(S)的值就是等于
这里x+y=n，题目中n=23333333，所以y=23333333-x，
带入公式中之后将x从0~23333333遍历，在自己的编译器中跑出来答案之后可以得到答案
如果答案大于23333333/2，记得把答案更新为23333333-ans，因为0出现的次数小于1的次数。
11027421
C题答案:
75 / 3 = 25
53 / 2 = 26
59 / 2 = 29
75 / (3+1) = 18
53 / (2+1) = 17
59 / (2+1) = 19
由题意可以知道，Vmax就是对所有的A/B取最小
Vmin则是我们对所有的A/（B+1）取最大之后因为是边界取不到，所以+1就是Vmin
#include <iostream> using namespace std; int n; int vis; int vis1; int Vmin = 999999999; int Vmax = 0; int main() { cin >> n; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; int vis = x / y; if (vis < Vmin) Vmin = vis; vis1 = x / (y + 1) + 1; if (vis1 > Vmax) Vmax = vis1; } cout << Vmax << " " << Vmin; 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
D题答案:
解题思路:利用全排列暴力测出全部的飞机排列情况,在试一试每个排列情况下是否可行
#include<bits/stdc++.h> using namespace std; const int N=15; int t[N],d[N],l[N]; int a[N]; int main() { 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++) a[i]=i; bool flag=false; do { int now=0; for(int i=1;i<=n;i++) { if(now<=t[a[i]]+d[a[i]]) now=l[a[i]]+max(now,t[a[i]]); else break; if(i==n) flag=true; } if(flag) break; }while(next_permutation(a+1,a+n+1));//全排列函数 if(flag) puts("YES"); else puts("NO"); } 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
E题答案:
这个题可以用线性DP来做
将每一个数当作字符串来存，其中x是第一位，y是最后一位（比如114514 x=1，y=4）
dp[y] 表示以y数字为结尾的最长数列
每次当前放或者不放取最优的状态，如果放，当前字符串的x就要和上一个的y一样，以y为结尾连下来的最优状态就是dp[y],加上当前的就是dp[x]+1
#include <bits/stdc++.h> using namespace std; int n; string s; int dp[15]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> s; int x = s[0] - '0'; int y = s[s.size()-1] - '0'; dp[y] = max(dp[y], dp[x] + 1); } int vis = 0; for (int i = 0; i < 10; i++) vis = max(vis, dp[i]); cout << n - vis; 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
F题答案:
从(0,0)开始染色，把遇到的0全部染成2，这样没染色的部分，一定为环，接着再搜索环的个数即可。
注意：开始染色的时候，可能有斜角，得使用八向搜索；搜索环的时候则用四向搜索。
#include<bits/stdc++.h> using namespace std; #define ll long long const int N = 5e1 + 5; int T, m, n; char g[N][N]; int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}; int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1}; int ans; struct point { int x, y; }; void bfs1() { queue<point>q; g[0][0] = '2'; q.push({0, 0}); while (!q.empty()) { point now = q.front(); q.pop(); for (int i = 0; i < 8; i++) { int tx = now.x + dx[i]; int ty = now.y + dy[i]; if (tx >= 0 && ty >= 0 && tx <= m + 1 && ty <= n + 1) { if (g[tx][ty] == '0') { g[tx][ty] = '2'; q.push({tx, ty}); } } } } } void bfs2(int x, int y) { queue<point>q; g[x][y] = '2'; q.push({x, y}); while (!q.empty()) { point now = q.front(); q.pop(); for (int i = 0; i < 4; i++) { int tx = now.x + dx[i]; int ty = now.y + dy[i]; if (tx >= 1 && ty >= 1 && tx <= m && ty <= n) { if (g[tx][ty] == '0' || g[tx][ty] == '1') { g[tx][ty] = '2'; q.push({tx, ty}); } } } } } int main() { cin >> T; while (T--) { cin >> m >> n; memset(g, '0', sizeof(g)); ans = 0; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cin >> g[i][j]; } } bfs1(); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (g[i][j] == '1') { ans++; bfs2(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
G题答案:
这道题也是可以用DP解决的
我们对字符串从后往前，定义dp[i]表示字符串从i到字符串末尾len即 [ i，len ] 区间中c2的个数
状态转移方程：
ans则是 [ 1， len-k+1 ]区间中所有当 s[i]=c1 时的 f[ i+k-1 ] 的和
即当s[i] = c1时，ans+= f[ i+k-1 ]（从i+k-1到len的区间内c2的个数）
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 5e5 + 5; int k; string s; char c1, c2; int f[N]; ll ans; int main() { cin >> k >> s >> c1 >> c2; int len = s.size(); s = " " + s; for (int i = len; i >= 1; i--) { f[i] = f[i + 1]; if (s[i] == c2) f[i] = f[i + 1] + 1; } for (int i = 1; i + k - 1 <= len; i++) { if (s[i] == c1) ans += f[i + k - 1]; } cout << ans; 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
H题答案:
由于要进行大量的删除操作, 不难想到可以使用链表.
而本题需要动态的求最小值, 显然可以使用堆.
每次从堆中取出最小值的下标, 然后在链表中删除它.
但本题特殊点在于将其删除。并把与它相邻的整数加上被删除的数值, 所以会导致还在堆中的元素的权的变化.
我们可以注意到, 每次删除操作只会让一些元素变大, 而不会让元素变小. 也就是, 可能会让原本的最小值变成不是最小值.
因此我们取出堆中的最小值时, 需要将此元素的排序权和实际的值进行对比, 如果实际的值变大了, 则当前元素并不一定是最小值, 需要重新放回堆中.
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 5e5 + 10; ll v[N], l[N], r[N]; //双向链表的删除操作， 删除x结点 void del(int 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>>> h; //输入并构造双向链表 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, h.push({v[i], i}); while (k --) { auto p = h.top(); h.pop(); //如果v发生变化， 则目前的元素不一定是最小值， 需要重新放入堆中 if (p.first != v[p.second]) h.push({v[p.second], p.second}), k ++; else del(p.second); } //输出链表剩余的元素 int 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
I题答案:
要确定的一点是， 由于题中的图是一棵树， 所以对于任意两个顶点， 它们的最短路径就是它们的简单路径。
求树中两个结点的简单路径距离， 可以想到利用它们的最近公共祖先即LCA。
本题就是一道LCA的模板题， 使用倍增法或者tarjan算法都是可以。
距离可能会爆int， 因此建议是所有整型都用long long。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; using ll = long long; vector<pair<int, int>> g[N]; ll dep[N], f[N][30], dist[N]; //倍增LCA预处理 void dfs(int u, int fa, ll d) { dep[u] = dep[fa] + 1, dist[u] = d, f[u][0] = fa; for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1]; for (auto &p : g[u]) { if (p.first == fa) continue; dfs(p.first, u, d + p.second); } } //求a和b的lca int lca(int a, int b) { if (dep[a] < dep[b]) swap(a, b); for (int i = 20; i >= 0; i --) { if (dep[f[a][i]] >= dep[b]) a = f[a][i]; if (a == b) return a; } for (int i = 20; i >= 0; i --) { if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i]; } return f[a][0]; } ll get(int a, int b) { return dist[a] + dist[b] - 2 * dist[lca(a, b)]; } int main () { int n, k; cin >> n >> k; for (int i = 1; i < n; i ++) { int u, v, t; cin >> u >> v >> t; g[u].push_back({v, t}), g[v].push_back({u, t}); } vector<int> a(k); for (auto &x : a) cin >> x; dfs(1, 0, 0); //求出原本整条路径的和 ll sum = 0; for (int i = 1; i < k; i ++) sum += get(a[i - 1], a[i]); //依次求出删除每个点时的和 for (int i = 0; i < k; i ++) { ll ans = sum; //减去当前顶点和左右顶点的路径距离 if (i != 0) ans -= get(a[i], a[i - 1]); if (i != k - 1) ans -= get(a[i], a[i + 1]); //左右都有顶点时， 要把两个顶点接到一起 if (i != 0 && i != k - 1) ans += get(a[i - 1], a[i + 1]); cout << ans << " "; } 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
J题答案:
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10, M = 18; vector<pair<int, int>> g[N]; int dep[N], f[N][20], cnt[N], w[N]; void init(int u, int fa) { dep[u] = dep[fa] + 1, f[u][0] = fa; for (int i = 1; (1 << i) <= dep[u]; i ++) f[u][i] = f[f[u][i - 1]][i - 1]; for (auto &e : g[u]) { if (e.first != fa) init(e.first, u), w[e.first] = e.second; } } int lca(int a, int b) { if (dep[a] < dep[b]) swap(a, b); for (int i = M; i >= 0; i --) { if (dep[f[a][i]] >= dep[b]) a = f[a][i]; if (a == b) return a; } for (int i = M; i >= 0; i --) { if (f[a][i] != f[b][i]) a = f[a][i], b = f[b][i]; } return f[a][0]; } void add(int a, int b) { int LCA = lca(a, b); cnt[a] ++, cnt[b] ++, cnt[LCA] -= 2; } void dfs(int u, int fa) { for (auto &e : g[u]) { if (e.first != fa) dfs(e.first, u), cnt[u] += cnt[e.first]; } } int main () { int n, m; cin >> n >> m; for (int i = 1; i < n; i ++) { int a, b; cin >> a >> b; g[a].push_back({b, i}), g[b].push_back({a, i}); } init(1, 0); for (int i = 0; i < m; i ++) { int a, b; cin >> a >> b; add(a, b); } dfs(1, 0); int res = -1; for (int i = 1; i <= n; i ++) if (cnt[i] == m && (w[i] > res)) res = w[i]; cout << res << 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
