算法合集之《回到起点-一种突破性思维》.ppt_第1页
算法合集之《回到起点-一种突破性思维》.ppt_第2页
算法合集之《回到起点-一种突破性思维》.ppt_第3页
算法合集之《回到起点-一种突破性思维》.ppt_第4页
算法合集之《回到起点-一种突破性思维》.ppt_第5页
已阅读5页，还剩22页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

回到起点一种突破性思维,南京市外国语学校朱泽园,问题一的提出USACOShapingRegions改编,N个不同颜色的不透明长方形（1=N=3000）放在一张长宽分别为A、B的白纸上边与白纸的边缘平行求俯视时看到的所有颜色的面积,问题一的解决简单的预处理,离散化整数坐标坐标范围在12n之间。,离散行,离散列,问题一的解决经典算法,3,8线段对应线段树上节点,问题一的解决经典算法,自顶至底依次插入颜色为X的线段l,r，该区间l,r上原有颜色不被替换，其余部分染上颜色X。O(logn)返回所有颜色的覆盖量。O(n),问题一的解决经典算法,O(n2logn)优点：广为人知复杂度较低，练习线段树的经典教材,问题一的解决朴素算法,O(n3),问题一的解决另类算法,O(n3)优点：极易实现启发性强（有潜力可挖）寻找冗余！这一段的检索有必要吗？,问题一的解决另类算法,对已覆盖的区间，新增后续指针走进已覆盖离散格时，沿指针进入下一个离散格将途径离散格的后续指针设为当前覆盖区间之后的第一格。路径压缩？神似并查集!,问题一的解决另类算法,将相邻的已染色线段看成一个集合红色覆盖2,5,1,2,3,4,5,6,7,8,问题一的解决另类算法,1,2,3,4,5,6,7,8,黄色覆盖4,6,问题一的解决另类算法,1,2,3,4,5,6,7,8,绿色覆盖1,8,问题一的解决另类算法,1,2,3,4,5,6,7,8,完整的路径压缩，再加上按秩合并可以使改进算法的时间复杂度完全降至O(n2)，具体操作和证明参见我的论文。,问题二的提出BalticOI20041-3Sequence改编,给定序列t1,t2,tN，要求构建一个递增序列z1=z2x。（如果某组最优方案不满足该条件，我们可以经过调整，使得另一个最优方案满足该条件）,问题二的解决引理,满足zix的最小的i，恰好是最小的i使得对任意ijn，ti.j的中位数x。,i,zjx|i=j=n,x,zj=x|1=ji,问题二的解决第二类算法,二分！,i,x,O(nlogn),总结,问题的表示往往比答案更重要，答案不过乃数学或实验。要提出新的问题、新的可能性、从某个新的角
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论