1、CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D雜題選講紹興市第一中學(xué)2014 年 3 月 28 日CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DGhd 11Source: Codeforces Round #213 (Div. 1) Problem D數(shù)據(jù)范圍1 n 106 , 1 ai 1012。題目大意給出 n 個數(shù) ai ，求一個最大的 g ，使其能整除至少一半的數(shù)。CF364DCF392DCF392E

2、historyCF398CCF380DCF232ECF396EarchitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。枚舉約數(shù)后計算能整除的個數(shù)，設(shè)約數(shù)個數(shù)為 d ，則復(fù)雜度為 O(nd) 。如何優(yōu)化？標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earc

3、hitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。枚舉約數(shù)后計算能整除的個數(shù)，設(shè)約數(shù)個數(shù)為 d ，則復(fù)雜度為 O(nd) 。如何優(yōu)化？先預(yù)處理出所有約數(shù)，然后把 ai 按約數(shù)中。(ai, ar) 統(tǒng)計到各個標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。枚舉約數(shù)后計算能整除的個數(shù)，設(shè)約數(shù)個數(shù)為 d ，則復(fù)雜度為 O(nd) 。如何優(yōu)化？先預(yù)處理出所有約數(shù)，然后

4、把 ai 按約數(shù)中。(ai, ar) 統(tǒng)計到各個最后從小到大枚舉所有約數(shù)，從它的倍數(shù)中累加，就能得到 被該約數(shù)整除的數(shù)的個數(shù)。復(fù)雜度 O(n log ar + d2) 。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。枚舉約數(shù)后計算能整除的個數(shù)，設(shè)約數(shù)個數(shù)為 d ，則復(fù)雜度為 O(nd) 。如何優(yōu)化？先預(yù)處理出所有約數(shù)，然后把 ai 按約數(shù)中。(ai, ar) 統(tǒng)計到各個最后從小到大枚舉所有約數(shù)，從它的倍數(shù)中累加，就能得

5、到被該約數(shù)整除的數(shù)的個數(shù)。復(fù)雜度 O(n log ar + d2) 。因為 g 要整除至少一半的數(shù)，所以隨機選一個數(shù)被 g 整除11的概率為，即錯誤概率。22標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。枚舉約數(shù)后計算能整除的個數(shù)，設(shè)約數(shù)個數(shù)為 d ，則復(fù)雜度為 O(nd) 。如何優(yōu)化？先預(yù)處理出所有約數(shù)，然后把 ai 按約數(shù)中。(ai, ar) 統(tǒng)計到各個最后從小到大枚舉所有約數(shù)，從它的倍數(shù)中累加，就能得到被該約數(shù)整

6、除的數(shù)的個數(shù)。復(fù)雜度 O(n log ar + d2) 。因為 g 要整除至少一半的數(shù)，所以隨機選一個數(shù)被 g 整除11的概率為，即錯誤概率。22隨機選 k 個數(shù)，錯誤的概率就會降到。 12k標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D設(shè) g 為最終，假設(shè)我們已知 ar 被 g 整除，那么就在 ar 的約數(shù)中。枚舉約數(shù)后計算能整除的個數(shù)，設(shè)約數(shù)個數(shù)為 d ，則復(fù)雜度為 O(nd) 。如何優(yōu)化？先預(yù)處理出所有約數(shù)，然后把 ai 按約數(shù)中。(ai, ar) 統(tǒng)計到各個最后從小到大枚舉所有約數(shù)，從

