一本大道久久东京热无码AV,亚洲国产一成人久久精品,久久久久亚洲AV无码网站

劃分樹

首先，Orz一下AHdoc神犇，本沙茶是看他的總結才搞懂劃分樹的。
原文地址

劃分樹，就是每個結點代表一個序列，設這個序列的長度為len，若len>1，則序列中前len/2（上取整，這里數學公式不好打，真囧）個元素被分到左子結點，左子結點代表的序列就是這些元素按照根結點中的順序組成的序列，而剩下的元素被分到右子結點，右子結點代表的序列也就是剩下的元素按照根結點中的順序組成的序列；若len=1，則該結點為葉結點。劃分樹最重要的應用就是找區間第K小（只是查找，不包括修改）。

寫劃分樹時主要有兩個函數：建樹和找區間第K小。由于后者AHdoc神犇已經總結了，所以這里只總結建樹的函數。

設目前結點為[l..r]（l<r，就是目前的結點是原序列不斷劃分后得到[l..r]這一段，其實也就是a0[l..r]打亂順序后得到的，a0為原序列遞增排序后的序列）首先找到中值，就是a0[mid]，mid=l+r>>1。然后可以得到，[l..r]中小于中值的的元素一定被劃分到左子結點，[l..r]中大于中值的元素一定被劃分到右子結點，而[l..r]中等于中值的元素則不確定，有的被劃分到左子結點，有的被劃分到右子結點，這就需要先找到應被劃分到左子結點的等于中值的元素個數sm（從mid開始不斷往左，直到找到邊界處或者找到一個小于中值的元素為止，或者說，sm就是a0[l..mid]中等于中值的元素個數），然后開始劃分，小于中值分到左子結點，大于中值分到右子結點，等于中值的，若目前還沒滿sm則分到左子結點否則分到右子結點。另外中間有兩個值需要記錄（找區間第K小時必須要用到）：sl和sr。sl[i]表示[l..i]中被分到左子結點的元素個數，sr[i]表示[l..i]中被分到右子結點的元素個數（這里l<=i<=r。顯然sl[i]+sr[i]=i-l+1，其實sr[i]可以不用記錄的，這里只是為了在找第K小操作中減少計算次數，起到空間換時間的作用）。
建樹代碼：

int mkt(int l, int r, int d)
{
    T[++No].l = l; T[No].r = r; int mid = l + r >> 1; T[No].mid = mid;
    if (l == r) return No;
    int midv = a0[mid], sm = mid - l + 1; rre2(i, mid, l) if (a0[i] < midv) {sm = mid - i; break;}
    int x = l, y = mid + 1;
    if (a[d][l] < midv) {
        a[d + 1][x++] = a[d][l]; sl[d][l] = 1; sr[d][l] = 0;
    } else if (a[d][l] == midv && sm) {
        a[d + 1][x++] = a[d][l]; sl[d][l] = 1; sr[d][l] = 0; sm--;
    } else {
        a[d + 1][y++] = a[d][l]; sl[d][l] = 0; sr[d][l] = 1;
    }
    re3(i, l+1, r) {
        if (a[d][i] < midv) {
            a[d + 1][x++] = a[d][i]; sl[d][i] = sl[d][i - 1] + 1; sr[d][i] = sr[d][i - 1];
        } else if (a[d][i] == midv && sm) {
            a[d + 1][x++] = a[d][i]; sl[d][i] = sl[d][i - 1] + 1; sr[d][i] = sr[d][i - 1]; sm--;
        } else {
            a[d + 1][y++] = a[d][i]; sl[d][i] = sl[d][i - 1]; sr[d][i] = sr[d][i - 1] + 1;
        }
    }
    int No0 = No; T[No0].lch = mkt(l, mid, d + 1); T[No0].rch = mkt(mid + 1, r, d + 1); return No0;
}

這里a是每層劃分后的序列。
查找區間第K小的代碼：

int Find_Kth(int l, int r, int K)
{
    int i = root, d = 0, l0, r0, mid0, s0, s1;
    while (1) {
        l0 = T[i].l, r0 = T[i].r; mid0 = T[i].mid;
        if (l0 == r0) return a[d][l];
        if (l == l0) s0 = l; else s0 = l0 + sl[d][l - 1]; s1 = l0 + sl[d][r] - 1;
        if (K <= s1 - s0 + 1) {
            i = T[i].lch; l = s0; r = s1; d++;
        } else {
            K -= (s1 - s0 + 1); if (l == l0) l = mid0 + 1; else l = mid0 + sr[d][l - 1] + 1;
            r = mid0 + sr[d][r]; i = T[i].rch; d++;
        }
    }
}

【具體題目】PKU2104、PKU2761（兩道任選一道）

posted @ 2011-06-27 20:54 Mato_No1 閱讀(2856) | 評論 (1) | 編輯收藏

Splay Tree處理區間問題的幾道好題及總結

（1）Robotic Sort（HDU1890、ZJU2985）
本題主要考察的是對此類問題，序列中給定值的索引問題。
當Splay Tree用來處理一個序列的時候，其關鍵字就是序列中元素的下標，而不是元素的值。這樣，如果要查找序列中給定的值的位置（假設序列中任意兩個元素的值不相等）看起來就無法實現。其實也是有辦法實現的：因為元素在樹中的下標是永遠不變的！也就是，設這個序列為A，如果A[i]在插入Splay Tree時的下標為j，那么在A[i]被刪除之前，其下標一直是j，永遠不會變（注意元素在序列中的下標和在樹中的下標是不同的）。利用這一性質可以解決給定值的索引問題。
對于本題，每次將從序列中第i小的元素到序列中第i個元素（這里假定元素下標是從1開始的，而不是從0開始）之間的所有元素反轉，并輸出第i小的元素在反轉之前的在序列中的下標。設B[i]為第i小的數的初始位置，S[i]為初始位置在第i位的元素的下標，B[i]和S[i]都可以通過預處理得到。然后，每次交換前，求出S[B[i]]在樹中的排名（基本操作），再減1（因為有邊界結點）就是該元素目前的位置，而序列中第i個元素就是樹中第(i+1)小的元素，再執行交換即可。
不過需要千萬注意的是本題的標記問題，在求S[B[i]]在樹中的排名時，有可能其祖先結點上有標記，需要先遍歷其所有的祖先結點，再逆向下放標記（標記只能自頂向下傳）。另外在交換的時候需要求出S[B[i]]的后繼，在求后繼的過程中需要查找，此時千萬別忘了下放標記（總的說，凡是有查找的地方，就有dm）
代碼（本沙茶太弱了，是抄別人的，因此其算法和上面總結的可能有差別，神犇不要鄙視）

