P8095 [USACO22JAN] Cereal 2 S

顯然有一個二分圖匹配 \(+\) 拓撲排序的做法，這里記錄另一個巧妙的貪心線性做法。

考慮經典建圖模型，我們對于一頭奶牛建立一條邊，邊的兩個端點分別為它最喜歡的麥片和次喜歡的。

每條邊要去貪心地匹配其某個端點。多條邊可能共端點，所以我們需要對于每個聯通塊都貪心一下。

對于每個聯通塊答案都有一個上界就是 \(\min(|E|,|V|)\)。

下面證明這個上界可以構造出來，要分類討論一下 \(|E|\) 和 \(|V|\) 的大小關系。

• 樹

此時滿足 \(|E|<|V|\)，也就是說我們需要對于每條邊都找到一個點來匹配。可以發現限制最寬松的地方是葉子節點向上的那一條邊，因為葉子節點只連了一條邊，所以沒邊和這條邊搶點，就算其上方端點被搶了，它也總能至少匹配到下方端點。因此我們只需要貪心地讓上方邊選就行了。dfs 一下，根據遍歷到邊的順序將邊放入排列即可。

• 圖

此時滿足 \(|E|\ge |V|\)。我們需要每個點都能有邊被匹配到。還是根據上面的思路，我們要優先滿足上方邊。一個很直接的思路就是我們隨機找一條邊，然后去滿足這條邊的 \(f_i\)。以 \(f_i\) 為根建立 dfs 樹（以 \(f_i\) 為根的原因是上方點被選擇了，不會導致下方邊無可選的點，和樹的思想一樣），在 dfs 樹上又能滿足 \(|V|-1\) 條邊，一共就是 \(|V|\) 條邊達到了上限。可是有一個問題，就是我們第一次選擇的邊不能出現在后面的那個 dfs 樹里，如果我們選擇了一條割邊，那后續就無法生成 dfs 樹了。直接 tarjan 找非割邊太麻煩了，可以先隨便建立一顆 dfs 樹，此時非樹邊就必然是非割邊了，隨便抽條非樹邊出來跑上述算法就行了。

時間復雜度 \(O(n+m)\)。

XYD20935.小 W 與鐵路

讓兩個人同時往前走，記錄狀態 \((i,j)\)，表示處于哪個點肯定會走重。

如果按照 DAG 每次剝離零度點，對于圖進行分層，讓兩個人盡量處于同一層中，每次都是進入下一層，這樣就就可以讓二人同步，不可能走到另一個人之前走過的點了。

上述做法等價于按照拓撲序進行轉移，每次選擇拓撲序小的點往前走一步。

二維 dp，時間復雜度 \(O(n^2)\)。

QOJ4212. Brackets

對于左括號出現的位置序列 \((p_1,p_2...p_n)\)，括號序列合法當且僅當其被 \((1,3...2n-1)\) 偏序。可以看成一個匹配問題。

設序列中元素相同的位置分別為 \(i\) 和 \(nxt_i\)，維護一個 std::set 里面是 \(1,3..2n-1\)，只需要 \(i\) 和 \(nxt_i\) 都能在其中分別找到一個比它大的數，那么它們都可以放左括號。

從左往右做，能放左括號就放左括號，然后在 std::set 中刪除對應匹配位置即可。

AH省集 D1T2 奇安凡尼銀行

可以發現我們確定了達到某個末狀態的最小操作次數之后是可以確定其能否被操作出來。

對于 \(n\) 是偶數的情況，可以發現轉一圈和左右交替交換都不會改變奇偶性，于是只要操作數 \(\le m\)，且和 \(m\) 同奇偶就可以完成。

根據糖果傳遞那題的結論，設 \(a_i-\rm ave\) 的前綴和為 \(s_i\)，我們最后的最小代價是 \(\sum|s_i-x|\)，其中 \(x\) 為 \(s\) 的中位數。\(s\) 序列和 \(a\) 序列是一一對應的，因此我們只需要對于 \(s_i-x\) 序列計數即可。枚舉其絕對值之和(也就是總操作數) \(i\)，\(<0\) 的數的個數 \(j\) 和 \(0\) 的個數 \(x\)。暴力做是 \(O(n^3)\) 的。枚舉兩個變量做兩次就是 \(O(n^2)\) 的。