7、它的倍數(shù)中累加，就能得到被該約數(shù)整除的數(shù)的個數(shù)。復(fù)雜度 O(n log ar + d2) 。因為 g 要整除至少一半的數(shù)，所以隨機選一個數(shù)被 g 整除11的概率為，即錯誤概率。22隨機選 k 個數(shù)，錯誤的概率就會降到。 12k【時間復(fù)雜度】O(k(n log ar + d2)。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DThree Arrays 22Source: Codeforces Round #230 (Div. 1) Problem D數(shù)據(jù)范圍1 n 105 , 1 ai, bi,

8、ci 109。題目大意有三個長度均為 n 的數(shù)組，找出三個數(shù) u, v, w ，使 a, b, c 中所有數(shù)的并集與 a 中前 u 個， b 中前 v 個， c 中前 w 個數(shù)的并集相等。最小化 u + v + w 。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D為方便處理，把 a, b, c 均補全為所有數(shù)的并集（把缺少的部分加到數(shù)組末尾，即 n+1 處）。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF39

9、8D為方便處理，把 a, b, c 均補全為所有數(shù)的并集（把缺少的部分加到數(shù)組末尾，即 n+1 處）。所有數(shù)在 a, b, c 中最早出現(xiàn)的位置。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D為方便處理，把 a, b, c 均補全為所有數(shù)的并集（把缺少的部分加到數(shù)組末尾，即 n+1 處）。所有數(shù)在 a, b, c 中最早出現(xiàn)的位置。初始 u 設(shè)為最大，隨著 u 的減小，一些數(shù)需要出現(xiàn)在 b 或 c 數(shù)組中，而且這樣的數(shù)越來越多。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF39

10、8CCF380DCF232ECF396EarchitectREMOVECF398D為方便處理，把 a, b, c 均補全為所有數(shù)的并集（把缺少的部分加到數(shù)組末尾，即 n+1 處）。所有數(shù)在 a, b, c 中最早出現(xiàn)的位置。初始 u 設(shè)為最大，隨著 u 的減小，一些數(shù)需要出現(xiàn)在 b 或 c 數(shù)組中，而且這樣的數(shù)越來越多。對于二元組 (x, y) ，若那么 (x, y) 是無效的。(x1, y1) 滿足 x x1 且 y y1 ，標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D刪去所有無效二元組后

11、，將其按 x 遞增排序，則 y 遞減。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D刪去所有無效二元組后，將其按 x 遞增排序，則 y 遞減。第 i 個的 x 和第 i + 1 個的 y 可組成一個合法方案。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D刪去所有無效二元組后，將其按 x 遞增排序，則 y 遞減。第 i 個的 x 和第 i + 1 個的 y 可組成一個合法方案。用 set 來維護

12、這個二元組序列，一個二元組時，先其是否無效，否則刪去變成無效的二元組。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D刪去所有無效二元組后，將其按 x 遞增排序，則 y 遞減。第 i 個的 x 和第 i + 1 個的 y 可組成一個合法方案。用 set 來維護這個二元組序列，一個二元組時，先其是否無效，否則刪去變成無效的二元組。用堆或 map 來存所有相鄰二元組組成的合法方案，并取最小值。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Ea

13、rchitectREMOVECF398D刪去所有無效二元組后，將其按 x 遞增排序，則 y 遞減。第 i 個的 x 和第 i + 1 個的 y 可組成一個合法方案。用 set 來維護這個二元組序列，一個二元組時，先其是否無效，否則刪去變成無效的二元組。用堆或 map 來存所有相鄰二元組組成的合法方案，并取最小值?！緯r間復(fù)雜度】O(n log n)。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DDeleting Substrings 33Source: Codeforces Round #230

14、 (Div. 1) Problem E數(shù)據(jù)范圍1 n 400 , 0 |vi| 2000 , 1 wi 109。題目大意在一個長度為 n 的數(shù)組上進行若干次刪除操作，每次可以刪除一個子串 l, r ，得到的價值為 vrl+1 ，要求該子串滿足|wi wi+1| = 1 ，對于所有 l i r 。2 wi wi+1 wi1 0 ，對于所有 l i r 。最大化得到的總價值。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析刪去的子串需要滿足的兩個條件，可以發(fā)現(xiàn)其一定是先遞增再遞減，且相鄰的兩數(shù)差為 1。

15、標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析刪去的子串需要滿足的兩個條件，可以發(fā)現(xiàn)其一定是先 遞增再遞減，且相鄰的兩數(shù)差為 1?？紤]區(qū)間 DP，用 fi,j 表示將 i, j 區(qū)間內(nèi)的所有數(shù)刪除后能得到的最大價值。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析刪去的子串需要滿足的兩個條件，可以發(fā)現(xiàn)其一定是先 遞增再遞減，且相鄰的兩數(shù)差為 1?？紤]區(qū)間 DP，用 fi,j 表示將 i,

16、 j 區(qū)間內(nèi)的所有數(shù)刪除后能得到的最大價值。轉(zhuǎn)移為枚舉分割點 k ， fi,j = maxfi,k + fk+1,j。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析刪去的子串需要滿足的兩個條件，可以發(fā)現(xiàn)其一定是先 遞增再遞減，且相鄰的兩數(shù)差為 1?？紤]區(qū)間 DP，用 fi,j 表示將 i, j 區(qū)間內(nèi)的所有數(shù)刪除后能得到的最大價值。轉(zhuǎn)移為枚舉分割點 k ， fi,j = maxfi,k + fk+1,j。同時，還有一種轉(zhuǎn)移，就是最后刪去的區(qū)間以 i 為開頭， 以 j 結(jié)束。標(biāo)準(zhǔn)算法CF36

