资源描述：
《算法合集之回到起点-一种突破性思维.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、回到起点——一种突破性思维南京市外国语学校朱泽园Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的提出USACOShapingRegions改编N个不同颜色的不透明长方形（1<=N<=3000）放在一张长宽分别为A、B的白纸上边与白纸的边缘平行求俯视时看到的所有颜色的面积Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5
2、.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——简单的预处理离散化整数坐标坐标范围在1~2n之间。123456123456离散行离散列离散格Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——经典算法[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][
3、8,10][8,9][9,10][3,8]线段对应线段树上节点Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——经典算法自顶至底依次插入颜色为X的线段[l,r]，该区间[l,r]上原有颜色不被替换，其余部分染上颜色X。O(logn)返回所有颜色的覆盖量。O(n)Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.
4、2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——经典算法O(n2logn)优点：广为人知复杂度较低，练习线段树的经典教材Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——朴素算法O(n3)Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2
5、004-2011AsposePtyLtd.问题一的解决——另类算法O(n3)优点：极易实现启发性强（有潜力可挖）寻找冗余！这一段的检索有必要吗？Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——另类算法…………对已覆盖的区间，新增后续指针走进已覆盖离散格时，沿指针进入下一个离散格将途径离散格的后续指针设为当前覆盖区间之后的第一格。路径压缩？神似并查集!Evaluationonly.Cre
6、atedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——另类算法将相邻的已染色线段看成一个集合红色覆盖[2,5]12345678Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——另类算法12345678黄色覆盖[4,6]Evaluationonly.Created
7、withAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——另类算法12345678绿色覆盖[1,8]Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题一的解决——另类算法12345678完整的路径压缩，再加上按秩合并可以使改进算法的时间复杂度完全降至O(n2)，具体操作和证明参见我的论
8、文。Evaluationonly.CreatedwithAspose.Slidesfor.NE
