10.23

擺完了，除了模擬賽就是幽默題，今天一共做了一個有難度的題

模擬賽

太失敗了，沒開 T4

T1

考慮當區間足夠大的時候，很有可能所有的數都能被湊出來，這個區間長度的 \(B\) 期望為 \(\sqrt[4]{P}\)

現在提出 \(\mathcal{O}(nB)\) 的做法，考慮 meet in the middle，記 \(lst_{v}\) 為滿足 \(a_{i}\times a_{j}=v\wedge i\le j\) 的最小的 \(i\)，掃一遍即可

T2

這是一個閉合回路，所以可以設一個零勢能點，不妨令 \(a_1=0\)，對于 \(i>1\)，有 \(a_{i}=a_{i-1}+w_{i}\)，那么我們每次操作可以變為給 \(c_i\) 加一并給 \(c_j\) 減一，其代價為 \(a_i-a_j\)，于是問題就變成求 \(\sum c_i\times a_i\) 的最大值，滿足 \(\sum c_i=0,c_i\in[-x,x]\)，發現 \(a\) 的順序無關緊要，于是可以排序，貪心的選擇前半的系數為 \(-x\)，后半的系數為 \(x\)，不難發現此時如何調整都不優，復雜度線性對數

T3

武帝了。

記 \(h(x)=\sum_{i,j}\frac{a_ia_jx^{c_i+c_j}}{c_i+c_j}\)，那么 \(f(a)\) 就是 \(h\left(\frac{2}{3}\right)+h\left(\frac{1}{3}\right)+h(1)\)，我們能夠說明，\(f(a)=0\) 當且僅當對于所有的 \(v\)，都有 \(\sum [c_i=v]a_i=0\)

如何推到？你發現 \(h\) 下面那個分母實在是太幾把丑了，而你 \(x\) 指數上又有 \(c_{i}+c_j\)，這啟發我們直接求導，可以得到

你發現對于 \(x>0\)，有 \(h'(x)\ge 0\)，當 \(x=0\) 時，有 \(h(x)=0\)，所以有 \(h(x)\ge 0\)，那么為了使得 \(h\left(\frac{2}{3}\right)+h\left(\frac{1}{3}\right)+h(1)=0\)，必須要滿足 \(h\left(\frac{2}{3}\right),h\left(\frac{1}{3}\right),h(1)\) 全都是 \(0\)，此時你也要滿足 \(h'(x)=0\)，所以能得到

那么現在就是 \(c_i=1\) 的問題，即求 \(\sum t_id_i=S,t_i\ge 0\) 的整數解的個數，由于 \(n\) 和 \(d_i\) 都很小，考慮一個經典的背包轉數位 dp，記 \(D=\max d_i\)

從低到高考慮，記 \(f_{w,v}\) 為考慮了前 \(w\) 位，進位為 \(v\) 的方案，這樣可以做到 \(\mathcal{O}(qn^2D\log S)\)

考慮 meet in the middle，記 \(f_{S,v}\) 為前 \(B\) 位為 \(S\)，進位為 \(v\) 的方案，詢問的時候再合并就可以了，總復雜度 \(\mathcal{O}(n^2D\sqrt S+qnD)\)

T4

求所有層中的括號匹配，我們發現如果 \(u<v<w\) 且 \(w\) 在兩層中分別和 \(u,v\) 匹配，那么讓 \(w\) 在這兩層中只與 \(u,v\) 中更低的那一個匹配是不劣的，于是就能轉化成一個匹配問題，給你一些 \(x\)，后面的可以向前面匹配，其貢獻為后面的 \(x\) 減掉前面的 \(x\) 的二倍，問最大權任意匹配

考慮費用流建模：

• \(S\rightarrow i,(1,2x_i)\)
• \(i\rightarrow i-1,(+\infty,0)\)
• \(i\rightarrow T,(1,-2x_i)\)

我們要求出最大費用任意流，考慮把他轉化成最大費用最大流，也就是讓費用非負，發現我們可以把所有沒流滿的 \(i\) 都流了 \(S\rightarrow i\rightarrow T\)，這樣不影響答案，這時候所有的 \(i\rightarrow T\) 都流滿了，于是我們可以重新建模

• \(S\rightarrow i,(2,2x_i)\)
• \(i\rightarrow i-1,(+\infty,0)\)
• \(i\rightarrow T,(1,0)\)

最后再把費用減去 \(\sum 2x_i\)

現在考慮怎么求這個的最大費用最大流，我們可以先求出任意一組最大流，然后在上面找環，而在這個圖中，所有正權環只可能是 \(S\rightarrow S\)，所以我們需要找到若干 \(S\rightarrow u\rightarrow v\rightarrow S\) 的環，然后加上他們的貢獻

