APIO2018 T2,一道神奇的 $\texttt{k-D Tree}$ 搜索剪枝题,或者一道毒瘤的 平衡树 + CDQ 分治 题。
题目链接:Luogu P4631/BZOJ 5465/LibreOJ 2586/APIO2018 T2。
Continue reading…Blog 主页
APIO2018 T2,一道神奇的 $\texttt{k-D Tree}$ 搜索剪枝题,或者一道毒瘤的 平衡树 + CDQ 分治 题。
题目链接:Luogu P4631/BZOJ 5465/LibreOJ 2586/APIO2018 T2。
Continue reading…一道诡异的 计算几何 的题目,光从名字就可以看出来它的诡异。
题目链接:Luogu P4227/LibreOJ 2329/UOJ 344/清华集训 2017 D4T1。
Continue reading…$\texttt{SAT}$ 是适定性(Satisfiability)问题的简称。一般形式为 $\texttt{k}$ – 适定性问题,简称 $\texttt{k-SAT}$。而当 $\texttt{k}>2$ 时该问题为 NP 完全的。所以我们只研究 $\texttt{k}=2$ 的情况。
$\texttt{k-D Tree}$(KDT , k-Dimension Tree) 是一种可以高效处理 $k$ 维空间信息的数据结构。
在结点数 $n$ 远大于 $2^n$ 时,应用 $\texttt{k-D Tree}$ 的时间效率很好。
在算法竞赛的题目中,一般有 $k=2$。在分析时间复杂度时,将认为 $k$ 是常数。
Continue reading…
近期评论