天天看點

NOI2020 簡要題解

NOI2020 簡要題解

\(A\)

首先不難發現一個暴力動态規劃的做法 , 記\(f_{i,j}\)表示第\(i\)天 ,目前在第\(j\)座城市所獲得的最大收益

有轉移方程 \(f_{i,j} = max\{f_{i-w_{i},u_{i}}+cost_i+extra_{i,j}\}\)

發現\(w_{i}\)非常小 , 考慮拆點。 将每個點拆成\(w_{i}\)個點 , 那麼一共會有至多\(5n\)個點。

接着 , 考慮矩陣乘法 , 事實上 , 将求和運算改為\(max\)運算 , 并将括号内的改為加法 , 是依然成立的 (廣義矩陣乘法)

那麼我們就隻需要預處理\(64\)個矩陣 , 并用向量乘矩陣合并答案

時間複雜度 : \(O({(5N)^2logT + (5N)^3logT})\)

代碼 : https://loj.ac/submission/917284

\(B\)

首先對于\(M <= 23\) , 有一個容斥原理的做法 :

考慮欽定每個限制是否一定不滿足 , 那麼就隻需建出虛樹 , 設一共有\(i\)個限制一定不滿足 , 虛樹的長度總和為\(l\) , 對答案的貢獻即為 \((-1)^i \cdot 2^{n-1-l}\)

但是這樣的指數級算法是不能接受的。

考慮一個動态規劃的思路 :

記 \(f_{i,j}\) 表示以 \(i\) 為根的子樹 , 在\(j\)深度或更大的點一定要有一條向上邊權為\(1\)的邊的方案數。

轉移的時候隻需枚舉其兒子節點 , 并讨論邊權為\(0/1\)的情況 , 依次合并即可。

直接這樣做是 \(O(ND)\) 的 , 其中\(D\)表示深度

考慮優化 , 不妨寫出轉移方程 : \(dp'_{x,i} = dp_{x,i} \cdot (sum_{y,depx} + sum_{y , i}) + dp_{y,i} \cdot sum_{x , i - 1}\) , 其中\(sum\)表示\(dp\)數組的字首和。

考慮線段樹合并 , 每次先将左子樹的和累加 , 然後加到右子樹上 , 我們隻需對于線段樹上每個節點維護一個整體乘法标記即可。2018年北大冬令營有過一個類似的套路。

時間複雜度 : \(O(NlogN)\)

代碼 : https://loj.ac/submission/916802

\(C\)

分塊。

\(D\)

首先觀察資料範圍 , 有 \(m \geq n - 2\) 。并且部分分中有一檔是 \(m = n - 1\) , 很可能起到提示标準算法的作用。

考慮\(m = n - 1\)怎麼做。

令 \(d_1 \leq d_2 \leq d_3 .... \leq d_{n}\)

首先 , \(m = n - 1\) 時一定有解。

我們發現 , \(n=2 , 3\) 的情況都可以直接構造 , 那麼我們是否能将 \(n\) 的情況向 \(n - 1\) 轉化呢?

引理 \(1\) : \(d_1 < k\)

證明 : 假設 \(d_1 \geq k\) , 那麼 \(d_1 + d_2 + d_3 + ... + d_n \geq nk > (n - 1)k = d_1 + d_2 + .... + d_n\) , 沖突。

引理 \(2\) : \(d_{1} + d{n} \geq k\)

假設 \(d_{1} + d_n \leq k - 1\) , 那麼 , \(d_n <= k - 1 - d_1\) , 則\(d_1 + d_2 + ... + d_n \leq d_1 + (k - 1 - d_1)(n - 1)\) , 沖突。

根據這兩條引理 , 我們就獲得了一個構造方案 , 每次将 \(d_1\) 用完 , 然後用 \(d_n\) 填補空缺 , 當隻剩兩個的時候直接放一起即可。

對于 \(m >= n\) 的情況 , 考慮向 \(m = n - 1\)轉化。

引理 \(3\) : \(d_{n} \geq k\)。

證明 : 若 \(d_{n} < k\) , 則 \(d_1 + d_2 + ... + d_n < nk \leq mk = d_1 + d_2 + ..... + d_n\)

單獨用一次 \(d_n\) , 就使 \(m\) 減小了\(1\) , 是以可以最終轉化為 \(m = n - 1\)的情況。

綜上 , 我們得到了一個 \(m \geq n - 1\)時的做法 , 可以得到 \(20\) 分。 如果加上 \(n <= 10\)的暴力做法 , 就可以得到 \(45\) 分的可觀得分。

接着 , 我們考慮如何處理 \(m = n - 2\)。

引理 \(4\) : 問題有解當且僅當可以找到一個子集 \(S\) , 記 \(x = |S|\) , \(S\)中的元素的和 \(= (x - 1)k\)。

證明 :

充分性 : 顯然 , 對于集合 \(S\) 與集合 \(T = U - S\) , 都是兩個滿足 \(m = n - 1\) 的子問題。 直接對于兩個集合分别構造一組解即可。

必要性 : 考慮一張圖\(G\) , 我們将兩種一起使用的節點連一條邊 , 那麼就一共有 \(n - 2\) 條邊 , 這張圖一定是不連通的。 是以滿足有解一定要找到這樣的一個集合。

根據引理 \(4\) , 我們可以将每個 \(d_i\) 減去 \(k\) , 那麼就隻需判斷是否有一個集合的元素和為 \(-k\)。

這是一個經典的背包問題 , 可以通過 \(bitset\) 優化。

時間複雜度 : \(O({N ^ 2K \over w})\) , 取 \(w\) = \(32\) 或 \(64\)。

代碼 : https://loj.ac/submission/917359

\(E\)

首先引出"好樹"的概念 , 我們将一棵每個節點左右兒子 \(size\) 值的最小值均不超過 \(1\) 的二叉樹稱為好樹。

觀察 \(1\) : 如果僅有有限個好樹不在集合 \(grow(T)\) 中 , 則該集合是幾乎完備的。

觀察 \(2\) : 輸入的集合中 , 非好樹是無用的。

觀察 \(1\) 比較顯然 , 而觀察 \(2\) 是因為根據觀察 \(1\) , 隻有好樹是值得關心的。

那麼我們就有了一個遞歸求解的思路 :

令 \(solve(T)\) 表示樹林 \(T\) 是否幾乎完備。

首先 , 如果有葉子節點 , 傳回完備。 如果樹林為空 , 傳回不完備。

否則 , 将其分為 \(4\) 類 :

\(1\) : 根隻有左兒子。

\(2\) : 根隻有右兒子。

\(3\) : 根有左右兒子且左兒子大小為 \(1\)。

\(4\) : 根有左右兒子且右兒子大小為 \(1\)。

判斷這四個子問題是否都成立即可。

因為每個節點的貢獻都是 \(1\) , 是以時間複雜度是 \(O(N)\) 級别。

代碼 : https://loj.ac/submission/918127

\(F\)

弦圖。