Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

Re:求更优算法

Posted by Remington7120 at 2020-11-08 15:57:54 on Problem 2236
In Reply To:求更优算法 Posted by:Hoblovski at 2014-07-03 16:47:09

> 近似O(MN)暴力并查集不用说了,比这个差的也不用了吧...
> 
> 虽然一次可能合并N个点,但是总共最多合并N次,所以蒟蒻想问一问本题更快的算法.
> kd树?
>     不会而且好像是不可做的样子呢
> cdq分治?
>     我记得cdq分治可以很简单的解决曼哈顿距离,本题是欧几里得距离??
> 分块?莫队?
>     怎么搞??
> 
> 嘛只是作为一个讨论,欢迎神牛们给出各种神奇的
> O(MlgN),O(Mlg^2N),O(MlgNlglgN),O(Msqrt(N))
> 之类的算法

Followed by:

Re:求更优算法 (0) Remington7120 2020-11-08 15:58:38

Post your reply here:

Home Page Go Back To top