對于 \(n\) 為奇數的情況，除了上述答案之外。還有轉了一圈之后，導致操作數的奇偶性變化了的選擇。這個時候直接套用轉一圈的情況是 \(m-n\) 次操作上界。但是其實可以更優，如果我們不選擇轉圈，而是選擇在上面不用最優中位數來操作，用 \(\pm 1\)，可以發現這個時候最優操作數變化量為 \(\max(-n_0+n_{+}-n_{-},-n_0-n_{+}+n_{-})\)，也就是變成了 \(m-n+2\max(n_+,n_-)\)。在偶數的時候使用這個調整是不優的，因為操作數的奇偶性不會改變。

從函數圖象上可以很好理解，\(n\) 段絕對值函數疊加，\(n\) 為偶數的時候，每段斜率為偶數，\(n\) 為奇數的時候，每段斜率為奇數。所以后者 \(x\) 每變化 \(1\)，結果的奇偶性都會改變。

AH省集 D2T1 洞穴

考慮將限制放到局部來看，就是任意兩點可以最后重合，且任意點都能到達 \(R\)。這顯然是一個必要條件，注意到這個條件很強，嘗試推廣到充要條件，由于你是圖上任意兩點都滿足這個限制，所以不管你怎么移動到新的點上，任意兩個點還都可以繼續合并，而且由于所有點都可達 \(R\)，所以你將 \(n\) 個點合并成一個點之后，不管在哪里最后都是可以繼續走到 \(R\) 的。

因此你直接建 \(n^2\) 個點表示二元組 \((u,v)\)，二元組之間建邊轉移。最后能到達 \((a,a)\) 就是勝利。每次挑選兩個點出來合并，總的時間復雜度是 \(O(n^3)\) 的，但是卡不滿可以通過。

P5540 [BalkanOI 2011] timeismoney

將一顆生成樹看成一個狀態 \((\sum a_i,\sum b_i)\)，顯然一棵樹的權值只與其狀態有關。

將這個狀態看成 \((x,y)\) 放到平面直接坐標系上，由于是要求 \((\sum a_i)\times (\sum b_i)\) 最小，也就是 \(x\times y\) 最小，所以可能成為答案的點一定在下凸包上面。

在 \(V\times V\) 的矩形內，凸包上點的個數是 \(O(V^{\frac{2}{3}})\) 級別的。

根據這條引理，有用的生成樹其實很少，如果我們能只遍歷這些生成樹，那么復雜度就是正確的。

可惜我們無法直接顯式建立這個凸包，但是我們知道凸包上的兩點 \(P\) 和 \(Q\)，分別是 \(\sum a_i\) 最小的生成樹和 \(\sum b_i\) 最小的生成樹。我們可以通過已有的兩點去構建這個凸包，直接尋找所有點還是不容易，考慮哪個點是一定在凸包上的，那么就是一個點 \(R\) 滿足在直線 \(PQ\) 下方且離 \(PQ\) 距離最大。找到 \(R\) 點之后更新答案，并且分治為 \((P,R)\) 和 \((R,Q)\) 去解決問題，這樣子我們每次找到一個肯定在凸包上的點，總的尋找復雜度也就是凸包上點的個數乘以單次尋找時間復雜度。

現在考慮如何找到 \(R\) 點，上述條件等價于三角形 \(PQR\) 的面積最大，也就是 \(\vec{RP}\times \vec{RQ}\) 最大。代入坐標，利用叉乘公式計算之后可以得到，希望最小化 \((X_Q-X_p) y_R+(Y_Q-Y_P)x_R\)。下面一步很巧妙，我們直接把每條邊的邊權設置為 \((X_Q-X_p) b_i+(Y_Q-Y_P)a_i\)，然后跑一遍 Kruskal 即可找到 \(R\) 點。遞歸下去即可找到所有點。

