Posted on 2012-01-22 23:08
Mato_No1 阅读(282)
评论(0) 编辑 收藏 引用
所谓数据结构询问类题，就是那种一大堆操作+询问的题（典型的有NOI2005 sequence、NOI2007 necklace等）。
对于这种题常用数据结构有：线段树（树状数组可以看成线段树的简化版本）、Segplaytree、各种块状结构，以及线段树在树结构上的应用——树链剖分、Segplaytree在树结构上的应用——Link-cut Tree实现动态树；
解题技巧：
（1）看到题以后，首先搞清楚题目是基于什么结构的——线性结构、树形结构、甚至可能还有图结构（比如SCOI2011的那题，对于图结构一般不能直接处理，而是采用三种办法搞定：一是有向图缩环转化为有向树、二是求生成树、三是遍历）
（2）在基本的数据结构（上面列出来的那些）当中看看有木有可以支持所有的操作的（其实，如果遇到一种基本数据结构就能支持题目中所有的操作，那这题就太水了，一般像AH这样的弱省全场30人以上AC木有问题，因此要特别小心），如果有就直接用这种数据结构搞了；
（3）如果木有，就要想到数据结构的联合或者是模型转化；
（4）然后就是写代码了，写的时候要注意这种数据结构模板中的易疵点；
（5）调试的时候，先检查样例和不超过5组的小数据，紧接着读一遍代码，观察那些易疵点，然后立刻开始对拍，节省时间；
（6）对拍的程序是很容易写的；
（7）造数据的时候可以造只有一种操作的，专门检查这种操作有木有问题；
（8）一定要设法考虑到并检查各种特殊情况。