（2）SuperMemo（PKU3580）
本題的6個操作中，add、reverse、insert、delete、min都不難搞，而revolve操作需要涉及到區間交換。
可以發現，所謂的旋轉其實就是交換兩個相鄰區間，這對于功能極強的Splay Tree來說根本不難搞。
設這兩個相鄰區間為[x, y]與[y+1, z]，假設它們均非空（也就是x<=y<z，因為若其中至少有一個區間是空區間，則交換沒有意義），先找到樹中x的前趨P與z的后繼S（這里x、z等指的都是對應的結點，下同），將P伸展到根、將S伸展到根的右子結點處，則S的左子樹就表示區間[x, z]。然后，設S的左子樹的根結點（也就是S的左子結點）為N，在這棵子樹中找到第1小的結點P0與第(y-x+2)小的結點S0（這需要涉及到找子樹內第K小的操作，只要把找整棵樹第K小的操作的root改為N即可），它們分別表示x與(y+1)，這樣將P0伸展到N處，將S0伸展到N的右子結點處，顯然P0無左子樹，S0的左子樹T1表示區間[x+1, y]，S0的右子樹T2表示區間[y+2, z]。然后，先將S0從P0的右子結點移動到P0的左子結點，再將T1作為P0的右子樹（注意移動是兩步：插入和刪除）。這樣整棵子樹的中序遍歷結果變成了S0->T2->P0->T1，也就是[y+1, z]∪[x, y]。
另外本題的標記有點難搞，只需注意rev是逆向標記，以及查找與dm共存就行了。
代碼
（3）Play with Chain(HDU3487)
這個米有神馬好說的，里面的操作在SuperMemo里都有；
代碼
（4）AHOI2006 文本編輯器(editor)
這題在這一類題里面算水的。對于光標，只要用一個值來維護就行了。
另外注意本題極為猥瑣的2點（題目中米有說明）：一是最初的文本并不是空的，而是有一個空格；二是執行GET操作時光標可能位于文本末尾，此時應輸出空格；
代碼
（5）HFTSC2011 高精度計算器(apc)，題目見這個帖子；
這題反映出了一個很囧的問題：有些信息會被rev整體破壞。
本題中的操作都是常見操作，但是本題所需要維護的信息卻不是那么容易維護。本題要求維護一棵子樹中所有結點所表示的元素序列（中序遍歷結果）模一個指定的M的值。設F[i]為R^i mod M的值（這里R是進制，也就是題目中的K），則有：
T[x].mod = (T[T[x].c[0]].mod * F[T[T[x].c[1]].sz + 1] + T[x].v * F[T[T[x].c[1]].sz] + T[T[x].c[1]].mod) % M;
這個式子其實是很好理解的。
關鍵是，本題的猥瑣之處并不在此。注意本題的rev操作，它會整體改變樹中所有結點所記錄的mod值，這時，如果再用上面這個式子來維護T[x].mod，就會出錯，因為此時引用到的T[T[x].c[0]].mod和T[T[x].c[1]].mod都是過時的。解決這一問題只有一種方法：記錄“逆mod”(rmod)，意思是將整個元素序列反轉后的mod，即：
T[x].rmod = (T[T[x].c[1]].rmod * F[T[T[x].c[0]].sz + 1] + T[x].v * F[T[T[x].c[0]].sz] + T[T[x].c[0]].rmod) % M;
這樣，在反轉某序列的時候，直接將根結點的mod值和rmod值交換就行了。
像mod這樣會被反轉操作整體破壞的信息還有很多，比如NOI2005 sequence里面的lmax和rmax。如果真的遇到這類信息，只有采用上面的方法。
另外，本題第6、9、10個點有誤。
代碼

現在Splay Tree差不多弄完了，接下來還有N多知名的、不知名的高級數據結構……時間MS有些不夠用了囧……

posted @ 2011-06-25 11:21 Mato_No1 閱讀(5067) | 評論 (2) | 編輯收藏

平衡樹調試技巧

平衡樹操作，尤其是Splay Tree的區間操作（當線段樹用的那種），代碼長且極易搞疵，當操作多的時候，甚至可能調試的時間比寫代碼的時間都長！
這里來總結一下平衡樹在實際應用（編程）中的易疵點和調試技巧。
【平衡樹（這里主要指Splay Tree）的操作】
這個MS前面已經總結過了，主要分以下幾類：
（1）基本操作：查找、單結點插入、單結點刪除、找第K小、求結點的排名、找指定結點的前趨和后繼；
（2）進階操作：找給定的值在樹中的前趨和后繼、對一個序列建平衡樹、插入整棵子樹、刪除整棵子樹；
（3）區間操作（與線段樹的結合）：標記（自頂向下）；
（4）區間操作（與線段樹的結合）：最大值、總和等自底向上維護的信息；
（5）一些特別猥瑣的操作（比如PKU3580的revolve）；
【主要函數及其易疵點】
（1）void sc(int _p, int _c, bool _d);
將_p的_d子結點（0左1右）置為_c，這個就三句話，應該不會搞疵；
（2）void upd(int x);
更新x記錄的一些信息（自底向上維護的信息，包括大小域sz），這個，有幾個信息就寫幾句話就行了，不易搞疵；
（3）void rot(int x);
旋轉操作，將x旋轉到其父結點的位置。這個函數中有兩個易疵點：一是若x的父結點為根，則需要在旋轉后將根置為x，且將x的父結點置為0（特別注意這個）；二是若x的父結點不為根，則需要將x的父結點的父結點的對應子結點（原來是x的父結點的那個）置為x；另外旋轉完成后別忘了更新；
（4）void splay(int x, int r);
伸展操作，將x伸展到r的子結點處，這個操作是最核心的操作，只要記住了過程，且rot不搞疵，這個也就不會搞疵；
（5）void dm(int x);
對于有標記的結點的下放標記操作，極易疵！
首先，對于任何結點，標記一打上就必須立即生效，因此除了將x的標記取消、x的兩個子結點（如果存在的話）打上標記外，還要更新兩個子結點的一些域（當然這里更新千萬不能用upd更新）；
其次，要搞清楚x的每一個標記的類型，是疊加型標記（如整體加上某一個數的標記）、覆蓋型標記（如整體置為某一個數的標記）還是逆向標記（如是否翻轉過的標記，因為翻轉兩次等于沒轉），然后在下放標記的時候注意寫法（因為x的子結點原來可能也有標記，此時只有覆蓋型標記需要將x的子結點的原來的標記覆蓋掉，對于疊加型標記，應為加法運算，對于逆向標記，應為取反操作，還有其它類型的標記分別處理）；
最后還有一點，就是x的左子結點或右子結點可能不存在（0），此時就不能對這里的0號結點下放標記。
（6）int Find_Kth(int x, int K);
在以結點x為根的子樹中找第K小的結點，返回結點編號；若省略x，默認x=root（即在整棵樹中找）；
這個一般不會搞疵，注意兩個地方即可：一是有mul域的時候需要考慮mul域，二是結點如果有標記，需要在找的時候下放標記。（凡是查找操作，包括插入新結點時的查找，在查找過程中必須不斷下放標記，因為查找之后很可能就要伸展）；
（7）void ins(int _v);
void ins(int x, int _v)
插入一個值為_v的結點。前者是普通插入，后者是用Splay Tree處理序列（當線段樹用）時的插入，表示在第x小的結點后插入；
前者注意有三種情況：樹為空；樹非空且值為_v的結點不存在；樹非空且值為_v的結點已存在；
后者需要注意，在將第x小的結點伸展到根，將第(x+1)小的結點伸展到根的右子結點，再插入后，需要upd上述兩個結點（注意upd順序）；
（8）void del(int x);
將結點x刪除。這個一般不會搞疵，唯一要注意的一點是刪除后的upd；
（9）打標記操作（add、reverse、makesame等）：
其實打標記操作的代碼量是很少的，關鍵就是對于不同標記要分別處理，同（5）；
（10）各種詢問操作：
這個直接調出相應的域即可，幾乎不可能搞疵；
（11）極其猥瑣的操作（revolve等）：
這個屬于最易疵的操作（否則就體現不出其猥瑣了）：
首先要搞清楚這個操作的具體過程，不要連具體過程都搞疵了，這樣寫出來的代碼肯定是疵的；
然后，注意一些非常猥瑣的細節問題（很多時候，本沙茶都是栽在細節上的）；
另外，這些操作中一般都會出現多次伸展，別忘了伸展后的upd；
（12）其它易疵點：
[1]“移動”是由“插入”和“刪除”兩部分組成的，因此凡是涉及到“移動”類的操作（如將某棵子樹或某個結點移動到另一個位置等），必須要同時出現“插入”和“刪除”，而不能只插入不刪除；
[2]注意檢查主函數main()中是否有搞疵的地方；