現在考慮 \(u\) 的權值被調大的影響，另一種情況是對稱的，這時候肯定是 \(u\) 流的不比之前少不劣，我們這時候會試圖找一個 \(v\)，然后跑 \(S\rightarrow u\rightarrow v\rightarrow S\) 的環，其貢獻就是 \(x_u-x_v\)，于是我們要找的就是 \(x_v\) 最小的，且至少流過 \(1\) 的流量，在 \(i\leftrightarrow i-1\) 的那些邊上能夠從 \(u\) 到達的 \(v\)，由于 \(i\rightarrow i-1\) 流量為正無窮，所以 \(<u\) 的位置都能到，而 \(>u\) 的位置，必須滿足 \((u,v)\) 中所有 \(i\rightarrow i-1\) 的反向邊的流量不為 \(0\)，于是可行的 \(v\) 是一個前綴，這個前綴可以線段樹上二分找到，然后做區間查詢，可以簡單維護

復雜度線性對數

P14231 復讀機 / repeat

qoj 970，沒想到還能單 log

將問題轉為數點，每一個貢獻都是形如 \((l,r,i,j)\) 表示在 \(v\in[l,r]\) 的時候 \(i,j\) 為相鄰的一類數，并且有 \(1\) 的貢獻，可以差分變成單點加矩形和，直接二分即可

發現對于一個時刻 \(v\)，仍有貢獻的四元組 \((l,r,i,j)\)，其中所有的區間 \([i,j]\) 除端點外不相交，那么數點就可以降一位，只要求 \(i\) 在區間內，此時只會多算包含右端點的一個貢獻區間

查前驅后繼可以在整體二分的時候雙指針

復雜度線性對數

P14230 不連續子串 / subseq

記 \(f_i\) 為 \(i\) 為 \(q\) 中末尾的方案，考慮從 \(j\) 轉移到 \(i\)，則應該滿足

• \(\forall k\in(j,i),a_k=a_i\)，\(k\) 不在 \(p\) 中
• 令 \(l=\max_{k\in(j,i),a_k=a_i} k\)，必須存在 \(x\in(l,i)\) 在 \(p\) 中
• 對于 \(p\) 中的相鄰兩個數 \(u,v\)，滿足 \(\not\exists k\in(u,v),a_k\ne a_v\)

復雜度平方

P14188 [ICPC 2024 Hangzhou R] Barkley III

哈哈。

P14194 [ICPC 2024 Hangzhou R] Heavy-light Decomposition

我場切了綠題，真是太厲害了呢！

P13976 數列分塊入門 1~9

很無聊

P14177 【MX-X23-T7】我愛數數

愛慕愛嗯愛慕愛艾克斯容斥，此時對于所有的操作，你會有一個限制，你每次只能操作那些沒有被限制到的區間，假如區間有 \(k\) 個，這樣概率是 \(\sum_{i=0}^{\infty}\left(\frac{k}{m}\right)^i=\frac{m}{m-k}\)

所以考慮找出來區間最小值，做區間 dp，區間最小值左右都是獨立的，于是可以直接 dp，容易做到復雜度 \(\mathcal{O}(m^3n^2)\)，轉移形如一個背包，把那一位用點值表示就能做到 \(\mathcal{O}(m^3n)\)

P14176 【MX-X23-T6】網格 III

考慮 \((i,j)\) 到 \((i+k-1,j+k-1)\)，如果是紅的，要么橫豎當前都是紅色，要么橫著的當前全是紅色，且豎著的白色最晚的出現時刻小于橫著的紅色的最早出現時刻，容易用線段樹維護，復雜度 \(\mathcal{O}(nk\log n)\)

P6982 [NEERC 2015] Jump

先問全 \(1\)，然后從左到右一個一個翻，這樣肯定有一個時刻能問出來 \(\frac{n}{2}\)

然后對于相鄰的兩位，歸為一組，每組翻轉了問一下，這樣能判斷是全問對了還是只問對了一個，全問對了好說，只問對了一個的可以找一個已知的再問一下，如果全是只問對了一個，可以把其中的兩組 \(12\) 和 \(34\) 拉出來，問一下 \(23\) 看是全問對了還是只問對了一個，如果只問對了一個，再問一下 \(13\) 就行了

這樣找一個 \(\frac{n}{2}\) 要 \(n\) 次操作，問出來正確的串也要 \(n\) 次操作，總操作次數 \(2n\)，這直接爆了

考慮最開始的時候隨機問，正確的概率是 \(\frac{\binom{n}{\frac{n}{2}}}{2^n}\)，問個五百次就差不多了

10.24

補了昨天的 T4，并沒有想象中這么難

今天仍然是擺完了，做了很多幽默題

如此狀態，如何 CSP？

P6276 [USACO20OPEN] Exercise P

求的實際上就是所有排列置換環長度的 \(\text{lcm}\)，我們可以參考 \(\min-\max\) 容斥做 \(\gcd-\text{lcm}\) 容斥，即

