基礎數據結構練習

這裏全是一些基礎的數據結構小練習。
在搞社團節沒什麼時間搞新科技(人太弱了。你看大爺們天天糖果公園,各種分塊。

這裏都是一些水題。

鏈表

[BZOJ 1588] 挺喜歡用鏈表的。方便。

塊狀鏈表

怎麼辦!怎麼辦!我才不會寫塊狀鏈表呢!
[BZOJ 3337]ORZJRY...趕快向rank1選手noname學習正確姿勢。
(聽說我只會傻逼暴力重構。

spaly

lazy思想
[BZOJ 1014] 字符串hash+splay
[BZOJ 3786] dfs序+splay
[BZOJ 1588] ...
[BZOJ 2329] 額。內心是崩潰的。寫了一晚上。我沒救了。注意各種標記的下傳就好。感覺還是貢獻一份代碼和mkdt咯。個人習慣用OCR去蓋掉之前的所有操作。

「COCI 2011 upit」 注意標記的下傳。

[GSS6] 裸的splay注意卡常數,不要寫class..

[HDU 1890]看懂題之後直接splay..(無名WA了一晚的腦殘的我。

「TASUFFIX」沒什麼難度的題。區間的切割翻轉啥的是splay的裸題。強套了一個已知後綴數組求字符串數,其中離散化後一樣的不算不同本質方案。然後就變成一個喜聞樂見的數等號問題。根據SA的性質可以列出形如然後其他地方隨便取。注意這裏的splay需要支持區間分裂。初始是的一個大節點。

启发式合并。每一次把小的全部连接到大的里面去。复杂度是的。不要写treap。

區間樹

還是注意lazy思想,和一些比較常見的處理技巧。
[hdu 3971] 離散化

不能下放和上传的标记?
标记的永久化。感觉很妙。
「poi 2006 tet」
二维线段树的第一维不能上传和下传标记。
怎么办?
标记永久化。
最大值等于所有包含整个区间的max与这个区间内所有的值的max
分别做包含这个区间的和这个区间内的。两个标记都无需下传。
标记就是值!

来自线段树的沉痛打击.sgt beats!
比较科学的东西,需要从灵魂上掌握线段树。

treap

常數小。

SBT

trie

注意一些經典思路

heap

額。主要用途還是堆貪心和dij

Fewick tree

[HDU3333] 离线处理。利用标记该数上一次出现的位置进行去重。
[SPOJ DQUERY] 同上。在线版本在另一题中。
这两个代码没什么区别,只给一个好了。

最后发现自己根本不会BIT
以下是三个BIT基本问题
1.树状数组上二分
2.区间修改的树状数组
3.二维树状数组
树状数组的意义?
卡常。

嵌套數據結構

嵌套思路千變萬化。
[Uva 12345/BZOJ 2120] 我可以说我是看着题号进来玩的么。其实是DQUERY的在线版本,并加入了修改操作。考虑的做法就是把之前的树状数组改成动态建点的线段树,然后在外层套一个树状数组维护每一个前缀操作和。至于每一次修改要考虑一下上一个与它相等的数和下一个与他相等的数的位置。时间复杂度是,空间复杂度是其中M为操作次数。N为序列长度。
0.5s代码
[SPOJ XXXXXXXX]额,HDU3333的带修改版。和上面那个一模一样。

樹上莫隊

會排序麼?
會莫隊麼?
會BZOj1086麼?
會暴力麼?
行。這樣就會樹上莫隊了。。
什麼?不會糖果公園?三關鍵字排序。
還不會?業界良心VFK的題解你值得一看。
一個好口胡但是口胡難度與實現難度成反比的東西。(現在我認爲是正比了。
[BZOJ 1086]
[SPOJ COT2]
額。雖然我不是跑到了rank1的owaski大爺,但是我從3.42卡到2.14

id Time MEM
16022273 2.14 11M
16019804 2.48 11M
16019783 2.50 11M
16019783 3.42 11M

還是有點策略的。
1.優化一:最大的優化,3.42->2.50 我們考慮排序前,把端點小的放在前面優先考慮。
2.優化二:2.50->2.48 額。。其實沒啥,就是到處加幾個寄存器。
3.優化三:就在我覺得不能優化的時候。回去寫糖果公園的時候,發現可以減少兩次求lca,然後求lca的次數可以化爲對於每一對詢問值求一次。2.48->2.14 這個優化還是蠻大的。
4.優化四:採用鏈剖求LCA。

大體上就這麼多優化。貼一份我2.14的代碼。

「WC2013」糖果公園。
帶修改的樹上莫隊。
挺好寫的,注意到我們需要把時間算作第三個關鍵字。這樣才能保證複雜度。
一個保證複雜度的分塊大小是,然而這題,推薦的玄學塊大小是1500!沒錯就是1500!
一般來說,你會1A。不要到處卡評測機。或者深夜刷題。複雜度是,玄學複雜度是在此基礎上乘上一個左右的常數。這個因人而定吧。

LCT/链剖

NOI上幾百人寫鏈剖的勝景十分感人吶。。
感覺這種DS題大家都有模塊
然後批量生產無聊題。
有意義的題還是有幾道的。論出題質量的重要性?出題質量不高導致大家爆切了。。。

鏈剖。需要掌握的。子樹、鏈,可持久化。
LCT。需要掌握的。維護子樹,鏈,鏈的反轉。

還有一些思路精妙的題目。

爆切。。

LCT的注意要點。
1.expose傳出查詢鏈。
2.聽說單旋更快?靠譜性未知。
3.getlca的寫法。
4.如何維護邊權?\
  「1」在每兩個點直接插入一個點。
  「2」每一個點記錄一個向上連接的邊權和一個向下連接的邊權。
感覺兩種做法常數差不多?「1」更加好寫。
此時要注意的問題有。link操作的正確姿勢應該是expose * 1+splay * 1。cut操作的正確姿勢應該是expose * 3 + splay * 3。感覺這樣已經是常數最小的可能了?
  記錄一下我的寫法:

inline void link(int x,int y,int p){
    mrt(x);
    t[x].fa=p;
    t[p].fa=y;
}
 
inline void cut(int x,int y,int p){
    mrt(p);
 
    expose(x);
    splay(x);
    t[p].fa=t[x].c[0]=0;
    t[p].rt=true;
    maintain(x);
 
    expose(y);
    splay(y);
    t[p].fa=t[y].c[0]=0;
    t[p].rt=true;
    maintain(y);
}

如何證明你維護邊權的LCT常數已經小飛?bzoj2001等着你。
5.rev怎么搞?注意先rev传下去..貌似有一些题一定要这样。举例子AC,WA所以建議是每一次翻了接着打標記。
6.卡常數。如果你發現你被卡常數了。試着splay之前暴力把所有上面的標記先pushdown爲敬,然後每一次rotate的時候只maintain下來的那個點,然後最後maintain一次根就行了。感覺常數會小很多。

「BZOJ 2594」水管局長加強版。不知道爲什麼無明WA了很久。結果是逗號和id-n寫成 id-m。好像我的常數并沒有小的飛起?感覺expose都ret不是好事?下次是不是寫一個不帶ret版本的?

「BZOJ 2001」正解并不是CDQ+LCT,不过我就是这么写的。复杂度是对的,就是常数比较大。不知道为什么别人都能卡常数的一次maintain到我这里就没用了。最后用单旋骗过去了。啊哈。跑到快18s的样子

樹分治

樹分治按分治方式有點分治,邊分治,鏈分治。大概我只會點分治。
此外還有動態點分治(我一般叫記錄分治結構),當然動態點分治的結構是一個樹,所以可以上替罪羊。從而實現修改分治結構信息。

做點題
「HNOI2015 開店」
ppfish:這不是大傻逼題麼?30min後切了此題。太勁。
方法:記錄分治結構,主要到分治結構是一棵樹。
我們考慮如何查詢當前重心到所有顏色爲[L,R]的點的距離和。做法,暴力排序。然後分治。
同理我們會了如何查詢給定點的,大概就是記錄分治樹上的父親,然後加加減減。

「ZJOI2015」幻想乡战略游戏
我会说前两题都是WJMZBMR的题?
QwQ...讲课的时候Halfsummer11一下就秒了这道题呢。
真是太妙了。
考虑。「保证每个点的度数均不超过20」这个重要条件。
我们记
即,我们需要找到的那个节点。
考虑这个东西是具有单峰性的。
所以我们随便取一个点做根。将它与它的所有叶子的进行一个比较。如果比某一个叶子的答案小,就往这个叶子里面走。(可以证明至多只有一个。),否则其就是答案。

我们考虑如何加速定位:
考虑点分治。我们每一次不是往这个叶子里面跳,而是往其所在的子树的重心跳。这样我们用便完成了带权重心的查询。
考虑如何快速支持查询和修改:
1.查询:
2.修改:由于我们进行了树分治。只需要对其分治树上所有的父亲的带权路径和加上一个,点权和加上一个
一个查询两点距离的好姿势,如果不是Halfsummer安利一发,我还真的忘记了这个东西:

每次dfs的时候直接加一条到当前根的询问边。

Recent Posts

comments powered by Disqus