信息學(xué)-集訓(xùn)隊(duì)作業(yè)

中國(guó)國(guó)家集訓(xùn)隊(duì)難題活海南省海南中學(xué)【題目大意】列滿足：M個(gè)子集中，每個(gè)子集的元素在排列中連續(xù)出現(xiàn)。【解決情況】【算法梗概】【正文】于任意數(shù)aka1a0，它是五位數(shù)的充要條件是aka40，可以由此直接構(gòu)造出這種思想同樣可在本問(wèn)題中得到應(yīng)用，關(guān)鍵是數(shù)據(jù)結(jié)構(gòu)。其實(shí)，題目所給構(gòu)（NM的矩陣）已經(jīng)可以表示出問(wèn)題的解集，但是在這種數(shù)據(jù)結(jié)構(gòu)下的查找時(shí)間是 9 9 然而如果再加上{5,6}4、5連續(xù)，5、6也連續(xù)，有規(guī)定它們的特定順序，所以單一的無(wú)序樹(shù)結(jié)構(gòu)在這里就 有有有有依次處理每個(gè)連續(xù)集合S，要使S中的元素連續(xù)，無(wú)非是在原來(lái)的樹(shù)上進(jìn)行修改，限制部分節(jié)點(diǎn)的順序，但同時(shí)，這種修改出原來(lái)的樹(shù)的含義（即后一棵樹(shù)對(duì)應(yīng)的具有至少兩個(gè)非零集的樹(shù)T為止。TL的修改，TR可根據(jù)對(duì)稱性得到。LTLSLTLS 若TL是有序樹(shù)，其子節(jié)點(diǎn)順序必須是“零集樹(shù)…半集樹(shù)—全集樹(shù)…”或“全集樹(shù)對(duì)TL的半集進(jìn)行同樣的處理。但樹(shù)的結(jié)構(gòu)并沒(méi)有改變，還需要對(duì)TL進(jìn)行本質(zhì)上的修改。深的一棵半集TD開(kāi)始考慮。TD是最深的半集，因此它沒(méi)有半集。子節(jié)點(diǎn)u、v，分別作為所有零集和所有全集的父親，并令u、v為無(wú)序節(jié)點(diǎn)，TD變?yōu)橛行驑?shù)。：Ti進(jìn)行調(diào)整Ti+1的子節(jié)點(diǎn)加入Ti。由Ti+1經(jīng)過(guò)調(diào)整成為有序樹(shù)，其到Ti+1的位置，：對(duì)TR進(jìn)行類似處理，得到子節(jié)點(diǎn)形如“全集樹(shù)…零集樹(shù)…”的有序樹(shù)。若T是無(wú)序樹(shù)，為了使T的全集出現(xiàn)在TL和TR之間而又不過(guò)多限制這些全集的順序，給T增加一個(gè)子節(jié)點(diǎn)u，作為這些全集的父親，并令u為無(wú)序節(jié)點(diǎn)。合并TL、u、TR三個(gè)節(jié)點(diǎn)，以使S中的元素最終連續(xù)。PQPQ樹(shù)可以在實(shí)現(xiàn)時(shí)，可以用附加節(jié)點(diǎn)屬性的二叉樹(shù)來(lái)表示PQ樹(shù)。在第1、2步中，所有的節(jié)點(diǎn)的都只被O(1)次；第3、4步中，由于使用的是鏈?zhǔn)浇Y(jié)構(gòu)，可以記下把出度為1的節(jié)點(diǎn)去掉，并在其父子節(jié)點(diǎn)之間連一條線。這并不影響樹(shù)的含義，因d(v)E

12

N

縱觀此題的解題過(guò)程，發(fā)現(xiàn)：對(duì)解集進(jìn)行等價(jià)轉(zhuǎn)化的思想是關(guān)鍵，PQ樹(shù)則是解集的一種