易疵點也就這么多了，下面是調試技巧：
【Splay Tree調試技巧】
（1）先用樣例調試，保證樣例能夠通過（注意，樣例中必須包含所有題目中給出的操作，如果不是這樣，那在調試完樣例后還要加一組包含所有題目中給出的操作的小數據）；
（2）然后用mkdt造大數據，一般平衡樹操作題的合法數據都不難造，只要注意別越界就行了；
（3）在調試過程中應不斷少量增大數據規模，因為在能找出問題的情況下，數據規模越小越好；
（4）如果調試過程中發現死循環或者RE：
[1]首先輸出每個操作，找出是在哪個操作處出了問題；
[2]進入該操作內部檢查，也就是把該操作的代碼讀一遍，一般都能找出問題；
[3]如果找不出問題，可以進入該操作內部跟蹤檢查；
[4]如果跟蹤檢查仍然沒找出問題，那可能是該操作是對的，而其它操作出了問題，此時可以弄一個vst，把整棵樹遍歷一下，找出真正出問題的操作，轉[2]；
（5）排除了死循環或RE后，接下來就是檢查輸出結果是否正確了：
[1]對于小規模數據可人工計算檢查，對于較大規模數據則必須采用對照方法，即弄一個模擬法的代碼，保證該代碼正確，然后進行對照；
[2]如果發現加入遍歷時，結果正確，但去掉遍歷后結果不正確，則表明是處理結點標記的時候出了問題（因為在遍歷過程中需要下放標記），進入dm或加標記操作中檢查即可；
[3]其它情況下，可以在遍歷中輸出整個序列（或整棵樹），進行對照，找出問題所在；
[4]如果數據過大，操作過多，人工分析時間較長，就只能采用讀代碼的方式檢查了；
（6）最后，用mkdt造一個最大規模的數據，檢查是否TLE、是否越界（數組是否開小）；
如果以上各點全部通過，就可以宣布AC了。

posted @ 2011-06-23 00:07 Mato_No1 閱讀(663) | 評論 (2) | 編輯收藏

【NOI2005 維護數列(sequence)】Splay Tree處理序列問題

【原題見這里】
本題是Splay Tree處理序列問題（也就是當線段樹用）的一個典型例題。

Splay Tree之所以可以當線段樹用，是因為它可以支持一個序列，然后用“左端前趨伸展到根，右端后繼伸展到根的右子結點，取根的右子結點的左子結點”這種伸展方法，對一個序列中的一整段進行整體操作。由于要防止出現前趨或后繼不存在的情況，需要在這個序列的兩端加入兩個邊界結點，要求其值不能影響到結點各種記載信息的維護（多取0、∞或-∞）。這兩個邊界結點在樹中永遠存在，不會被刪除。

（1）結點的引用：
在當線段樹用的Splay Tree中，真正的關鍵字是下標而不是值，因此，“序列中第i個結點”實際上對應的是“樹中第(i+1)小的結點”（因為左邊還有一個邊界結點），這就說明在對結點引用時需要找第K小的操作。因此，下面的“結點x”指的是“樹中第(x+1)小的結點”。
（2）標記：
在線段樹中，如果對一個結點所表示的線段整體進行了某種操作，需要在這個結點上打上一個標記，在下一次再找到這個結點時，其標記就會下放到其兩個子結點上。在Splay Tree中也可以引入標記。比如要對[2, 6]這一段進行整體操作，就將結點1伸展到根的位置，將結點7伸展到根的右子樹的位置，然后結點7的左子樹就表示[2, 6]這一段，對這棵子樹的根結點打上標記并立即生效（必須是立即生效，而不是等下一次引用再生效），也就是立即改變該結點記錄的一些信息的值。如果下次再次引用到這個結點，就要將其標記下放到其兩個子結點處；
需要注意的一點是，如果要伸展某個結點x到r的子結點的位置，就必須保證從x原來的位置到r的這個子結點（x伸展后的位置）上的所有結點上均沒有標記，否則就會導致標記混亂。因此，必須首先找到這個結點x，在此過程中不斷下放標記。
（3）自底向上維護的信息：
標記可以看成一種自頂向下維護的信息。除了標記以外，作為“線段樹”，往往還要維護一些自底向上維護的信息。比如在sequence這題中，就有lmax（左段連續最大和）、rmax（右段連續最大和）、midmax（全段連續最大和）以及sum（全段總和）等信息要維護。對于這類東東其實也很好辦，因為子樹大小（sz域）就是一種自底向上維護的信息，因此對于這些信息只要按照維護sz域的辦法維護即可（統一寫在upd函數里）。唯一的不同點是打標記時它們的值可能要改變。
（4）對連續插入的結點建樹：
本題的插入不是一個一個插入，而是一下子插入一整段，因此需要先將它們建成一棵樹。一般建樹操作都是遞歸的，這里也一樣。設目前要對A[l..r]建樹（A為待插入序列），若l>r則退出，否則找到位于中間的元素mid = l + r >> 1，將A[mid]作根，再對A[l..mid-1]建左子樹，對A[mid+1..r]建右子樹即可。這樣可以保證一開始建的就是一棵平衡樹，減小常數因子。
（5）回收空間：
根據本題的數據范圍提示，插入的結點總數最多可能達到4000000，但在任何時刻樹中最多只有500002個結點（包括兩個邊界），此時為了節省空間，可以采用循環隊列回收空間的方法。即：一開始將所有的可用空間（可用下標，本題為1~500002）存在循環隊列Q里，同時設立頭尾指針front和rear，每次如果有新結點插入，就取出Q[front]并作為新結點的下標，如果有結點要刪除（本題是一次刪除整棵子樹，因此在刪除后需要分別回收它們的空間），則從rear開始，將每個刪除的結點的下標放回到Q里。當然，這種方法是要犧牲一定的時間的，因此在空間不是特別吃緊的情況下不要用。

【2012年1月16日更新】
今天重寫sequence的時候，禿然發現加入的邊界點可能會對lmax、rmax、midmax等的維護造成影響：當序列中所有的值都是負數時，若邊界點的值設為0，將使這3個值也為0，所以，邊界點的值應設為-INF（不會影響到sum，因為可以單獨調出[l, r]的sum，避開邊界）。這就說明并非所有這樣的題中都可以設置邊界點（比如HFTSC2011的那題就不行），如果邊界點會對維護的信息造成影響，就不能設置邊界點，在各個操作中，分4種情況判斷。（代碼已經修改）

下面上代碼了：

