apio2009convention试题分析.ppt

Convention试题讨论,APIO2009 讲题大会 清华大学 余林韵 ,题目大意,数轴上有n条线段。 选出最多的线段，使得： 这些线段不互相重叠； 所选的线段编号的字典序最小。,得分情况（国内测评）,讨论时间,欢迎大家踊跃发言参与讨论 你的得分？ 你的算法？ 你在思考过程中遇到了哪些瓶颈？ 你是如何想办法解决这些困难的？,算法：,直接搜索 期望得分：1020分,算法：,1、只考虑最多选出多少条线段 贪心 将所有线段按右端点坐标从小到大排序 顺序处理每个线段。 如果它与当前已选的所有线段都没有重叠，则选择该线段，否则不选。,贪心 证明,显然，该算法最后选出的线段不互相重叠，下面证明所选出线段的数量是最多的。设f(i)为该算法所接受的第i条线段的右端点坐标，g(i)为某最优解中的第i条线段的右端点坐标。,贪心 证明,命题1.1 当i1时，该算法所接受的第i条线段的右端点坐标f(i)某最优解中的第i条线段的右端点坐标g(i)。,贪心 证明,命题1.1 当i1时，该算法所接受的第i条线段的右端点坐标f(i)某最优解中的第i条线段的右端点坐标g(i)。 运用数学归纳法来证明。 对于i=1，命题显然为真，因为算法第一个选择的线段拥有最小右端点坐标。,贪心 证明,命题1.1 当i1时，该算法所接受的第i条线段的右端点坐标f(i)某最优解中的第i条线段的右端点坐标g(i)。 运用数学归纳法来证明。 令i1，假定论断对i-1为真，即f(i-1) g(i-1)。则最优解的第i条可选线段所组成的集合包含于执行该算法时第i条可选线段所组成的集合；而当算法选择第i条线段时，选的是在可选线段中右端点坐标最小的一个，所以有f(i) g(i)。,贪心 证明,命题1.2 最优解选出的线段数量m=该算法选出的线段数量k。 假设mk，根据命题1.1，有f(k)g(k)。由于mk，必然存在某线段，在g(k)之后开始，故f(k)也在之后开始。而该算法一定不会在选了第k条线段后停止，还会选择更多的线段，产生矛盾。所以mk,又因为m是最优解选出线段个数，所以m=k。,选取最小字典序的方案,法一： 直接搜索 期望得分： 2050分,选取最小字典序的方案,这类问题的通法： 按照编号，从小到大一一枚举 如果使用后仍有可行解，就保留下来，否则放弃,选取最小字典序的方案,法二： 直接按顺序枚举每条线段 考虑它选的情况 去除掉所有与已选线段有交的线段 计算最多可选线段数 若能达到总的最多可选线段数，则保留下这个区间 算法复杂度： O(N2) ,O(N2log2N),O(N3) 期望得分：30-60分,判断摆放一条线段是否可行,线段必须坐落于一段空白的区间中 除了这个区间，其余部分的最优解显然没有改变,线段是否在一段空白的区间中,离散化后线段树 平衡树 其他数据结构,判断摆放一条线段是否可行,所以 X区间中线段的最优解 =Y区间中线段最优解+1+Z区间中线段的最优解,计算某一个特定区间中最优解,回顾之前的贪心方案 有性质：方案中的线段sj,tj必然没有线段被它真包含 假设sj,tj真包含sk,tk sjsk, tktj且等号不同时成立 如果选择j可行，则选择k必然可行 j在k之前考虑，所以必然先选j,计算某一个特定区间中最优解,不需要考虑所有的线段，只需要选取不包含其他线段的线段来考虑即可 拥有性质： 排序后右端点升序的同时，左端点同样升序否则必然有线段真包含于其他线段 这样可以在O(log2N)内找出特定区间内的所有这类线段,计算某一个特定区间中最优解,用MIS(I,J)表示第i-第j条线段可选，最优解个数： 令Right(i)=Minji|i和j不相交 则MIS(I,J)=1+Maxk:Rightk(i)j,快速计算Maxk:Rightk(i)j,开log2N个序列: Right-1,Right-2Right-log2N Righttk=Right2k(t) 可以在O(log2N)内计算出Maxk:Rightk(i)j,快速计算MISleft,rig,int calcMIS(int left, int rig) if (rig = m) rig -; if (left rig) return 0; int res = 1; for (int i = maxlogn - 1, cur = left; i = 0; i -) if (rightcuri = rig) cur =