526互联
首页
Ai
Java
Python
Android
Mysql
JavaScript
Html
CSS
506D
CF506D Mr. Kitayuta's Colorful Graph
好久没更新这个单题系列了,主要是最近没啥CF比赛空闲时间又少,今天忙里偷闲写了两个题 这个题就比较典了,两点是否连通一般都是想到并查集维护,现在的问题是要对每种颜色的边把贡献算清楚 很容易想到枚举所有颜色的边,每次求出所有连通分量后遍历一遍询问统计答案,这样正确性显然但复杂度是\(O(m\times ......
Kitayuta
Colorful
Graph
506D
506
更新时间 2023-10-07
CF506D - Mr. Kitayuta's Colorful Graph
本质不同的算法主要有两种:对子图大小根号分治和类启发式均摊。此外还有很多实现上的差别。 #### 对子图大小根号分治 在线做法: 我们发现,把每个颜色的边和它们的顶点取出为一个子图,所有子图大小的和是 $O(n)$ 级别的。那么我们就可以根号分治。 首先,要预处理每个颜色子图下的连通块。可以用并查集 ......
Kitayuta
Colorful
Graph
506D
506
更新时间 2023-05-30
共2篇 :1/1页
首页
上一页
1
下一页
尾页