十月模擬賽

10.3

T3

序列修改

在時間軸上考慮，相當于每個時間除了自己該有的還能額外帶上 \(k - 1\) 個東西。則對于每個數，將每兩個相鄰的出現中間視為一條線段，則希望選出一些線段滿足每個位置被覆蓋不超過 \(k - 1\) 次，并且費用最大。經典建模，建一條數軸，源向第一個點連流量 \(k - 1\)，每條線段起點向終點連流量 \(1\)，費用為其代價的邊。最大費用最大流即可。通過 \(S \rightarrow 1\) 的邊限制了每個時刻被覆蓋次數 \(\le k - 1\)。

T4

將子段歸零

要求 \(\max \{ \#(a_i \le x) - x \}\)，發現很像霍爾定理的形式，于是轉化為二分圖匹配問題。由于這里匹配的特殊性，可以直接貪心。每次新加入一個東西的時候，如果可以匹配，則直接匹配。否則踢掉位置最小的匹配的 \(a_i\)，換上新的東西。判斷匹配也用霍爾定理，然后再開一棵線段樹維護每個 \(a_i\) 是否匹配即可。

10.4

T3

魔法

形成路徑，等價于連通且每個點度數不超過 \(2\)。連通性只需要把每個點向父親連邊，若點集只有一條連向點集之外的邊則連通。而度數不超過 \(2\)，考慮維護從小往大加點時每個點第一次度數超過 \(2\) 的時間。每個點度數超過 \(2\) 有兩種情況，一種是選了三個兒子，一種是兩個兒子一個父親。三個兒子容易統計，兩個兒子一個父親的情況，由于每次更新父親的時候需要暴力兒子，但兒子其實沒有發生變化，于是把這種情況掛到父親上統計。這樣就能快速完成更新了，每次只需要更新常數個點。而對于連通性，注意到如果一個父親下面有超過兩個兒子，則第三小的兒子造成的限制沒有用，因為它限制的時刻已經被前兩小的兒子限制死了。因此只需要對每個點維護最小的兩個兒子的連邊即可。

• 我咋這都不會做？

T4

防御塔

注意到至少一對相對的方向只會各自選一個矩形。顯然。不妨假設左上-右下各只選一個，則可以預處理這兩類矩形分別覆蓋了什么。然后枚舉縱坐標最靠上的一個左下矩形，然后貪心選交它的縱坐標最靠下的右上矩形，然后再貪心選交它的橫坐標最靠右的左下矩形，依此類推。可以用記憶化搜索寫。但是由于最開始選的右上矩形和左下矩形的左上空白無法被左上矩形覆蓋，因此需要額外選一個。這樣就做完了。

• 第一步觀察，即使顯然。

10.7

T2

數據結構

考慮二分答案，每次 check 需要檢查區間是否存在比某個數大的數。若不帶修可以直接從小到大加數可持久化線段樹維護，帶修就直接把 \(x\) 的線段樹的 \([l, r]\) 區間貼到 \(x + 1\) 的 \([l, r]\) 區間上就好。注意貼上去的過程中被貼的線段樹所有被修改的節點都需要可持久化，否則會出問題。

T4

樹據結構

樹剖套可持久化線段樹維護修改，鏈查拆成到根鏈查，子樹查用定期重構，每次重構更新版本樹的子樹和，散塊暴力檢查即可。

10.8

T3

數據結構題

顯然的事實是交也是值域連續的區間。考慮枚舉交的右端點 \(x\)，并假設右邊比中間大。此時我們考察右端點往右這一塊，起點為 \(x + 1\) 的最長值域連續段。由于這個段已經占據了這個值域區間，因此中間的交要是想和右邊拼起來，則其必須包含這個最長值域連續段中的 \(\min - 1\)。那么在以 \(x\) 為右端點的所有包含 \(\min - 1\) 的值域連續區間中，顯然我們任選兩個出來作為左邊的左端點和交的左端點都是合法的。于是做完了。

T4

圖森破

條件即為 \(X\) 為自身的最小循環表示。發現所有最小整周期為 \(|X|\) 的串 \(X\)，它們所有循環表示不同，因此具有唯一的最小循環表示。因此只需要計算長度為 \(n\) 的最小整周期為 \(n\) 的數的個數。設為 \(f_n\)，則顯然 \(10^n = \sum\limits_{d | n}f_d\)。莫反即得 \(f_n = \sum\limits_{d | n} \mu(\frac n d)10^d\)。于是答案為 \(\sum\limits_{n}\sum\limits_{d | n}n\mu(\frac{n}w0obha2h00)10^d\)。將 \(n\) 拆開，得 \(\sum\limits_{n}\sum\limits_{d | n}\frac{n}w0obha2h00\mu(\frac{n}w0obha2h00)10^dd\)，即 \(\sum\limits_w0obha2h0010^dd\sum\limits_{i = 1}^{n / d}i\mu(i)\)。后面的杜教篩，前面的數論分塊即可。其前綴和是好求的。

10.10

T2

過半數

對每個絕對眾數 \(x\) 計算答案。將 \(x\) 視為 \(1\)，別的視為 \(-1\)，則我們要求前綴和序列中的順序對數。數據結構維護即可 \(1\log\)。由于所有的總升高次數是線性的，因此考慮拿這個來均攤。掃到每個位置的時候，維護前面的前綴和的最小值，記為 \(minval\)。若當前要減少 \(x\)，如果沒有減過 \(minval\)，則暴力減，因為這里減掉的都可以用前面的加來均攤。而若減過了，則顯然不會產生貢獻，直接一次減完。而對于中間的數的出現次數的維護，只需要在后面加回來的時候判一下設為 \(1\) 就好了。

10.11

T3

顏色

子樹外容易，現在需要支持鏈加和查詢兒子信息和。考慮將每個點的兒子分為重兒子和輕兒子維護。對于輕兒子，每次修改的時候跳重鏈，就把鏈頂父親的輕兒子貢獻更新一下。對于重兒子，每次查的時候直接訪問即可。

• 寫代碼一定要注意特殊情況，如把原本顏色改成原本顏色。

T4

線下見面

考慮若存在 \(u, v, w\) 滿足 \((u, v), (v, w)\) 有邊，\((u, w)\) 無邊，則若 \(v\) 空，我們可以讓 \(u, w\) 通過操作 \((u, v, w)\) 變成空的。

先考慮樹的情況。任意找到這樣的一個結構，并以 \(u\) 為根。先用 \(v\) dfs 一遍整棵樹，這樣即使 \(v\) 一開始不是空的也已經相遇過了。因此可以視為空的。接下來清空 \(u\) 和 \(w\)。接下來我們可以清空所有第二層點。我們先把 \(v\) 上的東西移到 \(w\)，然后用這個點和 \(u\) 操作，然后再 \((u, v, w)\) 就好。那么現在清空了第二層。

然后從上往下清空所有偶數層。設當前點為 \(x\)。由于祖父為空，因此通過 \((fa_x, fa_{fa_x})\) 和 \((x, fa_x, fa_{fa_x})\) 兩步操作可以將 \(x\) 移到父親。

然后從下往上清空所有奇數層。由于父親為空，因此通過 \((x, fa_x, fa_{fa_x})\) 和 \((fa_x, fa_{fa_x})\) 兩步操作即可將自己扔到祖父。

這樣整棵樹就全部匯集到根了。

而對于圖，若非完全圖則可以找到 \((u, v, w)\) 的結構。然后我們希望找到一棵生成樹，滿足每個點和其祖父沒有邊。不難發現 bfs 樹滿足這樣的性質。于是拎出以 \(u\) 為根的 bfs 樹套上面的做法即可。而完全圖是容易做的，只需要輪流操作 \((1, 2), (3, 4) \cdots\) 和 \((2, 3), (4, 5), \cdots\) 即可。

• 希望獲得一個空點，于是憑空創造了等效的空點 \(v\)。

• 逐層清空。

一步都想不到啊。

10.13

T1

壓縮表格

出現在相同行列的相同元素直接合并，對于已經填的東西將其對當前元素離散化后的值的約束取 \(\max\) 再加一即得當前元素的值。

T3

悶聲刷大題

wqs 二分之后反悔貪心 check。具體地，從后往前加入 \(a_i\)，每次的決策是匹配一個新的 \(b_i\)，或者換掉一個之前已經匹配的 \((a_j, b_k)\)。可以證明當采取第二種決策時拆掉原本的匹配之后被解放的 \(b_k\) 一定還會在這一輪作為最優決策和 \(a_i\) 配對。總復雜度 \(2\log\)。

• 沒有 clear 的 STL，最好每次用都新開一個，不然清空會多常數。

T4

時鐘裝置

首先無論如何容易發現只有那些不同時存在于新樹和原樹的邊是需要被操作的，而答案也就是這種邊的數量（除以二）。然后考慮構造。首先先把原樹和新樹都有的邊縮連通塊，然后只需要每次斷掉一個葉子連通塊向上的連邊，并將其中的任意一條還沒連的新樹邊連上即可。可以啟發式合并維護每個連通塊的未連邊。

• 縮連通塊。從葉子考慮。

10.14

T4

航空系統

• 補圖上一些連通性之類東西的處理。

10.17

T1

布谷鳥

• 想題一定要用腦子。要考慮到所有情況。

T2

航拍

• 會了做法可以不急著寫，而是想想有無可以優化的地方。

T3

哥譚市

分塊，預處理所有左端點或右端點為 \(B\) 的倍數的區間的答案，最后答案就是 \([L_{id_l + 1}, r] + [l, R_{id_r - 1}]\) 再加兩邊散塊。

• 分塊小技巧。

10.20

T3

望鄉臺

• SAM 求子串排名要建反串 SAM！！！

T4

翻修道路

類似最小斯坦納樹的 dp，\(f_{i, j, S}\) 表示當前根 \(i\)，\(j\) 條翻修邊，包含了 \(S\) 關鍵點。同 \(S\) 之內 dijkstra，不同 \(S\) 枚舉子集合并兩邊。暴力做是 \(m^2\) 的，但是由于這里 dp 隨第二維單調，而合并的卷積是 \(\max \{ f_i, g_j \} \rightarrow h_{\max(i, j)}\)，因此可以直接由單調性優化到 \(\mathcal{O}(m)\) 單次合并。

• \((f_i, f_j) \rightarrow f_{\max(i, j)}\) 的卷積，性質很好，很容易優化。

• 單調不一定凸，凸也不一定單調。不是一個概念。但都有可以用于優化的性質。

10.21

T2

特產聚會

顏色很少，那么求出每種顏色能給哪些人拿。如果視為二分圖，則二分答案之后轉化為二分圖多重匹配問題。考慮對人拆點用霍爾定理，則對于任意人的子集，能夠被這子集中任意一人取到的顏色的數量和不能少于 \(\text{popcount} \times ans\)。而要求這個數量和只需要一個高維前綴和就可以了。

• 拆點，霍爾定理。

T3

集合魔術

• 兩個凸函數最多只有兩個交點。

10.24

T1

旋轉排列

• \(n\) 個點排成環的方案數是 \((n - 1)!\)，也就是長度為 \(n\) 的只有一個置換環的排列數量。

• 錯排的遞推式：\(f_n = (n - 1)(f_{n - 1} + f_{n - 2})\)。

T2

樹的期望深度

定義狀態為 \(f_{i, j}\) 表示大小為 \(i\) 的子樹，深度為 \(j\) 的概率。轉移時合并兩棵子樹，考慮從小往大給兩棵樹分配編號。由于當編號變化時，需要每個點維持當前的父親不變的概率，因此提前預處理出 \(g_{i, j}\) 表示左邊加了 \(i\) 個點，右邊 \(j\) 個點時，原來的兩棵樹合并之后形態不變的概率。然后 \(f\) 的轉移就是平凡的了。

• 場上一直想狀態為編號為 \(i\) 的子樹期望深度，但根本沒法做。本來以為第一維記大小信息不夠，但其實概率可以之后再修改。

T3

蘋果樹

假設可以求出詢問時每個點子樹每種顏色的出現次數，我們考慮判定轉計數。我們計數最終湊出來 \(w\) 的方案數（取模，因此本質是哈希）。每個顏色有限制，容斥掉。容斥之后剩下的就是完全背包了，可以最開始預處理。而要求子樹顏色出現次數，可以平衡樹維護歐拉序，也可以直接定期重構。都能過。

T4

前綴和數組

考慮 \(k = 1\)。要求的東西很抽象，考慮組合意義：顏色為 \(1\) 到 \(n\) 的小球分別有 \(a_1, a_2, \cdots a_n\) 個，將所有球放在一塊隨機重排，記最終每個顏色的球最后一次出現的位置為 \(p_i\)，則列出 \(p\) 單調遞增的概率并對某種 \(a\) 的所有排列求和，稍微移項就會發現所求等于 \(\frac{1}{\prod a_i}\)。于是就只需要平凡的 dp 就可以了。

而 \(k = 2\) 也差不多，只不過要枚舉 \(a_1\) 是什么。為了保證 \(a_1\) 是 \(a_1\)，需要它的所有球的最后一次出現比其他顏色球的最后一次出現都靠前。這不太好做，考慮容斥掉，欽定一些東西在 \(a_1\) 之前。然后就可以直接對著值域帶容斥系數 dp 了，過程中記錄是否已經選過 \(a_1\) 即可規避對 \(a_1\) 的枚舉。

• \(k = 1\) 時的組合意義。

10.25

T1

還原圖

• \(n\) 個點（\(n\) 偶數）兩兩配對的方案數：\((n - 1)!!\)，考慮每次給最小的未匹配點選匹配。

T4

點點的計算

無論如何觀察到答案為 \(\text{lcm}(i - k + 1, i - k + 2, \cdots, i)\)。考慮分塊，預處理左右端點都為 \(B\) 的倍數的區間的答案，然后只需要每次往兩邊擴展就可以了。擴展是容易的，只需要維護當前 \(\text{lcm}\) 在每個質因子處的冪次然后每次加入時檢查是否能更新即可。

10.27

T1

異或和

考慮拆位，可以證明 \(f\) 值即為所有 \(a_i\) 的按位或乘以 \(2^{n - 1}\)。然后發現一堆 \([l, r]\) 中數的按位或都可以只用兩個數構造出來。然后分類討論每一段值是否能構造即可。

• 怎么做到異或問題不想拆位的？？？

T2

構造

考慮每次歸位最小的數，但在往前移的過程中可能提前歸為一些前面的數。具體地，\(p_i = i + 1\) 的數會被提前歸位。于是把所有這樣的數構成的連續段統一往前移一位即可。最開頭一段就不用動了。

但是這個東西真能保證不超過 \(\frac{n(n - 1)}{2}\) 嗎？？？

T3

松鼠公司

考慮直接 dp，\(f_{i, j}\) 表示 \(i\) 子樹內以 \(j\) 為左端點時的最小右端點。每次轉移暴力枚舉兒子的一個區間作為最左段，然后狀壓往后扔東西。然后只需要每次做完之后把包含別的區間的區間扔掉，就可以證明復雜度是對的。因為可以發現每個點的每個區間至少有一個端點是來自輕兒子的，只需要將其視為輕兒子貢獻上來的東西就可以根據啟發式合并的復雜度證明這一部分總共是一個 \(\log\) 的。

• 看似暴力東西的復雜度證明。

T4

樹上的游戲

首先先手必放在直徑中點，若中點在邊上就必敗。然后考慮枚舉后手放在哪。然后兩人的行動就是一段相向而行，然后一個人拐進側鏈。一個人拐進側鏈就是當且僅當這條側鏈中可以走的長度比另一個人接下來無論如何走能走的長度都更長。然后補的做法就是假的了。真做法還沒看。

10.28

T1

最小生成樹

首先容易調整證明每加入一種權值的邊，這種權值合并出來的連通塊只有一個。然后大概可以猜測一定存在一棵 MST 是鏈，并且所有邊的權值形如若給每個點賦上權值，則一條邊的權值是兩邊權值的 \(\max\)。假設點權按從 \(1 \rigtarrow n\) 的順序升序，那么顯然的貪心是把前若干點連成完全圖。只要邊的數量沒有超過 \((n - 1)(n - 2) / 2 + 1\)，則可以做到只有一條非 \(1\) 權的邊。否則需要考慮剩余權值的分配。初始先把所有點權設為 \(1\)，之后每次分配 \(n - 1\) 個權值。將這 \(n - 1\) 個權值要么全部扔給最后一個點，要么均攤給所有 \(n - 1\) 個點，兩者取優。剩下的權值也是在全給最后和均攤給后那么多個中取優。這樣就做完了。

• 想題一定要有條理，要動腦子。

T3

歸并排序

• 保證 \(x < y\) 的二維數點：\(n - \#[y_j < x_i] - \#[x_j > y_i]\)。不需要任何二維數據結構。

T4

排列櫥柜

考慮差分數組，則 \(w_i = \max \{ |d_i|, |d_{i + 1}|, |d_{i} + d_{i + 1}| \}\)。于是直接 \(f_{i, j}\) 表示前 \(i\) 個，最后一個差分是 \(j\) 是否可行。對著轉移瞪眼可以發現每層轉移之后合法數構成的連續段不會增多超過一個，而且變化形式也很簡單。于是直接用什么東西維護一下所有合法連續段就可以了。構造方案也可以根據轉移倒推。

• 據說寫暴力并觀察暴力代碼就可以想到考慮差分？那看來可能還是要寫點暴力。

10.29

T1

括號匹配

先把給定的括號匹配完，剩下的一定是一堆前括號加一堆后括號，還有問號穿插的形式。先把前面的問號盡量匹配掉前括號，再把后面的問號盡量匹配掉后括號，剩下的問號交替即可。

也可以反悔貪心，每次遇到一個問號，要是前面有未匹配的前括號就做后括號，否則做前括號。遇到一個后括號，如果前面有還剩的前括號就匹配，否則考慮前面如果有問號變成的后括號，就把這個問號反悔成前括號來和自己匹配，還能多一個前括號。

• 反悔。

T3

排列相似度

\(a_i \rightarrow b_i\)，則得到環和鏈。已經給定的環不用管，而鏈有四種，分別是開頭 \(0 / x\)，結尾 \(0 / x\)。而我們現在要把鏈接成環，那么唯一的要求就是兩個 \(0\) 不能接到一塊。于是考慮依次插入每種鏈。先把沒限制的 \(x \rightarrow x\) 鏈擺好，\(f_{i}\) 表示當前拼成 \(i\) 個環的方案數。初始 \(f_i = { \#(x \rightarrow x) \brack i}\)（第一類斯特林數）。接下來插入 \(0 \rightarrow x\)。注意這種鏈是可以自己成環的，于是要先枚舉有多少個用來自己成環，然后把剩下的東西插進已經有的環里，每多插進一個之后的可以插到后面的位置就會多一個，因此這里是上升冪。由于這里兩邊基本是獨立的，因此可以直接算出這里用這么多這種鏈多搞出 \(i\) 個環的方案數，然后只需要和前面卷起來就好了。剩下的 \(x \rightarrow 0\) 和 \(0 \rightarrow 0\) 都可以類似分析，除了最后一種不能自己成環之外都沒啥區別。

• 需要盡量嘗試讓問題（限制等）更清晰。

T4

票價系統

\(a_i = [c_i < c_{fa_i}]\)，則限制容易用帶權并查集刻畫為各個 \(i\) 之間的 \(f\) 的關系。之后二分答案 chk 的時候只需要 \(f_i\) 表示 \(a_i = 1\) 時自己的最小值，以及 \(g_i\) 反過來時的最大值。由于這兩個對稱，只記一個就可以了。剩下的轉移只需要討論兒子和自己的父邊是否在同一連通塊，合并它們的限制就可以求出自己的 \(f\)。構造方案也是容易的。

10.30

T1

知知穿夾克

顯然每天只需要保留三件。然后從只有一件的開始拓撲排序即可。

• 每天只保留三件。

T2

點分治

考慮直接做，觀察一個子樹中的點分樹。發現 \(x\) 子樹的點分樹應當是原樹點分樹的一個虛樹，而且原樹上只有 \(x\) 到根的鏈上會有非這棵虛樹上的點。也就是說我們只關注 \(x\) 在它子樹點分樹中的深度。而每次合并 \(x\) 的兩棵子樹的點分樹的時候，只需要把兩條到根鏈任意插起來就可以。當然 \(x\) 自己后面的東西的順序是不重要的，因此還要枚舉新的子樹的到根鏈有多少要放在 \(x\) 后面。暴力是三次方的，后綴和優化一下就平方了。

• 直接考慮子樹中的子問題。

T3

高爾夫球賽

無論如何觀察到只需要觀察到只需要對每個洞左上角 \(3 \times 3\) 矩形暴力 dp 即可。

• 也許可以打表注意到。