數(shù)據(jù)結(jié)構(gòu)題目選講

數(shù)據(jù)結(jié)構(gòu)題目選講江蘇省淮陰中學(xué)張坤有哪些數(shù)據(jù)結(jié)構(gòu)？數(shù)組棧隊(duì)列鏈表樹堆有哪些高級(jí)數(shù)據(jù)結(jié)構(gòu)？哈希表優(yōu)先隊(duì)列與二叉堆并查集線段樹樹狀數(shù)組平衡樹塊狀鏈表后綴數(shù)組樹鏈剖分和動(dòng)態(tài)樹……有哪些NOIP會(huì)考的高級(jí)數(shù)據(jù)結(jié)構(gòu)？哈希表優(yōu)先隊(duì)列與二叉堆并查集線段樹樹狀數(shù)組平衡樹塊狀鏈表后綴數(shù)組樹鏈剖分和動(dòng)態(tài)樹……題目選講例題零NOIP2012借教室在大學(xué)期間，經(jīng)常需要租借教室。大到院系舉辦活動(dòng)，小到學(xué)習(xí)小組自習(xí)討論，都需要向?qū)W校申請(qǐng)借教室。教室的大小功能不同，借教室人的身份不同，借教室的手續(xù)也不一樣。面對(duì)海量租借教室的信息，我們自然希望編程解決這個(gè)問題。我們需要處理接下來n天的借教室信息，其中第i天學(xué)校有ri個(gè)教室可供租借。共有m份訂單，每份訂單用三個(gè)正整數(shù)描述，分別為dj,sj,tj，表示某租借者需要從第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj個(gè)教室。例題零NOIP2012借教室我們假定，租借者對(duì)教室的大小、地點(diǎn)沒有要求。即對(duì)于每份訂單，我們只需要每天提供dj個(gè)教室，而它們具體是哪些教室，每天是否是相同的教室則不用考慮。借教室的原則是先到先得，也就是說我們要按照訂單的先后順序依次為每份訂單分配教室。如果在分配的過程中遇到一份訂單無法完全滿足，則需要停止教室的分配，通知當(dāng)前申請(qǐng)人修改訂單。這里的無法滿足指從第sj天到第tj天中有至少一天剩余的教室數(shù)量不足dj個(gè)?，F(xiàn)在我們需要知道，是否會(huì)有訂單無法完全滿足。如果有，需要通知哪一個(gè)申請(qǐng)人修改訂單。例題零NOIP2012借教室輸入文件為classroom.in。第一行包含兩個(gè)正整數(shù)n,m，表示天數(shù)和訂單的數(shù)量。第二行包含n個(gè)正整數(shù)，其中第i個(gè)數(shù)為ri，表示第i天可用于租借的教室數(shù)量。接下來有m行，每行包含三個(gè)正整數(shù)dj,sj,tj，表示租借的數(shù)量，租借開始、結(jié)束分別在第幾天。每行相鄰的兩個(gè)數(shù)之間均用一個(gè)空格隔開。天數(shù)與訂單均用從1開始的整數(shù)編號(hào)。例題零NOIP2012借教室輸出文件為classroom.out。如果所有訂單均可滿足，則輸出只有一行，包含一個(gè)整數(shù)0。否則（訂單無法完全滿足）輸出兩行，第一行輸出一個(gè)負(fù)整數(shù)-1，第二行輸出需要修改訂單的申請(qǐng)人編號(hào)。例題零NOIP2012借教室輸入432543213324424輸出-12對(duì)于10%的數(shù)據(jù)，有1≤n,m≤10；對(duì)于30%的數(shù)據(jù)，有1≤n,m≤1000；對(duì)于70%的數(shù)據(jù)，有1≤n,m≤10^5；對(duì)于100%的數(shù)據(jù)，有1≤n,m≤10^6,0≤ri,dj≤10^9,1≤sj≤tj≤n。例題零NOIP2012借教室此題就是一個(gè)線段樹裸題，但100萬的數(shù)據(jù)比較大。線段樹的做法？例題零NOIP2012借教室此題就是一個(gè)線段樹裸題，但100萬的數(shù)據(jù)比較大，線段樹也許會(huì)承受不了。而最終結(jié)果表明，由于鑒于CCF的評(píng)測(cè)機(jī)，線段樹只能拿到90，所以，我們不得不另尋他法。例題零NOIP2012借教室這道題的數(shù)據(jù)范圍比較大，因此必須要考慮對(duì)數(shù)級(jí)及一下的算法。本題的實(shí)質(zhì)是找到第一組不能滿足要求的申請(qǐng)，因此可以考慮用二分法。設(shè)初始左端點(diǎn)為1，右端點(diǎn)為n，在二分的過程中，每次判斷的是從第一組申請(qǐng)到當(dāng)前區(qū)間中點(diǎn)這一組申請(qǐng)是否全部都能被滿足。如果這一段申請(qǐng)都能滿足，則左端點(diǎn)下移否則右端點(diǎn)上移。最后得到的長度為1的區(qū)間就是答案。另外，可能要特判一下答案是n的情況。（根據(jù)程序?qū)懛ú煌瑳Q定是否需要特判……）例題零NOIP2012借教室

