目錄題目[WC2006]水管局長題面：題解：[FJOI2015]火星商店問題題面題解[USACO13OPEN]陰和陽Yin and Yang題面題解[51nod]1472 取余最大值題意題解CF1137C Museums Tour題面題解

題目

以下題解里面要是有不對的地方歡迎提醒/打臉。

[WC2006]水管局長

題面：

[WC2006]水管局長

題解：

首先根據一些常識,我們可以發現，符合要求的邊一定在最小生成樹上，因為有刪邊操作，因此我們需要做的就是動態維護最小生成樹。
因為刪邊不好處理，因此我們可以直接倒著處理，這樣刪邊就變成加邊了。
因為要維護邊，因此我們考慮將每條邊都視作一個帶權中轉點。即對于x --- > y的邊，連x ---> now --- > y,其中now為一個帶權點。
同時如果已經構成一棵樹，我們要再往里面塞邊的話，就必須要刪掉一條邊，否則會構成環。
因此對于一條連接x ---> y，邊權為(k)的邊，我們查詢x -- > y路徑上邊權的最大值(maxn)，那么會有2種情況：

(maxn > k)，那么說明插入這條邊是優的，因此我們刪去最大值所代表的邊，加入當前邊
(maxn le k),那么說明保留最大值比較優，所以我們忽略這條邊，不進行修改。

然后就可以了。

[FJOI2015]火星商店問題

題面

[FJOI2015]火星商店問題

題解

觀察到，如果沒有最近d天的限制，那么我們只需要將所有物品按照所屬商店的順序加入可持久化trie樹。
如果我們要查詢商店編號在([ll, rr])之間的最大xor值，那么我們只需要查詢區間([l, r])內的xor最大值即可。
其中(l)表示第一個屬于查詢范圍內的物品編號，(r)表示最后一個屬于查詢范圍內的物品編號。
具體如何獲取這2個編號？因為物品是按照所屬商店順序加入的，所以我們只需要在加入的物品序列中二分一下就可以了。
那么再考慮最近d天的限制。
相當于是查詢商店編號屬于([ll, rr]),時刻屬于([l, r]) 內的最大xor值。
我們考慮線段樹分治。
對于每個詢問區間，我們將它的查詢時刻區間分成log段，掛在線段樹上。
對于每個物品，因為我們需要將物品按照所屬商店的順序加入，因此對于線段樹上的每個區間，我們都需要重建整個可持久化trie樹。
不過因為物品是一個單點修改，因此就算我們在每個包括了這個物品的區間都放一個這個物品，每個物品也最多放log個。
因此我們在每個包括了這個物品的區間內放一個這個物品，然后每到一個區間，就取出所有在這個區間內出現過的物品，重建整棵trie樹。
然后對于每個掛在這個區間上的詢問，二分我們需要查詢的物品區間，在可持久化trie樹上查詢并更新這個詢問的答案。
最后再輸出即可。
復雜度是(O(nlog^2n))的

[USACO13OPEN]陰和陽Yin and Yang

題面

[USACO13OPEN]陰和陽Yin and Yang

題解

看上去點分搞搞就可以了？

[51nod]1472 取余最大值

題意

有一個長度為n的數組a，現在要找一個長度至少為2的子段，求出這一子段的和，然后減去最大值，然后對k取余結果為0。
問這樣的子段有多少個。

題解

之前做過這題的樹上版本，可以直接套上來做。
我們考慮點分治，因為拼接2條路徑時需要知道最大值是誰，所以不能直接做完個子樹就放桶。
我們考慮容斥，先求出所有的路徑，按照max從小到大排序，然后每枚舉到一條線段，就減去max然后在桶里面找方案，再加入桶。
但是這樣會有重復，因此我們單獨求出每棵子樹內部互相匹配的方案。然后用總方案減去這部分，就得到了答案。

CF1137C Museums Tour

題面

一個國家有 (n) 個城市，通過 (m) 條單向道路相連。有趣的是，在這個國家，每周有 (d) 天，并且每個城市恰好有一個博物館。
已知每個博物館一周的營業情況（開門或關門）和 (m) 條單向道路，由于道路的設計，每條道路都需要恰好一個晚上的時間通過。你需要設計一條旅游路線，使得從首都：(1) 號城市開始，并且當天是本周的第一天。每天白天，如果當前城市的博物館開著門，旅行者可以進入博物館參觀展覽，否則什么也做不了，這一天的晚上，旅行者要么結束行程，要么通過一條道路前往下一個城市。當然，旅行者可以多次經過一個城市。
要求讓旅行者能夠參觀的不同博物館數量盡量多（同一個城市的博物館參觀多次僅算一次），請你求出這個最大值。

題解

如果我們對原圖縮點會怎樣？
每個強聯通分量的貢獻會隨著進入的時間而改變。
考慮到(d)不大，可以考慮將每個城市拆成(d)個單獨的點，((x, i))表示點(x)在星期i的狀態，再用((x, i)) ---> ((x, i + 1))，然后再縮點。
那么我們會發現，一旦我們可以到達一個點，并且((x, i))是開啟狀態，那么我們一定可以獲得這個貢獻，因為我們走(k)到達的，一定是某個城市的第(k)個狀態。因此我們就可以在新圖上直接跑最長路了。

總結

以上是生活随笔為你收集整理的杂题记录的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。