17、4DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D分析刪去的子串需要滿足的兩個條件，可以發(fā)現(xiàn)其一定是先 遞增再遞減，且相鄰的兩數(shù)差為 1?？紤]區(qū)間 DP，用 fi,j 表示將 i, j 區(qū)間內(nèi)的所有數(shù)刪除后能得到的最大價值。轉(zhuǎn)移為枚舉分割點 k ， fi,j = maxfi,k + fk+1,j。同時，還有一種轉(zhuǎn)移，就是最后刪去的區(qū)間以 i 為開頭， 以 j 結(jié)束。由于刪除的子串可以明顯地分為兩個部分，均為公差為 1的等差數(shù)列標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF2

18、32ECF396EarchitectREMOVECF398D分析刪去的子串需要滿足的兩個條件，可以發(fā)現(xiàn)其一定是先 遞增再遞減，且相鄰的兩數(shù)差為 1?？紤]區(qū)間 DP，用 fi,j 表示將 i, j 區(qū)間內(nèi)的所有數(shù)刪除后能得到的最大價值。轉(zhuǎn)移為枚舉分割點 k ， fi,j = maxfi,k + fk+1,j。同時，還有一種轉(zhuǎn)移，就是最后刪去的區(qū)間以 i 為開頭， 以 j 結(jié)束。由于刪除的子串可以明顯地分為兩個部分，均為公差為 1的等差數(shù)列在枚舉最高點位置 k 以及知道兩端的值后，可以直接得到刪去子串的長度。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF23

19、2ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f 的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk)標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF39

20、6EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f 的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的轉(zhuǎn)移為枚舉滿足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f

21、的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的轉(zhuǎn)移為枚舉滿足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f 的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj w

22、k) g 的轉(zhuǎn)移為枚舉滿足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有轉(zhuǎn)移可以使用記憶化搜索，相用來實現(xiàn)。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f 的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的轉(zhuǎn)移為枚舉滿足|wi wk| = 1 且 |w

23、k wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有轉(zhuǎn)移可以使用記憶化搜索，相邊界條件 fi,i = v1, gi,i = 0 。用來實現(xiàn)。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f 的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的轉(zhuǎn)移為枚舉滿足|wi wk| = 1 且 |wk w

24、j| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有轉(zhuǎn)移可以使用記憶化搜索，相邊界條件 fi,i = v1, gi,i = 0 。用來實現(xiàn)。得到 f 數(shù)組后再進行一次簡單的 DP 即可。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D用 gi,j表示把 i, j 區(qū)間刪到只剩下 ai 至 aj 的等差序列能得到的最大價值。那么 f 的另一種轉(zhuǎn)移為fi,j = maxgi,k + gk,j + vwkwiwj+1(wi, wj wk) g 的轉(zhuǎn)移為枚舉滿

25、足|wi wk| = 1 且 |wk wj| + 1 = |wi wj| 的 k ，gi,j = maxfi+1,k1 + gk,j所有轉(zhuǎn)移可以使用記憶化搜索，相邊界條件 fi,i = v1, gi,i = 0 。用來實現(xiàn)。得到 f 數(shù)組后再進行一次簡單的 DP 即可?！緯r間復(fù)雜度】O(n3)。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dhistory44Source: POJ Challenge Round 5 Problem D數(shù)據(jù)范圍點數(shù) n、操作數(shù) m 3 105。題目大意在無支持兩

26、種操作：添加一條連接某兩點的邊。詢問某一過去時刻某兩點是否連通。強制。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D由于只有加邊和詢問連通性，所以只需維護森林。在詢問時求兩點之間時間最遲的邊即可。偽標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D由于只有加邊和詢問連通性，所以只需維護森林。在詢問時求兩點之間時間最遲的邊即可。用數(shù)據(jù)結(jié)構(gòu)優(yōu)化剛才的，需要支持維護森林和求兩點間的最大值，直接套用動態(tài)樹 (Li

27、nk Cut Tree) 即可。數(shù)據(jù)范圍較大，可能需要優(yōu)化常數(shù)。偽標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D由于只有加邊和詢問連通性，所以只需維護森林。在詢問時求兩點之間時間最遲的邊即可。用數(shù)據(jù)結(jié)構(gòu)優(yōu)化剛才的，需要支持維護森林和求兩點間的最大值，直接套用動態(tài)樹 (Link Cut Tree) 即可。數(shù)據(jù)范圍較大，可能需要優(yōu)化常數(shù)?！緯r間復(fù)雜度】O(m log n)。偽標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earchitect