#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
const int MAXN = 500002, NOSM = -2000, INF = ~0U >> 2;
struct node {
    int v, c[2], p, sz, sum, lmax, rmax, midmax, sm;
    bool rev, d;
} T[MAXN + 1];
int root, Q[MAXN + 1], front, rear, a[MAXN], len, res;
int max(int SS0, int SS1)
{
    return SS0 >= SS1 ? SS0 : SS1;
}
int max(int SS0, int SS1, int SS2)
{
    int M0 = SS0 >= SS1 ? SS0 : SS1; return M0 >= SS2 ? M0 : SS2;
}
void newnode(int n, int _v)
{
    T[n].v = T[n].sum = T[n].lmax = T[n].rmax = T[n].midmax = _v; T[n].c[0] = T[n].c[1] = 0; T[n].sz = 1; T[n].sm = NOSM; T[n].rev = 0;
}
void sc(int _p, int _c, bool _d)
{
    T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
void sm_opr(int x, int SM)
{
    T[x].sum = T[x].sz * SM;
    if (SM > 0) T[x].lmax = T[x].rmax = T[x].midmax = T[x].sum; else T[x].lmax = T[x].rmax = T[x].midmax = SM;
}
void rev_opr(int x)
{
    int c0 = T[x].c[0], c1 = T[x].c[1]; sc(x, c0, 1); sc(x, c1, 0);
    int tmp = T[x].lmax; T[x].lmax = T[x].rmax; T[x].rmax = tmp;
}
void dm(int x)
{
    int SM0 = T[x].sm;
    if (SM0 != NOSM) {
        T[x].v = T[T[x].c[0]].sm = T[T[x].c[1]].sm = SM0; T[x].sm = NOSM;
        sm_opr(T[x].c[0], SM0); sm_opr(T[x].c[1], SM0);
    }
    if (T[x].rev) {
        T[T[x].c[0]].rev = !T[T[x].c[0]].rev; T[T[x].c[1]].rev = !T[T[x].c[1]].rev; T[x].rev = 0;
        rev_opr(T[x].c[0]); rev_opr(T[x].c[1]);
    }
}
void upd(int x)
{
    int c0 = T[x].c[0], c1 = T[x].c[1];
    T[x].sz = T[c0].sz + T[c1].sz + 1;
    T[x].sum = T[c0].sum + T[c1].sum + T[x].v;
    T[x].lmax = max(T[c0].lmax, T[c0].sum + T[x].v + max(T[c1].lmax, 0));
    T[x].rmax = max(T[c1].rmax, max(T[c0].rmax, 0) + T[x].v + T[c1].sum);
    T[x].midmax = max(T[c0].midmax, T[c1].midmax, max(T[c0].rmax, 0) + T[x].v + max(T[c1].lmax, 0));
}
void rot(int x)
{
    int y = T[x].p; bool d = T[x].d;
    if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
    sc(y, T[x].c[!d], d); sc(x, y, !d); upd(y);
}
void splay(int x, int r)
{
    int p; while ((p = T[x].p) != r) if (T[p].p == r) rot(x); else if (T[x].d == T[p].d) {rot(p); rot(x);} else {rot(x); rot(x);} upd(x);
}
int Find_Kth(int K)
{
    int i = root, S0;
    while (i) {
        dm(i); S0 = T[T[i].c[0]].sz + 1;
        if (K == S0) break; else if (K < S0) i = T[i].c[0]; else {K -= S0; i = T[i].c[1];}
    }
    return i;
}
int mkt(int l, int r)
{
    if (l > r) return 0;
    int n0 = Q[front], mid = l + r >> 1; if (front == MAXN) front = 1; else front++;
    newnode(n0, a[mid]); int l_r = mkt(l, mid - 1), r_r = mkt(mid + 1, r);
    sc(n0, l_r, 0); sc(n0, r_r, 1); upd(n0); return n0;
}
void ins(int pos)
{
    int P0 = Find_Kth(pos); splay(P0, 0); int P1 = Find_Kth(pos + 1); splay(P1, root); sc(P1, mkt(0, len - 1), 0); upd(P1); upd(P0);
}
void era(int x)
{
    if (!x) return;
    if (rear == MAXN) rear = 1; else rear++; Q[rear] = x;
    era(T[x].c[0]); era(T[x].c[1]);
}
void del(int l, int r)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root);
    int root0 = T[P1].c[0]; sc(P1, 0, 0); upd(P1); upd(P0); era(root0);
}
void mksame(int l, int r, int x)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root);
    int n = T[P1].c[0]; T[n].sm = x; sm_opr(n, x); upd(P1); upd(P0);
}
void reve(int l, int r)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root);
    int n = T[P1].c[0]; T[n].rev = !T[n].rev; rev_opr(n); upd(P1); upd(P0);
}
int get_sum(int l, int r)
{
    int P0 = Find_Kth(l - 1); splay(P0, 0); int P1 = Find_Kth(r + 1); splay(P1, root);
    int n = T[P1].c[0]; return T[n].sum;
}
int max_sum()
{
    return T[root].midmax;
}
void prepare()
{
    T[0].sz = T[0].sum = T[0].lmax = T[0].rmax = T[0].midmax = 0;
    front = 3; rear = MAXN; re1(i, MAXN) Q[i] = i;
    newnode(1, -INF); newnode(2, -INF); sc(1, 2, 1); root = 1; T[root].p = 0;
}
int main()
{
    freopen("sequence.in", "r", stdin);
    freopen("sequence.out", "w", stdout);
    prepare();
    int m, l, r, x;
    scanf("%d%d", &len, &m); char ch = getchar(), str[1000];
    re(i, len) scanf("%d", &a[i]); ins(1);
    re(i, m) {
        scanf("%s", str);
        if (!strcmp(str, "INSERT")) {scanf("%d%d", &l, &len); re(i, len) scanf("%d", &a[i]); ins(++l);}
        if (!strcmp(str, "DELETE")) {scanf("%d%d", &l, &r); r += l++; del(l, r);}
        if (!strcmp(str, "MAKE-SAME")) {scanf("%d%d%d", &l, &r, &x); r += l++; mksame(l, r, x);}
        if (!strcmp(str, "REVERSE")) {scanf("%d%d", &l, &r); r += l++; reve(l, r);}
        if (!strcmp(str, "GET-SUM")) {scanf("%d%d", &l, &r); r += l++; printf("%d\n", get_sum(l, r));}
        if (!strcmp(str, "MAX-SUM")) printf("%d\n", max_sum());
        ch = getchar();
    }
    fclose(stdin); fclose(stdout);
    return 0;
}

最后把我的這個代碼與BYVoid神犇的本題代碼進行測試比較，結果（BYVoid神犇的代碼見這里）：

BYVoid神犇的：

本沙茶的：

【相關論文】
運用伸展樹解決數列維護問題 by JZP
【感謝】
JZP神犇（提供論文）
BYVoid神犇（提供標程）

posted @ 2011-06-21 16:06 Mato_No1 閱讀(2125) | 評論 (0) | 編輯收藏

Splay Tree 重復次數mul以及一些進階操作

額……最近兩天光顧著刷題忘了總結了……正好現在把總結的東東全部補上吧囧……

