重視模擬賽以及補題

多口胡少寫代碼？感覺碼力還有大問題，多找點細節多的題目寫寫，碰到這樣的題容易腦子不清醒

5.4

[PA 2025] 考試 / Egzamin

666

\(\mathcal{O}(n^2)\) dp 很顯然，先從大到小排序，可以記 \(f_{i,j}\) 為考慮了前 \(i\) 個，做對了 \(j\) 個的概率，有轉移

結論：如果我們把 \(\ge \epsilon\) 的 dp 值都去掉，那么有效的 dp 值只有 \(\mathcal{O}(\sqrt{n\log \frac{1}{\epsilon}})\) 個

太神秘了，證明需要概率論知識（切爾諾夫限），等我變強了再來學吧

[USACO22OPEN] Hoof and Brain P

難

能無限走的充要很好找，就是存在兩條不交路徑，使得詢問點能夠到達兩個不交環上

考慮如何更好的刻畫這個東西？我們可以考慮一個類似支配的玩意，如果 \(u\) 想要無限走，必須經過點 \(v\)，那么我們說 \(v\) 支配 \(u\)，可以記支配 \(u\) 的點集為 \(S_u\)，那么充要條件就變成 \(S_u \cap S_v = \emptyset\)，我們只需要判斷集合之間是否有交

發現支配具有傳遞性： \(u\) 支配 \(v\)，\(v\) 支配 \(w\)，則有 \(u\) 支配 \(w\)

另外，支配具有偏序性：\(u,v\) 支配 \(w\)，那么有 \(u\) 支配 \(v\) 或 \(v\) 支配 \(u\)

因此，我們可以發現最終的支配關系是一個樹狀物，那么我們可以把支配關系變成無向關系，那么我們兩個點的支配集有交，當且僅當兩個點在同一個支配關系上的連通塊內

可以用set維護所有點的入點集合和出點集合，用并查集維護支配圖上的連通性，用啟發式合并的方式便可以做到 \(\mathcal{O}(n\log^2n)\)

[AGC068E] Sort and Match

需要靈光一現

注意到 \(x\)、\(y\) 中每個數出現次數相同，那么我們可以把他當作點的出度和入讀，又由于 \(y\) 是有序的，那么我們每一個序列都和一個歐拉圖一一對應，即構成雙射，歐拉圖并不好計數，而歐拉回路是比較好計數的，而我們的序列其實也和歐拉回路一一對應

考慮 dp，記 \(f_{i,j}\) 表示前 \([1,i]\) 個點的歐拉回路走完了，且我當前用了 \(j\) 條邊，記 \(g_{i,j}\) 表示走到 \(i\)，用了 \(j\) 條邊，轉移復雜度是 \(\mathcal{O}(n^3m)\)

而他要求的東西比較奇怪，我們需要把上面的 dp 倒過來，在轉移結束后統計答案

5.5

幽默模擬賽

模擬賽

T1

我超，原

還是說一下思路吧

發現每個點雙上邊權肯定一樣，那么問題就變成了形如 $\sum\limits a_i\times w_i=K $，要求最小化 \(\sum\limits b_i\times w_i^2\)，其中 \(a_i\) 為點雙大小減一，\(b_i\) 為這個點雙上的邊數

那么我們就可以做背包，發現 dp 值在膜 \(a_i\) 下是凸的，那么我們可以按膜 \(a_i\) 的剩余系把 dp 值劃分開，然后做一個 \(\min+\) 卷積

由于 \(\sum\limits a_i=n-1\)，那么不同 \(a_i\) 的個數是自然根號級別，最后總復雜度就是 \(\mathcal{O}(n\sqrt n+n\log^2 n)\)

T2

幽默構造

首先我們可以把格子分成兩類，一類是四面被其他積木圍起來的，比如

.v.
>.<
.^.

還有一種是格子上有積木的，比如 ^

從邊界開始考慮，我們觀察到邊界上的格子必須都是第二種，因為第一種會要求邊界外有其他格子，而且邊界上不可能出現形如 <^> 的情況，因為這樣的話，>、< 向右向上延伸出去之后，出現 >< 相撞的情況

這樣我們的邊界肯定是

^>>>
^..v
^..v
<<<v

這樣的螺旋狀，而且肯定是

^>>>>
^.v.v
^>.<v
^.^.v
<<<<v

