《算法合集之《回到起点——一种突破性思维》》由会员分享，可在线阅读，更多相关《算法合集之《回到起点——一种突破性思维》（27页珍藏版）》请在金锄头文库上搜索。
1、回到起点一种突破性思维,南京市外国语学校 朱泽园,问题一的提出 USACO Shaping Regions 改编,N个不同颜色的不透明长方形（1=N=3000） 放在一张长宽分别为A、B的白纸上 边与白纸的边缘平行 求俯视时看到的所有颜色的面积,问题一的解决简单的预处理,离散化整数坐标 坐标范围在12n之间。,离散行,离散列,问题一的解决经典算法,3,8线段对应线段树上节点,问题一的解决经典算法,自顶至底依次插入颜色为X的线段l,r，该区间l,r上原有颜色不被替换，其余部分染上颜色X。 O(logn) 返回所有颜色的覆盖量。 O(n),问题一的解决经典算法,O(n2logn) 优点： 广为人知
2、 复杂度较低，练习线段树的经典教材,问题一的解决朴素算法,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,
3、问题一的解决另类算法,1,2,3,4,5,6,7,8,完整的路径压缩，再加上按秩合并可以使改进算法的时间复杂度完全降至O(n2)，具体操作和证明参见我的论文。,问题二的提出 BalticOI2004 1-3 Sequence改编,给定序列t1, t2, , tN，要求构建一个递增序列z1 = z2 = x的最小的i，恰好是最小的i使得对任意ijn，tij的中位数x。 （如果某组最优方案不满足该条件，我们可以经过调整，使得另一个最优方案满足该条件）,问题二的解决引理,满足zix的最小的i，恰好是最小的i使得对任意ijn，tij的中位数x。,i,zjx | i=j=n,x,zj=x | 1=ji,问题二的解决第二类算法,二分！,i,x,O(nlogn),总结,问题的表示往往比答案更重要，答案不过乃数学或实验。 要提出新的问题、新的可能性、从某个新的角度考虑一个旧问题，都要求创造性的想象力，回到起点对问题重新定义，这才是真正的科学进步之所在。,