【重復次數mul】
在前面第一篇總結Splay Tree的時候就提到了結點的重復次數(mul)域，這個東東至今在網上還米看見有犇用（在本沙茶見過的范圍內），但是不可否認的是這個域在某些情況下幾乎是“必須使用”的。
所謂重復次數，就是將樹中所有值(v)相同的結點全部合并成一個，這些結點的總個數就是合并后的結點的mul值。比如，在一棵空樹中插入3個值為5的結點后，在使用mul域的情況下，樹中只有一個結點，其v值為5，mul值為3。
在平衡樹中，值相同的結點確實非常礙事。按照二叉查找樹的定義：“要么是一棵空樹，要么是一棵滿足以下條件的非空樹：根結點左子樹中所有結點的值均小于根結點，根結點右子樹中所有結點的值均大于根結點，且根的左右子樹均為二叉查找樹”，在二叉查找樹中，是不應該出現值相同的結點的。可是在實際問題中，出現值相同的結點幾乎是不可避免的。此時，樹的定義就會變得非常模糊，也就是要把二叉查找樹定義中的“小于”全部改為“小于等于”，“大于”全部改為“大于等于”。這樣定義的樹在一般情況下也米有神馬問題，但是在找前趨(Pred)和找后繼(Succ)操作中，問題就來了。因為根結點的前趨和后繼的值可能與根結點相等（比如 HNOI2004 寵物收養所那一題），這時，根結點的前趨既有可能在左子樹里，也有可能在右子樹里，根結點的后繼也一樣。此時，這兩個操作就無法進行了。
【mul域的維護】
mul域其實可以看成結點的一個本身屬性，和v一樣。因此在旋轉、伸展操作中任何結點的mul值都是不會改變的。可能改變結點mul值的地方只有兩處：一是插入，二是刪除。在插入一個值為_v的結點的時候，如果發現值為_v的結點在樹中已經存在，則只會將這個結點的mul值加1，而不是真正插入一個新的結點。同樣的，在刪除一個結點的時候，如果這個結點的mul值大于1，則只會將這個結點的mul值減1，而不是真正刪除。
【mul域的作用】
mul域最主要的作用就是解決值相同的結點對于某些操作的影響。另外，mul域的引入可以減少樹中結點的總個數（尤其是當插入的結點數很多而結點的值的范圍不大的時候），從而降低時間復雜度（準確來說可以降低常數）。
【Splay Tree的進階操作】
<1>找非根結點的前趨和后繼。
Splay Tree由于有伸展操作，可以將要求前趨或后繼的點伸展到根再求前趨或后繼。如果要不通過伸展操作找一個非根結點的前趨或后繼怎么辦？
設這個結點為x。如果x有左子結點，則x的前趨就是x的左子結點的右鏈上的最后一個結點；如果x沒有左子結點，則x的前趨就是從x開始往上（往x的祖先）查找，直到找到第一個是其父結點的右子結點的結點為止，則這個結點的父結點就是x的前趨（或者說，就是不斷沿著x的父結點往上找，一開始都是往右的，找到第一個往左的就行了）。后繼則正好相反。證明可以用中序遍歷。
<2>找某個值v0的前趨和后繼（值為v0的結點在樹中不一定存在）。
所謂v0的前趨和后繼，就是指在樹中值小于（也有的是不大于）v0的最大的結點的值，和樹中值大于（也有的是不小于）v0的最小的結點的值。在有了操作（1）【不通過伸展操作找非根結點的前趨和后繼】以后，這個操作變得極為容易：先進行普通的查找操作（查找值為v0的結點），如果能找到，則剩下的步驟就和操作（1）一樣了；如果找不到，則必然是找到某個空結點（0）處，假設在這里插入一個值為v0的結點（只是假設，不是真插入），則該結點顯然是沒有左子結點的，因此就是“從該結點開始往上查找，直到找到第一個是其父結點的右子結點的結點為止，則這個結點的父結點就是該結點的前趨”，也就是v0的前趨；后繼類似。
在查找過程中可以進行一個常數優化：設點i為查找過程中“右轉”的最后一個結點（即找到該結點后，接下來是該結點的右子結點），每次往右子結點轉的時候就更新i，則最后結點i就是值v0的前趨；后繼類似。
<3>刪除所有值在某區間內的結點（這個區間可以是開區間、閉區間或半開半閉區間）。
以開區間為例：刪除樹中所有值在(l, r)范圍內的結點。先找到l的前趨P和r的后繼S（注意這里的前趨和后繼是包括“等于”的），然后將P伸展到根，S伸展到P的右子結點處，則S的左子樹中就是所有值在(l, r)范圍內的結點，直接刪掉這棵子樹即可（注意刪除后要更新S和P）；若改為閉區間，則將前趨和后繼中的“等于”去掉（即必須是小于或大于）；半開半閉區間則一半按開區間處理，一半按閉區間處理。問題是，如果點P或點S不存在怎么辦。有兩種解決辦法，一是若P和S之一存在，則將其伸展到根，然后直接刪掉其左子樹或右子樹即可；若P和S都不存在，則樹為空，直接將root置為0即可；二是按照sequence的辦法，加入兩個邊界結點，當前趨或后繼不存在時就認為是邊界結點。
其實不光是刪除，在找到了這棵子樹后可以對它進行一些整體操作，從而讓Splay Tree具有線段樹的功能（這個在下面的NOI2005 sequence那一題里面會總結）。
<4>插入一棵樹（當然這棵樹也是Splay Tree，并且原樹中的結點值序列與新樹中的結點值序列不相交）。
有時候，題目中會連續出現很多插入操作，中間沒有其它操作，此時，與其一個一個插入，還不如將它們先建成一棵樹（建樹的方法在下一篇里總結），再整體插入。整體插入的方法：設L和R分別是新樹里值最小的結點和值最大的結點，在原樹中找到L的前趨P和R的后繼S，將P伸展到根，S伸展到P的右子結點處，由于原樹中的結點值序列與新樹中的結點值序列不相交（也就是原樹中的結點值要么小于L的值，要么大于R的值），因此S無左子結點，此時將新樹作為S的左子樹即可。

posted @ 2011-06-21 11:31 Mato_No1 閱讀(758) | 評論 (0) | 編輯收藏

終于摘掉了不會平衡樹的帽子

摘要: 今天真是有紀念意義啊……以前試著捉了N遍的cashier今天竟然AC了，本沙茶終于掌握了平衡樹！！！【Splay Tree及其實現】<1>結點記錄的信息：一般情況下Splay Tree是用線性存儲器（結構數組）來存儲的，可以避免在Linux下的指針異常問題。這樣對于某個結點，至少要記錄以下的域：值（又叫關鍵字）、左子結點的下標、右子結點的下標、父結點下標、子樹大... 閱讀全文

posted @ 2011-06-18 21:21 Mato_No1 閱讀(1074) | 評論 (0) | 編輯收藏

次小生成樹

給出一個帶邊權的無向圖G，設其最小生成樹為T，求出圖G的與T不完全相同的邊權和最小的生成樹（即G的次小生成樹）。一個無向圖的兩棵生成樹不完全相同，當且僅當這兩棵樹中至少有一條邊不同。注意，圖G可能不連通，可能有平行邊，但一定沒有自環（其實對于自環也很好處理：直接舍棄。因為生成樹中不可能出現自環）。
【具體題目】URAL1416（注意，這一題的邊數M的范圍沒有給出，視為124750）
【分析】
定義生成樹T的一個可行變換(-E1, +E2)：將T中的邊E1刪除后，再加入邊E2（滿足邊E2原來不在T中但在G中），若得到的仍然是圖G的一棵生成樹，則該變換為可行變換，該可行變換的代價為(E2權值 - E1權值)。這樣，很容易證明，G的次小生成樹就是由G的最小生成樹經過一個代價最小的可行變換得到。進一步可以發現，這個代價最小的可行變換中加入的邊E2的兩端點如果為V1和V2，那么E1一定是原來最小生成樹中從V1到V2的路徑上的權值最大的邊。

