后缀树-后缀数组-离散化.pptxVIP

算法与实践（二） Taotao Cai;离散化;UVA 10173 求覆盖所有点最小矩形面积; 这里的倾斜放置很不好处理，因为我们不知道这个矩形最终会倾斜多少度。假设我们知道这个矩形的倾角是α，那么答案就很简单了：矩形面积最小时四条边一定都挨着某个点。也就是说，四条边的斜率已经都知道了的话，只需要让这些边从外面不断逼近这个点集直到碰到了某个点。你不必知道这个具体应该怎么实现，只需要理解这可以通过某种方法计算出来，毕竟我们的重点在下面的过程。;?我们的算法很显然了：枚举矩形的倾角，对于每一个倾角，我们都能计算出最小的矩形面积，最后取一个最小值。 YES OR NO??;它根本不可能实现！;我们可以证明，最小面积的矩形不但要求四条边上都有一个点，而且还要求至少一条边上有两个或两个以上的点。试想，如果每条边上都只有一个点，则???们总可以把这个矩形旋转一点使得这个矩形变“松”，从而有余地得到更小的矩形。于是我们发现，矩形的某条边的斜率必然与某两点的连线相同。如果我们计算出了所有过两点的直线的倾角，那么α的取值只有可能是这些倾角或它减去90度后的角（直线按“\”方向倾斜时）这么C(n,2)种。我们说，这个“倾角”已经被我们 “离散化”了。虽然这个算法仍然有优化的余地，但此时我们已经达到了本文开头所说的目的。;对于那些坐标虽然已经是整数（离散的）但范围极大的问题我们也可以用离散化思想缩小问题的规模;发一张示意图，注意左边的10*7的数组是如何等价地转化为右边两个4*4的数组的;离散化的基本思路算是搞清楚了，接下来再上两个例子熟悉一下它的具体流程顺便复习一下线段树;POJ 2528 Mayor’s posters;POJ 2528 Mayor’s posters;如果每个叶子节点都代表一块瓷砖，那么线段 树会导致MLE，即单位区间的数目太多。 实际上，由于最多10,000个海报，共计20,000 个端点，这些端点把墙最多分成19,999个单位 区间（题意为整个墙都会被盖到）。每个单位 区间的瓷砖数目可以不同。 我们只要对这19,999个区间编号，然后建树即 可。这就是离散化。;POJ 2528 Mayors posters;;更好的离散化方法，是将所有海报的端点瓷砖 排序，把每个海报的端点瓷砖都看做一个单位 区间，两个相邻的端点瓷砖之间的部分是一个 单位区间 这样最多会有 20000 + 19999个单位区间;关键： 插入数据的顺序 ------ 从上往下依 次插入每张海报，这样后插入的海报不可 能覆盖先插入的海报，因此插入一张海报 时，如果发现海报对应区间有一部分露出 来，就说明该海报部分可见。 时间复杂度: nlogn (n为海报数目);POJ 2528 Mayors posters;POJ 2528 Mayors posters;#include iostream #include algorithm #include math.h using namespace std; int n; struct CPost { int L,R; }; CPost posters[10100]; int x[20200]; //海报的端点瓷砖编号 int hash; //hash[i]表示瓷砖i所处的离散化后的区间编号 struct CNode { int L,R; bool bCovered; //区间[L,R]是否已经被完全覆盖 CNode * pLeft, * pRight; }; CNode Tree[1000000]; int nNodeCount = 0;;int Mid( CNode * pRoot) { return (pRoot-L + pRoot-R)/2; } void BuildTree( CNode * pRoot, int L, int R) { pRoot-L = L; pRoot-R = R; pRoot-bCovered = false; if( L == R ) return; nNodeCount ++; pRoot-pLeft = Tree + nNodeCount; nNodeCount ++; pRoot-pRight = Tree + nNodeCount; BuildTree( pRoot-pLeft,L,(L+R)/2); BuildTree( pRoot-pRight,(L+R)/2 + 1,R); };bool Post( CNode *pRoot, int L, int R) { //插入一张正好覆盖区间[L,R]的海报,返回true则说明区间[L,R]是部分或 全部可见的