28、REMOVECF398D如果只要求詢問當(dāng)時的情況，那么并足矣，但如果要查詢之前的情況呢？一種是 O(mn) 的了。的思想是全部存下來，但空間就標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D如果只要求詢問當(dāng)時的情況，那么并足矣，但如果要查詢之前的情況呢？一種是 O(mn) 的了。的思想是全部存下來，但空間就但是，把每次修改前的結(jié)果存下來是不是太浪費了？很多信息是可以共用的。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earchitect

29、REMOVECF398D如果只要求詢問當(dāng)時的情況，那么并足矣，但如果要查詢之前的情況呢？一種是 O(mn) 的了。的思想是全部存下來，但空間就但是，把每次修改前的結(jié)果存下來是不是太浪費了？很多信息是可以共用的。由于路徑壓縮修改的信息較多，我們采用另一種并化：按秩合并。的優(yōu)標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D這種優(yōu)化即在并的根節(jié)點上再多一個值表示這個森林中的最大深度，由于并詢問和深度有關(guān)，所以在合并時要盡可能減小森林的深度，把深度小的合并到深度大的即可。標(biāo)準(zhǔn)算法CF364DCF392D

30、CF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D這種優(yōu)化即在并的根節(jié)點上再多一個值表示這個森林中的最大深度，由于并詢問和深度有關(guān)，所以在合并時要盡可能減小森林的深度，把深度小的合并到深度大的即可。那么這樣并的合并只修改了一個節(jié)點的父親，而且這個節(jié)點的父親一旦確定就再修改，所以可以直接下這個節(jié)點父親確定的時間。而在詢問時，若詢問時間大于該父親確定的時間，則說明此時這條邊還沒有連上，當(dāng)前節(jié)點就 是當(dāng)時的根。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectR

31、EMOVECF398D這種優(yōu)化即在并的根節(jié)點上再多一個值表示這個森林中的最大深度，由于并詢問和深度有關(guān)，所以在合并時要盡可能減小森林的深度，把深度小的合并到深度大的即可。那么這樣并的合并只修改了一個節(jié)點的父親，而且這個節(jié)點的父親一旦確定就再修改，所以可以直接下這個節(jié)點父親確定的時間。而在詢問時，若詢問時間大于該父親確定的時間，則說明此時這條邊還沒有連上，當(dāng)前節(jié)點就 是當(dāng)時的根。這樣就得到了一個可以處理歷史詢問的并了。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D但是再仔細想想這個并，覺得似乎這

32、已經(jīng)不像并了，它維護的就是森林，但是這里的樹的形態(tài)卻和原來的樹不同，但這沒有。所以，忽略樹的形態(tài)后，我們可以按我們想要的方式合并兩棵樹，而不一定要按給出的邊合并。 同時，按秩合并就像啟發(fā)式合并，有效地使樹高降低到了 log n 的級別。也就是說，從最開始的算法出發(fā)，用啟發(fā)式合并來維護森林，也可以到達這里。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D但是再仔細想想這個并，覺得似乎這已經(jīng)不像并了，它維護的就是森林，但是這里的樹的形態(tài)卻和原來的樹不同，但這沒有。所以，忽略樹的形態(tài)后，我們可以按我們

33、想要的方式合并兩棵樹，而不一定要按給出的邊合并。 同時，按秩合并就像啟發(fā)式合并，有效地使樹高降低到了 log n 的級別。也就是說，從最開始的算法出發(fā)，用啟發(fā)式合并來維護森林，也可以到達這里?！緯r間復(fù)雜度】O(m log n)。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每個點維護其第 2i 個祖先，以及這段路徑上的最遲的合并時間。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每個點維護其第

34、 2i 個祖先，以及這段路徑上的最遲的合并時間。在后啟發(fā)式合并該數(shù)組。時利用該數(shù)組倍增求出lca，以及路徑上最遲的時間。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每個點維護其第 2i 個祖先，以及這段路徑上的最遲的合并時間。在后啟發(fā)式合并該數(shù)組。時利用該數(shù)組倍增求出lca，以及路徑上最遲的時間?！緯r間復(fù)雜度】O(n log2 n)。數(shù)據(jù)不夠強，沒把這個卡掉。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOV

35、ECF398D每個點維護其第 2i 個祖先，以及這段路徑上的最遲的合并時間。在后啟發(fā)式合并該數(shù)組。時利用該數(shù)組倍增求出lca，以及路徑上最遲的時間?！緯r間復(fù)雜度】O(n log2 n)。數(shù)據(jù)不夠強，沒把這個卡掉。用表每個節(jié)點不同時間的根。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每個點維護其第 2i 個祖先，以及這段路徑上的最遲的合并時間。在后啟發(fā)式合并該數(shù)組。時利用該數(shù)組倍增求出lca，以及路徑上最遲的時間?！緯r間復(fù)雜度】O(n log2 n)。數(shù)據(jù)不夠強，沒把這個卡掉。用表每個節(jié)點不同

36、時間的根。在后啟發(fā)式合并，只修改小樹所有點的根。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D每個點維護其第 2i 個祖先，以及這段路徑上的最遲的合并時間。在后啟發(fā)式合并該數(shù)組。時利用該數(shù)組倍增求出lca，以及路徑上最遲的時間?！緯r間復(fù)雜度】O(n log2 n)。數(shù)據(jù)不夠強，沒把這個卡掉。用表每個節(jié)點不同時間的根。在后啟發(fā)式合并，只修改小樹所有點的根。時兩點當(dāng)時的根是否相同。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396Earchit

37、ectREMOVECF398D每個點維護其第 2i 個祖先，以及這段路徑上的最遲的合并時間。在后啟發(fā)式合并該數(shù)組。時利用該數(shù)組倍增求出lca，以及路徑上最遲的時間?！緯r間復(fù)雜度】O(n log2 n)。數(shù)據(jù)不夠強，沒把這個卡掉。用表每個節(jié)點不同時間的根。在后啟發(fā)式合并，只修改小樹所有點的根。時兩點當(dāng)時的根是否相同?！緯r間復(fù)雜度】O(n log n)。其他算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DTree and Array 5題目大意對于一棵點數(shù)為 n 的帶若有一條連接 x, y(x y) 的

38、。為 z 的邊，則給 tx, tx+1, . . . , ty1, ty 都加上 z 。y i=x若 x, y(x yti ，則稱 x, y 為一對 good) 在樹上的距離 =pair 。 n要求構(gòu)造這樣一棵樹，使其 good pair 的數(shù)量至少為。25Source: Codeforces Round #233 (Div. 1) Problem C數(shù)據(jù)范圍5 n 105，為不超過 105 正整數(shù)。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D(4, 5), (5, 6), (5, 7) 為 goo

39、d pair 。樣例CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D先考慮怎么構(gòu)造一對 good pair 。構(gòu)造一對CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D先考慮怎么構(gòu)造一對 good pair 。以 4 個點為例， 1 3 4 2 的鏈，t1 + t2 = z1,3 2 + z2,4 ,dist1,2 = z1,3 + z3,4 + z2,4。構(gòu)造一對CF364DCF392DCF392Ehistory

40、CF398CCF380DCF232ECF396EarchitectREMOVECF398D先考慮怎么構(gòu)造一對 good pair 。以 4 個點為例， 1 3 4 2 的鏈，t1 + t2 = z1,3 2 + z2,4 ,dist1,2 = z1,3 + z3,4 + z2,4。設(shè)為 1 即若要兩者相等，則 z3,4 = z1,3 。將三條邊的可得到一對 good pair 。構(gòu)造一對CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D構(gòu)造順著剛才的想法下去，如果要構(gòu)造 1 號點和其他很多點的 good

41、pair ，那么只需套用上述結(jié)構(gòu)，從 1 連出去很多條鏈，重新計算一下。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D構(gòu)造順著剛才的想法下去，如果要構(gòu)造 1 號點和其他很多點的 good pair ，那么只需套用上述結(jié)構(gòu)，從 1 連出去很多條鏈，重新計算一下。n對 good pair 。1這樣可以構(gòu)造出3CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D構(gòu)造順著剛才的想法下去，如果要構(gòu)造 1 號點和其他很多點的

42、good pair ，那么只需套用上述結(jié)構(gòu)，從 1 連出去很多條鏈，重新計算一下。n對 good pair 。1這樣可以構(gòu)造出3但這樣的浪費比較多，如果合并一些，使其均攤用兩條邊構(gòu)成一對大概就能滿足要求了。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D標(biāo)準(zhǔn)算法n2設(shè) m =。CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dn設(shè) m =。2由于題目要求的是至少 m 對，所以考慮把點分兩組，其中一組 (1 m) 用