這樣，對于本題就有兩種算法了：（以下的T全部指G的最小生成樹）
（1）Prim：
設立數組F，F[x][y]表示T中從x到y路徑上的最大邊的權值。F數組可以在用Prim算法求最小生成樹的過程中得出。每次將邊(i, j)加入后（j是新加入樹的邊，i=c[j]），枚舉樹中原有的每個點k（包括i，但不包括j），則F[k][j]=max{F[k][i], (i, j)邊權值}，又由于F數組是對稱的，可以得到F[j][k]=F[k][j]。然后千萬記住將圖G中的邊(i, j)刪除（就是將鄰接矩陣中(i, j)邊權值改為∞）！因為T中的邊是不能被加入的。等T被求出后，所有的F值也求出了，然后，枚舉點i、j，若鄰接矩陣中邊(i, j)權值不是無窮大（這說明i、j間存在不在T中的邊），則求出{(i, j)邊權值 - F[i][j]}的值，即為加入邊(i, j)的代價，求最小的總代價即可。
另外注意三種特殊情況：【1】圖G不連通，此時最小生成樹和次小生成樹均不存在。判定方法：在擴展T的過程中找不到新的可以加入的邊；【2】圖G本身就是一棵樹，此時最小生成樹存在（就是G本身）但次小生成樹不存在。判定方法：在成功求出T后，發現鄰接矩陣中的值全部是無窮大；【3】圖G存在平行邊。這種情況最麻煩，因為這時代價最小的可行變換(-E1, +E2)中，E1和E2可能是平行邊！因此，只有建立兩個鄰接矩陣，分別存儲每兩點間權值最小的邊和權值次小的邊的權值，然后，每當一條新邊(i, j)加入時，不是將鄰接矩陣中邊(i, j)權值改為無窮大，而是改為連接點i、j的權值次小的邊的權值。

代碼：

#include <iostream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 7000, INF = ~0U >> 2;
int n, s[MAXN][MAXN], s2[MAXN][MAXN], f[MAXN][MAXN], c[MAXN], v[MAXN], res1 = 0, res2 = 0;
bool vst[MAXN];
void init()
{
    freopen("mst.in", "r", stdin);
    scanf("%d", &n);
    re(i, n) re(j, n) s[i][j] = s2[i][j] = INF;
    int m, a, b, len;
    scanf("%d", &m);
    if (!m) {
        if (n > 1) res1 = -INF; res2 = -INF;
        return;
    }
    re(i, m) {
        scanf("%d%d%d", &a, &b, &len); a--; b--;
        if (len < s[a][b]) {s2[a][b] = s2[b][a] = s[a][b]; s[a][b] = s[b][a] = len;} else if (len < s2[a][b]) s2[a][b] = s2[b][a] = len;
    }
    fclose(stdin);
}
void solve()
{
    re(i, n) {f[i][i] = c[i] = vst[i] = 0; v[i] = s[0][i];} vst[0] = 1;
    int l0, l1 = INF, x, y, z;
    re2(i, 1, n) {
        l0 = INF; re(j, n) if (!vst[j] && v[j] < l0) {l0 = v[j]; x = j; y = c[j];}
        if (l0 == INF) {res1 = res2 = -INF; return;}
        vst[x] = 1; res1 += l0; s[x][y] = s[y][x] = INF; if (s2[x][y] < INF && s2[x][y] - l0 < l1) l1 = s2[x][y] - l0;
        re(j, n) if (!vst[j] && s[x][j] < v[j]) {v[j] = s[x][j]; c[j] = x;}
        re(j, n) if (vst[j] && j != x) f[j][x] = f[x][j] = max(f[j][y], l0);
    }
    re(i, n-1) re2(j, i+1, n) if (s[i][j] < INF) {
        z = s[i][j] - f[i][j];
        if (z < l1) l1 = z;
    }
    if (l1 == INF) res2 = -INF; else res2 = res1 + l1;
}
void pri()
{
    freopen("mst.out", "w", stdout);
    printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
    fclose(stdout);
}
int main()
{
    init();
    if (!res2) solve();
    pri();
    return 0;
}

效率分析：Prim算法求次小生成樹的時空復雜度均為O(N²)。

（2）Kruskal：
Kruskal算法也可以用來求次小生成樹。在準備加入一條新邊(a, b)（該邊加入后不會出現環）時，選擇原來a所在連通塊（設為S1）與b所在連通塊（設為S2）中，點的個數少的那個（如果隨便選一個，最壞情況下可能每次都碰到點數多的那個，時間復雜度可能增至O(NM)），找到該連通塊中的每個點i，并遍歷所有與i相關聯的邊，若發現某條邊的另一端點j在未選擇的那個連通塊中（也就是該邊(i, j)跨越了S1和S2）時，就說明最終在T中"刪除邊(a, b)并加入該邊"一定是一個可行變換，且由于加邊是按照權值遞增順序的，(a, b)也一定是T中從i到j路徑上權值最大的邊，故這個可行變換可能成為代價最小的可行變換，計算其代價為[(i, j)邊權值 - (a, b)邊權值]，取最小代價即可。注意，在遍歷時需要排除一條邊，就是(a, b)本身（具體實現時由于用DL邊表，可以將邊(a, b)的編號代入）。另外還有一個難搞的地方：如何快速找出某連通塊內的所有點？方法：由于使用并查集，連通塊是用樹的方式存儲的，可以直接建一棵樹（準確來說是一個森林），用“最左子結點+相鄰結點”表示，則找出樹根后遍歷這棵樹就行了，另外注意在合并連通塊時也要同時合并樹。
對于三種特殊情況：【1】圖G不連通。判定方法：遍歷完所有的邊后，實際加入T的邊數小于(N-1)；【2】圖G本身就是一棵樹。判定方法：找不到這樣的邊(i, j)；【3】圖G存在平行邊。這個對于Kruskal來說完全可以無視，因為Kruskal中兩條邊只要編號不同就視為不同的邊。
其實Kruskal算法求次小生成樹還有一個優化：每次找到邊(i, j)后，一處理完這條邊就把它從圖中刪掉，因為當S1和S2合并后，(i, j)就永遠不可能再是可行變換中的E2了。

代碼：

