《算法合集之《回到起点-一种突破性思维》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《回到起点-一种突破性思维》.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、回到起点回到起点一种突破性思维一种突破性思维南京市外国语学校南京市外国语学校南京市外国语学校南京市外国语学校 朱泽园朱泽园朱泽园朱泽园问题一的提出问题一的提出USACO Shaping Regions USACO Shaping Regions 改编改编N N个不同颜色的不透明长方形（个不同颜色的不透明长方形（1=N=30001=N=3000）放在一张长宽分别为放在一张长宽分别为A A、B B的白纸上的白纸上边与白纸的边缘平行边与白纸的边缘平行求俯视时看到的所有颜色的面积求俯视时看到的所有颜色的面积问题一的解决问题一的解决简单的预处理简单的预处理离散化离散化整数坐标整数坐标坐标范围在坐标范围在
2、1 12n2n之间。之间。123456123456离散行离散行离散列离散列离散格离散格问题一的解决问题一的解决经典算法经典算法1,101,55,101,33,55,77,101,22,33,44,55,66,77,88,108,99,103,8线段对应线段树上节点线段对应线段树上节点问题一的解决问题一的解决经典算法经典算法自顶至底依次插入颜色为自顶至底依次插入颜色为X X的线段的线段l,rl,r，该区间该区间l,rl,r上原有颜色不被替换，其余部上原有颜色不被替换，其余部分染上颜色分染上颜色X X。O(logn)O(logn)O(logn)O(logn)返回所有颜色的覆盖量。返回所有颜色的覆盖
3、量。O(n)O(n)O(n)O(n)问题一的解决问题一的解决经典算法经典算法O(nO(n2 2logn)logn)优点：优点：广为人知广为人知广为人知广为人知复杂度较低，练习线段树的经典教材复杂度较低，练习线段树的经典教材复杂度较低，练习线段树的经典教材复杂度较低，练习线段树的经典教材问题一的解决问题一的解决朴素算法朴素算法O(nO(n3 3)问题一的解决问题一的解决另类算法另类算法O(nO(n3 3)优点：优点：极易实现极易实现极易实现极易实现启发性强（有潜力可挖）启发性强（有潜力可挖）启发性强（有潜力可挖）启发性强（有潜力可挖）寻找冗余！寻找冗余！这一段的检索有必要吗？这一段的检索有必要吗
4、？问题一的解决问题一的解决另类算法另类算法 对已覆盖的区间，新增后续指针对已覆盖的区间，新增后续指针走进已覆盖离散格时，沿指针进入下一个走进已覆盖离散格时，沿指针进入下一个离散格离散格将途径离散格的后续指针设为当前覆盖区将途径离散格的后续指针设为当前覆盖区间之后的第一格。间之后的第一格。路径压缩？神似并查集路径压缩？神似并查集路径压缩？神似并查集路径压缩？神似并查集!问题一的解决问题一的解决另类算法另类算法将相邻的已染色线段看成一个集合红色 覆盖2,512345678问题一的解决问题一的解决另类算法另类算法12345678黄色 覆盖4,6问题一的解决问题一的解决另类算法另类算法12345678
5、绿色 覆盖1,8问题一的解决问题一的解决另类算法另类算法12345678完整的路径压缩，再加上按秩合并可以使改进算法的时间复杂度完全降至O(n2)，具体操作和证明参见我的论文。问题二的提出问题二的提出BalticOI2004 1-3 SequenceBalticOI2004 1-3 Sequence改编改编给定序列给定序列t t1 1,t,t2 2,t,tN N，要求构建一个递增，要求构建一个递增序列序列z z1 1=z=z2 2=z=xzix的最小的的最小的i i，恰好是最小的，恰好是最小的i i使得使得对任意对任意ijnijn，ti.jti.j的中位数的中位数xx。（如果某组最优方案不满足
6、该条件，我们可（如果某组最优方案不满足该条件，我们可以经过调整，使得另一个最优方案满足该条以经过调整，使得另一个最优方案满足该条件）件）问题二的解决问题二的解决引理引理满足满足zixzix的最小的的最小的i i，恰好是最小的，恰好是最小的i i使得使得对任意对任意ijnijn，ti.jti.j的中位数的中位数xx。izjx|i=j=nxzj=x|1=ji问题二的解决问题二的解决第二类算法第二类算法二分！二分！ixO(nlogn)总结问题的表示往往比答案更重要，答案不过乃问题的表示往往比答案更重要，答案不过乃数学或实验。数学或实验。要提出新的问题、新的可能性、从某个新的要提出新的问题、新的可能性、从某个新的角度考虑一个旧问题，都要求创造性的想象角度考虑一个旧问题，都要求创造性的想象力，力，回到起点回到起点对问题重新定义，这才是真正对问题重新定义，这才是真正的的科学进步科学进步之所在。之所在。