做題筆記20

10.18

給學弟的題單，Misty7、lsj2009、testib 別看了

模擬賽

T1

貪心

T2

分討

T3

線段樹

T4

不會

AT_abc288_h [ABC288Ex] A Nameless Counting Problem

把 \(M\) 加一，求

\[[x^{n}z^{X}]\prod_{i=0}^{M-1}\frac{1}{1-xz^{i}} \]

FWT，記 \(F_i=\frac{1}{1-xz^i}\)

\[\begin{aligned} &[z^s]FWT\left(\frac{1}{1-xz^i}\right)\\ =&[z^s]FWT\left(\sum_{j=0}^{\infty}(xz^i)^j\right)\\ =&[z^s]FWT\left(\sum_{j=0}^{\infty}x^{2j}+\sum_{j=0}^{\infty}x^{2j+1}z^i\right)\\ =&[z^s]FWT\left(\frac{1}{1-x^2}+z^i\frac{x}{1-x^2}\right)\\ =&\frac{1}{1-x^2}+(-1)^{|s\cap i|}\frac{x}{1-x^2} \end{aligned} \]

當 \(|s\cap i|\equiv 1\bmod 2\)，上式為 \(\frac{1}{1+x}\)，否則，上式為 \(\frac{1}{1-x}\)，記 \(cnt_s=\sum_{i=0}^{M-1}[|s\cap i|\equiv 1\bmod 2]\)，那么原 GF 可以寫出來

\[\begin{aligned} &[z^{s}]FWT\left(\prod_{i=0}^{M-1}\frac{1}{1-xz^i}\right)\\ =&\left(\frac{1}{1+x}\right)^{cnt_s}\left(\frac{1}{1-x}\right)^{M-cnt_s}\\ \Rightarrow&\\ &[z^s]\prod_{i=0}^{M-1}\frac{1}{1-xz^i}\\ =&\frac{1}{2^k}\sum_{t=0}^{2^k-1}(-1)^{|k\cap s|}\left(\frac{1}{1+x}\right)^{cnt_t}\left(\frac{1}{1-x}\right)^{M-cnt_t} \end{aligned} \]

于是我們可以找到所有的 \(cnt_t\) 相同的 \(t\)，這個可以數位 dp，后面那個生成函數是微分有限的，而且有一個簡單的卷積式，于是可以快速計算，復雜度 \(\mathcal{O}(N^3\log X)\)

P3214 [HNOI2011] 卡農

和上面那題一樣，不過 \(cnt_s\) 好算的多

P11459 [USACO24DEC] It's Mooin' Time P

關于牛叫個數有凸性，分治閔和，復雜度 \(\mathcal{O}(L^2n\log n)\)

P11458 [USACO24DEC] All Pairs Similarity P

對于所有的 \(S\)，求

\[\sum_{T}\frac{|T|c_T}{|S\cup T|} \]

和

\[\sum_{T}\frac{1}{|S\cup T|} \]

問題變成求形如

\[\sum_{T}f_{T}g_{S\cup T} \]

也就是求

\[\sum_{T}f_T\sum_{P}g_{P}[S\cup T= P] \]

考慮把 \([S\cup T=P]\) 拆了，也就是求

\[[x^{P}]x^Sx^T \]

FWT，得到

\[\begin{aligned} &[x^P]IFWT\left(\sum_{Q}[S\subseteq Q][T\subseteq Q]\right)\\ =&\sum_{Q\subseteq P}(-1)^{|P|+ |Q|}[S\subseteq Q][T\subseteq Q] \end{aligned} \]

當然也可以直接寫出來這個很經典的容斥系數

所以原式

\[\begin{aligned} &\sum_{T}\sum_{P}f_Tg_{P}[S\cup T= P]\\ =&\sum_{T}\sum_{P}f_T(-1)^{|P|}g_{P}\sum_{Q\subseteq P}(-1)^{|Q|}[S\subseteq Q][T\subseteq Q]\\ =&\sum_{S\subseteq Q}(-1)^{Q}\left(\sum_{T\subseteq Q}f_T\right)\left(\sum_{Q\subseteq P}(-1)^Pg_P\right) \end{aligned} \]

幾遍高維前綴和，復雜度 \(\mathcal{O}(n2^n)\)

P11928 [PA 2025] 子序列 / Podci?gi

數本質不同子序列個數減去只出現了一次的子序列個數，前者直接 dp

