夜间模式暗黑模式
字体
阴影
滤镜
圆角

月份:2017年2月

篇文章

2013 Multi-University Training Contest 1
4600 Harvest Moon 待补 4601 Letter Tree 待补 4602 Partition OEIS一波即可 交的时候错了两次,是因为没有判断\(N \le K\)的情况 [crayon-5ed799e4c1fe1350375911/] (更多…)
莫队算法
唉,拖延症好严重啊。 其实分块的写法还是很简单的,高中不太懂,看了一堆什么最小曼哈顿生成树,感觉被吓尿,现在感觉也不是太难。 就是说如果区间查询可以离线,并且相邻的区间可以通过较快的时间复杂度进行转移,这种题目就是典型的莫队题啦。 先来一道例题 (更多…)
kd树练习:矩形区域查找
建立完kd树之后,对于每个子树,在根的位置记录一下覆盖这颗子树的最小的矩形,然后查询或者修改的时候算一下矩形交,之后就好啦。 不过因为两棵子树都有可能进入,所以我感觉时间复杂度还是比较玄学的,所幸题目上的表现似乎都还可以。 (更多…)
kd树练习:最近距离查询
k-d就是k个维度,k-d树其实就是用不同的维度来对点集进行划分,从而达到快速查找的目的。 时间复杂度比较科学的方法,一般是算出点集在某个维度上的方差,然后选择方差最大的维度,对点集进行划分,但是由于涉及到double的运算,有时在时间复杂度上并不尽如人意。所以轮换维度进行分割的方法也比较常见。 k-d树最简单的应用,就是查询在一个点集中,离一个点…