算法合集之《回到起点-一种突破性思维》.pptxVIP

回到起点——一种突破性思维南京市外国语学校朱泽园

问题一的提出

USACOShapingRegions改编N个不同颜色的不透明长方形（1=N=3000）放在一张长宽分别为A、B的白纸上边与白纸的边缘平行求俯视时看到的所有颜色的面积

问题一的解决——简单的预处理离散化整数坐标坐标范围在1~2n之间。123456123456离散行离散列离散格

问题一的解决——经典算法[1,10][1,5][5,10][1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7,8][8,10][8,9][9,10][3,8]线段对应线段树上节点

自顶至底依次插入颜色为X的线段[l,r]，该区间[l,r]上原有颜色不被替换，其余部分染上颜色X。O(logn)返回所有颜色的覆盖量。O(n)010302问题一的解决——经典算法

O(n2logn)优点：广为人知复杂度较低，练习线段树的经典教材问题一的解决——经典算法

问题一的解决——朴素算法O(n3)

O(n3)01优点：极易实现启发性强（有潜力可挖）02寻找冗余！03这一段的检索有必要吗？04问题一的解决——另类算法

…………对已覆盖的区间，新增后续指针走进已覆盖离散格时，沿指针进入下一个离散格将途径离散格的后续指针设为当前覆盖区间之后的第一格。路径压缩？神似并查集!问题一的解决——另类算法

将相邻的已染色线段看成一个集合01红色覆盖[2,5]02问题一的解决——另类算法

问题一的解决——另类算法黄色覆盖[4,6]

问题一的解决——另类算法绿色覆盖[1,8]

问题一的解决——另类算法完整的路径压缩，再加上按秩合并可以使改进算法的时间复杂度完全降至O(n2)，具体操作和证明参见我的论文。

问题二的提出

BalticOI20041-3Sequence改编给定序列t1,t2,…,tN，要求构建一个递增序列z1=z2=…=zN，使得|t1-z1|+|t2-z2|+…+|tN-zN|尽可能小。其中1≤N≤1000000，0≤tK≤2000000000。iti最优z序列注：为了更清楚地说明诸引理与算法，下文将多次出现类似的图。其中黑点代表t序列，线段代表某一个z序列的方案。

问题二的解决——定义与说明01由于最优方案不为一，下文中描述X是一组最优方案的同时，并不表示最优方案一定是X。对方案进行微调时，不保证原方案不是最优，但我们可以保证调整后的方案一定不会变差（某种程度上更接近最优）。z序列组成的方案可用(z1,z2,…zn)表示。02

问题二的解决——引理对给定的t1,t2,...,tn，如果最优方案满足z1=z2=...=zn=x，那么x为t[1..n]中位数时，其为一个最优方案。iti最优的z序列两个虚线表示的序列中，

下面一条序列比上面的优

问题二的解决——引理对于给定的t1,t2,...,tn，如果最优方案是z1=z2=...=zn=u，那么iti最优序列虚线比实线方案优

问题二的解决——引理对t1,t2,...tn，以及tn+1,tn+2,...tn+m，如果(u,u,...u)和(v,v,...,v)分别是它们的最优方案，并且u≥v，那么z[1..n+m]=t[1..n+m]的中位数iti最优序列后半部分的局部最优序列前半部分的局部最优序列

问题二的解决——第一类算法依次处理每个元素，对先前已经得到的最优方案进行微调iti第1个区间第2个区间第3个区间将z值相同的子序列看作一个连续的区间为插入的新元素建立一个独立的临时区间

问题二的解决——第一类算法如果当前最后一个区间的z值较前一个区间小，根据引理我们合并这两个区间，新的z值设定为它们的中位数iti第1个区间第2个区间第3个区间合并，找到新的中位数

问题二的解决——第一类算法如果当前最后一个区间的z值较前一个区间小，根据引理我们合并这两个区间，新的z值设定为它们的中位数iti第1个区间第2个区间第3个区间合并，找到新的中位数

问题二的解决——第一类算法01选取一个优秀的数据结构，它可以高效地完成如下任务：02集合合并03求出该集合的中位数。注意到集合最多和并n-1次，求中位数操作不超过n-1次。04

问题二的解决——第一类算法方法一：平衡二叉树O(n(logn)2)方法二：最大堆O(n(logn)2)可以严密证明，区间合并时相邻两个区间的数，最大一半的并集，恰好是合并后区间最大的一半方法三：在方法二基础上寻找冗余，努力避免集合的合并操作O(nlogn)方法四：左偏树O(nlogn)实现难！思考深度大！

对给定的t序列t[1..n]，如果z[1..n]是一组最优策略，那么我们可以假定：满足z[i]