\[f_{i,j}=\sum_{k}f_{i,k}+1+[a_i\ne j]f_{i-1,j} \]

后者怎么辦？考慮線段樹合并的過程，記 \(f(a,b)\) 表示左端點字符為 \(a\)，右端點字符為 \(b\) 的答案，什么時候合并會出鍋呢，我們發現如果 \(a\) 那個位置和 \(b\) 那個位置中間還有一個 \(a\) 或者 \(b\) 就爆了，那可以記二進制數 \(s(x)\) 和 \(t(x)\)，表示最后一個/第一個 \(x\) 右邊/左邊的字符集，如果 \(a,b\not\in s(x)\cup t(x)\) 就能轉移了

所以轉移是

\[f(a,b)=\sum_{x}\sum_{y}f(a,x)f(y,b)[x,y\not\in s(a)\cup t(b)] \]

可以分兩步矩陣乘法轉移

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

P5828 邊雙連通圖計數

設有根連通圖的 EGF 是 \(D\)，有根邊雙的 EGF 是 \(B\)，則有

\[D=\sum_{n\ge 0}b_n\exp(nD)\frac{x^n}{n!}=B(x\exp(D)) \]

為啥是這樣？要尋找 \(B\) 和 \(D\) 的關系，考慮枚舉根所在邊雙的大小，對于每個點，他都能連若干個不相關的連通塊，所以每條邊的 EGF 就是 \(nD\)，你再把這些邊組合起來就是 \(\exp(nD)\) 了

拉反，記 \(H=x\exp D\)，因為 \(D=B\circ H\)，所以 \(B=D\circ H^{-1}\)，求 \(D\circ H^{-1}\) 好辦，我們有

\[[x^n]B=\frac{1}{n}[x^{n-1}]D'\left(\frac{x}{H^{-1}}\right)^n=\frac{1}{n}[x^{n-1}]D'\exp(-nD) \]

P6596 How Many of Them

記 \(g_n\) 為 \(n\) 個點的無向連通圖個數，這個可以 \(\mathcal{O}(n^2)\) 計算

考慮算欽定 \(k\) 個割邊的方案，用一下 cayley 公式

\[\begin{aligned} f_k=&\frac{1}{k!}\sum_{\sum a_i=n}\binom{n}{a_1,a_2,\cdots,a_k}n^{k-2}\prod_{i=1}^{k}a_i\prod_{i=1}^{k}g_{a_i}\\ =&\frac{1}{n^2k!}\sum_{\sum a_i=k}\binom{n}{a_1,a_2,\cdots,a_k}\prod_{i=1}^{k}a_ig_{a_i}n\\ =&\frac{n!}{n^2k!}[x^k]\left(\sum_{i\ge 1}\frac{ig_in}{i!}x^i\right)^k \end{aligned} \]

直接算可以 \(\mathcal{O}(n^3)\)，再二項式反演即可

AT_agc058_d [AGC058D] Yet Another ABC String

誰跟你容斥，可以戰斗爽！設 \(8\) 個狀態！

算了容斥更簡單

容斥有多少不合法的段，去欽定不合法段的起點，設段數為 \(i\)，則其他位置隨便放的方案為

\[\binom{a+b+c-3i}{a-i,b-i,c-i} \]

然后把這 \(i\) 個扔進去，每一個段前面的東西是有限制的，但是所有整個串的開頭沒有限制，就是

\[\binom{a+b+c-2i-1}{i}\times2^i+\binom{a+b+c-2i-1}{i-1}\times2^{i-1}\times 3 \]

復雜度線性

10.19

P9334 [JOIST 2023] 水羊羹 2 / Mizuyokan 2

首先發現對于一個合法方案，我們可以把所有的小段都縮到只剩一個使得方案仍然合法，于是考慮每一個大段旁的兩個位置，假如這個大段是 \([l,r]\)，那么一定有 \(\text{sum}([l,r])>\max(a_{l-1},a_{r+1})\)，這是一個方案的必要條件，對于所有小段長為 \(1\) 的方案，這顯然也是充要的

如果我們能說明這對于所有小段長不為 \(1\) 的方案，也是充要的，那么我們就可以將問題轉化為數能成為大段的最大段數，證明也是簡單的，考慮兩個段和 \([u,v]\) 和 \([x,y]\)，記 \(s1\) 為第一段的和，\(s_2\) 為第二段的和，有 \(s_1>a_{v+1},s_2>a_{x-1}\)，如果 \(a_{v+1}>a_{x-1}\)，我們可以把 \(s_1\) 擴張到 \([u,x-2]\)，此時第一段的和肯定比 \(a_{v+1}\) 大了，否則我們可以擴另一段，與前一種情況類似