在螺旋的內層 ^、>、<、v 與 . 交替圍成一個圈，所以邊長不可能是偶數

那這樣，我們可以考慮拆分成更小的子問題，也就是填上了一層層螺旋，這樣每次可以做到長、寬減六

而對于長為 \(9\) 或 \(11\)，我們各有一種構造循環的方法，太長了，這里不填了

而有解的條件是什么，首先，每個積木大小為 \(3\)，那么需要滿足 \((n,m)\) 膜 \(3\) 為 \((0,0)\) 或 \((2,2)\)，同時滿足其為奇數，那么就是要滿足 \((n,m)\) 膜 \(6\) 為 \((5,5)\) 或 \((3,3)\)，而這種兩種情況正好對應我們 \(9\) 和 \(11\) 的兩種構造方案，再加上 \(2*2\)、\(5*5\)、\(3*3\) 三個特例，就可以完成此題

T3

what can i say

環沒啥用，區間不交可以放到序列上做，那 \(\mathcal{O}(n^2)\) 的區間 dp 比較顯然，不詳細說了

數據隨機，答案不會太大，大概是 \(\mathcal{O}(\sqrt n)\) 級別的，而且答案具有單調性，那么我們可以轉置一下，優化 dp 狀態，即 \(f_{l,i}\) 表示以 \(l\) 為開頭，答案為 \(i\) 的最靠左的右端點，轉移比較簡單，這樣總復雜度就是 \(\mathcal{O}(n\sqrt n)\)

[ARC160D] Mahjong

令 \(a_i\) 為以 \(i\) 為左端點進行區間加的次數，\(b_i\) 為單點加 \(K\) 的次數，注意到所有滿足 \(a_i<K\) 的方案都是合法的，那么問題就變成了計數 \(\sum\limits a_i+b_i=m,\forall i,a_i<K\)

律師給我講過這個東西，考慮容斥，我們欽定 \(i\) 個 \(a\) 的值大于 \(K\)，其他的隨便填，答案的式子就是

[ARC140E] Not Equal Rectangle

難飛了

閾值分治，我們取一個質數 \(P\)，定義一個單元格 \(G_k\)，滿足 \(G_{k_{i,j}}\equiv (i+j+k) \pmod P\)，把行列按 \(P\) 分塊，如果某一塊的位置為 \((i,j)\)，那么在這個地方填 \(G_{i\times j}\)

取 \(P=23>\sqrt n\)，便可以通過

5.6

模擬賽

T1

換根

T2

有點好玩

有一個性質，若 \(|x \oplus y|\) 為偶數，那必定存在一個 \(z\)，使得 \(|x \oplus z|=|y \oplus z|=\frac{|x\oplus y|}{2}\)

這啟發我們可以做一個雙向 bfs，我們把所有的原集合中的點放到隊列里，每次更改一個二進制位，如果碰到一個沒有遇到過的點，把他放到來時點所在的并查集中，碰到一個走過的點說明可能遇到了 \(z\)，此時我們將兩個并查集合并，這樣我們也就完成了一個 kruskal 的過程，求出最小生成樹

T3

把 \((l,r)\) 的狀態放到網格上，單調區間對應的點都是必敗的，在網格上構成一個階梯狀物，階梯外面的第一層都是必勝態，階梯拐點所對應的對角線都是必敗態，其他的狀態可以遞推，而且有很多都是比敗態必勝態交替出現，二分出來然后分討就完了

CF1060F Shrinking Tree

對每個點 \(u\) 分別考慮，同時我們發現，只有在抉擇 \((u,*)\) 時，會使 \(u\) 存活下來的概率減半，而其他的刪邊操作實際上是無關緊要的，而且這個時候 \(u\) 對應的另一個點已經成為了 \(u\) 的相鄰點，那么我們稱 \((u,*)\) 后保留下來 \(u\) 的操作為一次“擴張”，因為這個操作過后，\(u\) 所在的被刪的邊形成的連通塊會與其他的連通塊合并。記“擴張”次數為 \(c\)，則最后我們 \(u\) 存活下來的概率會乘上 \(2^{-c}\)