考慮欽定 \(d|gcd\) 做容斥，記 \(f_{i}\) 為把 \(i\) 個數劃分到若干個環上的答案，每次枚舉第一個元素的環長，則有轉移

我們還要記一個 \(g_i\) 表示把環上 \(id\) 個數劃分到若干個長度是 \(d\) 的倍數的環上的答案，這個要帶上容斥系數，則有轉移

那么欽定 \(d|gcd\) 的答案就是 \(\sum_{i=1}^{\frac{n}{i}}g_i\times f_{n-id}\times\binom{n}{id}\)

直接做復雜度就是 \(\mathcal{O}(n^2)\)

\[\int_{1}^{n}\frac{1}{x^2}\mathrmw0obha2h00x=1-\frac{1}{n} \]

P11816 [PA 2019 Final] 擺棋 / Pionki/#1250. Tokens / Pionki

問題是一個最大匹配的判定，考慮霍爾定理，如果選了左部點 \((i,j,k)\)，那么其鄰域會加上 \(\sum_{a\le i,b\le j,c\le k}b_{i,j,k}\)，那么被 \((i,j,k)\) 偏序的左部點肯定也會都選上，最后要求的就相當于一個最大全閉合子圖

\(B,C\) 很小，考慮狀壓，發現每一層的狀態其實都是一個折線，于是可以輪廓線 dp 轉移，復雜度 \(\mathcal{O}\left(A(B+C)\binom{B+C}{B}\right)\)

P5999 [CEOI 2016] kangaroo

連續段 dp，每次加一個數，若 \(i\ne s/t\)，可以新開一個段或者合并兩個段，否則只能放在首/尾

容斥確實能做

P9675 [ICPC 2022 Jinan R] Shortest Path

太強了

考慮最終路徑大概是走了 \(\mathcal{O}(n)\) 步，然后在一條邊上反復橫跳，然后再走 \(\mathcal{O}(n)\) 步到達 \(n\)，而且我們可以說明當 \(k>4n\) 時結論一定成立

對于一條最短路徑，我們取出來他的最小邊 \(e\)，觀察到如果一個環長度為偶數，我們可以把這個環替換成若干邊 \(e\)，而如果全是奇環，有兩個我們也可以把他替換掉，所以考慮鴿巢原理，對于任意一條點數 \(>2n\) 的最短路徑，至少存在某一個點 \(x\)，在這條路徑上出現了三次，這三次會形成至少兩個環，于是我們只需要分討這個兩個環的奇偶性就能消環了，這樣會一直消環直到點數 \(\le 2n\)，所以結論得證

于是預處理出來 \(f(u)\) 表示 \(1\rightarrow u\rightarrow n\)，走了 \(4n+1\) 步的答案，\(g(u)\) 表示 \(1\rightarrow u\rightarrow n\)，走了 \(4n\) 步的答案對于，那么最終答案的形式是一個半平面交，我們可以求出來凸包再等差數列求和，復雜度 \(\mathcal{O}(nm)\)

P8916 [DMOI-R2] 暗號

考慮把貢獻拆到每個點上，其貢獻只和到根鏈上的黑色連續段數有關，所以可以直接存到狀態里，從下往上 dp 即可，復雜度 \(\mathcal{O}(n^3)\)

P6072 『MdOI R1』Path

考慮淀粉質，可以做到三個老哥

發現淀粉質太唐了，考慮對于每個點，分別求出其子樹內的最大值和子樹外的最大值，前者可以啟發式合并做到 \(\mathcal{O}(n\log n\log V)\)，后者考慮拉出來全局最大的路徑，于是只需要求這條路徑上的答案，正著倒著分別掃一遍即可，復雜度 \(\mathcal{O}(n\log V)\)

總復雜度 \(\mathcal{O}(n\log n\log V)\)

你發現這個子樹內最大值太唐了，因為我們只需要對最大的鏈上的點求子樹內最大值，這個啟發式合并就不用對每個點都做一遍了，只需要把最大的鏈上的相鄰點合并就行了

復雜度線性對數

P14250 [集訓隊互測 2025] 攜春同行

為啥是黑來著

自然的想法是問菊花，我們把 \(a_i\) 最大的叫做 \(A\)，次大的叫做 \(B\)，第三大的叫做 \(C\)，你發現你問出來的每個結果都形如 \(A+B+x\)，而且你考慮最大的、次大的、第三大的，他們三個問出來肯定都是 \(A+B+C\)，這樣用了 \(n\) 次就知道了很多信息，但是題目說 \(n+1\) 次，所以你可以再問一次鏈，得到 \(\sum a_i\) 的值，這樣你就能解出來 \(C\) 的值，從而能得到 \(A+B\) 的值，進而能得到所有的非最大、次大的值