注意每次找到一個點后，需要用叉乘判斷其是否在凸包上，否則會超時。

記 \(V=\sum a_i\)，時間復雜度為 \(O(V^{\frac{2}{3}}m\log m)\)。

時間復雜度 \(O(n+m)\log n\)。

QOJ9840.Tree Partition

直接進行樹上背包，顯然復雜度太高且無法刻畫聯通塊編號連續這個信息。

考慮轉化一下，我們在值域上進行這個 dp，每次提取一個值域連續段，要求其在樹上構成一個聯通塊。對于一個點集，可以通過點減邊為一來判定其為一個聯通塊。于是我們直接 dp，利用線段樹維護轉移點到目前點構成區間的點減邊數量，同時注意到點減邊最少也得是 \(1\)，于是我們就直接記錄最小值位置的 dp 值之和，進行轉移即可，時間復雜度 \(O(nk\log n)\)。

發掘一些性質，我們給樹定向，從兒子指向父親。放到值域上，就是若干前向邊和后向邊。發現最多可以"浪費一條邊"（向區間外部連），也就是這個聯通塊的根向父親的邊，其余的邊必須在這個區間內部。

于是我們可以得到判定條件就是，掃描到 \(i\) 的時候，對于 \(fa_j>i\) 的 \(j\) 最近和次近的 \(j\) 分別為 \(x,y\)。那么 \(j\in [y,x)\) 能轉移到 \(i\) 的條件為 \([j,i]\) 沒有連到 \([1,j)\) 的邊。這是對于后向邊區間的判定條件。對于前向邊區間類似判斷即可，可以先 \(O(n\log n)\) 用數據結構維護出來轉移點，然后再 dp 一遍 \(O(nk)\) 解決。

P12503 「ROI 2025 Day1」索契游樂園

不錯的函數最優化練習題。考驗選手卡常技巧。

首先，對于一個選手來說向左走和向右走是獨立的。有兩種策略，一個是向左來回走一趟然后向右，另一種是向右來回一趟再向左。直接把來回的權值設成 \(2w\) 即可。然后兩種策略的答案取 \(\min\) 即可。

于是經過上述轉化，我們只需要平移坐標然后考慮從 \(x_0=0\) 開始的單方向行走就行了。一個最直接的策略就是枚舉走到了哪個位置 \(x\)，有一個行走的能量，\(w\times x\)，已經被覆蓋的點 \(c_i\) 消耗的能量就是 \(\min((c_i\bmod d)^2,(c_i-c_i\bmod d)^2)\)，未被覆蓋點消耗的能量是 \((c_i-x)^2\)。于是答案就是

記錄一些前后綴和可以 \(O(\log n)\) 計算這個式子，帶 $\log $ 的原因是你需要二分出 \(c_i\le x\) 的分界點 \(i\)。

這個式子是一些二次函數狀物構成的，所以我們猜測其具有凸性，且是一個單谷函數。

于是可以通過直接三分來找到極值點，單次計算 \(f(x)\) 的代價為 \(O(n\log n)\)。所以總的時間復雜度就是 \(O(m\log n\log V)\)，可以喜提 \(87\rm pts\)。

發現復雜度的瓶頸是在于每次三分內部要要二分出是在哪一段。于是我們可以先三分出在哪一段，然后段內再三分出哪個是極值點，這樣子第一次計算的時候取點我們直接取段內的左右端點即可，第二次計算的時候已經確定段了就不需要再二分段了。時間復雜度也可以做到 \(O(m(\log n+\log V))\)，可以獲得 \(91 \rm pts\)。

不過其實最后確定段之后，其中一個變量分界點 \(i\) 已經確定了，于是這就是一個純的二次函數，我們可以直接求出二次函數極值點，然后在附近找到 \(d\) 的倍數看看誰最優即可（注意特判二次項系數為 \(0\)）。于是又優化掉一個 \(\log V\)。時間復雜度 \(O(m\log n)\)，還是 \(91\rm pts\)。