#include <iostream>
#include <stdlib.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
const int MAXN = 7000, MAXM = 130000, INF = ~0U >> 2;
struct edge {
    int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge2 {
    int a, b, len, No;
} ed2[MAXM];
int n, m = 0, m2, u[MAXN], ch[MAXN], nx[MAXN], q[MAXN], res1 = 0, res2 = INF;
void init_d()
{
    re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
    if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int l)
{
    ed[m].a = a; ed[m].b = b; ed[m].len = l; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a = b; ed[m].b = a; ed[m].len = l; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
    ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
    ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
    freopen("mst.in", "r", stdin);
    scanf("%d%d", &n, &m2);
    if (!m2) {
        if (n > 1) res1 = -INF;
        res2 = -INF; return;
    }
    init_d();
    int a, b, len;
    re(i, m2) {
        scanf("%d%d%d", &a, &b, &len);
        ed2[i].No = m; add_edge(--a, --b, len);
        ed2[i].a = a; ed2[i].b = b; ed2[i].len = len;
    }
    fclose(stdin);
}
int cmp(const void *s1, const void *s2)
{
    return ((edge2 *)s1)->len - ((edge2 *)s2)->len;
}
void prepare()
{
    re(i, n) u[i] = ch[i] = nx[i] = -1;
    qsort(ed2, m2, 16, cmp);
}
int find(int x)
{
    int r = x, r0 = x, tmp;
    while (u[r] >= 0) r = u[r];
    while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
    return r;
}
void uni(int r1, int r2, int No, int l0)
{
    q[0] = r1;
    int j, k, l1, front, rear;
    for (front=0, rear=0; front<=rear; front++) {
        j = ch[q[front]];
        while (j != -1) {
            q[++rear] = j;
            j = nx[j];
        }
    }
    re3(i, 0, rear) {
        j = q[i];
        for (int p=ed[j].next; p != j; p=ed[p].next) {
            k = ed[p].b;
            if (p != No && find(k) == r2) {
                l1 = ed[p].len - l0;
                if (l1 < res2) res2 = l1;
                del_edge(p);
            }
        }
    }
    u[r2] += u[r1]; u[r1] = r2; nx[r1] = ch[r2]; ch[r2] = r1;
}
void solve()
{
    int r1, r2, l0, num = 0;
    re(i, m2) {
        r1 = find(ed2[i].a); r2 = find(ed2[i].b);
        if (r1 != r2) {
            l0 = ed2[i].len; res1 += l0; num++;
            if (u[r1] >= u[r2]) uni(r1, r2, ed2[i].No, l0); else uni(r2, r1, ed2[i].No ^ 1, l0);
        }
    }
    if (num < n - 1) {res1 = res2 = -INF; return;}
    if (res2 == INF) res2 = -INF; else res2 += res1;
}
void pri()
{
    freopen("mst.out", "w", stdout);
    printf("Cost: %d\nCost: %d\n", res1 == -INF ? -1 : res1, res2 == -INF ? -1 : res2);
    fclose(stdout);
}
int main()
{
    init();
    if (!res1 && res2 == INF) {
        prepare();
        solve();
    }
    pri();
    return 0;
}

效率分析：可以證明，如果每次都選取點少的連通塊，Kruskal算法求次小生成樹的時間復雜度為O(M*(logN+logM))，空間復雜度為O(M)。
總結：顯然Prim適用于稠密圖，而Kruskal適用于稀疏圖。

下面是對于一些數據的測試結果（數據說明：第1~9個點和第15個點為稠密圖或一般圖，第10~14個點為稀疏圖）

Prim：

Kruskal（加入刪邊優化）：

Kruskal（未加刪邊優化）：

posted @ 2011-05-29 16:03 Mato_No1 閱讀(6773) | 評論 (5) | 編輯收藏

最小度限制生成樹

給出一個帶邊權連通無向圖，當中指定一個點V0，要求這個圖的一個生成樹，使得樹中V0點的度數（和V0點關聯的邊數）剛好為一個指定值P，求滿足此條件的邊權和最小的生成樹。

【算法】（某神犇的論文里有詳細證明，這里省略了囧……）
設l[i]為連接圖中點V0與點i之間的邊的長度（若有多條邊取權值最小的，若沒有邊則為無窮大）。
（1）在圖中刪除點V0，新的圖不一定是連通圖，設其有B個連通塊；
（2）若P<B則無解，否則轉下一步；
（3）對這B個連通塊分別求最小生成樹，得到一個生成森林。然后在圖中重新加入點V0，對每個連通塊，找出該連通塊內l值最小的點V'，添加邊(V0, V')，這樣就得到了一棵初始的生成樹，或者說，這是V0點度數為B的最小的生成樹；
（4）然后就是不斷往里面加入與V0相關聯的邊。從V0點開始，對整棵生成樹BFS遍歷，對每個點i，找到目前的生成樹中從V0到i的路徑上權值最大的邊，設E_len[i]為這條邊的權值，E_No[i]為這條邊的編號（由于本沙茶使用的是DL邊表，故記錄編號），這個東東的求法很容易，省略；
（5）最后，枚舉除V0點外的每個點，找到(E_len[i]-l[i])值最大的點i，然后在圖中刪除邊E_No[i]，加入邊(V0, i)，這樣得到的仍然是原圖的生成樹，且V0的度數增加1；
（6）重復以上過程(P-B)次即得結果。

【實現注意】
為了編程實現更加方便，注意以下幾點：
（1）一開始不加入V0，而不是加入了再刪去（但各點l值要在輸入時求出）；
（2）一開始不用先求出B的值，而是先求出最小生成森林（用Kruskal，不斷加邊，直到加到不能再加為止）和初始生成樹，再遍歷初始生成樹得到B值；
（3）由于涉及刪邊，一定要用DL邊表。