現在就變成了數最大段數，我們有經典的貪心做法，記 \(f(r)\) 為 \(r\) 為端點，最大的左端點 \(l\) 使得 \([l,r]\) 是一個合法的大段，那么可以從左往右掃一遍求答案

對于靜態查詢，我們記 \(nxt(r)\) 為最小的 \(k\) 滿足 \(f(k)\ge r+2\)，在 \(nxt\) 上一直跳就行了，但是不好維護單點修改

我們能說明 \(nxt(r)-r\) 是 \(\mathcal{O}(\log V)\) 的，因為 \(r-f(r)\) 是 \(\mathcal{O}(\log V)\) 的，因為你 \(f\) 每擴張一次，總和都至少乘二，所以最多擴張 \(\mathcal{O}(\log V)\) 次

那么單點修改可以直接暴力修，可以寫一個 LCT 維護 \(nxt\)，復雜度 \(\mathcal{O}(n\log \log V)\)，但這樣實在是太唐了！用線段樹維護，維護每個區間左邊 \(\log V\) 個點首次跳到區間外面的位置及段數，信息合并也是 \(\mathcal{O}(\log V)\) 的，所以總復雜度 \(\mathcal{O}(n\log^2V)\)

P10009 [集訓隊互測 2022] 線段樹

對于 \(l=1,r=n\) 的詢問，操作 \(k\) 次相當于卷上 \((1+x)^k\)，此時對于 \(r\)，\(l\) 對他有貢獻當且僅當 \((r-l)\subseteq k\)，考慮根號重構，取 \(k=2^\)，這樣每次重構是 \(\mathcal{O}(n)\) 的，復雜度就可以做到 \(\mathcal{O}(q\sqrt n)\)

對于區間修改，考慮序列分塊，我們發現在 \(B\) 次操作之內，每個點的權值之和其之前的 \(B\) 個數有關，于是我們把所有塊及其前一個相鄰塊拉出來單獨處理，對于整塊修改可以直接打標記，散塊修改可以暴力重構，這里需要做一個高維前綴和，所以復雜度是 \(\mathcal{O}(B\log B)\)，查詢時也暴力重構即可

如果操作次數 \(\ge B\)，此時重構，從后往前掃描每個塊更新 \(a_i\) 的值即可

于是總復雜度為 \(\mathcal{O}(\frac{q}{B}\frac{n}{B}B\log B+qB\log B)\)，取 \(B=\sqrt n\) 即可，復雜度 \(\mathcal{O}(q\sqrt n\log n)\)

P11265 【模板】靜態區間半群查詢

貓樹，從下面的分治中心往上掃，維護每個葉子到其當前中心的答案，這個可以并查集路壓，但你合并的時候都是兒子并向父親，所以這個可以看作按秩合并，復雜度就是 \(\mathcal{O}(n\alpha(n))-\mathcal{O}(1)\)

P9040 [PA 2021] Desant 2

有一個 bongbong dp \(f_{i}=\max(f_{i-1},f_{i-k}+\text{sum}(i-k+1,i))\)，這樣是 \(\mathcal{O}(nq)\) 的

這實際上是在做一個最長路，我們連邊 \((x,x+1,0)\) 和 \((x,x+k,\text{sum}(x+1,x+k))\)，我們發現一個點只連了兩條邊，于是可以考慮構造一個網格圖，具體的，原來的 \(x\) 映射到網格圖上 \((\left\lfloor\frac{x}{k}\right\rfloor,x\bmod k)\) 的位置，然后考慮分治，取出中間行或者中間列，然后向兩邊 dp 算出來最長路，對于跨過中間的詢問直接更新出來，復雜度即為 \(T(n)=2T\left(\frac{n}{2}\right)+\mathcal{O}(n\sqrt n)=\mathcal{O}(n\sqrt n)\)，需要注意的是在前幾輪中可能會有一些斜著的邊，這個也更新一下就行

CF2109F Penguin Steps

很生動的題目！