其實整數域的三分是可以用二分替代的，因為下凸函數滿足差分單調遞增，我們直接二分出差分值在 \(0\) 附近的點即可。這樣子能大幅度減少常數，獲得 \(100 \rm pts\)。

當然由于我的寫法比較丑陋，所以還需要加入下面若干常數優化。

• 可以發現隨著 \(w\) 的增大，我們的最優行走距離 \(x\) 是單調遞減的，所以我們可以對于詢問的 \(w\) 進行排序，然后每次就可以縮短二分上界了。

• 雖然是 \(O(1)\) 計算函數值，但是由于計算過程中涉及 __int128，所以下面代碼中的 \(g\) 函數的計算會異常地慢，可以發現由于 \(g\) 是段的函數值，一共只有 \(O(n)\) 段，我們可以提前算出這些值，然后直接用即可。

QOJ8706. 解方程

很妙的一題，注意到后面那一坨實在難以處理，但是數據隨機生成，所以考慮進行一步放縮，把最后的一部分放縮掉，我們可以得到 \(a_ix\in [c_i-10^{11},c_i]\)，數據隨機情況下所以我們選擇前兩個方程，可以保證滿足這兩個約束的 \(x\) 的個數大約為 \((\dfrac{10^{11}}{P})^2\times P=10^4\) 這個量級，這樣子我們只要找到所有滿足條件的 \(x\)，再驗證 \(m\) 個方程即可。

如何找到所有符合條件的 \(x\)，BSGS！具體來說就是，我們先把第一個方程調整成 \(x\in [0,R]\) 的形式（這一步可以令 \(x\gets a_1x-(c_1-10^{11})\)，最后再變回去）。然后對于第二個方程是 \(a_2x\in [c_2-10^{11},c_2]\)，令 \(B=\sqrt {10^{11}}\)，預處理 \(x\in [0,B]\) 的 \(a_2x\bmod P\) 排序。枚舉 \(i\in [0,B]\)，對于 \(a_2iB\) 在排序數組中二分找到所有滿足條件的數，組合出 \(x\) 之后進行 check。之前說了滿足條件的 \(x\) 的期望個數為 \(1000\)，所以 BSGS 暴力找到所有解并且檢驗的復雜度是正確的。

除了上述講的做法，還存在一種類歐解法。

P12796 [NERC 2022] Game of Questions

本題的重點在于觀察到：一個問題最多被提問一次，如果提問第二次是不會產生任何效果的。于是我們并不關心哪些問題已經被提問過了，只關心哪些問題可以使得當前集合發生變化，\(s\to t\) 的時候拿發生 \(s\to t\) 變化的問題的種數除以能使得 \(s\) 發生變化的問題數就是單步的概率。

同時除了一個問題被問兩次之外，我們還要思考是否會出現有一個問題一次也沒有被問。由于上面說了，每次集合之間的轉移是考慮能使得當前集合發生變化的問題，那么在某條轉移路徑中沒有被列舉的問題就是對于單步不產生影響的，問不問也不影響某個變化過程中的概率。

設 \(g_{S,T}\) 表示 \(S\to T\) 的方案數，那么對于 \(f\) 的轉移有 \(f_T\gets \dfrac{f_Sg_{S,T}}{n-g_{S,\emptyset}-g_{S,S}}\)。

接下來要求解 \(g_{S,T}\)，由于 \(T\subset S\)，所以這部分的空間是 \(O(3^n)\) 的。

設問題 \(i\) 能回答出來的人的集合為 \(s_i\)，那么 \(g_{S,T}\) 為 \(s_i\cap S=T\) 的 \(i\) 的個數。唉我怎么不會求。考慮增量法，令 \(x\) 為任意一個不在 \(S\) 中的元素，那么 \(g_{S,T}=g_{S\cup \{x\},T}+g_{S\cup \{x\},T\cup \{x\}}\)。觀察這個遞推形式，考慮按照 \(S\) 從大到小推，每個 \(S\) 內部要按照 \(T\) 從大往下推。所以需要利用 \(s_i\) 信息得到所有的 \(g_{S,S}\) 就可以推全局了，也就是 \(S\subset s_i\) 的 \(i\) 個數，直接超集求和即可。

