Posted on 2012-01-22 23:08
Mato_No1 閱讀(290)
評論(0) 編輯 收藏 引用
所謂數據結構詢問類題，就是那種一大堆操作+詢問的題（典型的有NOI2005 sequence、NOI2007 necklace等）。
對于這種題常用數據結構有：線段樹（樹狀數組可以看成線段樹的簡化版本）、Segplaytree、各種塊狀結構，以及線段樹在樹結構上的應用——樹鏈剖分、Segplaytree在樹結構上的應用——Link-cut Tree實現動態樹；
解題技巧：
（1）看到題以后，首先搞清楚題目是基于什么結構的——線性結構、樹形結構、甚至可能還有圖結構（比如SCOI2011的那題，對于圖結構一般不能直接處理，而是采用三種辦法搞定：一是有向圖縮環轉化為有向樹、二是求生成樹、三是遍歷）
（2）在基本的數據結構（上面列出來的那些）當中看看有木有可以支持所有的操作的（其實，如果遇到一種基本數據結構就能支持題目中所有的操作，那這題就太水了，一般像AH這樣的弱省全場30人以上AC木有問題，因此要特別小心），如果有就直接用這種數據結構搞了；
（3）如果木有，就要想到數據結構的聯合或者是模型轉化；
（4）然后就是寫代碼了，寫的時候要注意這種數據結構模板中的易疵點；
（5）調試的時候，先檢查樣例和不超過5組的小數據，緊接著讀一遍代碼，觀察那些易疵點，然后立刻開始對拍，節省時間；
（6）對拍的程序是很容易寫的；
（7）造數據的時候可以造只有一種操作的，專門檢查這種操作有木有問題；
（8）一定要設法考慮到并檢查各種特殊情況。