4月 2020

「OI」2-SAT

2020年4月16日 0 知识

$\texttt{SAT}$ 是适定性（Satisfiability）问题的简称。一般形式为 $\texttt{k}$ – 适定性问题，简称 $\texttt{k-SAT}$。而当 $\texttt{k}>2$ 时该问题为 NP 完全的。所以我们只研究 $\texttt{k}=2$ 的情况。

Continue reading…

「OI」k-D Tree

2020年4月15日 0 知识

$\texttt{k-D Tree}$(KDT , k-Dimension Tree) 是一种可以高效处理 $k$ 维空间信息的数据结构。

在结点数 $n$ 远大于 $2^n$ 时，应用 $\texttt{k-D Tree}$ 的时间效率很好。

在算法竞赛的题目中，一般有 $k=2$。在分析时间复杂度时，将认为 $k$ 是常数。

Continue reading…