A、Ancestor题解
前置知识：dfs序，倍增法求lca
OI wiki上的倍增LCA模板，
看文字嫌累还有b站的讲解视频（个人觉得不错）
题目主要是让我们求长度为k-1的点集的最近公共祖先（一个点被删了），对于求多个点的最近公共祖先，我们并不真的要对所有点两两都求一次。我们只用取这些点中dfs
展开全文
考虑删除一个结点之后 LCA 会怎么变化
只考虑 A 树，当且仅当存在 k−1k-1k−1 个结点在lca的一颗子树上时，删除剩下的那个结点，才会使 LCA 变化。如果存在这种情况，我们只需要找到删除掉之后能使 LCA 产生变化的结点并记录下来。
对于 B 树我们拥有相同的结论。
所以我们只需要
展开全文
A Ancestor
题目大意
给定两颗根节点均为 111 的树 A,BA,BA,B 以及每个点的权值，对于一个包含 kkk 个点的序列，求在序列中选取恰好一个点，除去该点剩下的点在 AAA 上的 lcalcalca 的权值严格大于下的点在 BBB 上的 lcalcalca 的权值
解题思路
Sol
展开全文
2022 牛客多校第三场 部分题解
比赛链接："蔚来杯"2022牛客暑期多校训练营3
C题 Concatenation （贪心，排序）
给定 nnn 个仅包含 0-4 的字符串，问怎么将他们拼接起来，使得最后得到的字符串，其转换成数字的值最大？
n≤2∗106,∑∣s∣≤2∗107n\leq 2*
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