現在考慮一般的情況，這時候你的 \(A+B+C\) 可能不止三個，而題目要求出 \(n-2\) 個數，那就別管最大次大了，考慮如何求出所有的 \(C\)，要求次數是 \(\log\) 級別的，于是考慮二分，把可能等于 \(C\) 的一半拿出來，構造一個鏈，其他的點放成一條，然后你把拿出來的點放在中間，這樣你就能問出來你拿出來的點中是否存在不是 \(C\) 的點，這樣你二分兩次就行了，詢問次數 \(2\log_2n\le 20\)，隨便過

感覺訓了這么長時間，唯一提升的是交互水平

P14252 [集訓隊互測 2025] 集你太美

在最終情況下，所有點都會被操作無窮次，因為肯定存在某一個點操作了無窮次，其相鄰點就不可能操作有限次

假如 \(i\) 第一次操作在 \(i+1\) 之前 ，那么一定有 \(w_i\ge\sum_{j=1}^{i=1}e(i,j)\)

所以對于操作序列 \(1,2,\cdots ,n\)，我們可以操作一次之后將 \(n\) 放在開頭，你發現此時仍然合法，于是上述條件是充要的

于是 \(\sum_{i=1}^{n} w_i\) 的下界是所有邊的權值之和，并且可以將圖定向為一個 \(DAG\) 之后，給每個點賦權值為其所有入邊的權值之和來構造 \(o=1\)

對于 \(o=2\)，隨便定向，觀察定向后任意一個出度為 \(0\) 的點 \(u\)，該點顯然滿足 \(w_u\ge \sum_{(u,v,x)\in E}x\)，將 \(u\) 刪掉遞歸判定即可，最終 \(G\) 被刪空則有解，否則無解

CF2129E Induced Subgraph Queries

看起來根本就不能 polylog，于是考慮根號數據結構，發現每個點的操作代價是 \(\mathcal{O}(deg)\) 的，這太難受了，于是可以拆點，每個點拆成 \(deg\) 次操作，再跑莫隊復雜度就對了

對于 kth，可以用值域分塊維護

總復雜度 \(\mathcal{O}((n+m)\sqrt{n+m})\)

CF2115E Gellyfish and Mayflower

考慮一條路徑上性價比最大的 \((c,w)\)，感性理解一下，當選了一些數之后就只會再選性價比最大的了，因為考慮在膜 \(c\) 意義下，如果同一個余數出現了兩次，那么不如把那一段路徑的其他點直接選若干個 \(c\)，這樣肯定是更優的，為了不讓一個余數出現兩次，背包大小只需要開到 \(c^2\)

于是考慮同余最長路，記 \(f_{s,u,r,0/1}\) 表示性價比最大的為 \(s\)，當前在 \(u\)，膜 \(c\) 余 \(r\) 的答案，最后只需要查詢 \(\max_s f_{s,u,r\bmod c_{s},1}+\left\lfloor\frac{r}{c_s}\right\rfloor\times w_s\)

轉移的話，單點之間的轉移可以轉圈，這樣轉移復雜度是線性的，不同點之間的轉移，邊權為 \(w_i-\left\lfloor\frac{r+c_i}{c_s}\right\rfloor\times w_s\)

所以當詢問的 \(r\) \(>c^2\) 時，我們跑這個算法，對于 \(r\) 比較小的情況，我們跑 \(\mathcal{O}(n(n+m)c)\) 的暴力，所以總復雜度 \(\mathcal{O}(nq+(n+m)(n+c)c)\)

CF2122F Colorful Polygon

沒想到組合數乘積，太失敗了

如果能表示成組合數乘積，我們就可以變成幾個高度為 \(2\) 的矩形，然后在上邊放 \(n+1\) 個點，下面放 \(m+1\) 個點，這樣就是 \(\binom{n+m}{n}\)

容易把兩個矩形拼起來，變成乘積，那么考慮最簡單的方案就是 \(\prod_{i=1}^{n}\binom{\sum_{j=1}^{i}a_j}{a_i}\)，然而這樣點數是 \(\mathcal{O}(n\sum a_i)\) 的，考慮分治，把集合 \(S\) 對應的多項式系數表示成 \(f(S)\)，則把他分成兩個集合 \(U\) 和 \(V\)，可以得到 \(f(S)=\binom{s(U)+s(V)}{s(V)}f(U)f(V)\)，其中 \(s(U)\) 是 \(U\) 中元素的和，我們按照重量比較平衡的分法進行遞歸就行了，點數 \(\mathcal{O}(\log n\sum a_i)\)

CF2097E Clearing the Snowdrift

掃描值域，每次做一個問題：給你一堆 \(1\) 和一堆 \(0\)，求最小長度為 \(d\) 的區間數能包含所有的 \(1\)，用 LCT 維護，\(0\) 點連向 \(i+1\)，\(1\) 點連向 \(\min(i+d,n+1)\)，答案就是 \(1\) 到 \(n+1\) 鏈上權值和

