知識點

數據結構

簡單題偏多。數據結構注重技巧性，這主要依靠經驗的積累。此外碼力也很重要，一定要寫出優雅易讀、易于調試的代碼。

本次的數據結構總體來說偏非常規。主要在于發現性質。

正確可控的時間復雜度是數據結構的核心。

所有的數據結構本質都是基于對于問題規模的預期來構建元素。

例如線段樹，即是將區間問題進行類似于二進制拆分來達到對數的時間預期，

以這次的幾道題為例。

• [雅禮集訓 2017 Day1] 市場

  構建數據結構支持區間向下取整除和區間加減、求和操作。

  首先一個直覺的想法就是如果是除法，那么除上不超過 log 次就會變成一段相同的區間。這樣的想法顯然是對的，我們來證明。

  考慮區間的極差。經過若干次除法，最終的極差會變為 0 或者 1 。在做除法時極差每次至少減半。

  所以除法就直接暴力做，直到當前區間極差為 0 或 1 就行了。

  再考慮加法的影響，每次加法只會最多讓 O(log) 個區間極差重置，勢能分析一下均攤下來是對的。

我們注意到這道題主要考慮到了出發會使得問題規模快速減小，在減小到一定程度時可以更改維護方式（這也是根號分治的原理！），并以區間極差作為衡量問題規模的標準。

• 區間切割

  對于每個點，注意到將其三等分之后，左右兩邊的切割操作相當于直接更改線段端點，而中間的操作會使線段長度至少減小 1/3 。
  所以我們對于每個線段直接暴力模擬，每次找到第一個切在中間 1/3 的切點再更新即可。最多更新 log 次，左右端點取 min 用數據結構也是很好維護的。

這道題以線段長度為衡量問題規模的標準。

由此可見我們主要通過對于問題規模減小的預期來構建預期時間復雜度的數據結構。

對于“問題規模”的定義顯得尤為重要。

還有一個維護一棵線段樹 2log 維護前綴最大/最小值個數的小 trick 。就是直接定義一個輔助函數計算某個節點區間小于等于某個數或者大于等于某個數的前綴 min/max 個數。你會發現這個東西可以單 log 實現。所以后面的事情就順理成章了。這不太重要。

森林連通塊的貢獻可以拆成點數減去邊數。這也不是很重要，見過一次就會了！！

樹上問題

復習為主。

換根。樹形背包。注意背包的復雜度依賴的是物品體積和點數線性相關。

樹上的根號分治利用的是度數超過 sqrt 的點只有 O(sqrt) 個。

直徑。所有直徑中點重合于一點。它有優秀的性質，就是它到任何點距離的最大值最小。

在多棵樹合并時，直徑是非常好維護的，直接拎出原來幾棵樹的端點互相求一下距離取 max 就行了。原來寫 lct 還做過這題呢。

在處理某些跟樹上路徑長度相關的問題時，把直徑的中點設為根會獲得出人意料的效果。

樹的重心就更不用說了。它作為根的性質就是沒有哪顆子樹大小大于原樹大小的一半。

比如說有道題是什么求最長路徑長度，但是路徑端點還有一個非路徑上的子樹大小限制。如果是垂直路徑的話意味著要換根，很麻煩。但是如果將重心設為根，我們便可以證明垂直路徑一定不優，因為沒有哪個子樹會有超過一半的大小。

dp 及其優化

長鏈剖分優化

其實是在樹上問題一節講的，但是除了優化打牌好像沒有什么卵用。

長鏈剖分顧名思義，不再贅述。顯然是用來優化樹形 dp 的。

具體來講 dp 方程需要具有如下特征：

• 是一個二維方程。
• 方程第二維的大小與子樹深度線性相關。
• 轉移的延續性。對于一個點，我們可以依任何次序處理它的若干子樹來進行轉移。
• 轉移的繼承性。對于一個點，它的方程的初始狀態可以通過繼承它的任意一個兒子得到。
  所謂繼承包括但不限于直接復制數據，或是做信息熵不多、可以用數據結構直接維護的信息，比如區間加等等。

具體過程就是繼承長鏈信息，對于短鏈直接暴力轉移。

剩下就是一堆雜題，天知道是什么東西，也沒辦法分類，挑重點記一下。

• 關于狀態記錄的優化

注意并不是狀態設計的優化。狀態本質并沒有改變，我們在做的事情只是合并當前轉移的同類項。

對于判定性的方程，我們可以試著找出等價的狀態，將其劃分為一個等價類，然后去重進行轉移。

一個常見的 trick 是直接用一個動態數組記錄每一維的狀態等價類有哪些。

對于狀壓方程有的時候不必每個狀態都進行記錄，而是直接分段進行記錄，變成一個多進制狀態。因為狀態總數和每一維狀態空間的乘積有關，現在最壞的情況從 log_2 變成了 ln 或者說 log_3 。

dp 也可以套上一些其它的東西，比如說折半狀壓和根號分治。但是折半狀壓的轉移方式實在是有些陰間，現在還是不會寫代碼。

在某些情況下我們可以考慮直接記錄 dp 的差分數組即其導數，并利用一些性質（比如說原方程的凸性轉換到這里就變成了單調性）來快速進行維護。

比賽

7/13

我也不知道自己在打什么，發呆時間至少有 1~2h 。沒什么策略可言，如果有策略的話就會去看后面兩道很 trivial 的題，也不至于就拿這點分了。

但是 T1 確實不會。

下次要記住碰到 dp 方程值域過大的情況，往三個方向考慮：

• 減少無用信息量，優化方程設計。
• 分析方程性質，換個方式或者上科技維護。
• 合并等價狀態。

7/16

這場沒有水平全是策略。打暴力還能掛分也是神人。

T1 是唐唐推式子題。我似乎根本沒有真正去推過原問題。打了很豐厚的部分分，但是最后發現就是這玩意再推廣一下就是正解了。感覺還是太保守了。

T2 一眼會了 2log 做法，但是沒敢寫。據說敢寫就敢過。

但是確實沒想到單 log 做法，原因讓人哭笑不得——原來基環樹上任意兩點路徑長可以 O(1) 求啊。

T3 第三道題是很典的二分答案加上一堆數據結構亂草過去，完全沒想到。

暴力的思路和正解幾乎沒有關聯。感覺思維鏈路出了些問題。主要還是有些很直覺的東西自己想不到，很神奇。這樣的事情我也不知道怎么解決，或許多做些題就好了。

7/19

兩道簽到和兩道不可做。

T3 是看上去很典、實則很毒瘤的數據結構。

T4 是披著字符串皮的凸包優化 dp 。

沖后面的正解導致少打了一點暴力。問題不大，反正正賽不會這么干。

總之這段時間比賽狀態顯然沒有暑假在校內時那么好了。隨便調整調整就好了。

主要是下周要講生成函數這種很抽象的東西。在那之前自己的數學基礎一定一定要牢固，要完全理解對于這個板塊獨有的思維方式才行。

我想放假。