信息学-集训队作业_第1页
信息学-集训队作业_第2页
全文预览已结束

下载本文档

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

文档简介

中国国家集训队难题活海南省海南中学【题目大意】列满足：M个子集中，每个子集的元素在排列中连续出现。【解决情况】【算法梗概】【正文】于任意数aka1a0，它是五位数的充要条件是aka40，可以由此直接构造出这种思想同样可在本问题中得到应用，关键是数据结构。其实，题目所给构（NM的矩阵）已经可以表示出问题的解集，但是在这种数据结构下的查找时间是 9 9 然而如果再加上{5,6}4、5连续，5、6也连续，有规定它们的特定顺序，所以单一的无序树结构在这里就 有有有有依次处理每个连续集合S，要使S中的元素连续，无非是在原来的树上进行修改，限制部分节点的顺序，但同时，这种修改出原来的树的含义（即后一棵树对应的具有至少两个非零集的树T为止。TL的修改，TR可根据对称性得到。LTLSLTLS 若TL是有序树，其子节点顺序必须是“零集树…半集树—全集树…”或“全集树对TL的半集进行同样的处理。但树的结构并没有改变，还需要对TL进行本质上的修改。深的一棵半集TD开始考虑。TD是最深的半集，因此它没有半集。子节点u、v，分别作为所有零集和所有全集的父亲，并令u、v为无序节点，TD变为有序树。：Ti进行调整Ti+1的子节点加入Ti。由Ti+1经过调整成为有序树，其到Ti+1的位置，：对TR进行类似处理，得到子节点形如“全集树…零集树…”的有序树。若T是无序树，为了使T的全集出现在TL和TR之间而又不过多限制这些全集的顺序，给T增加一个子节点u，作为这些全集的父亲，并令u为无序节点。合并TL、u、TR三个节点，以使S中的元素最终连续。PQPQ树可以在实现时，可以用附加节点属性的二叉树来表示PQ树。在第1、2步中，所有的节点的都只被O(1)次；第3、4步中，由于使用的是链式结构，可以记下把出度为1的节点去掉，并在其父子节点之间连一条线。这并不影响树的含义，因d(v)E

12

N

纵观此题的解题过程，发现：对解集进行等价转化的思想是关键，PQ树则是解集的一种

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

温馨提示

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

最新文档

评论

0/150

提交评论