復雜度線性對數

CF2096F Wonderful Impostors

雙指針

對于加入 \(1\)，查詢其覆蓋的是不是已經全是 \(0\) 了，可以線段樹維護區間加，區間最值

對于加入 \(0\)，查詢其構成的最長的 \(0\) 連續段是否包含了一個 \(1\)，也就是查詢 \(r\le qr\) 的最大的 \(l\)，線段樹套 set 完事

復雜度 \(\mathcal{O}(n\log^2n)\)

10.25

模擬賽

T1

模擬

T2

類似括號序列 dp 就行了

T3

容斥

T4

枚舉每個數的貢獻，區間合法當且僅當被貢獻了兩次，掃描線維護區間加、區間最大值、區間最大值的權值加

10.26

P13540 [IOI 2025] 羊駝的坎坷之旅（obstacles）

太難了，只會 \(l=0,r=m-1\)

手玩一下發現路徑大概都是一堆 \((0,x)\rightarrow (z,x)\rightarrow (z,y)\rightarrow(0,y)\)，于是考慮 \((0,i)\) 能不能到達 \((0,j)\)，記 \(pre_i\) 為 \((0,i)\) 直著往下走能走到最遠的位置，記 \(T'_{r}=\max_{k=1}^{r}T_k\)，記 \(H'_{l,r}=\max_{k=l}^{r}H_k\)，那么 \(i\) 能到達 \(j\) 當且僅當 \(T'_{\min(pre_i,pre_j)}\ge H'_{i,j}\)，于是這樣就能給 \(i,j\) 連一條邊，最后可以并查集判斷連通性

發現很多邊都沒用，具體來說，如果存在 \(i<j<k\) 且 \(pre_i\le pre_j\le pre_k\)，此時只需要保留 \((i,j)\) 和 \((j,k)\) 的邊，于是我們只需要單調棧兩邊，連 \(i\) 和左邊第一個 \(pre_j>pre_i\) 的 \(j\) 記作 \(L_i\)，右邊第一個 \(pre_j>pre_i\) 的 \(j\) 記作 \(R_i\)，判斷一下是否能連邊就能 \(83\) 分了

既然都單調棧了，不妨在笛卡爾樹上考慮，\(i\) 與 \(j\) 能互相到達，也就是 \(i\) 和 \(j\) 有能到達的公共祖先，于是考慮問出 \(i,j\) 在 \([l,r]\) 內的最淺的祖先，判斷是否相同

首先一直倍增跳父親，直到 \(x\) 的子樹包含了 \(l\) 或者 \(r\)，此時不能再隨便跳了，但是舒服的是他只能往其中一邊跳，再往后跳的過程可以直接倍增，問題是找到這個一直往一邊跳之前到的祖先，如果我們找到一條極長的左偏的鏈 \(a_1,a_2,\cdots ,a_k\)，他們之間互相能到達，且他們的 \(L\) 都是一樣的，記作 \(p\)，現在想要跳到 \(p\)，你這時候發現，如果 \(a_i\) 能直接到達 \(p\)，那么 \(a_{i+1}\) 也能直接到達 \(p\)，所以如果想讓 \(a_1\) 跳到 \(p\)，只需要找到最小的 \(a_k\) 滿足 \(a_k\) 能到達 \(p\)，然后跳過去就行了

所以找到 \(x\) 的這個祖先，如果 \(x\) 和 \(L_x\) 和 \(R_x\) 都能到達，跳深度更淺的那一個，否則直接跳

復雜度線性對數

P13691 [CEOI 2025] highest

考慮倍增，普通的倍增直接爆了，于是考慮怎么讓每次倍增可以決策一個兩步，考慮到 \(2^i=2^{i-1}+2^{i-1}\)，也可以是 \(2^{i}=(2^{i-1}-1)+(2^{i-1}-1)+2\)，這樣就能考慮到 \(2\) 了，再加上 \(2^{i}-1=2^{i-1}+(2^{i-1}-1)\)，直接倍增即可

復雜度線性對數

P14311 【MX-S8-T4】平衡三元組

考慮如果固定中間值，左右肯定越大越好，所以肯定有一個取到全局最大值，假如 \(z\) 取到全局最大值，\(x\) 必定是 localmax，掃所有 \(x\)，查一下 \(x\) 右邊有沒有合法的 \(y\)，如果沒有，則去考慮前一個 localmax，此時會除二，所以只用做 \(\mathcal{O}(\log V)\) 次，總復雜度 \(\mathcal{O}(n\log n\log V)\)

P13695 [CEOI 2025] theseus

我曹

首先給一條邊賦 \(0/1\) 可以給這條邊定向從編號小的或者是編號大的，跑一邊 bfs 給圖分層，如果所有邊都是不同層了，直接連就行了，出現同層的就廢了，現在考慮怎么處理同層的邊