于是就可以快速遞推出 \(g\) 數組。

時間復雜度 \(O(3^n)\)。

以下為未完成的題解

P10559 [ICPC 2024 Xi'an I] The Last Cumulonimbus Cloud

有意思，圖上鄰域問題根號分治是經典解法，本題沒卡，但是實際還有更優做法。

ZROI3083.Xorshift

復雜題逐步分析。這個 \(3\) 操作很復雜，大概是線性基自由元之類的，所以肯定要用上 \(A\) 性質。

考慮 \(AD\) 搭配，可以發現由于沒有輸入的 \(x\)，所以初始值是固定的，我們可以時刻維護當前 \(f\) 的值，如果遇到了 \(g\) 操作，就可以直接模擬出 \(g(f(a_i))\) 的值。不需要每次回答都從頭做一遍。時間復雜度 \(O(nm)\) 可以過 1-5。

對于 14，15 沒有 \(D\) 性質，可以 \(O(nm^2)\) 模擬。

發現瓶頸在于修改，這個函數復合太難做了，很難整體做出什么事來。

考慮一下 \(C\) 性質 \(z=0\)，有一個很 nb 的觀察就是 \(g(x\oplus y)=g(x)\oplus g(y)\)，于是我們只需要維護全局異或值即可。去掉 \(C\) 性質呢？無非多判斷一下操作次數的奇偶來決定是否帶上 \(z\)。

QOJ5092.森林游戲

多個單點，就是對于點權排序。考慮長度為 \(2,3\) 的鏈模擬一下，

CF1511G Chips on a Board

即求 \(\bigoplus\limits_{l\le a_i\le r}(a_i-l)\)。

很反直覺啊，其實這個區間信息是可以合并的。

設 \(f_{i,j}\) 表示 \(\bigoplus\limits_{i\le a_k<i+2^j}(a_k-i)\)，\(g_{i,j}=\sum [a_k\in [i,i+2^j)]\)。

首先有，\(f_{i,j}\gets f_{i,j-1}\)。其次考慮 \(f_{i+2^{j-1},j-1}\) 的貢獻，拆位角度來思考，可以發現其實是被多減去了一個 \(2^{j-1}\)，我們需要補上這一位的貢獻，那么就是通過 \(g_{i+2^{j-1}.j-1}\) 的奇偶性來決定。

求解出 \(f_{i,j}\) 之后，我們需要對于區間 \([l,r]\) 求答案。

WC2025 士兵

先想貪心，發現根本不可做。因此考慮 DP。

思考一下

P11363 [NOIP2024] 樹的遍歷

好題啊。不妨從菊花圖入手，可以發現對于一個點，其周圍的邊生成樹是一個鏈狀，這是因為我們從一條邊出發不斷到某一條未遍歷的邊。轉化到圖上也就是說對于一個點周邊的一些邊也是類似的遍歷情況，就是我們逐步遍歷所有點，每次通過一條邊到下一條邊，雖然它們下方還有邊，但是那些下方的邊不影響，因為下方的邊永遠不可能跨過當前的邊來到上面。所以對于一個點其周圍的遍歷順序就是一個排列，由于第一個被遍歷的邊已經確定了，所以就是 \((deg_u-1)!\)。

求一下 \(\prod\) 就是 \(k=1\) 對應的情況。

考慮一下 \(k=2\) 的情況，先累加兩倍 \(k=1\) 的答案。然后我們需要減去從兩條邊出發得到的相同的生成樹。發現其中的關鍵就在于兩條邊之間的鏈，假設是 \(L\to...\to R\)，我們從左邊

P8171 [CEOI 2021] Diversity