算法合集之《回到起点-一种突破性思维》.ppt
回到起点一种突破性思维,南京市外国语学校 朱泽园,问题一的提出USACO Shaping Regions 改编,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)，具体操作和证明参见我的论文。,问题二的提出BalticOI2004 1-3 Sequence改编,给定序列t1,t2,tN，要求构建一个递增序列z1=z2=zN，使得|t1-z1|+|t2-z2|+|tN-zN|尽可能小。其中1N1000000，0tK2000000000。,最优z序列,注：为了更清楚地说明诸引理与算法，下文将多次出现类似的图。其中黑点代表t序列，线段代表某一个z序列的方案。,问题二的解决定义与说明,由于最优方案不为一，下文中描述X是一组最优方案的同时，并不表示最优方案一定是X。对方案进行微调时，不保证原方案不是最优，但我们可以保证调整后的方案一定不会变差（某种程度上更接近最优）。z序列组成的方案可用(z1,z2,zn)表示。,问题二的解决引理,对给定的t1,t2,.,tn，如果最优方案满足z1=z2=.=zn=x，那么x为t1.n中位数时，其为一个最优方案。,问题二的解决引理,对于给定的t1,t2,.,tn，如果最优方案是z1=z2=.=zn=u，那么,问题二的解决引理,对t1,t2,.tn，以及tn+1,tn+2,.tn+m，如果(u,u,.u)和(v,v,.,v)分别是它们的最优方案，并且uv，那么z1.n+m=t1.n+m的中位数,后半部分的局部最优序列,前半部分的局部最优序列,问题二的解决第一类算法,依次处理每个元素，对先前已经得到的最优方案进行微调,第1个区间,第2个区间,第3个区间,将z值相同的子序列看作一个连续的区间,为插入的新元素建立一个独立的临时区间,问题二的解决第一类算法,如果当前最后一个区间的z值较前一个区间小，根据引理我们合并这两个区间，新的z值设定为它们的中位数,第1个区间,第2个区间,第3个区间,合并，找到新的中位数,问题二的解决第一类算法,如果当前最后一个区间的z值较前一个区间小，根据引理我们合并这两个区间，新的z值设定为它们的中位数,第1个区间,第2个区间,第3个区间,合并，找到新的中位数,问题二的解决第一类算法,选取一个优秀的数据结构，它可以高效地完成如下任务：1、集合合并2、求出该集合的中位数。注意到集合最多和并n-1次，求中位数操作不超过n-1次。,问题二的解决第一类算法,方法一：平衡二叉树 O(n(logn)2)方法二：最大堆 O(n(logn)2)可以严密证明，区间合并时相邻两个区间的数，最大一半的并集，恰好是合并后区间最大的一半方法三：在方法二基础上寻找冗余，努力避免集合的合并操作 O(nlogn)方法四：左偏树 O(nlogn)实现难！思考深度大！,问题二的解决引理,对给定的t序列t1.n，如果z1.n是一组最优策略，那么我们可以假定：满足zix的最小的i，恰好是最小的i使得对任意ijn，ti.j的中位数x。（如果某组最优方案不满足该条件，我们可以经过调整，使得另一个最优方案满足该条件）,问题二的解决引理,满足zix的最小的i，恰好是最小的i使得对任意ijn，ti.j的中位数x。,i,zjx|i=j=n,x,zj=x|1=ji,问题二的解决第二类算法,二分！,i,x,O(nlogn),总结,问题的表示往往比答案更重要，答案不过乃数学或实验。要提出新的问题、新的可能性、从某个新的角度考虑一个旧问题，都要求创造性的想象力，回到起点对问题重新定义，这才是真正的科学进步之所在。,
