数据结构询问类题解决方法

Posted on 2012-01-22 23:08 Mato_No1 阅读(275) 评论(0)  编辑 收藏 引用
所谓数据结构询问类题,就是那种一大堆操作+询问的题(典型的有NOI2005 sequence、NOI2007 necklace等)。
对于这种题常用数据结构有:线段树(树状数组可以看成线段树的简化版本)、Segplaytree、各种块状结构,以及线段树在树结构上的应用——树链剖分、Segplaytree在树结构上的应用——Link-cut Tree实现动态树;

解题技巧:
(1)看到题以后,首先搞清楚题目是基于什么结构的——线性结构、树形结构、甚至可能还有图结构(比如SCOI2011的那题,对于图结构一般不能直接处理,而是采用三种办法搞定:一是有向图缩环转化为有向树、二是求生成树、三是遍历)
(2)在基本的数据结构(上面列出来的那些)当中看看有木有可以支持所有的操作的(其实,如果遇到一种基本数据结构就能支持题目中所有的操作,那这题就太水了,一般像AH这样的弱省全场30人以上AC木有问题,因此要特别小心),如果有就直接用这种数据结构搞了;
(3)如果木有,就要想到数据结构的联合或者是模型转化;
(4)然后就是写代码了,写的时候要注意这种数据结构模板中的易疵点;
(5)调试的时候,先检查样例和不超过5组的小数据,紧接着读一遍代码,观察那些易疵点,然后立刻开始对拍,节省时间;
(6)对拍的程序是很容易写的;
(7)造数据的时候可以造只有一种操作的,专门检查这种操作有木有问题;
(8)一定要设法考虑到并检查各种特殊情况。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理