43、來構(gòu)造樹上，另一組 (m + 1 n) 形成 good pair 。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dn設(shè) m =。2由于題目要求的是至少 m 對，所以考慮把點分兩組，其中一組 (1 m) 用來構(gòu)造樹上，另一組 (m + 1 n) 形成 good pair 。一個前半部分掛一個后半部分的點， i 到 m + i 的給后半部分的 t 數(shù)組造成等差的影響，而 (1 m) 之間的半部分有影響。后標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232E

44、CF396EarchitectREMOVECF398Dn設(shè) m =。2由于題目要求的是至少 m 對，所以考慮把點分兩組，其中一組 (1 m) 用來構(gòu)造樹上，另一組 (m + 1 n) 形成 good pair 。一個前半部分掛一個后半部分的點， i 到 m + i 的給后半部分的 t 數(shù)組造成等差的影響，而 (1 m) 之間的后半部分有影響。構(gòu)造后半部分相鄰兩個組成一對 good pair ，為方便構(gòu)造， 可直接把前半部分連成一條鏈。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dn設(shè) m =。

45、2由于題目要求的是至少 m 對，所以考慮把點分兩組，其中一組 (1 m) 用來構(gòu)造樹上，另一組 (m + 1 n) 形成 good pair 。一個前半部分掛一個后半部分的點， i 到 m + i 的給后半部分的 t 數(shù)組造成等差的影響，而 (1 m) 之間的后半部分有影響。構(gòu)造后半部分相鄰兩個組成一對 good pair ，為方便構(gòu)造， 可直接把前半部分連成一條鏈。具體奇偶兩種情況討論。其中偶數(shù)會多出來一對 (n 2, n) ，而奇數(shù)可以把 n 掛到 n 1 上（觀察樣例），形成一對 (n 2, n) 。標(biāo)準(zhǔn)算法CF364DCF392DCF392EhistoryCF398CCF380DCF2

46、32ECF396EarchitectREMOVECF398Dm + in 1n. . .111 2m2i1/ . . . 3 / m 1 1/ m im+in-2n-1ntn+1-m-i321m,n+1+1+1+1m-1,n-1+1+1+1m-2,n-2+1+1 k ,m+k+1偶數(shù)CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398Dm + in 2n 1 1/ n. . .111 2m2i1/ . . . 3 / m 1 2/ mim+in-3n-2n-1ntn-m-i3221n-1,n+1+1m,n-1

47、+1+1+1+1m-1,n-2+1+1+1m-2,n-3+1+1 k ,m+k+1奇數(shù)CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398DSereja and Cinema 66Source: Codeforces Round #223 (Div. 1) Problem D數(shù)據(jù)范圍1 n 105。題目大意一排 n 個座位，兩端和相鄰座位間都有槽（比如放水杯的）。每個人就坐后會占用與其相鄰未占用的槽。給出每個人是第幾個就坐的（0 表示未知），求每個人都能得到至少一個槽的方案數(shù) mod 109 + 7 的結(jié)果。

48、CF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D考慮什么時候有人會沒有槽，就是他就坐時兩邊都有人。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D考慮什么時候有人會沒有槽，就是他就坐時兩邊都有人。所以，為了保證每個人都有槽，在邊界上的人應(yīng)該最后坐下。而去掉邊界上的人，縮小規(guī)模后又變成原。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectRE

49、MOVECF398D考慮什么時候有人會沒有槽，就是他就坐時兩邊都有人。所以，為了保證每個人都有槽，在邊界上的人應(yīng)該最后坐下。而去掉邊界上的人，縮小規(guī)模后又變成原可以發(fā)現(xiàn)，某一時刻已就坐的人應(yīng)該是一段區(qū)間。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREMOVECF398D考慮什么時候有人會沒有槽，就是他就坐時兩邊都有人。所以，為了保證每個人都有槽，在邊界上的人應(yīng)該最后坐下。而去掉邊界上的人，縮小規(guī)模后又變成原可以發(fā)現(xiàn)，某一時刻已就坐的人應(yīng)該是一段區(qū)間。然后就可以使用 DP， fi,j 表示已就坐 i 個人，且區(qū)間的開頭是 j 的方案數(shù)。DPCF364DCF392DCF392EhistoryCF398CCF380DCF232ECF396EarchitectREM