在判斷申請(qǐng)的時(shí)候，需要使用差分?jǐn)?shù)組來計(jì)算申請(qǐng)的數(shù)量。差分?jǐn)?shù)組用于記錄原數(shù)值數(shù)組中相鄰兩個(gè)數(shù)的差值。（以下為與前面的數(shù)的差值）。在對(duì)于從l到r的數(shù)值為num的操作中，將l的數(shù)值增加num，r+1的數(shù)值減少num即可。最后對(duì)差分?jǐn)?shù)組求前綴和即可得到每天教室的數(shù)量。差分?jǐn)?shù)組的sumi對(duì)應(yīng)原數(shù)組第i個(gè)元素的數(shù)值。例題的啟示數(shù)據(jù)結(jié)構(gòu)題的解法往往不止一種。往往我們可以使用時(shí)間分治優(yōu)化一維，減少編程復(fù)雜度和常數(shù)。例題一NOI2001食物鏈

動(dòng)物王國中有三類動(dòng)物A,B,C，這三類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B，B吃C，C吃A?，F(xiàn)有N個(gè)動(dòng)物，以1－N編號(hào)。每個(gè)動(dòng)物都是A,B,C中的一種，但是我們并不知道它到底是哪一種。有人用兩種說法對(duì)這N個(gè)動(dòng)物所構(gòu)成的食物鏈關(guān)系進(jìn)行描述：第一種說法是“1XY”，表示X和Y是同類。第二種說法是“2XY”，表示X吃Y。例題一NOI2001食物鏈此人對(duì)N個(gè)動(dòng)物，用上述兩種說法，一句接一句地說出K句話，這K句話有的是真的，有的是假的。當(dāng)一句話滿足下列三條之一時(shí)，這句話就是假話，否則就是真話。1）當(dāng)前的話與前面的某些真的話沖突，就是假話；2）當(dāng)前的話中X或Y比N大，就是假話；3）當(dāng)前的話表示X吃X，就是假話。你的任務(wù)是根據(jù)給定的N（1<=N<=50,000）和K句話（0<=K<=100,000），輸出假話的總數(shù)。輸入格式第一行是兩個(gè)整數(shù)N和K，以一個(gè)空格分隔。以下K行每行是三個(gè)正整數(shù)D，X，Y，兩數(shù)之間用一個(gè)空格隔開，其中D表示說法的種類。若D=1，則表示X和Y是同類。若D=2，則表示X吃Y。輸出格式只有一個(gè)整數(shù)，表示假話的數(shù)目。樣例輸入100711011212223233113231155樣例輸出3例題一NOI2001食物鏈自由討論如果

動(dòng)物王國中只有兩類動(dòng)物A,B，這兩類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B，B吃A……如果

動(dòng)物王國中只有兩類動(dòng)物A,B，這兩類動(dòng)物的食物鏈構(gòu)成了有趣的環(huán)形。A吃B，B吃A……這是一個(gè)二分圖那么是不是可以對(duì)這些動(dòng)物進(jìn)行染色，令顏色相同的為一類。但當(dāng)你遇到一個(gè)沒有染過色的動(dòng)物，你需要給它染什么顏色呢？而且這好像是圖論的內(nèi)容與數(shù)據(jù)結(jié)構(gòu)選講無關(guān)一些想法如果A吃B，B吃C，C吃D，……F→E→D→C→B→A那么A和D是同類，他們也是捕食關(guān)系，矛盾？同類的意義F→E→D→C→B→AA和D的距離為3模3意義下相等啟發(fā)圖可以變?yōu)闃潢P(guān)系可以用距離表示，模3意義下加加減減想到了什么并查集！具體步驟用father[n],path[n]數(shù)組分別記錄當(dāng)前結(jié)點(diǎn)的祖先和到祖先的距離。這里規(guī)定距離為0時(shí)為同類，為1時(shí)表示被祖先吃，為2時(shí)表示吃祖先。初始時(shí)每個(gè)元素的祖先是自己，距離為0。

