526互联
首页
Ai
Java
Python
Android
Mysql
JavaScript
Html
CSS
7215
P7215首都
2023-09-14 题目 P7215 [JOISC2020] 首都 难度&重要性(1~10):8 题目来源 luogu 题目算法 点分治 解题思路 一个显然的 \(O(n^2)\) 的暴力思路。 因为这是一颗树,我们就每一次将城镇 \(1\sim n\) 定为根节点,将这个城镇的所属城市定为首都, ......
首都
P7215
7215
更新时间 2023-09-17
题解 P7215
点分治。 考虑当前的分治重心的城市被完全联通。 这可以用队列接解决。每次放入一种城市,就把那些城镇的父亲加入队列,如果存在城镇不在当前分治重心的联通块内,那么说明必定存在另一个分治重心能算到它,直接退出即可。 剩下的和模板没有任何区别。 复杂度 $O(n\log n)$。 code: ```cpp ......
题解
P7215
7215
更新时间 2023-07-17
共2篇 :1/1页
首页
上一页
1
下一页
尾页