\(\text{dis}_M\) 和 \(\text{dis}_{F}\) 顯然都有可二分性，考慮先二分出來 \(\text{dis}_M\)，bfs 即可，現在考慮如何讓 \(\text{dis}_{F}\) 更大，考慮二分這個值 \(k\)，這時候我們要做的，就是 ban 掉一些格子，令他們的值為 \(k\)，使得不存在 \((n,1)\) 到 \((r,n)\) 的路徑，這顯然是一個最小割！四聯通圖的最小割，可以轉成跑八連通圖的最短路，具體來說，建一個源點 \(s\) 和一個匯點 \(t\)，然后 \(s\) 去連那些在 \((n,1)\) 和 \((r,n)\) 分割出來的兩條邊界的上面那條上的所有點，\(t\) 去連下面的點，跑 dij 即可

那如何使得 \(\text{dis}_{M}\) 還是合法的呢？直覺告訴我們可以找到一條最靠右上的 \((1,1)\) 到 \((r,n)\) 的路徑，而且容易說明一定存在這樣的路徑，因為普通的圖可能會出現先向右走，然后不得不提前向下走的一條路，以及一條先向下走一段，但是可以向右走很多的路，而在網格圖中，這兩條路必定相交，此時我們可以選擇更靠右靠上的那一段！

那如何找到這條路？發現可以把 \((1,1\sim n)\) 以及 \((1\sim r,n)\) 這些點拉下來，然后跑 bfs，對于每一個點，如果其滿足 \(a_{i,j}> \text{dis}_M\)，這樣會填滿一部分區域，緊貼著這部分的就是我們要的路徑！

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

AT_agc016_f [AGC016F] Games on DAG

幽默

枚舉 SG 值相同的層，從低到高不好轉移，考慮從高到低轉移，記 \(f_{S}\) 為當前的答案，枚舉 \(T\subseteq S\)，滿足 \(1\) 和 \(2\) 同時在/不在 \(T\) 中，\(S\) 中的每個元素都至少向 \(T\) 中的某個元素連一條邊，\(T\) 中的元素可以隨便連 \(S\)，\(T\) 中元素自己不能有邊

容易做到 \(\mathcal{O}(n3^n)\)

AT_agc058_f [AGC058F] Authentic Tree DP

小廖半年前就說過這個神秘題，今天終于見識上了

思路沒有，能想到的都是神人了

對于每條邊 \((u,v)\)，將其變成 \((u,p)\) 和 \((p,v)\)，我們稱 \(p\) 為邊點，并在所有的 \(p\) 下面掛 \(P-1\) 個點，現在問題就變成了

對于新的圖，給每個點確定一個權值 \(v\) 滿足 \(v_i\) 互不相同，求所有邊點的權值比鄰居都小的概率

于是給所有邊定向，大的連向小的

容斥，對于 \(p\rightarrow u\)，欽定其反向，記 \(f_{u,i}\) 為 \(u\) 下面連了膜 \(P\) 意義下 \(i\) 個點，所生成的外向樹的帶容斥系數的概率，則有轉移

\(f_{u,i}\times f_{v,j}\times\frac{1}{j}\rightarrow f_{u,i+j}\)
\(f_{u,i}\times\sum_{j}f_{v,j}\times \frac{1}{j}\rightarrow f_{u,i}\)

最后要轉移 \(f_{u,i}\times \frac{1}{i}\rightarrow f_{u,i}\)

其中 \(\frac{1}{j}\) 是邊點能作為外向樹的根的概率，\(\frac{1}{i}\) 同理

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

10.21

擺爛確實有點太多了，需要找回一些狀態。

CF1279F New Year and Handle Change

wqs 二分

P4072 [SDOI2016] 征途

本質平方和，斜率優化/李超樹

P4983 忘情

wqs 二分+斜率優化

P6246 [IOI 2000] 郵局加強版加強版

有決策單調性，再套個 wqs 二分即可

P4383 [八省聯考 2018] 林克卡特樹

記 \(f_{u,i,0/1/2}\) 為 \(u\) 在最終選出的那些直徑上的形態，\(1\) 表示其為鏈端點，\(2\) 表示其為鏈頂，\(0\) 表示其不在鏈上，發現我們做的只有 \(\max,+\) 卷積和一些取 \(\max\)，所以可以 wqs 二分把第二維搞掉

P10104 [GDKOI2023 提高組] 異或圖

可以把第二維容了，于是先考慮解決子問題：

\(\forall 1\le i\le n,0\le b_i\le a_i\)
\(\bigoplus_{i=1}^{n}b_i=C\)