對(duì)于每一句話，首先判斷是x,y是否大于n，是否出現(xiàn)自己吃自己的情況，滿足時(shí)討論如下兩種情況：如果d=1，表示讀入的x和y是同類，這時(shí)分別找到x,y和祖先fx,fy，如果fx=fy，說明他們是同一祖先。這時(shí)判斷x和y到祖先的距離是否相等，顯然，不相等證明這是一句假話。如果fx<>fy，說明x和y不在同一集合中，此時(shí)將這兩個(gè)集合合并。合并時(shí)可以通過一個(gè)簡(jiǎn)單的向量關(guān)系算出fx->fy的距離，即path[fx]=path[y]-path[x].

對(duì)于每一句話，首先判斷是x,y是否大于n，是否出現(xiàn)自己吃自己的情況，滿足時(shí)討論如下兩種情況：如果d=2，表示x吃y，同樣的找到它們的祖先，若fx=fy，則根據(jù)向量關(guān)系判斷它們的距離是否矛盾，即檢查path[x]-path[y]-2是否為0。若fx<>fy，則類似地根據(jù)已有的向量關(guān)系算出fx->fy的距離，即path[fx]=path[y]-path[x]+2.注意的地方是，因?yàn)閜ath在運(yùn)算過程可能出現(xiàn)負(fù)數(shù)，為避免這一情況且保證path的性質(zhì)，可以在每次對(duì)path運(yùn)算后加三再對(duì)三取模。int

Fa[maxn],Dis[maxn];int

