集训队作业-解题报告_第1页
集训队作业-解题报告_第2页
免费预览已结束，剩余2页可下载查看

付费下载

下载本文档

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

文档简介

一、题目简k(1≤k≤20000)个整数区间[liri]i1lirin(1≤n≤20000)。liljrirjljlirjri，则称区间[liri]和[ljrj]严格相交。判断能否将kNS7[12],[13],[24],[57],[48],[78],[6{[1,2],[1,3],[7,8],[6,{[2,4],[5,7],[4,二、题目解由于只需要将顶点划分成两个独立集，所以问题的本质是判断这个图是否是一个二分O(E)E为边的数量级。由于上图的边的数量O(k2)级别的情况：继续在朴素算法上进行思考。之所以朴素算法达到O(E)的时间复杂度，是因为朴素算而且判断一个染色方案是否成功（即一个区间图是否是独立集O(klogk)的时间复O(E)的。解uQQu}2QQv31u相连的未染色顶点（u相交的其他区间，并将这些顶Q2。：其中步骤3需要设计一个数据结构来实现如下功能未染间集合T，能查找出：点[l,r]

liri，两个儿子结点的区间分别为[l,mid]

[midi+1,ri]对于线中每个结点[li,ri]，记录了所有右端点在[li,ri]中的区间。这些区间都用根据线的性质，每个区间中最多被logn个结点记录，因此总的空间复杂度为8 8 5 含1，那么递归考虑结点i与区间u有公共点的儿子结点。如果结点i所表示的区间被区间uu严格相交的区间即可。ujlj<lu。又因为线u严格相交的区间，O(klogn)。建立线的时间复杂度也为O(klogn)。O(klogk)。1区间i真包含区间j，指liljrj<ri判断li+1到ri-1优为了能够一次找出所有与区间u对于线中每个非叶子结点[li,ri]，记录了右端点在[li,ri]的未染间中左端点对于线中的叶子结点[li,ri]，记录了所有右端点在[li,ri]中的未染间。这些间u相交的所有未染间时，可以通过在新线中进行多次查找得到。O(klogk)。试题来源XPolishO

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论