20xxacm區(qū)域賽北京賽區(qū)題目講評-資料下載頁
2025-08-07 11:10本頁面
【正文】 往前，對于每一個點 x，按照出邊從小到大，把后繼節(jié)點按順序插入 x的平衡樹中，最后，如果 x本身就是個合法的結(jié)束點，那么我們在 x的平衡樹最前面加一個長度為 0的節(jié)點。 但問題是現(xiàn)在平衡樹不可能存這么多個元素，所以我們使用可持久化平衡樹即可，每次就是可持久化的合并兩個平衡樹而已，而且要保證平衡樹的深度是 log級別的，而且不能 rotate，所以可以用平衡樹的一些特別寫法，比如基于隨機合并的 Treap。 時間 復雜 度為 ??(??log2?? ) Just A Mistake ?題目大意：輸入一棵樹，求在隨機均勻采樣一個排列 P，輸出此排列對應(yīng)的獨立集大小的期望。 ?總提交人數(shù)： 7+7=14 ?封榜前 AC數(shù)： 0 ? ?題目解法：樹形 DP Just A Mistake 根據(jù)期望的線性可疊加的性質(zhì)，我們可以分別計算每一個點得貢獻，也就是先枚舉一個點 r，計算有多少個 permutation使得 r可以被選中。 枚舉完 r后，那么唯一會影響到 r得只有 r的相鄰點，如果 r的某個相鄰點 x， permutation中的位置在 r之后，那么他不會對 r有什么影響，關(guān)鍵在于如果在 r之前，如果 x成為了獨立集中的點，那么 r自然就不行了，否則，還要看 x得孩子中的選取情況。 就這樣，成了一個樹上的 DP Just A Mistake 依次枚舉一個點作為根。定義 F[I][J]表示 I這個節(jié)點，它在以它為根的子樹中，列第 J位，對于期望的貢獻。對于此狀態(tài)，可用 O(N)時間進行轉(zhuǎn)移。時間復雜度為 ??(??4)。 經(jīng)過發(fā)現(xiàn)，不難看出若按照 DFS序依次枚舉不同的節(jié)點作為根，只有常數(shù)個節(jié)點的 DP值有變化，故該樹 DP的時間復雜度可優(yōu)化至??(??3)。 謝謝大家 ACM Always Challenge Miracle
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1