Find(intx){

if(x==Fa[x])returnx;

inty=Find(Fa[x]);

Dis[x]+=Dis[Fa[x]];returnFa[x]=y;}例題二InputOutputSampleInputSampleOutput12例題二自由討論一些想法共三維x,y,cc很小對(duì)c暴力處理，好像可以接受一些想法如何對(duì)某個(gè)顏色快速維護(hù)子矩陣中該顏色的數(shù)量可選擇的數(shù)據(jù)結(jié)構(gòu)四分樹二維線段樹二維樹狀數(shù)組各種數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢(shì)和劣勢(shì)兼顧編程復(fù)雜度和運(yùn)行效率例題三Input輸入共兩行，第一行為一個(gè)整數(shù)N，N表示物品的個(gè)數(shù)，1<=N<=100000。第二行為N個(gè)用空格隔開的正整數(shù)，表示N個(gè)物品最初排列的編號(hào)。Output輸出共一行，N個(gè)用空格隔開的正整數(shù)P1,P2,P3…Pn，Pi表示第i次操作前第i小的物品所在的位置。注意：如果第i次操作前，第i小的物品己經(jīng)在正確的位置Pi上，我們將區(qū)間[Pi,Pi]反轉(zhuǎn)(單個(gè)物品)。SampleInput6345162SampleOutput464566自由討論要求支持區(qū)間最小值查詢，區(qū)間翻轉(zhuǎn)的數(shù)據(jù)結(jié)構(gòu)如果沒有翻轉(zhuǎn)……支持翻轉(zhuǎn)的數(shù)據(jù)結(jié)構(gòu)塊狀鏈表——時(shí)間效率√n平衡樹做法無與倫比的splay和spaly歡迎用作模版題Picks博士觀察完金星凌日后，設(shè)計(jì)了一個(gè)復(fù)雜的電阻器。為了簡(jiǎn)化題目，題目中的常數(shù)與現(xiàn)實(shí)世界有所不同。這個(gè)電阻器內(nèi)有編號(hào)為1～n的n個(gè)獨(dú)立水箱，水箱呈圓柱形，底面積為1m2，每個(gè)水箱在頂部和底部各有一個(gè)閥門，可以讓水以1m3/s的流量通過，每個(gè)水箱的上閥門接水龍頭，可以無限供應(yīng)水，下閥門不接?xùn)|西，可以讓水流出。水箱頂部和底部都有一個(gè)接口，水的電阻率為1Ω?m。水箱的高度足夠高，有一個(gè)導(dǎo)電浮標(biāo)浮在水面上，通過導(dǎo)線與水箱頂?shù)慕涌谙噙B。一開始時(shí)第ii個(gè)水箱中有aim3的水。例題四Picks博士接下來就需要對(duì)這個(gè)復(fù)雜的電阻器進(jìn)行調(diào)試。他會(huì)進(jìn)行以下五種操作。1、打開編號(hào)在[l,r]中的所有水箱的上方閥門x秒，然后關(guān)上它們的上方閥門。2、打開編號(hào)在[l,r]中的所有水箱的下方閥門x秒，然后關(guān)上它們的下方閥門。3、將編號(hào)在[l,r]中的所有水箱的下方閥門與大海通過連通器以一定方式相連，使得這些水箱中都恰擁有xm3的水，然后關(guān)上它們的下方閥門，撤去連通器。4、在第y個(gè)水箱的上下方接口處接上一個(gè)電動(dòng)勢(shì)為1V的電源，電源沒有內(nèi)阻，Picks博士會(huì)測(cè)量出通過電源的電流大小，之后撤去該電源。5、由于水浸泡過的地方會(huì)留下明顯的水漬而沒有被水浸泡過的地方不會(huì)有，Picks博士可以據(jù)此測(cè)量出此時(shí)第y個(gè)水箱的水漬高度，以推斷曾經(jīng)最多有多少水，節(jié)約他的建造成本?，F(xiàn)在，他請(qǐng)你來幫他做預(yù)實(shí)驗(yàn)，你能告訴他每次測(cè)量得到的電流大小以及測(cè)量得到的最多的水量是多少嗎？例題四輸入格式第一行兩個(gè)數(shù)：n,m。接下來一行n個(gè)數(shù)，第i個(gè)數(shù)表示初始時(shí)第i個(gè)水箱內(nèi)有aim3的水。接下來m行中，第i行第一個(gè)數(shù)ti表示操作類型：若ti=1，則接下來三個(gè)整數(shù)li,ri,xi表示打開編號(hào)在[li,ri]中的所有水箱的上方接口xi秒。若ti=2，則接下來三個(gè)整數(shù)li,ri,xi表示打開編號(hào)在[li,ri]中的所有水箱的下方接口xi秒。若ti=3，則接下來三個(gè)整數(shù)li,ri,xi表示將編號(hào)在[li,ri]中的所有水箱與大海連接，使這些水箱中都恰有xim3的水。若ti=4，則接下來一個(gè)整數(shù)yi，表示測(cè)量在第yi個(gè)水箱的上下方接口處接上一個(gè)電動(dòng)勢(shì)為1V的電源時(shí)通過電源的電流。若ti=5，則接下來一個(gè)整數(shù)yi，表示測(cè)量此時(shí)在第yi個(gè)水箱中的水漬高度。輸出格式對(duì)于每個(gè)ti=4，輸出一個(gè)整數(shù)表示通過電源的電流大小的倒數(shù)（單位為A?1），如果電流為無窮大則輸出0。對(duì)于每個(gè)ti=5，輸出一個(gè)整數(shù)表示在第yi個(gè)水箱中的水漬高度（單位為m）。樣例輸入一5612345213241114153315442樣例輸出一034自由討論一些想法操作三可以被操作一和操作二取代如何做題目要義請(qǐng)你寫一個(gè)數(shù)據(jù)結(jié)構(gòu)支持以下功能：1：區(qū)間[l,r]加x2：區(qū)間[l,r]減x并和0取max3：區(qū)間值修改為x4：?jiǎn)吸c(diǎn)詢問5：?jiǎn)吸c(diǎn)歷史最大值詢問如何拿到部分分做法線段樹維護(hù)分段函數(shù)標(biāo)記就是一個(gè)二元組(a,b)表示標(biāo)記生效后x=max(x+a,b)1操作就是打(x,0)的標(biāo)記2就是(-x,0)3就是(-inf,v)做法標(biāo)記是滿足結(jié)合律和封閉性的然后兩個(gè)標(biāo)記怎么合并呢？g(f(x))=max(x+max(fa+ga,-inf),max(fb+ga,gb))（打f標(biāo)記的時(shí)間在前，打g標(biāo)記在后）中間和-inf取max是為了不使多個(gè)-inf加爆了做法對(duì)于歷史最大值，我們要記錄的是歷史最大標(biāo)記而不是直接在每個(gè)點(diǎn)記錄歷史最大值為什么是這樣的？假設(shè)我們進(jìn)行一次區(qū)間賦為inf的操作，接著有全部賦為0，標(biāo)記還沒來得及下傳更新歷史最大值就被后一個(gè)標(biāo)記cha了所以每個(gè)點(diǎn)記錄歷史最大值是錯(cuò)的更簡(jiǎn)單的做法……再觀察題目請(qǐng)你寫一個(gè)數(shù)據(jù)結(jié)構(gòu)支持以下功能：1：區(qū)間[l,r]加x2：區(qū)間[l,r]減x并和0取max3：區(qū)間值修改為x4：?jiǎn)吸c(diǎn)詢問5：?jiǎn)吸c(diǎn)歷史最大值詢問再觀察題目如何簡(jiǎn)化操作函數(shù)？再觀察題目如何簡(jiǎn)化操作函數(shù)？用一個(gè)數(shù)組序列表示。再觀察題目請(qǐng)你寫一個(gè)數(shù)據(jù)結(jié)構(gòu)支持以下功能：1：區(qū)間[l,r]加x表示為+x2：區(qū)間[l,r]減x并和0取max表示為-x3：區(qū)間值修改為x表示為-inf+x舉例5612345213241114153315442對(duì)于第3位而言3-2+1-inf+4性質(zhì)？性質(zhì)目前的水位是包含右端點(diǎn)的和最大的一個(gè)子序列歷史最高的水位是和最大的一個(gè)子序列證明？性質(zhì)目前的水位是包含右端點(diǎn)的和最大的一個(gè)子序列歷史最高的水位是和最大的一個(gè)子序列線段樹維護(hù)即可。問題描述:一個(gè)無向樹的度數(shù)為2的結(jié)點(diǎn)稱為假結(jié)點(diǎn)，其它結(jié)點(diǎn)稱為真結(jié)點(diǎn)。一個(gè)無向樹的簡(jiǎn)化樹其結(jié)點(diǎn)由原樹的全體真結(jié)點(diǎn)組成，兩個(gè)真結(jié)點(diǎn)之間有邊當(dāng)且僅當(dāng)它們?cè)谠瓨渲杏羞?，或者在原樹中有一條聯(lián)結(jié)這兩個(gè)結(jié)點(diǎn)的路，其中間節(jié)點(diǎn)全是假結(jié)點(diǎn)。兩個(gè)無向樹各自的簡(jiǎn)化樹如果同構(gòu)，即存在結(jié)點(diǎn)之間的一一對(duì)應(yīng)，使得在一個(gè)樹中的任意兩個(gè)結(jié)點(diǎn)之間有邊當(dāng)且僅當(dāng)它們的對(duì)應(yīng)結(jié)點(diǎn)在另一個(gè)樹中有邊，則稱原來的兩個(gè)無向樹實(shí)質(zhì)同構(gòu)。給定若干個(gè)無向樹，將相互實(shí)質(zhì)同構(gòu)的無向樹只保留一個(gè)其余刪除。統(tǒng)計(jì)剩下的相互不實(shí)質(zhì)同構(gòu)的無向樹個(gè)數(shù)，并將它們的簡(jiǎn)化樹結(jié)點(diǎn)個(gè)數(shù)從小到大輸出。例題五輸入格式:第一行只有一個(gè)正整數(shù)m,后面依次輸入m個(gè)無向樹，每個(gè)無向樹先用一行輸入結(jié)點(diǎn)個(gè)數(shù)n，結(jié)點(diǎn)就用1到n表示，然后用n-1行輸入n-1條無向邊，每行有兩個(gè)1到n之間的不同的正整數(shù)，用一個(gè)空格隔開，代表這兩個(gè)結(jié)點(diǎn)之間有無向邊。兩個(gè)樹之間無空行。輸出格式:

第一行輸出一個(gè)正整數(shù)，即輸入中不計(jì)實(shí)質(zhì)同構(gòu)包含無向樹的個(gè)數(shù)m0(1<=m0<=m)。第二行包含不嚴(yán)格遞增的m0個(gè)正整數(shù)，表示這m0個(gè)無向樹的簡(jiǎn)化樹結(jié)點(diǎn)個(gè)數(shù)。相鄰兩數(shù)用一個(gè)空格隔開。例題五樣例輸入24142434513233445樣例輸出14例題五30%的數(shù)據(jù)滿足2<=m<=10，2<=n<=1060%的數(shù)據(jù)滿足：2<=