考慮在加一個數 \(a_{n+1}=C\)，計算其異或和為 \(0\) 的答案，再計算 \(a_{n+1}=C-1\) 異或和為 \(0\) 的答案，兩者做差即為異或和為 \(C\) 的答案，如果直接數位 dp，還是不好做，我們觀察到一個事情，如果存在 \(a_i=2^k-1\)，且其他的 \(a_j\) 都小于 \(a_i\)，那么別的 \(a_j\) 無論取什么，\(a_i\) 都能取到一個合法的值，所以其貢獻就是 \(\prod (a_j+1)\)，所以我們在數位 dp 的時候，如果在某一個位上，有一個位置沒頂到，比他低的位都可以隨便算，于是考慮直接枚舉這個位，記一個 \(dp_{i,0/1,0/1}\) 表示考慮了前 \(i\) 個 \(a\)，目前是否有沒頂到的數，異或和為多少，復雜度 \(\mathcal{O}(n\log V)\)

容第二維，我們在做集合劃分，\(S\) 的容斥系數即為點集 \(S\) 所對應的所有連通子圖的 \((-1)^{E}\) 之和，這個可以直接 \(\mathcal{O}(3^{n})\) 算，但是也可以令 \([x^S]F(x)=1\) 當且僅當 \(S\) 在原圖上是獨立集，那么容斥系數即為 \([x^S]\ln(F+1)\)

現在考慮 dp，我們直接 dp 的話需要記兩維，這樣狀態數太爆了，而每個連通塊的限制就是最小值的限制，于是考慮先給 \(a\) 排序，我們從前往后掃，如果 \(i\) 不在任何一個連通塊中，給他確定一個連通塊，其肯定為這個連通塊的最小值，此時對于 \(1\sim i-1\)，他們肯定都在某一個連通塊中，所以狀態里只需要記錄他們是否為其連通塊的最小值，對于 \(i\sim n\)，需要記錄他們是否已經在一個連通塊內，這樣狀態數就只有 \(\mathcal{O}(2^n)\) 了，轉移復雜度是 \(\mathcal{O}(n3^n)\)

總復雜度 \(\mathcal{O}((n\log V+m)2^n+n3^n)\)

P13758 【MX-X17-T7】夏終

大亂斗。

提出了一種很？的重構樹方法，我也是被震撼

給出一種重構樹的方法，其實叫重構鏈更合適，做 kruskal，每個連通塊維護一個鏈表，連通塊合并時將鏈表首尾相接，把這個鏈表拉下來建一個新的圖，則我們可以說明，在原圖上加入若干邊后的 MST 的權值等于在新圖上加入若干條邊后的 MST 的權值，為啥呢？因為你做 kruskal 就保證了保留權值 \(\le w\) 的邊后的連通性不變，那你權值就肯定相同了