【代碼】（PKU1639，注意這題是求V0度數不超過給定值P的最小生成樹，簡單改裝即可）：

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
const int MAXN = 30, MAXM = 5000, MAXLEN = 20, INF = ~0U >> 2;
struct edge {
    int a, b, len, pre, next;
} ed[MAXM + MAXM];
struct edge0 {
    int a, b, len;
} ed0[MAXM];
int n, m, m0 = 0, P, B = 0, l[MAXN], u[MAXN], B_No[MAXN], q[MAXN], E_No[MAXN], E_len[MAXN], res = 0;
string NAMELIST[MAXN];
bool vst[MAXN];
void add_edge0(int a, int b, int len)
{
    ed0[m0].a = a; ed0[m0].b = b; ed0[m0++].len = len;
}
void init_d()
{
    re(i, n) ed[i].a = ed[i].pre = ed[i].next = i;
    if (n % 2) m = n + 1; else m = n;
}
void add_edge(int a, int b, int len)
{
    ed[m].a = a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
    ed[m].a = b; ed[m].b = a; ed[m].len = len; ed[m].pre = ed[b].pre; ed[m].next = b; ed[b].pre = m; ed[ed[m].pre].next = m++;
}
void del_edge(int No)
{
    ed[ed[No].pre].next = ed[No].next; ed[ed[No].next].pre = ed[No].pre;
    ed[ed[No ^ 1].pre].next = ed[No ^ 1].next; ed[ed[No ^ 1].next].pre = ed[No ^ 1].pre;
}
void init()
{
    n = 1; NAMELIST[0] = "Park"; int m_;
    scanf("%d", &m_); char ch = getchar(), s01[MAXLEN], s02[MAXLEN]; int No1, No2, l0, tmp;
    re(i, MAXN) l[i] = INF;
    re(i, m_) {
        scanf("%s %s %d", s01, s02, &l0); ch = getchar();
        No1 = -1; re(j, n) if (NAMELIST[j] == s01) {No1 = j; break;} if (No1 == -1) NAMELIST[No1 = n++] = s01;
        No2 = -1; re(j, n) if (NAMELIST[j] == s02) {No2 = j; break;} if (No2 == -1) NAMELIST[No2 = n++] = s02;
        if (No1 > No2) {tmp = No1; No1 = No2; No2 = tmp;}
        if (No1) add_edge0(No1, No2, l0); else if (l0 < l[No2]) l[No2] = l0;
    }
    scanf("%d", &P);
}
int cmp(const void *s1, const void *s2)
{
    return ((edge0 *)s1)->len - ((edge0 *)s2)->len;
}
int find_root(int x)
{
    int r = x, r0 = x, tmp;
    while (u[r] >= 0) r = u[r];
    while (u[r0] >= 0) {tmp = u[r0]; u[r0] = r; r0 = tmp;}
    return r;
}
void uni(int r1, int r2)
{
    int sum = u[r1] + u[r2];
    if (u[r1] >= u[r2]) {u[r1] = r2; u[r2] = sum;} else {u[r2] = r1; u[r1] = sum;}
}
void prepare()
{
    qsort(ed0, m0, 12, cmp);
    re2(i, 1, n) u[i] = -1; init_d();
    int x1, x2, l0, r1, r2;
    re(i, m0) {
        x1 = ed0[i].a; x2 = ed0[i].b; l0 = ed0[i].len; r1 = find_root(x1); r2 = find_root(x2);
        if (r1 != r2) {uni(r1, r2); add_edge(x1, x2, l0); res += l0;}
    }
    re2(i, 1, n) B_No[i] = -1;
    int Best, Best_No;
    re2(i, 1, n) if (B_No[i] == -1) {
        B_No[i] = B; Best = l[i]; Best_No = q[0] = i;
        int j, k;
        for (int front=0, rear=0; front<=rear; front++) {
            j = q[front];
            for (int p=ed[j].next; p != j; p=ed[p].next) {
                k = ed[p].b;
                if (B_No[k] == -1) {
                    B_No[k] = B; q[++rear] = k; if (l[k] < Best) {Best = l[k]; Best_No = k;}
                }
            }
        }
        add_edge(0, Best_No, Best); res += Best; B++;
    }
}
void solve()
{
    vst[0] = 1;
    re2(P0, B, P) {
        re2(i, 1, n) {E_len[i] = INF; vst[i] = 0;} q[0] = 0;
        int i, j, l0;
        for (int front=0, rear=0; front<=rear; front++) {
            i = q[front];
            for (int p=ed[i].next; p != i; p=ed[p].next) {
                j = ed[p].b; l0 = ed[p].len;
                if (!vst[j]) {
                    vst[j] = 1; q[++rear] = j;
                    if (E_len[i] > l0) {E_len[j] = E_len[i]; E_No[j] = E_No[i];} else {E_len[j] = l0; E_No[j] = p;}
                }
            }
        }
        int Best = 0, Best_No, Best_v;
        re2(i, 1, n) {
            l0 = E_len[i] - l[i];
            if (l0 > Best) {Best = l0; Best_No = E_No[i]; Best_v = i;};
        }
        if (Best) {del_edge(Best_No); add_edge(0, Best_v, l[Best_v]); res -= Best;} else break;
    }
}
void pri()
{
    printf("Total miles driven: %d\n", res);
}
int main()
{
    init();
    prepare();
    solve();
    pri();
    return 0;
}

posted @ 2011-05-23 21:05 Mato_No1 閱讀(590) | 評論 (0) | 編輯收藏

最近捉的一些圖論題

摘要: 【1】PKU1094思考難度不大，就是不斷在有向圖中加邊，求加了幾條邊以后，圖中出現一條連接N個點的簡單路徑（就是一條長度為(N-1)的鏈），或者圖中出現環。判定連接N個點的簡單路徑的算法：拓撲排序，若每次隊列中有且只有一個入度為0的點，則這樣的路徑存在，所排出的順序就是結果。注意兩點：（1）如果在前面的若干條邊加入后，已經找到了解，那么就輸出解，結束（不管后面的邊了，即使后面的邊加入后形成環也無... 閱讀全文

posted @ 2011-05-22 11:09 Mato_No1 閱讀(426) | 評論 (0) | 編輯收藏

Topcoder注冊成功

經GYZ、CLJ神牛指點，在N次Error后終于注冊成功了……

Topcoder與NOI的規則區別：
【1】Topcoder的代碼不是一個完整的代碼（連main()都米有），而只是一個類，類里面只有一個方法（相當于main()）。不用輸入、輸出，系統會將輸入數據直接傳遞到這個方法的參數里，在方法執行完后將返回值直接傳遞到輸出里。類名、方法名、輸入參數類型、輸出結果類型是在原題中規定的（但參數名、輸出結果名可以自定義）。代碼中可以（也必須）使用C++ STL。
【2】捉題的時候，題目描述下面的編碼區里可以直接編代碼，編好后點下面的Compile編譯，再點Test測試（可以測試樣例和自己的數據），測試完畢后，點Submit提交。所以，不必向其它OJ一樣在IDE里編好再Ctrl+ACV提交。
其它的可以參照網上其他人寫的東東。

本沙茶先在里面捉了幾題（全是水題，神犇不要鄙視），代碼：

SRM 506 DIV1 250：

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define debug(x) cout << #x << " = " << x << endl;
#define pb push_back
#define re_t(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define MP make_pair
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
const int MAXN = 175000, INF = ~0U >> 2;
class MathContest {
    public:
    int countBlack(string s0, int p)
    {
        string s = "";
        bool a[MAXN];
        re(i, p) s += s0;
        int n = s.length(), res = 0;
        re(i, n) a[i] = s[i] == 'B';
        int i = 0, j = s.length() - 1;
        bool reversed = 0, turned = 0, v;
        while (i <= j) {
            if (reversed) {
                v = a[j--];
                if (turned) v = !v;
            } else {
                v = a[i++];
                if (turned) v = !v;
            }
            if (v) {res++; turned = !turned;} else reversed = !reversed;
        }
        return res;
    }
};

SRM 506 DIV2 250：

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define debug(x) cout << #x << " = " << x << endl;
#define pb push_back
#define re_t(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define MP make_pair
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
const int MAXN = 10000, INF = ~0U >> 2;
class SlimeXSlimeRancher2 {
    public:
    int train(vector <int> a)
    {
        int n = a.size(), m = -INF, res = 0;
        re(i, n) m = max(m, a[i]);
        re(i, n) res += m - a[i];
        return res;
    }
};

SRM 506 DIV2 500：

#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <iomanip>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
#define debug(x) cout << #x << " = " << x << endl;
#define pb push_back
#define re_t(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)
#define all(x) x.begin(),x.end()
#define SORT(x) sort(all(x))
#define MP make_pair
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vi::iterator vit;
typedef set<int> si;
typedef si::iterator sit;
typedef map<int,int> mii;
typedef mii::iterator mit;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef istringstream ISS;
typedef ostringstream OSS;
const int MAXN = 10000, INF = ~0U >> 2;
class SlimeXSlimesCity {
    public:
    int merge(vector <int> a)
    {
        int n = a.size();
        SORT(a);
        ll s = 0, s1;
        int res = 0;
        bool ff;
        re(i, n) {
            s += a[i]; s1 = s; ff = 1;
            re2(j, i + 1, n) {
                if (s1 < a[j]) {ff = 0; break;}
                s1 += a[j];
            }
            res += ff;
        }
        return res;
    }
};

posted @ 2011-05-15 12:20 Mato_No1 閱讀(1362) | 評論 (6) | 編輯收藏

僅列出標題

Mato is No.1

留言簿(21)

隨筆分類

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

劃分樹