CF1103 部分題解

連結

究極下飯，賽時做出 AB，B 死活想不出來一個多小時才 AC

直接給橫着的分一半，豎着的分一半，然後 xjb 填就行了

考慮先問出這個數的最高位。

當滿足 \(x<a\) 時，若 \(2x \% a>x \% a\)，那麼有 \(2x < a\)，否則 \(2x>a\)。

然後确定最高位以後逐位确定即可，具體地，每次問 \(ans-1\) 和 \(ans+2^i-1\)。

有關圖的構造，一般要想到生成樹；有關兩個條件滿足其一的，一般是在最壞情況下發現一些性質。

考慮一顆生成樹，如果深度 \(\geq \frac{n}{k}\)，那麼直接輸出，否則通過抽屜原理，可以保證葉子個數 \(>k\)。

然後可以對于每個葉子都能找到一個不同的環。

因為是生成樹，是以葉子多餘的兩個邊一定是返祖的，并且這兩個邊可以保證至少有一個滿足要求的環。

同時因為深度 \(\leq \frac{n}{k}\) ，是以總長度是 \(\leq n\) 的。

想到生成樹的話思路還是很順的。

逐漸縮小資料範圍的思想還是很震撼的。

質因子個數 \(m \leq 12\)

考慮把每個數隻留下公因數的因子，然後把數相同的隻留下代價最便宜的 \(m\) 個，不同的數個數 \(N \leq 12000\)。

直接暴力複雜度 \(O(N3^mm^2)\)，無法通過。

然後繼續優化，考慮在枚舉補集進行轉移的時候，可能作為這個集合轉移的也隻有最便宜的 \(m\) 個，處理出這 \(m\) 個複雜度為 \(2^mN\)。

最後轉移的時候對于每個數隻更新這個數被選中的轉移，這樣每種狀态枚舉子集的次數隻有 \(m\) 次，複雜度 \(O(3^mm^2)\)。