把每一層的邊摘出來，從層數大的處理到層數小的，不同層的邊把他歸到兩個點中層數更高的那一層去，對于邊 \((x,y)\)，以 \(x\) 為第一關鍵字，\(y\) 為第二關鍵字從大到小排序，給每個點記一個勢能 \(f\)，初始值都是 \(1\)，依此遍歷每一條邊，如果不同層，讓層數大的連向層數小的，否則讓 \(f\) 小的連向 \(f\) 大的，把 \(f\) 小的清空，加到 \(f\) 大的上，最后你走的時候每次走出邊中編號最大的即可

去掉無向邊后該圖變成一個有向樹，勢能為子樹 \(siz\)，每次走相同層的邊都會使得勢能翻倍，于是總次數 \(dis+\log n\)

P10055 [CCO 2022] Good Game

考慮把所有的連續段搞出來，長度 \(>1\) 的為一類叫做 \(2\)，否則叫做 \(1\)，這樣顯然和原來沒有任何區別，有用的操作只有兩種：刪掉最左邊或者最右邊的 \(2\)、刪掉中間的 \(2\)，并將兩邊的東西合并成一個 \(2\)，因為把一個 \(2\) 變成一個 \(1\) 顯然更劣，\(2\) 是更加自由的

接下來對串長分奇偶討論：

當串長為奇數，形如 \(2k+1\)，我們可以說明串能被消完當且僅當串正中間是 \(1\)，且存在長度至少為 \(k\) 的 \(1\) 連續段

容易說明充分性，考慮長度為 \(k\) 的那一段，左邊和右邊必定有兩個 \(1\) 不能刪掉，那就沒了

否則如果正中間不是 \(1\)，我們可以一直操作正中間的 \(2\) 把所有數都消了，否則考慮此時所有的 \(2\) 之間的間隔 \(< k\)，我們考慮與中間的 \(1\) 相鄰的兩個 \(2\)，觀察最中間的數的變化，如果刪掉一邊的 \(2\)，那么中間的 \(1\) 會減少一個，并且中間位置會向另一邊偏，考慮最偏的情況，左邊的 \(2\) 在 \(L\) 處，右邊的 \(2\) 在 \(L+k\) 處，如果我們只刪左邊，可以刪 \(L-1\) 次，那么最中間的下標在 \([k+1,L+k]\)，也就是說右邊的 \(2\) 肯定在某個時刻會變成最中間的數，這時候刪他就行了

對于偶數的情況，最后一定會剩下 \(22\)，于是合法的偶數串一定能劈成兩個合法的奇數串，判斷前后綴即可

構造方案是簡單的，復雜度線性

P12033 [USACO25OPEN] Package Pickup P

如果確定了一個奶牛所控制的區間，其肯定是先往一邊跑再掉頭跑另一邊，考慮 dp，記 \(f_{i,0/1/2/3}\) 表示 \(i\) 被左邊還是右邊經過，經過了一次還是兩次，轉移是矩陣乘法

可以按 \(M\) 分塊，本質不同的塊只有 \(\mathcal{O}(N)\) 種，我們可以把對塊形態的修改掛到開頭結尾，用線段樹維護單點修改全局矩陣乘積，本質相同的塊做矩陣快速冪即可，復雜度線性對數，會帶一個大常數

10.28

真他媽無敵了，今天做題數=1，晚上看了一個題還沒看懂

模擬賽

T1

幽默

T2

打表

T3

拉出極小的 mex 區間，對于 mex 相同的 mex 區間，做一個點減邊，查詢區間 \(\sum_{L\le l,r\le R}v_{l,r}(R-r+1)(l-L+1)\)，復雜度線性對數

T4

直接看原題解吧，寫在這有點太有點了

P9970 [THUPC 2024 初賽] 套娃

我們稱一個區間 \([l,r]\) 為極小的 \(\text{mex}\) 區間，滿足不存在 \([l',r']\subset [l,r]\)，其中 \([l',r']\) 的 \(\text{mex}\) 等于 \([l,r]\) 的 \(\text{mex}\)，有結論，極小的 \(\text{mex}\) 區間的個數是線性的

考慮區間 \([l,r]\)，其中肯定有 \(a_l=\text{mex}\) 或者 \(a_r=\text{mex}\)，且肯定有 \(a_l\ne a_r\)，不妨設 \(a_l<a_r\)，假如有 \([l,r]\) 是極小的 \(\text{mex}\) 區間，如果存在另一個極小的 \(\text{mex}\) 區間 \([l,r_1]\) 滿足 \(a_{r_1}<a_l\)，因為有 \(\text{mex}([l,r])\ge a_l>a_{r_1}\)，所以 \(a_{r_1}\) 肯定在 \([l,r]\) 中出現過了，所以不可能存在這樣的 \(r_1\)，于是我們證明了對于所有的 \(l\) 只存在一個這樣的 \(r\)，同理我們能證明對于所有的 \(a_r>a_l\) 只存在一個這樣的 \(l\)，所以極小的 \(\text{mex}\) 區間的個數是線性的，且其個數上界為 \(2n\)