我們考慮一個刪邊 \((u,v)\) 操作能成為“擴張”的條件是什么，可以發現，這時候 \((v,fa_{v})\) 被刪除的時刻需要大于所有 \(v\) 到根鏈上的邊被刪除的時刻，于是可可以把邊的刪除時刻放到點上，可以記這個時刻為 \(p_v\)，則條件就是到根鏈上 \(p_{x}\) 的最大值小于 \(p_v\)

考慮設計狀態 \(f_{u,i}\) 表示 \(u\) 子樹中，我欽定其中 \(i\) 條“擴張”的邊，發現這樣不方便欽定 \(p_i\)，于是我們還可以考慮記一個 \(j\)，表示到根鏈上的最大值為 \(j\)，這里是欽定他的相對順序

轉移是一個關于 \(i,j\) 兩維的樹上背包，我們做背包時有轉移系數 \(\binom{j_1+j_2}{j_1}\binom{siz_u+siz_v-j_1-j_2}{siz_u-j_1}\)

接著我們去枚舉 \(u\) 的點權 \(val\)，也是在子樹中的相對順序，若 \(val>j\)，則不合法，若 \(val=j\)，則這是一次擴張，\(i\leftarrow i+1\)，新的限制可以任意選，但不能超過 \(j\)，若 \(val<j\)，則不是一次擴張，\(j\leftarrow j+1\)

答案為 \(\frac{\sum\limits_{j=0}^{n-1}\frac{f_{root,j,0}}{2^j}}{(n-1)!}\)，這樣可以做到 \(\mathcal{O}(n^5)\)

再用一些優化技巧可以優化到 \(\mathcal{O}(n^3)\)

[ABC257Ex] Dice Sum 2