所以我們把這張圖變成了鏈，現在考慮加入新邊怎么做，我們發現一定是取出 \(b\) 最小的點 \(x\)，然后把不包含 \(x\) 的連續段中的 \(b\) 的最小值和 \(x\) 連邊，這樣連續段 \([l,r]\) 的代價就是 \(b_x+C+\min_{i=l}^{r} {b_i}+\sum_{i=l}^{r-1}w(i,i+1)\)，不妨令 \(C'=C+b_x\)，考慮一個 dp，記 \(f_{i,j,0/1}\) 為考慮了前 \(i\) 個點，有 \(j\) 個連續段，當前段已經算了代價/沒算代價，則有轉移

\(f_{i,j,0}=\min(f_{i-1,j,0}+w_i,f_{i-1,j-1,1})\)
\(f_{i,j,1}=\min(f_{i-1,j,1}+w_i,f_{i-1,j-1,1}+b_i,f_{i-1,j-1,0}+w_i+b_i)\)

答案為 \(\min(f_{n,i,1}+i\times C')\)，你發現轉移要么是取 \(\min\) 要么是 \(\min,+\) 卷積，于是可以往凸性上考慮，對于這樣的連續段狀 dp，凸性的說明也是簡單的，可以直接拆點費用流

那對于兩個凸殼，定義其乘法為 \(min,+\) 卷積，其加法為取 \(\min\)，你發現上面的轉移可以寫成一個 \(2\times 2\) 的矩陣，于是可以考慮用線段樹維護，直接線段樹維護做單點修改是 \(\sum_{i}\frac{n}{2^i}=\mathcal{O}(n)\) 的，但是查詢快的飛起，考慮平衡一下，直接上一個序列分塊，修改復雜度 \(\mathcal{O}(B)\)，查詢怎么辦，凸殼有加法還有乘法，正常的都是只有加法或者乘法，但是要處理這個也是簡單的，考慮記 \(f(A)\) 為 \(A\) 這個凸殼對于 \(C'\) 的答案，即為 \(\min(A_i+i\times C')\)，發現有 \(f(A+B)=\min(f(A),f(B))\)，而 \(f(A\times B)=f(A)+f(B)\)，于是我們可以對于每一塊先查詢出來四個凸殼的答案，然后再矩陣乘法合并起來，復雜度 \(\mathcal{O}(\frac{n}{B}\log B)\)

可以平衡到 \(\mathcal{O}(n\log n+q\sqrt{n\log n})\)，可以直接過了，也可以離線基排，這樣能做到 \(\mathcal{O}(n\log n+q\sqrt n)\)，但是感覺常數不會小

#1004. 【UR #32】王之沉淀

太唐了。

既然是冒泡，考慮轉 \(01\)，枚舉一個 \(w\)，\(\le w\) 的看作 \(0\)，否則看作 \(1\)，答案顯然就等于把所有 \(w\) 所對應的 \(01\) 序列排好序的輪數的最大值，直接考慮最后一步就行了，所以現在考慮 \(01\) 序列

對于 \(U\) 操作，我們發現其把第一個 \(1\) 挪到了最后，對于 \(D\) 操作，其把最后一個 \(0\) 挪到了最前面，這個零一序列拍好序了，當且僅當所有的位置，要么其左邊全是 \(0\)，要么右邊全是 \(1\)，所以我們發現一輪操作中只有 \(U\) 和 \(D\) 的個數是關鍵的，分別記為 \(C_U\) 和 \(C_D\)，于是答案就是

\[\max_{i=1}^{n}\left\{\min\left(\left\lceil\frac{L_1}{C_U}\right\rceil,\left\lceil\frac{R_0}{C_D}\right\rceil\right)\right\} \]

其中 \(L_1\) 為 \(i\) 及左邊 \(1\) 的個數，\(R_0\) 為 \(i\) 右邊 \(0\) 的個數

那就豁然開朗了，枚舉所有的 \(C_U\)，掃描值域，維護一個指針 \(pos\)，為最小的滿足 \(\left\lceil\frac{R_0}{C_D}\right\rceil \le \left\lceil\frac{L_1}{C_U}\right\rceil\) 的位置，每次改變一個位置的 \(a\) 的值，\(pos\) 的總移動量是 \(\mathcal{O}(n)\) 的，總復雜度 \(\mathcal{O}(nk)\)

CF690A3 Collective Mindsets (hard)

太唐了，為啥我一直在想直接輸出編號

考慮尋找一個不變量，不難發現所有數的和是不變的，如果我們能讓某一個人猜到這個和膜 \(n\) 意義下的值，就能直接知道它對應的數是啥了，于是我們可以直接猜這個東西膜 \(n\) 意義下的值，對于編號為 \(r\) 的，猜這個東西是 \(r\bmod n\)，這樣至少會有一個對的

#950. 【UER #12】電子運動

這么強？！

考慮位置 \(i\)，記他左邊第一個 + 在 \(x\)，右邊第一個 - 在 \(y\)，那么 \(i\) 走 \(i\rightarrow x\rightarrow y\rightarrow i\) 這條路的時候，對序列的影響僅僅是交換了 \(x\) 和 \(y\) 的符號，那么我們可以通過這種交換操作，使得整個序列左邊全是 - 右邊全是 +，那么整個序列只有 + 的個數和起點的位置是重要的

那分討一下，對于起點 \(i\)，如果有 \(\ge n-i+1\) 個 +，最終會減少 \(n-i\) 個 +，否則會增加 \(i\) 個 +

那么起點 \(i\)，+ 數量為 \(j\) 的貢獻就是 \((i+j)\bmod {(n+1)}\)，直接卷積就行了，有那么一會我還覺得得寫一個循環卷積，腦子真是越來越拉了

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

#937. 梅花侍從

當年被擊敗了

考察任意兩組 \((a,b,c)\)，用 \(0\) 和 \(1\) 來區分，我們可以發現最優的肯定是 \(000111\) 或者 \(110001\)，于是可以直接當成括號做區間 dp，復雜度 \(\mathcal{O}(n^3)\)

#961. 【UR #30】賽場設計

把不可達性建圖，由于原圖是個 DAG，所以跟據不可達性建出來的圖，對于每一個 \((u,v)\)，要么有 \(u\) 不可達 \(v\)，要么有 \(v\) 不可達 \(u\)，要么 \(u,v\) 互相不可達，這是一個比競賽圖還要強的圖，他也有競賽圖的性質，我們的要求是不存在大小 \(\ge 3\) 的 SCC，于是先縮掉大小為 \(2\) 的 SCC，剩下的圖就是一張競賽圖，而且是一個 DAG，則需要滿足不存在三元環，經典的，考慮其縮完了點是一條鏈，我們不妨讓這條鏈正好就是 \(1\leftarrow2\leftarrow\cdots\leftarrow n\)，考慮每次加入一個點或者兩個點，最后再乘上 \(n!\)

記 \(f_{i,1/2}\) 為考慮了 \(i\) 個點，鏈尾點作為一個 SCC 的大小為 \(1/2\)，以當前點 \(i+1\) 所在 SCC 大小為 \(1\) 舉例，這時候每個之前的點都不能不可達，也就是必須可達，而之前的點也都滿足 \(j\) 可達 \(j+1\)，于是只有 \(i\) 必須要和 \(i+1\) 連一條邊，而其他點是否連邊無所謂，所以轉移系數是 \(2^{i-1}\)，轉移 \(f_{i,1}\times 2^{i-1}\rightarrow f_{i+1,1}\)，而如果鏈為大小為 \(2\)，則他們倆肯定每沒邊相連，所以這倆點都必須向 \(i+1\) 連邊，而其他點無所謂，所以轉移系數為 \(2^{i-2}\)，轉移 \(f_{i,2}\times 2^{i-2}\rightarrow f_{i+1,1}\)，當前點所在 SCC 大小為 \(2\) 的情況也類似，轉移是 \(f_{i,2}\times 2^{2(i-2)}+f_{i,1}\times2^{2(i-1)}\rightarrow f_{i+2,2}\)

復雜度線性

10.22

模擬賽

T1

容

T2

輪廓線 dp，沒調完

T3

題出的好！難度適中，覆蓋知識點廣，題目又著切合實際的背景，解法比較自然。給出題人點贊！

T4

最優解是直徑長度的一半，可以以直徑中點為根構造內向樹取得最優解，設這個值為 \(D\)

設一個勢能函數 \(h(x)\)，滿足若存在有向邊 \((x,y)\)，有 \(h(x)=h(y)-1\)，則有 \(d(s,t)=\frac{\text{dis}(s,t)+|h(x)-h(y)|}{2}\)，最優解下，所有的葉子的勢能肯定為 \(D\)，所以不妨設葉子的勢能為 \(0\)

考慮合法方案的充要條件為 \(\forall x,y,\frac{\text{dis}(x,y)+|h(x)-h(y)|}{2}\le D\)，即 \(|h(x)-h(y)|\le2\times D-\text{dist}(x,y)\)

對于任意一個 \(x\)，在根的另一個子樹中拿出來一個深度為 \(D\) 的葉子節點 \(y\)，則有 \(|h(x)|\le D-dep_x\) 是方案合法的必要條件

證明充分性：\(|h(x)-h(y)|\le |h(x)|+|h(y)|\le D+D-dep_x-dep_y\le 2\times D-\text{dis}(x,y)\)

總結一下 \(h\) 滿足的條件

對于所有深度為 \(D\) 的葉子節點，\(h=0\)
對于邊 \((x,y)\)，\(|h(x)-h(y)|=1\)
\(\forall x,|h(x)|\le D-dep_x\)

此時合法的 \(h\) 與合法方案構成雙射，直接 dp 可做到 \(\mathcal{O}(n^2)\)

題出的好！難度適中，覆蓋知識點廣，題目又著切合實際的背景，解法比較自然。給出題人點贊！

AT_agc014_f [AGC014F] Strange Sorting

太難了

步數肯定是有限的，因為每次操作，至少會讓某個最大值歸位

考慮最大值沒什么前途，所以考慮最小值，我們發現 \(1\) 完全不影響其他的數是否是 local max，于是可以考慮 \(i=n\sim 1\)，每次加入一個數 \(i\)，維護 \([i,n]\) 排好序的信息，記 \(T_i\) 為其輪數，那么要么有 \(T_i=T_{i+1}\)，要么有 \(T_i=T_{i+1}+1\)，為啥，因為 \(i+1\) 排好了的時候，要么是 \(1\) 正好放在最開頭，此時取得 \(T_{i+1}\)，否則 \(1\) 會放在中間，此時取得 \(T_{i+1}+1\)

有一個觀察，就是 \(i+1\) 在第 \(T_{i+1}-1\) 輪的時候一定不在首位，如果其在首位，其一定會作為第 \(T_{i+1}-1\) 輪的高項，這時候它就會被調到后面，如果不想讓他調到后面，需要所有位置都是高項，那這本身就排好序了，所以觀察成立

于是現在考慮什么時候需要 \(+1\) 而什么時候不需要，因為 \(i+1\) 不可能在第 \(T_{i+1}-1\) 輪在首位，所以他不可能成為一個高項，那 \(i\) 同樣不可能成為高項，所以在下一輪中 \(i\) 和 \(i+1\) 兩個數的相對順序不會改變，那肯定是讓 \(i\) 在 \(i+1\) 之前，這樣第 \(T_{i+1}\) 輪的時候 \(i+1\) 會被調到 \([i+1,n]\) 的首位，\(i\) 正好在他左邊，所以我們可以說，\(T_i=T_{i+1}\)，當且僅當 \(i\) 在 \(i+1\) 左邊

既然首位不可能是 \(i+1\)，我們可以考慮 \(T_{i+1}-1\) 時的首位 \(f_{i+1}\)，那么 \(f_{i+1},i,i+1\) 三者在第 \(T_{i+1}-1\) 輪時，相對順序是 \((f_{i+1},i,i+1)\) 的時候，\(T_i=T_{i+1}\)

接下來我們可以說明，\(f_{i+1},i,i+1\)，三者的相對順序的循環位移始終不變，這個結論是真的不自然

首先我們能夠說明，在前 \(T_{i+1}-1\) 輪種，\(f_{i+1}\) 如果不是在開頭，必然不會是一個高項，考慮反證法，如果 \(f_{i+1}\) 某一次作為了一個非開頭的高項，那么考慮他前面第一個高項 \(x\)，這一次操作之后，\(f_{i+1}\) 肯定和 \(x\) 緊挨著，考慮下一次操作，如果 \(f_{i+1}\) 和 \(x\) 都是高項或者都是低項，那么 \(f_{i+1}\) 就不會到首位，如果 \(f_{i+1}\) 是高項而 \(x\) 不是，在下一次操作之后 \(f_{i+1}\) 又變成了一個非開頭的高項，這樣就會無限遞歸，而我們的步數是有限的，\(f_{i+1}\) 就到不了首位，所以結論得證

然后考慮 \(f_{i+1},i,i+1\) 三者的相對順序，如果其相對順序發生了改變，肯定是在某一次操作的時候，形如高低高或者低高低，下面分討一下三者的位置關系

\(i+1\) 是開頭，\(f_{i+1}\) 和 \(i\) 一定是低
\(f_{i+1}\) 是開頭，\(i\) 和 \(i+1\) 一定是低
\(i\) 是開頭
- 如果 \(f_{i+1}\) 在第二個位置，\(f_{i+1}\) 和 \(i+1\) 都是低
- 如果 \(i+1\) 在第二個位置，\(i+1\) 可能是高，但 \(f_{i+1}\) 一定是低
否則 \(f_{i+1},i,i+1\) 都是低

所以結論得證，那我們只需要在每次加入 \(i\) 的時候看一下 \(f_{i+1},i,i+1\) 三者的相對順序就行了，復雜度線性

AT_agc020_c [AGC020C] Median Sum

取補集，所以只需要求所有的 \(>\frac{s}{2}\) 的最小的，復雜度 \(\mathcal{O}(\frac{ns}{w})\)

CF963E Circles of Waiting

每行第一個為主元，高消即可

posted @ 2025-10-18 13:44 fqmzwmhx 閱讀(33) 評論(0) 收藏舉報

刷新頁面返回頂部

oaigoaigilowoaigiy

10.18

模擬賽

T1

T2

T3

T4

10.19

10.21

10.22

模擬賽

T1

T2

T3

T4

公告