BZOJ1941  Hide and Seek

题目传送门 Solution: 可能是我写KDtree最后一道题了,主要是重新理解了KDtree点到块的距离在针对最大值和最小值的不同计算方式。 结合前面的两篇: 1、插入 2、求最大(小)点对 3、求k远点对 也只会这些操作了,可能还是我太菜。 Code: #include<cstdio …
BZOJ4520 K远点对

题目传送门 Solution: 一直想知道KDtree怎么求K远点对(可能是我比较菜),原来只是用一个堆来维护,其实也是一道模板题。 Code: #include<cstdio> #include<algorithm> #include<cstring> #inc …
BZOJ2648 SJY摆棋子

题目传送门 开坑!!kdtree Solution: 先来简单的讲一下kdtree,是一个支持n维空间的插入和查询K远点对的数据结构,其本质就是经过优化的暴力搜索,至于建树过程(百度百科里介绍的很清楚),我们就以二维为例:平面内有(2,1),(3,2),(5,7),(6,4),(9,6)这些点,我们 …