先不管最優化，考慮這個期望到底是啥，刻畫一個生成函數，對于第 \(i\) 個骰子，其生成函數為 \(F_{i}(x)=\sum\limits_{j=1}^{6}x^{A_{i,j}}\)，那么總的概率生成函數 \(P(x)=\prod\limits_{i=1}^{k} F_i\)，要求的是期望的平方，那就有 \(E(x)=P'(x)+P''(x)\)

那期望化出來之后是形如 \(E(1)= \left( \sum x_i \right)^2+\sum y_i\) 的樣子

這里有一個神秘結論，對于一種方案集合 \(S\)，我們肯定存在一個實數 \(c\)，滿足 \(\forall i\in S,j\notin S,cx_i+y_i>cx_j+y_j\)

那我們枚舉所有的 \(i,j\)，把 \(c\) 從小到大排序，每次會有 \(\mathcal{O}(1)\) 的變化，這樣是好維護的，復雜度為 \(\mathcal{O}(n^2\log n^2)\)

5.7

模擬賽

T1

幽默數據

\(\mathcal{O}(n^2)\) 的 dp 很搞笑，很顯然有轉移 \(f_{i,j}\leftarrow \min(f_{i-1,j},f_{i-1,j-1})+|a_i-j|\)，發現這是一個凸函數，只需要做到整體右移然后加上一個絕對值函數就可以了，可以用平衡樹大力維護

這樣做太不爽了，數據還比較隨機，打個表發現最小值大概在很后面的位置，dp 的時候取后 600 個點就完了

T2

純難

\(n\times p\) 啟示我們可以每 \(p\) 個點分組，分成 \(n\) 組，對其中的一組進行分析，考慮一個置換 \(Q=\left\{ 2,3,4,...,P-1,1 \right\}\)，發現我們如果置換了 \(P\) 次，這樣會有 \(P\) 的貢獻，而在膜 \(P\) 下貢獻會變成 \(0\)

什么情況下不會被消掉呢？發現當且僅當每一組中，每個點互相之間沒有連邊，而且一個點到另一組點的連邊肯定是全連或者一個都不連，那我們每組點可以縮成一個點

縮點之后只需要數沒有長度為 \(P\) 的環的方案數？其實不然，我們發現只要在組之間存在一個奇環，可以每次在環中增加兩個點，最終搞出來一個長度為 \(P\) 的環

于是就變成了數大小為 \(n\)，有標號的二分圖個數，可以做到 \(\mathcal{O}(n^2)\)

對于 \(n\ge P\) 來說，有 \(ans(n)=ans(n-p+1)\)，然后就做完了

T3

？

可以把每個數根據下標和權值放在坐標系上，發現最后會連成一張全是三角形的平面圖，可以發現有奇輪圖的都不能三染色，有三角形的都不能三染色，這樣我們每次要做的就是判斷是否有存在這樣一個奇輪

考慮在奇輪的中心統計，發現這個中心肯定要處在圖的內部，也就是需要滿足它連出去的有四個點 \((l_1,l_2,r_1,r_2)\)，而且這個點的度數需要是奇數，那么包含 \([min(l_1,l_2),max(r_1,r_2)]\) 這個區間的大區間的染色數都為 \(4\)

\(3,2,1\) 的情況都是容易處理的，把這些區間拉出來，二分一下查一個區間和就完了，也可以寫雙指針做到線性

P10005 基礎寄術練習題

還是能學一些東西的，\(\prod\limits_{i=1}^{n}\frac{a_i}{s_i}\) 這個東西的組合意義有點聰明，這種后效性的東西牢記從后往前考慮

先考慮 \(k=1\)

\(f(a)=\frac{1}{\prod\limits_{i=1}^{n}s_i}\) 這個權值太神秘了，直接做肯定完蛋了，我們考慮給他一個組合意義

一種構造是 \(g(a)=\prod\limits_{i=1}^{n}\frac{a_i}{s_i}\)，這個東西的組合意義是，考慮一個序列，其中有 \(n\) 種數，每種數的個數是 \(a_i\)，將其隨機打亂，記每種數最后出現的位置為 \(R_i\)，我們強制 \(R_i<R_{i+1}\)，上面這個式子，從后往前考慮，對于最后一個位置，第 \(i\) 種數成為當前序列中最后一個數的概率是 \(\frac{a_i}{s_i}\)，這樣總的概率就是乘積，而對于一個 \(a_i\) 構成的集合，他的概率和就是 \(1\)，也就是有 \(\sum g(a)=1\)，那就有 \(\sum f(a)=\frac{1}{\prod a_i}\)

這樣我們就可以背包了，可以簡單做到 \(\mathcal{O}(n^2)\)

對于 \(k=2\)，這時候相當于給 \(f(a)\) 乘上了 \(a_1\)，那我們實際上需要計數的就是確定 \(a_1\) 必須在序列的第一個位置出現，而且不用管 \(R_i\) 列，那我們需要滿足的就只有 \(R_i>R_1\)，考慮容斥，我們去欽定一個集合 \(S\)，\(S\) 中數的 \(R\) 大于 \(R_1\)，那么方案數就是

第一個多項式系數指的是我們放那些比 \(a_1\) 靠后的方案，第二個式子是放 \(a_1\)，但是要保證第一個放在序列中的最前面，第三個式子是沒有欽定的隨便放

上式可化為

那我們最后的答案就是

這樣我們最后考慮一個 dp，記 \(f_{i,j,k,0/1}\) 表示考慮了值域的前 \(i\) 個數，\(\sum\limits_{i\in S}a_i=j\)，\(|S|=k\)，最后一維 \(0/1\) 為 \(a_1\) 是否已經選到 \(S\) 中，可以做到 \(\mathcal{O}(n^4)\)

5.8

這一天的沒來得及寫，印象已經不太深了，隨便寫寫得了

模擬賽

T1

難題，做了三個小時

觀察一些性質發現可以線段樹去維護單調棧，或者直接線段樹合并

T2

油墨線性遞推，不過知道了線性遞推數列某一項的求法，就是求

\(f\) 為這個數列的特征多項式，即 \(a_n=\sum\limits_{i=1}^{k}a_{n-i}\times f_{i}\)

T3

阿斯頓法國紅酒快樂，維護甲方和浪費我，和精神復活卡我把骨科病房，阿喀琉斯激發了發表

5.9

模擬賽

T1

我操，原

不說了

T2

挺簡單的，但是為什么沒想到

首先發現如果我們已經分割成了若干個段，每個段的 \(0\) 的個數為 \(S_0\)，\(1\) 的個數為 \(S_1\)，那么我們的答案大概為 \(\sum\limits \max\left \{ S_{0_i},S_{1_i} \right \}\)，但其實這時候會出現一個問題，我們的策略其實可能是選擇一段 \(01\) 都有貢獻，其他的只選 \(0\) 或 \(1\)，但其實我們只需要按照每一段只選 \(0\) 或只選 \(1\) 的情況算就行了，最后再讓 \(\forall i\ge 2,ans_i\leftarrow \max \left\{ ans_i,ans_{i+1} \right\}\)，因為對于段數大于 \(2\) 的情況，我們實際上可以合并相鄰的全 \(0\)、全 \(1\) 兩個段，讓段數減一，而貢獻不變，這個策略做到 \(\mathcal{O}(n^2)\) 是簡單的

這樣我們可以把全相同的段縮起來，發現其實最終的狀態其實都是一樣的，也就是每個段都獨立的情況，我們可以考慮從最終狀態往前推，每次我們的決策就是刪去一個獨立的段，同時他相鄰的兩個段會被合并起來，這樣會有段數減二，而答案加上這個點上的權值

而對于邊界上的點，我們只會有段數減一，但這個情況的處理其實是簡單的，枚舉邊界上的點選或不選一共四種情況即可

然后就是一個可以反悔貪心的題了，我們搞一個小根堆，每次取出最小的值，然后合并兩個相鄰的，我們合并一段后可以把相反的決策加進小根堆里

那這題就做完了，關鍵在于后面的反悔貪心部分

T3

？？？？？？？？？？？？？？

糖丸了

孫神純神

把所有的點之間的邊極角排序，我們要取出一個凸包，那么凸包上每個邊是有序的，這樣可以直接設狀態 \(f_{i,j}\) 表示凸包的起點為 \(i\)，終點為 \(j\)，這樣我們可以保證每次轉移的時候不會出現凹的情況，就不用在 dp 的時候多記一維了

那做到 \(\mathcal{O}(n^3)\) 就很簡單了

5.11

模擬賽

T1

唐中唐，找到每個顏色 LCA，把這些點到他們 LCA 的路徑上的點都縮起來，隨便 dp 一下就做完了

T2

純難

首先手玩一下可以發現，我們只有在 \(a\)，\(b\) 從低位到高位考慮二進制位不同時是有貢獻的，我們把這些子樹拉出來，發現每一輪操作都是子樹對位交換，這樣總的好的序列的個數就是 \(2^{\sum siz}\)

這樣我們就可以考慮一個貪心，從前到后枚舉每一位，我們可以算出固定當前位置上的數為 \(v\)，會造成的貢獻是多少，枚舉這一位的值復雜度很搞，而且這個貢獻該怎么算？

這一位的可能的值是 \(\mathcal{O}(n)\) 級別的，而且我們可以 dfs 一遍搜出所有的值，我們把交換兩個位置進行連邊，若那些交換或者不交換對于字典序無影響的邊的個數為 \(m\)，那每次的貢獻就是 \(2^m\)，這樣我們可以在 \(\mathcal{O}(n2^n)\) 的復雜度完成此題

T3

簡單題，為啥沒想到呢

考慮一手霍爾定理，我們在 dp 時去強制一些區間內的值全都 \(>v\)，這樣對于兩段 \(m\) 上的區間之間的轉移，若前一段區間的右端點為 \(R\)，后一段的左端點為 \(L\)，我們只需要滿足 \(\min\limits_{l,r,[l,r]\subset [L+1,R-1]}\left\{\sum v-w_i-(r-l)\right\}\ge 0\)，前綴和一下可以線段樹優化轉移，然后就做完了

[Ynoi2008] rdCcot

先考慮如何對連通塊進行計數，我們有兩種數連通塊的方法，一種是點減邊，另一種是這道題需要用的“代表元”思想

我們考慮去欽定“最小元”，比如連通塊中編號最小的啥的，對于區間查詢數區間中“最小元”的個數

記每個點的 bfs 序為 \(b_i\)，考慮用連通塊中 \(b_i\) 最小的點最為這個連通塊的代表元，那有一個結論，對于點 \(x\)，若其與 bfs 更小的點五連邊，則我們可以令他為代表元，這樣計數不會重

為什么呢？這里給出一個引理：對于 \(b_i<b_j<b_k\)，若 \(\text{dis}(i,k)\le C,\text{dis}(j,k)\le C\) 則 \(\text{dis}(i,j)\le C\)

為什么選其他的編號方法不行呢，因為這里我們連出去的的點是距離小于等于 \(C\)，而不是不在連通塊中的點，而其他的編號會出現記重的情況

為了做到區間詢問，我們需要預處理出來 \(pre_i\)、\(suf_i\) 分別表示 \(\max\limits_{j<i,b_j<b_i,\text{dis}(i,j)\le C} j,\min\limits_{j>i,b_j<b_i,\text{dis}(i,j)\le C}j\)

為了去掉 \(\text{dis}(i,j)\le C\) 的限制，我們可以點分治把 \(\text{dis}(i,j)\) 變成 \(dep_i+dep_j\)，在每個分治中心，我們按 \(dep\) 從小往大掃，維護一個以節點標號為下標，同時存儲 \(b_i\) 最小值的平衡樹，每次左一個平衡樹上二分即可

求出 \(pre\)、\(suf\) 之后，我們只要進行一個二維數點就行了，復雜度是 \(\mathcal{O}(n\log^2n+m\log n)\)

5.12

好吃的題目

這不是我們貓樹嗎

CF1142E Pink Floyd

有點好玩

首先考慮所有的邊都沒被定向該怎么做，我們可以取出一個點當起點，然后隨便取一個沒有被問過的點，詢問其與當前點的連邊情況，如果那個點有連向當前點的邊，那么我們可以直接把起點變成那個點，當前點扔掉不去管他，如果最后只剩下一個點，那這個點就是我們想要的答案

但是有邊被定向很難處理，而且有顏色的限制，如果每個粉色連通塊都是 DAG，那么我們可以做一個拓撲排序的過程，這樣我們每次詢問的邊可以保證沒有被定向，因為不會有一個強連通分量中的點同時出現在可能成為起點的集合當中

處理強連通分量，其實也是簡單的，我們可以先縮點，然后在拓撲排序的過程中，對于單個強連通分量，我們任意選取一個點放到可以成為起點的集合中，若這個強連通分量中又出現了入度為零的點，把他加進集合中即可，如果這個強連通分量沒有入度為零的點，我們接著隨機取點即可

CF1034D Intervals of Intervals

*3500 的數據結構？

怎么感覺我做過，這幾個關于單調性的優化還是挺有啟發性的

我們先去考慮一個更弱的問題，有若干個詢問，每次詢問一個區間 \(L,R\)，求 \([L,R]\) 中的區間并，考慮把詢問離線下來，然后從左往右掃右端點，對于每個左端點 \(L\)，維護其區間并的大小 \(f(L)\)，即 \(\text{siz}(L,R)\)，接著對于序列上的每個點，維護 \(lst_i\) 表示覆蓋 \(i\) 這個位置的區間最晚出現的時刻，這其實是一個顏色段均攤的過程，我們可以用 std::set 快速維護（所謂的珂朵莉樹），每次更改一段區間的 \(lst\) 值，只需要用樹狀數組維護前綴加減，單點求值就行了，這樣可以把這個弱化版的問題做到 \(\mathcal{O}(n \log n)\)

由于 \(k\) 比較大，我們可以考慮二分區間并的大小 \(mid\)，那我們每次要做的就是查詢區間并比 \(mid\) 大的區間個數，顏色段均攤的過程我們可以只做一遍，記錄下來 \(lst\) 的變化即可，那么可以直接掃每個右端點 \(R\)，由于 \(f(L)\) 關于 \(L\) 是單調的，我們可以二分出每個 \(R\) 的貢獻，這樣總的復雜度是 \(\mathcal{O}(n\log V\log^2n)\)，二分 \(k\) 一個老哥，樹狀數組一個老哥，二分 \(L\) 一個老哥

考慮如何優化，發現 \(f(L)\) 關于 \(R\) 也具有單調性，那我們其實可以雙指針雙指針掃一遍，不用去二分 \(L\) 了，這樣復雜度少一個老哥

緊接著，我們樹狀數組要做的是前綴加，單點查，我們可以差分，變成全局加，單點修，前綴和，這樣我們在移動 \(L\) 的過程中，可以快速維護出 \(f(L)\) 的值，這樣樹狀數組的老哥也被我們優化掉了

最后我們的復雜度可以做到 \(\mathcal{O}(n \log V)\) 了

『PG2』模擬最大流

666

最大流=最小割，之后狀壓 \(f_S\) 表示從源點走到 \([i-k,i-1]\)，\(S\) 中的點與源點相連的最小割，直接枚舉子集轉移即可，復雜度 \(\mathcal{O}(n3^k)\)

CF1647F Madoka and Laziness

首先發現最大值肯定是其中的一個峰，那么我們可以固定最大值的位置 \(x\)，枚舉另一個峰 \(y>x\)（\(y<x\) 再做一遍就行了），判斷是否有解，發現最后的兩個單峰序列肯定是 \([1,x]\) 中兩個單增序列，\([y,n]\) 中兩個單減序列，在 \([x+1,y]\) 中一個單增一個單減

那我們 \([1,x]\)、\([y,n]\) 的 dp 情況是類似的，記 \(f_i\) 為 \(i\) 不是現在單調序列的終點時，單調序列的終點最小值是多少，舉 \([1,x]\) 的情況為例，若 \(a_i<a_{i+1}\) 則 \(f_{i}\rightarrow f_{i+1}\)，若 \(f_i<a_{i+1}\) 則 \(a_{i}\rightarrow f_{i+1}\)，我們這樣兩遍就行了

對于中間的部分，我們從 \(x\) 往右做，則可以記 \(f_{i,0/1}\) 分別表示當前數為單增區間的終點/單減區間的終點，那么有轉移

\(f_{i,0}\rightarrow f_{i+1,0}\)（ \(a_i<a_{i+1}\) ）

\(f_{i,1}\rightarrow f_{i+1,1}\)（ \(a_i>a_{i+1}\) ）

\(a_{i}\rightarrow f_{i+1,0}\)（ \(f_{i,1}<a_{i+1}\) ）

\(a_{i}\rightarrow f_{i+1,1}\)（ \(f_{i,0}>a_{i+1}\) ）

這樣就做完了，感覺真不難

CF526G Spiders Evil Plan

感覺這個題用的東西我都見過

發現我們肯定是選出 \(2y\) 個葉子，這些葉子互相連邊成 \(y\) 條路徑，其形成的連通圖中最大的邊數就是我們想要的答案

這里有一個結論，如果我們選了 \(2y\) 個葉子，那么肯定能選出 \(y\) 條路徑使得這些路徑的并是樹上的一個連通塊，可以考慮調整法，對于一個沒有被覆蓋的邊，我們可以找到他分成的兩個子樹中的兩條沒有交的路徑，交換對應點，這樣只會使連通塊的大小增加

那我們暴力的做法，就是以 \(x\) 為根，選出 \(2y\) 個葉子，使得其連通塊大小最大，這是個經典問題，我們可以以 \(x\) 為根進行一個長剖，直接取前 \(2y\) 條長鏈，這樣就可以求得以 \(x\) 為根時的答案

然后我們會發現，其實這 \(2y\) 條路徑中一定會有一條路徑是以樹上直徑的一個點為端點的，這比較顯然，那我們可以定這個點為根，選出 \(2y-1\) 個葉子，使得路徑并包含 \(x\) 即可

直接取前 \(2y-1\) 個長鏈肯定不行，因為會出現不包含 \(x\) 的情況，我們其實可以取前 \(2y-2\) 條長鏈，即去掉了最短的那個長鏈，選擇出 \(x\) 子樹中最遠的那個葉子，然而這樣還是會出現問題，需要取出 \(2y-1\) 條長鏈，并從 \(x\) 往上跳到第一個路徑并中的點，然后把其別的子樹中的邊都去掉，我們的答案肯定是這兩種情況之一

那這題就沒了，還是有點好玩的

CF923E Perpetual Subtraction

這有點太強了，這個積分真太幾把牛批了

CF1810G The Maximum Prefix

5.13

沒來得及寫，不寫了

模擬賽

T1

唐

T2

這輩子有了

T3

啥必三角剖分毀我青春

學了一個三角剖分的方法，把所有的二度點找到，加入一個隊列中，我們每次取出來一個，把這個點刪掉，然后更新二度點，這樣我們每次可以割出來一個三角形，就能三角剖分了，感覺還挺聰明的

先考慮三角剖分，把原來不在圖中的邊的邊權設成 \(\infty\)，然后考慮一個分治，我們去找一條邊 \((x,y)\)，然后把整張圖分成兩部分，那么我們對于在兩邊的點 \(u\in L,v\in R\)，他們之間的最短路肯定要經過 \(x\) 或者 \(y\)，那么他們的貢獻就是 \(\min\left \{\text{dis}(x,u)+\text{dis}(x,v),\text{dis}(y,u)+\text{dis}(y,v)\right\}\)，那可以對于左部點，按 \(\text{dis}(x,u)-\text{dis}(y,u)\) 排序，右部點按 \(\text{dis}(y,v)-\text{dis}(x,v)\) 排序，掃一遍就行了，然后我們遞歸地去做，因為其對偶圖是一個二叉樹，那我們可以直接按邊分治的流程去做，復雜度就是 \(\mathcal{O}(n\log^2n)\) 的

5.14

模擬賽

沒打

T1

T2

概率生成函數

首先考慮一手 minmax 容斥，如果記第 \(i\) 個串出現的時刻為 \(a_i\)，我們原來要求的其實是 \(E(\max a_i)\)，即 \(E(\max\limits_{i\in S} a_i)=\sum\limits_{\emptyset \ne T\subseteq S} (-1)^{|T|-1}E(\min\limits_{i\in T}a_i)\)。我們去枚舉集合 \(T\)，記 \(g_i\) 為進行了 \(i\) 次，仍未停止的概率，記 \(f_{i,j}\) 為考慮第 \(i\) 個串，恰好進行了 \(j\) 次，這個串成為集合中第一個出現的串的概率，那么有轉移 \(g_{n+1}=g_n-\sum\limits_{i\in T} f_{i,n+1}\)，考慮 \(g,f_{i}\) 的生成函數 \(G(x),F_i(x)\)，則有 \(xG=\sum\limits_{i\in T}F_i+G\)，我們最后要求的答案，其實就是 \(\sum\limits_{i\in T} F_i'(1)\)，那我們對于上面的遞推式兩邊同時求導，可得

\(G+xG'=\sum\limits_{i\in T}F_i'+G'\)，代入 \(x=1\) 可得 \(G(1)=\sum\limits_{i\in T}F_i(1)\)，那我們要求的就變成了 \(G(1)\) 的值

考慮一個位置 \(i\)，我們向他后面加上 \(s_j\)，那么有

\(\forall j\in T,\sum\limits_{i}g_i\times (\frac{1}{26})^{|s_j|}=\sum\limits_{i}\sum\limits_{k}\sum\limits_{p} [suf(s_k,p)=pre(s_j,p)]\times f_{k,i+p}\times (\frac{1}{26})^{|s_j-p|}\)

前面一個式子就是我們往 \(i\) 后面加上 \(s_j\)，后面的式子就是因為你加 \(s_j\) 時，可能 \(s_j\) 的前綴和錢 \(i\) 個字符的后綴可以拼成一個在 \(T\) 中的串，這兩種概率是相同的

由于我們要求的 \(G(1)\) 就是 \(\sum g_i\)，而且 \(g\) 和 \(f_i\) 實際上都是有無窮項的，那么我們可以設 \(\sum\limits_{i} g_i\) 為 \(sG\)，\(\sum\limits_{j} f_{i,j}\) 為 \(sF_{i}\)

那么從上面那個式子可以推出來

\(\forall j\in T,sG=\sum\limits_{k}\sum\limits_{p}[suf(s_k,p)=pre(s_j,p)]\times 26^p\times sF_k\)

以及我們一開始就有的

\(\sum sF_i=1\)

這樣我們有 \(|T|+1\) 個元和 \(|T|+1\) 個線性方程，可以高消出來，那我們總復雜度就是 \(\mathcal{O}(2^nn^3)\)

T3

首先定根，那我們可以確定出來所有點的深度，我們考慮把這個樹分層，考慮每一層的點集 \(A\)，與其上一層的點集 \(B\) 的連邊情況，若 \(i\in A\)，\(j\in B\)，\(j\) 是 \(i\) 的父親，那么要滿足 \(\forall S\subseteq A\)，\(\text{ask}(i,S)=\text(j,S)+|S|\)，那我們把 \(A\) 隨機平分成 \(A_l\) 和 \(A_r\) 兩個集合，每個點問一遍 \(\text{ask}(u,A_r)\)，把按 \(\text{ask}(u,A_r)\) 分組，每組的大小不會超過 \(\frac{|A_r|}{2}\)，然后遞歸去做，這樣我們的詢問次數是 \(\mathcal{O}(n\log n)\)，詢問集合大小是 \(\mathcal{O}(n^2)\)，但是不會跑滿