如何取出所有的區間？考慮從 \(0\sim x-1\) 的區間推出 \(x\) 的區間，首先顯然，所有 \(\text{mex}=x\) 的極小的區間肯定要包含一個 \(\text{mex}< x\) 的區間，所以可以考慮從 \(x-1\) 擴展出其他的，對于 \(\text{mex}=x-1\) 的區間 \([l,r]\)，我們找到其左邊第一個 \(x-1\)，記其位置為 \(pl\)，再找到其右邊第一個 \(x-1\)，記其位置為 \(pr\)，那么我們再在 \(\text{mex}(pl,r)\) 的位置加入 \((pl,r)\)，在 \(\text{mex}(l,pr)\) 的位置加入 \((l,pr)\)，一直這樣做就能找到所有的區間了

回到本題，我們可以考慮找到所有極小的 \(\text{mex}\) 區間 \([l,r]\)，再在其基礎上左右擴展，其對應的找到極大的 \(\text{mex}\) 不變的區間 \([l',r']\)，那么就能貢獻到 \([r-l+1,r'-l'+1]\)，用老司機樹維護顏色段即可，總復雜度線性對數

10.29

模擬賽

T1

感覺比 T2 難

T2

奇異搞笑

T3

幽默

T4

\(F_{i+j}=F_{i+1}F_{j}+F_{i}F_{j-1}\)

10.30

去海邊了，很好玩

10.31

嗯

11.1

太幽默了，就這樣吧

11.2

刺激戰場

11.3

擺爛

11.4

有兩個題完全沒看懂，太失敗了

模擬賽

T1

800。

T2

幽默。

T3

神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！

T4

神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！神題！

AT_agc073_c [AGC073C] Product of Max of Sum of Subtree

記題目中要求的 \(x_i\) 為 \(g_i\)

如果我們知道了所有點的權值 \(w_i\)，那么有 dp，\(f_u=w_u+\sum_{v\in \text{son}(u)}\max(f_v,0)\)，\(g_u=f_u+\max(g_{fa}-\max(f_u,0),0)\)，\(g\) 太難考慮了，我們考慮找到合法的 \(f\) 的充要條件

有一個必要條件是 \(f_1\in[0,1]\)，\(\forall u>1,f_u\in [-1,1]\)，首先有 \(g_1=f_1\)，所以有 \(f_1\in[0,1]\)，對于 \(f_u\) 的上界，有 \(g_u\ge f_u\)，所以有 \(f_u\le 1\)，對于 \(f_u\) 的下界，有 \(g_u=f_u+\max(g_{fa}-\max(f_u,0),0)\)，其中 \(g_{fa}\le 1\)，所以 \(\max(g_{fa}-\max(f_u,0),0)\le 1\)，所以 \(f_u\ge -1\)

記 \(s_u=\sum_{v\in \text{son}(u)}\max(f_v,0)\)，有 \(f_u=w_u+s_u\)，我們發現此時有 \(0\le s_u\le|\text{son}(u)|\)，所以如果我們確定了所有點的 \(f\) 值，有且僅有一組 \(w_u\in[1-N,1]\) 的方案滿足當前的 \(f\)

于是只需要考慮 \(f\)，跟據 \(g_u=f_u+\max(g_{fa}-\max(f_u,0),0)\) 討論：

• 若 \(f_u\in[-1,-g_{fa})\)，\(g_u=f_u+g_{fa}<0\)，此時不合法
• 若 \(f_{u}\in[-g_{fa},0)\)，\(g_u=f_u+g_{fa}\)
• 若 \(f_{u}\in[0,g_{fa})\)，\(g_{u}=g_{fa}\)
• 若 \(f_{u}\in[g_{fa},1]\)，\(g_u=f_{u}\)

于是可以 dp，記 \(F_u(x)\) 為 \(g_u=x\) 的答案，則有

也就是

直接維護多項式轉移即可，復雜度 \(\mathcal{O}(n^2)\)

P11420 [清華集訓 2024] 乘積的期望

首先把 \(\prod a_i\) 拆開，變成操作若干次，每次操作將所有的 \(n\) 個數劃分到若干個集合中，集合總數為 \(C\)，每個集合中的數相差小于 \(m\)，對這樣的方案求和，考慮 dp，記 \(f_{i,j,S}\) 為考慮了前 \(i\) 個數，將其劃分到 \(j\) 個非空的集合中，\(S\) 中存儲 \([i-m,i-1]\) 那些位置中，作為集合中的最小值且還沒有最大值和其匹配的位置都有哪些，于是有這幾種轉移‘：

