- 1使用Python进行情感分析
- 2AI Agents系列—— 探究大模型的推理能力，关于Chain-of-Thought的那些事儿_chain of thought存在什么问题
- 3XSS（跨站脚本攻击）及部分解决方案_xss攻击原理与解决方法
- 4《Redis设计与实现》第6章 整数集合（intset）_redis 设计一个int每次加一
- 5NLP入门——语言结构/语言建模_lexeme和morpheme区别
- 6【免费】面向多微网网络结构设计的大规模二进制矩阵优化算法
- 7基于梯度的神经网络优化算法总结_基于梯度的算法(后向传播)的神经网络
- 8ThinkPHP（7）：路由_thinkphp7文档
- 9国产Android视频，Broncho A1_国产视频
- 10T5模型简单介绍
第十四届蓝桥杯大赛软件赛省赛（C/C++ 大学B组）_第十四届蓝桥杯大赛软件赛决赛 ca-6
赞
踩
目前除 B、F题未补，其余题均已更完，经非官方数据测试均可AC。欢迎交流
试题 A. 日期统计
1.题目描述
小蓝现在有一个长度为 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 8 8；
-
- . 这个子序列可以按照下标顺序组成一个
y
y
y
y
m
m
d
d
yyyymmdd
yyyymmdd 格式的日期，并且
要求这个日期是 2023 2023 2023 年中的某一天的日期，例如 20230902 ， 20231223 20230902，20231223 20230902，20231223。
y y y y yyyy yyyy 表示年份， m m mm mm 表示月份， d d dd dd 表示天数，当月份或者天数的长度只
有一位时需要一个前导零补充。
- . 这个子序列可以按照下标顺序组成一个
y
y
y
y
m
m
d
d
yyyymmdd
yyyymmdd 格式的日期，并且
请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。
对于相同的日期你只需要统计一次即可。
2.解题思路
考虑八层循环枚举一下，中间需要进行减枝加快搜索步骤，不建议写 dfs，不然就像我一样在考场写烂，注意答案需要去重，答案为235。
3.模板代码
暂更
试题 B.01 串的熵
1.题目描述
没学过数学，暂更
2.解题思路
3.模板代码
试题 C. 冶炼金属
1.题目描述
小蓝有一个神奇的炉子用于将普通金属
O
O
O 冶炼成为一种特殊金属
X
X
X。这个
炉子有一个称作转换率的属性
V
V
V，
V
V
V 是一个正整数，这意味着消耗
V
V
V 个普通金
属
O
O
O 恰好可以冶炼出一个特殊金属
X
X
X，当普通金属
O
O
O 的数目不足
V
V
V 时，无法
继续冶炼。
现在给出了
N
N
N 条冶炼记录，每条记录中包含两个整数
A
A
A 和
B
B
B，这表示本次投入了
A
A
A 个普通金属
O
O
O，最终冶炼出了
B
B
B 个特殊金属
X
X
X。每条记录都是独立
的，这意味着上一次没消耗完的普通金属
O
O
O 不会累加到下一次的冶炼当中。
根据这
N
N
N 条冶炼记录，请你推测出转换率
V
V
V 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
2. 解题思路
如果看过样例的话，显然答案两个上下界都是可以直接二分出来的。因为式子的结构都是
A
C
=
B
\frac{A}{C} = B
CA=B。
A
A
A 是不变的，我们先考虑二分求最小的
C
C
C，因为需要保证所有式子的
B
B
B 都不变，如果
C
C
C 太小，显然会有某一组的
B
B
B 增大，所以需要保证每一组都符合a[i]/x <= b[i]。反过来考虑求最大的
C
C
C, 如果
C
C
C 太大，显然会有某一组的
B
B
B 变小，需要保证每一组都符合 a[i]/x >= B。
3.模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s); #define SZ(s) ((int)s.size()); #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 200010; int n; int a[N], b[N]; bool check(LL x) { for (int i = 1; i <= n; ++i) { if (a[i] / x > b[i]) return false; } return true; } bool check2(LL x) { for (int i = 1; i <= n; ++i) { if (a[i] / x < b[i]) return false; } return true; } void solve() { cin >> n; for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i]; LL l = 1, r = 1e9; while (l < r) { LL mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } int s = r; l = 1, r = 1e9; while (l < r) { LL mid = l + r + 1 >> 1; if (check2(mid)) l = mid; else r = mid - 1; } cout << s << " " << r << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } 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
试题 D. 飞机降落
1.题目描述
N
N
N 架飞机准备降落到某个只有一条跑道的机场。其中第
i
i
i 架飞机在
T
i
Ti
Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋
D
i
Di
Di 个单位时间，即它最早
可以于
T
i
Ti
Ti 时刻开始降落，最晚可以于
T
i
+
D
i
Ti + Di
Ti+Di 时刻开始降落。降落过程需要
L
i
Li
Li
个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不
能在前一架飞机完成降落前开始降落。
请你判断
N
N
N 架飞机是否可以全部安全降落。
2. 解题思路
看
N
N
N 最大为10，T最大也为10，考虑全排列枚举所有的降落情况，只要有一种符合的情况即可，大概计算一下复杂度为
10
!
×
10
×
10
10 ! \times10\times10
10!×10×10 等于3e8，理论可过 。
3.模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s); #define SZ(s) ((int)s.size()); #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 200010; int n; int a[N], b[N], c[N]; void solve() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i]; std::vector<int> d(n); auto check = [&]() { int v = 0; for (int i = 0; i < n; ++i) { int x = d[i]; if (i == 0) { v = a[x] + c[x]; } else { if (a[x] + b[x] < v) return false; v = max(v, a[x]) + c[x]; } } return true; }; iota(all(d), 0); bool f = false; do { if (check()) { f = true; break; } } while (next_permutation(all(d))); if (f) cout << "YES" << '\n'; else cout << "NO" << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } 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
试题 E. 接龙数列
1.题目描述
对于一个长度为
K
K
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
≤
i
≤
K
)
(2 ≤ i ≤ K)
(2≤i≤K)。
例如
12
,
23
,
35
,
56
,
61
,
11
12, 23, 35, 56, 61, 11
12,23,35,56,61,11 是接龙数列；
12
,
23
,
34
,
56
12, 23, 34, 56
12,23,34,56 不是接龙数列，因为
56
56
56 的首位数字不等于
34
34
34 的末位数字。所有长度为
1
1
1 的整数数列都是接龙数列。
现在给定一个长度为
N
N
N 的数列
A
1
,
A
2
,
.
.
.
,
A
N
A_1, A_2, . . . , A_N
A1,A2,...,AN，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
2. 解题思路
考场读完题的时候感觉有点奇怪，发现思路还是比较简单的。首先一个数我们只需要关注其首位数字和末位数字，定以
f
[
i
]
f[i]
f[i] 为以数字
i
i
i 结尾的最长接龙序列的长度，
i
i
i 的范围是
[
0
,
9
]
[0,9]
[0,9]。对于每个数字设其首位数字为
a
a
a ，末尾数字为
b
b
b，则有转移方程：
f
[
b
]
=
m
a
x
(
f
[
b
]
,
f
[
a
]
+
1
)
f[b]=max(f[b],f[a]+1)
f[b]=max(f[b],f[a]+1)
最后在
f
[
0
]
、
f
[
1
]
.
.
.
f
[
9
]
f[0]、f[1]...f[9]
f[0]、f[1]...f[9] 取一个最大值
a
n
s
ans
ans，答案则为
n
−
a
n
s
n-ans
n−ans。
3.模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s); #define SZ(s) ((int)s.size()); #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 200010; int n; int a[N], b[N]; int f[10]; void solve() { cin >> n; for (int i = 1; i <= n; ++i) { int x; cin >> x; b[i] = x % 10; string s = to_string(x); a[i] = s[0] - '0'; } for (int i = 1; i <= n; ++i) { f[b[i]] = max(f[b[i]], f[a[i]] + 1); } int ans = 0; for (int i = 0; i <= 9; ++i) ans = max(ans, f[i]); cout << n - ans << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } 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
试题 F. 岛屿个数
1.题目描述
暂更，感觉不好写
2. 解题思路
3.模板代码
试题 G. 子串简写
1.题目描述
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如
i
n
t
e
r
n
a
t
i
o
n
−
a
l
i
z
a
t
i
o
n
internation-alization
internation−alization 简写成
i
18
n
i18n
i18n，
K
u
b
e
r
n
e
t
e
s
Kubernetes
Kubernetes （注意连字符不是字符串的一部分）简写成
K
8
s
,
L
a
n
q
i
a
o
K8s, Lanqiao
K8s,Lanqiao 简写成
L
5
o
L5o
L5o等。
在本题中，我们规定长度大于等于
K
K
K 的字符串都可以采用这种简写方法（长度小于
K
K
K 的字符串不配使用这种简写）。
给定一个字符串
S
S
S 和两个字符
c
1
c1
c1 和
c
2
c2
c2，请你计算
S
S
S 有多少个以
c
1
c1
c1 开头
c
2
c2
c2 结尾的子串可以采用这种简写？
2. 解题思路
这道题放在 G 题感觉更奇怪了，一道前缀和模板题。假设下标为
i
i
i 的字符为
c
1
c1
c1，那我们只需要统计在区间
[
i
+
k
−
1
,
n
]
[i+k-1,n]
[i+k−1,n]有多少个
c
2
c2
c2 即可，前缀和预处理一下
c
2
c2
c2 字符，直接累加答案即可，注意答案会爆int，复杂度
O
(
n
)
O(n)
O(n)
3.模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s); #define SZ(s) ((int)s.size()); #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 500010; int k; string s; char c1, c2; int a[N]; void solve() { cin >> k >> s >> c1 >> c2; int n = s.size(); s = '?' + s; for (int i = 1; i <= n; ++i) { a[i] = (s[i] == c2); a[i] += a[i - 1]; } LL ans = 0; for (int i = 1; i + k - 2 < n; ++i) { if (s[i] == c1) ans += a[n] - a[i + k - 2]; } cout << ans << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } 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
试题 H.整数删除
1.题目描述
给定一个长度为
N
N
N 的整数数列：
A
1
,
A
2
,
.
.
.
,
A
N
A_1, A_2, . . . , A_N
A1,A2,...,AN。你要重复以下操作
K
K
K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出
K
K
K 次操作后的序列。
2. 解题思路
感觉是比较典的题目，用优先队列维护，存入值和下标，再用一个数组cnt累计每个下标增加的和，当弹出最小的值下标为 i 时，如果此时cnt[i]不等于0，说明它实际的值需要加上cnt[i]，我们将其增加后再放回优先对列，注意需要清空cnt[i]。如果此时cnt[i]等于0，那我们就成功弹出当前最小元素，这时需要将其前一个元素和后一个元素值增加，我们需要模拟链表去记录每个元素的前后元素是谁，pre[i]表示下标为i的上一个元素是谁，ne[i]表示下标为 i 的下一个元素是谁，直到堆的元素个数只剩n-k时结束循环。不难想象，堆元素的出入次数是线性的。
3.模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s); #define SZ(s) ((int)s.size()); #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 500010; int n, k; int pre[N], ne[N]; LL cnt[N]; void solve() { cin >> n >> k; priority_queue<pair<LL, int>, vector<pair<LL, int>>, greater<pair<LL, int>> >q; for (int i = 1; i <= n; ++i) { LL v; cin >> v; q.push({v, i}); pre[i] = i - 1; ne[i] = i + 1; } int g = n - k; while (q.size() > g) { auto p = q.top(); q.pop(); LL v = p.first, ix = p.second; if (cnt[ix]) { q.push({v + cnt[ix], ix}); cnt[ix] = 0; } else { int l = pre[ix], r = ne[ix]; cnt[l] += v; cnt[r] += v; ne[l] = r; pre[r] = l; } } std::vector<LL> a(n + 1); for (int i = 0; i < g; ++i) { auto p = q.top(); q.pop(); a[p.second] = p.first + cnt[p.second]; } for (int i = 1; i <= n; ++i) { if (a[i]) cout << a[i] << " "; } } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } 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
试题 I. 景区旅游
1.题目描述
某景区一共有
N
N
N 个景点，编号
1
1
1 到
N
N
N。景点之间共有
N
−
1
N − 1
N−1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中
K
K
K 个景点：
A
1
,
A
2
,
.
.
.
,
A
K
A_1, A_2, . . . , A_K
A1,A2,...,AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中
K
−
1
K − 1
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
Ai
Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？
2. 解题思路
L
C
A
LCA
LCA 模板题（问题是比赛写不出板子呢），首先肯定需要考虑求树上任意两点的距离。设点
u
,
v
u,v
u,v 的最近公共祖先为
z
z
z，定义
f
[
i
]
f[i]
f[i] 为点
i
i
i 到根节点的距离，那么则有公式:
d
i
s
t
(
u
,
v
)
=
f
[
u
]
+
f
[
v
]
−
2
∗
f
[
z
]
dist(u,v)=f[u]+f[v]-2*f[z]
dist(u,v)=f[u]+f[v]−2∗f[z]
先求出不跳过任何的点时需要走的距离为ans以及任意相邻两个跳点的距离。假设我们跳过四个点分别为
a
,
b
,
c
,
d
a,b,c,d
a,b,c,d。当跳过的点为
a
a
a 时，我们只需要用ans减去
a
a
a到
b
b
b的距离，当跳过的点为
d
d
d 时，我们只需要用ans减去
c
c
c 到
d
d
d 的距离，这是首尾两个点的情况。
那么当跳过的点为中间点呢？比如我们跳过的是
b
b
b，那么则需要用ans减去
a
a
a到
b
b
b以及
b
b
b到
c
c
c的距离，并且还需要加上
a
a
a到
c
c
c的距离，其余的中间点处理同理。
3.模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s) #define SZ(s) ((int)s.size()) #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 200010; int n, m; std::vector<pair<int, LL>> e[N]; int depth[N], fa[N][32]; LL f[N]; int root; void bfs(int root) { memset(depth, 0x3f, sizeof depth); depth[0] = 0, depth[root] = 1; queue<int> q; q.push(root); while (!q.empty()) { auto t = q.front(); q.pop(); for (auto [j, c] : e[t]) { if (depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; q.push(j); fa[j][0] = t; for (int k = 1; k <= 20; k++) { fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } } } void dfs(int u, int fa) { for (auto [v, c] : e[u]) { if (v == fa) continue; f[v] = f[u] + c; dfs(v, u); } } int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); for (int k = 20; k >= 0; k--) { if (depth[fa[a][k]] >= depth[b]) { a = fa[a][k]; } } if (a == b) return a; for (int k = 20; k >= 0; --k) { if (fa[a][k] != fa[b][k]) { a = fa[a][k]; b = fa[b][k]; } } return fa[a][0]; } LL calc(int u, int v) { int z = lca(u, v); return f[u] + f[v] - 2 * f[z]; } void solve() { cin >> n >> m; for (int i = 0; i < n - 1; ++i) { int u, v , c; cin >> u >> v >> c; e[u].push_back({v, c}); e[v].push_back({u, c}); } bfs(1); dfs(1, -1); std::vector<LL> g(m + 1); for (int i = 1; i <= m; ++i) cin >> g[i]; LL ans = 0; for (int i = 1; i < m; ++i) { ans += calc(g[i], g[i + 1]); } for (int i = 1; i <= m; ++i) { if (i == 1) cout << ans - calc(g[i], g[i + 1]) << " "; else if (i == m) cout << ans - calc(g[i - 1], g[i]) << " "; else { LL res = ans - calc(g[i], g[i + 1]) - calc(g[i - 1], g[i]) + calc(g[i - 1], g[i + 1]); cout << res << " "; } } } signed main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } 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
- 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
试题 J. 砍树
1.题目描述
给定一棵由
n
n
n 个结点组成的树以及
m
m
m 个不重复的无序数对
(
a
1
,
b
1
)
,
(
a
2
,
b
2
)
,
.
.
.
,
(
a
m
,
b
m
)
(a1, b1), (a_2, b_2),. . . , (a_m, b_m)
(a1,b1),(a2,b2),...,(am,bm)，其中
a
i
ai
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
)
(ai , bi)
(ai,bi) 满足
a
i
ai
ai和
b
i
bi
bi 不连通，如果可以则输出应该断掉的边的编号（编号按输入顺序从
1
1
1 开始），否则输出
−
1
-1
−1。
2. 解题思路
又是
L
C
A
LCA
LCA 模板题啊，但我之前没做过（反正也写不出
L
C
A
LCA
LCA）。考虑一对无序数对的点
x
x
x 和
y
y
y ，如果我们砍掉某条边可以让这两个点不连通，那么这条边一定是从
x
x
x 到
y
y
y 路径上的一点，我们可以让从
x
x
x 到
y
y
y 路径的边权值都加1。这个操作我们可以使用树上差分。 对于
m
m
m 个无序数对我们都如此操作，最后如果某条边的权值为
m
m
m 则说明它符合条件，我们选出符合条件编号最大的那条边就是答案，如果没有权值为
m
m
m 的边则说明无解。
3. 模板代码
#include<bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long uLL; typedef pair<int, int> PII; #define pb(s) push_back(s); #define SZ(s) ((int)s.size()); #define ms(s,x) memset(s, x, sizeof(s)) #define all(s) s.begin(),s.end() const int inf = 0x3f3f3f3f; const int mod = 1000000007; const int N = 200010; int n, m; std::vector<int> e[N]; int depth[N], fa[N][32]; int f[N]; int root; int ans; map<PII, int> mp; void bfs(int root) { ms(depth, 0x3f); depth[0] = 0, depth[root] = 1; queue<int> q; q.push(root); while (!q.empty()) { auto t = q.front(); q.pop(); for (int j : e[t]) { if (depth[j] > depth[t] + 1) { depth[j] = depth[t] + 1; q.push(j); fa[j][0] = t; for (int k = 1; k <= 15; k++) { fa[j][k] = fa[fa[j][k - 1]][k - 1]; } } } } } int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); for (int k = 15; k >= 0; k--) { if (depth[fa[a][k]] >= depth[b]) { a = fa[a][k]; } } if (a == b) return a; for (int k = 15; k >= 0; --k) { if (fa[a][k] != fa[b][k]) { a = fa[a][k]; b = fa[b][k]; } } return fa[a][0]; } int dfs(int u, int fa) { int res = f[u]; for (auto v : e[u]) { if (v == fa) continue; int g = dfs(v, u); if (g == m) { ans = max(ans, mp[ {v, u}]); } res += g; } return res; } void solve() { cin >> n >> m; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; mp[ {u, v}] = mp[ {v, u}] = i + 1; e[u].push_back(v); e[v].push_back(u); } bfs(1); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; int z = lca(u, v); f[u]++; f[v]++; f[z] -= 2; } dfs(1, -1); cout << (ans == 0 ? -1 : ans) << '\n'; } int main() { ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int t = 1; while (t--) { solve(); } 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
- 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
