526互联
首页
Ai
Java
Python
Android
Mysql
JavaScript
Html
CSS
P9058
洛谷 P9058 [Ynoi2004] rpmtdq
洛谷传送门 类比 P9062 [Ynoi2002] Adaptive Hsearch&Lsearch 处理区间最近点对的思路,尝试只保留可能有贡献的点对。 处理树上路径容易想到点分治。设点 \(u\) 到分治中心的距离为 \(a_u\)。我们有 \(\text{dis}(u, v) \le a_u ......
rpmtdq
P9058
9058
2004
Ynoi
更新时间 2023-12-28
P9058 [Ynoi2004] rpmtdq 题解
支配点对实在是太有意思了。 本质上就是一个合法的减枝。 思路 考虑维护树上路径问题。 容易想到点分治。 考虑在当前的分治中心 \(\text{rt}\),每个点到当前分治中心的距离为 \(dp_x\)。 求出每一组点对的贡献。 假设每个点对在距离长的那部分贡献,即 \(dp_i>dp_j\),求出所 ......
题解
rpmtdq
P9058
9058
2004
更新时间 2023-11-25
共2篇 :1/1页
首页
上一页
1
下一页
尾页