• \(i\) 既不是集合中的最大值又不是集合中的最小值
• \(i\) 是集合中的最小值
• \(i\) 是集合中的最大值，枚舉和 \(S\) 中的某個最小值匹配
• \(i\) 獨自一個集合

最終答案為 \(\sum_{i} f_{n,i,S}\times A(C,i)\times \left(\sum b\right)^{-i}\)

當 \(m\le 16\) 時，采用此算法可以做到 \(\mathcal{O}(n^2m2^m)\) 的復雜度，同時我們也知道，最終答案一定是關于 \(C\) 的 \(n\) 次多項式

當 \(m>16\) 時，考慮在結尾填上若干個 \(0\) 湊成 \(n=3m\)

考慮將 \(n\) 分成三組，\(1\sim m\)、\(m+1\sim 2m\)、\(2m+1\sim 3m\)，對其進行計數，記 \(a_i\) 為最終 \(i\) 覆蓋的次數，考慮合法 \(a\) 的充要條件

• \(\forall i\)，有 \(a_i\ge 0\)
• \(\forall 1\le i\le m\)，有 \(a_i+a_{i+m}+a_{i+2m}=C\)
• \(\forall 1\le i<m\)，有 \(a_i\le a_{i+1}\)
• \(\forall 2m+1\le i<3m\)，有 \(a_i\ge a_{i+1}\)
• \(a_{m}+a_{2m+1}\le C\)

于是直接 dp，在最外面枚舉 \(a_{2m+1}\)，記 \(f_{i,a,b}\) 表示考慮前 \(i\) 列，當前列上 \(i\)、\(2m+i\) 分別是 \(a\)、\(b\) 的方案，直接 dp 就能做到 \(\mathcal{O}(nC^5)\)，分步轉移即可去掉一個 \(C\)，再拉格朗日插值就能 \(\mathcal{O}(n^6)\)

P11425 [清華集訓 2024] 路南柯

結論：答案為刪去葉子后得到的樹的葉子個數，特別的，菊花的答案為 \(2\)

把拓撲序倒過來，就變成了 dfn 序，我們隨便拉一個 dfn 序，其中對樹的形態的限制只有形如點 \(i\) 的父親的 dfn 序在點 \(i\) 之前，所以當前一個點可能有很多個父親，我們就需要把所有點的父親找到

考慮原樹上的葉子，為了區分其父親和祖父，一定要存在一次拓撲的起點在這個葉子的父親的子樹中，否則無論如何都無法區分其父親和祖父，于是答案不會小于刪去葉子后得到的樹的葉子個數

考慮構造到這個下界，找到所有的刪掉葉子后剩下的葉子 \(x_1,x_2,\cdots,x_k\)，任選一個作為根跑一邊 dfs，遍歷時優先訪問葉子節點，此時，對于點 \(u\)，若其子樹內存在某個點作為拓撲序的開頭，\(u\) 的父親就能被確定了，所以只需要考慮那些葉子的父親，對于 \(x_{2},x_3,\cdots,x_k\)，以他們出發進行 dfs，訪問節點是優先訪問 dfn 大的，這樣就能找到葉子的父親了

P11428 [清華集訓 2024] 前往何方

考慮問出若干個獨立集，之后可以變色龍

所有點問一遍 \(U/\left\{u\right\}\)，然后可以確定重心，如果我們按這個結果排序，可以確定一個拓撲序，所以可以直接二染色，這樣就兩個獨立集，直接變色龍就行了

P11423 [清華集訓 2024] 阿爾塔爾 2

有經典結論，長度 \(\le 2\)，不過我突然不會證了

取出出度最大的點 \(u\)，其出度集合為 \(S\)，入度集合為 \(T\)，此時若長度大于 \(2\)，則所有 \(T\) 中必定存在點向 \(S\) 中的點有出邊，此時其度數大于 \(u\)，與條件矛盾，得證

考慮隨便取出一個點，若該點入度為 \(0\)，那么它就是答案，答案肯定在其入點集合中，因為此時其入點集合中的點到集合外路徑 \(\le 2\)，而該入點集合內又滿足結論，所以我們只需要在入點集合內找，那么每次隨機一個點就行了，這樣期望會把入點集合的大小減半，次數 \(n+\frac{n}{2}+\frac{n}{4}+\cdots=2n\)

P11421 [清華集訓 2024] 最大匹配 2

暴力怎么做，從左到右掃一遍，每一個顏色維護一個棧，能肖戰就肖戰，把最后剩下的再做一遍匹配即可，因為肯定是留下來越靠左的左括號和越靠右的右括號越優

然后考慮單調修改，此時只有 \(\mathcal{O}(1)\) 個位置會受到影響，我們可以直接做一個人員調度，用線段樹維護區間加，區間最值以及線段樹上二分