小王精心做題筆記，堂堂連載！

5.21

昨天講的網絡流

連邊時都是形如 \(u\rightarrow v,(cap,cost)\) 的格式

CF2046D For the Emperor!

首先縮點，一下對縮點后的 DAG 考慮，直接費用流建模

考慮記一個很大的數 \(B\)，我們每經過一個點，讓費用減去 \(B\)，而再放一個計劃的時候，使費用加上一，這樣我們肯定是優先遍歷所有的點，最后只需要算一個 \(n\times B+flow\) 就行了

對于每個點 \(u\)，拆成三個點 \(F_u\)、\(P_u\)、\(Q_u\)，用 \(F_u\) 來限制這個點的初始流量，那么直接 \(S\rightarrow F_u,(a_u,0)\)。\(P_u\)、\(Q_u\) 為 \(u\) 的出點和入點，連 \(P_u \rightarrow Q_u\)，考慮用這條邊來刻畫這個點是不是被經過，連出兩條邊，一條為 \((1,-B)\)，另一條為 \((inf,0)\)，這樣連就是相當于限制第一次經過這個點時才有 \(-B\) 的貢獻，而以后是費用不變的。另外，連 \(F_u \rightarrow P_u,(1,1)\)，連 \(F_u \rightarrow Q_u,(inf,0)\)，若 \(u\)，\(v\) 有邊，那么 \(Q_u \rightarrow P_u,(inf,0)\)

QOJ9224 Express Eviction

首先顯然可以把左上到右下的一條路徑轉化成左下到右上的一組最小割，而且我們肯定只會考慮那些有人的格子，首先拆點，可以考慮把有角相交的格子連邊，在邊界上的和源匯相連（下邊界左邊界連源，上邊界右邊界連匯）

發現這樣其實是存在問題的，考慮一個 \(3\times 3\) 宮格的對角，如果他們擋在我們的割邊路徑上，那肯定會造成至少 \(1\) 的貢獻，而且不在邊界上的 \(2\times 2\) 的對角肯定也會有 \(2\) 的貢獻

那如何建圖呢？把切比雪夫距離小于 \(2\) 的格子相互連邊，實際上，這是因為如果我們考慮每一對格子，實際上只有他們所破壞掉的邊是連通的才是有貢獻的

這樣再跑最小割就是對的

[ABC397G] Maximize Distance

當最短距離的最大值為 \(1\) 時，實際上就是跑一遍最小割，這啟發我們從最小割考慮這個問題

形式化的，我們可以記 \(01\) 變量 \(x_{i,j}\) 表示從 \(1\) 走到 \(i\) 這個點的最短路長度是否 \(\ge j\)，那么我們可以直接連邊 \((i,j)\rightarrow (i,j+1),inf\)，若 \(u,v\) 有邊，則 \((u,j)\rightarrow (v,j),1\)，\((u,j)\rightarrow (v,j),inf\)，我們用這兩條邊來刻畫最短路的轉移

這樣我們是不好求出答案的，考慮一下二分出答案 \(d\)，我們欽定 \(x_{1,1}=0,x_{n,d}=1\)，連一下源匯就行了

[ARC142E] Pairing Wizards

首先發現這個絕對值很搞笑，因為我們可以把 \(A_u\) 調整到 \(a_i\)，使得滿足限制的同時使得答案更優，然后對于每一組 \(u,v\)，我們肯定有 \(A_u\ge \min(b_u,b_v),A_v\ge min(b_u,b_v)\)，我們把 \(a_u\) 對這些值取 \(\max\)，考慮最終更新后的 \(a_i\)，對于 \(a_u\ge b_u,a_v\ge b_v\)，我們根本不需要考慮這一類情況，而 \(a_u < b_u,a_v<b_v\) 這種情況肯定是不合法的，于是我們需要考慮的只剩下 $a_u < b_u,a_v\ge b_v $ 了

我們考慮把限制轉化成 \(a_u\ge \max(b_u,b_v)\) 或 \(a_v\ge \max(b_u,b_v)\)，那么實際上要刻畫的就是一個“若 \(a<x\)，則 \(b\ge y\)”的命題，可以考慮切糕模型，只需要把 \(a_u \ge b_u\) 的那一組點的邊倒過來連，就可以刻畫這個限制了

CF1427G One Billion Shades of Grey

首先考慮值域為 \([1,2]\) 的情況，我們直接把權值為 \(1\) 的點與源點連邊，權值為 \(2\) 的與匯點連邊，四聯通的點之間相互連雙向邊，直接跑最小割

我們填的數肯定是在邊界上出現過的數，從大到小排序之后的數組為 \(v_1\sim v_n\)

這里我們有一個結論，對于每一個 \(i\)，把小于等于 \(v_i\) 的點看成 \(1\)，大于 \(v_i\) 的點看成 \(2\)，跑一遍值域是 \([1,2]\) 的情況，再加起來就是答案

暫時不給出證明

這樣復雜度太高，考慮退流（若要刪掉 \((u,v)\) 這條邊，直接跑一邊 \((v,u)\) 的最大流，然后把總流量減去這么多，然后再刪掉這條邊即可，而退流可以把所有要刪的邊都刪掉，在最后求一遍 \((s,t)\) 的最大流正確性也是對的）

最小值之和

對于這種涉及區間最小值的題，我們可以考慮枚舉最小值 \(k\)，可以發現，如果我們把所有的數都減去一個 \(k\)，那么有 \(d_{l,r}\leftarrow d_{l,r}-k\)，而所有的 \(f'\) 都會有 \(f'\leftarrow f'-k\times (n-1)\)，如果這個最小值在 \(x\) 這個位置，那這時候的 \(f'_{1}\sim f'_{x}\) 只和 \(f_{1}\sim f_{x}\) 有關了，那我們可以考慮區間 dp

記 \(f_{l,r,k}\) 表示令 \(\forall i\in [l,r],g'_{i}\leftarrow f'_i-k\)，能否構造出 \(g\) 使得 \(g\) 與 \(g;\) 滿足 \(f\) 與 \(f'\) 的限制

轉移時考慮枚舉最小值在哪個位置即可

這樣狀態數就是 \(\mathcal{O}(n^2V)\) 的，顯然不能接受，考慮優化狀態，發現如果使得區間中的 \(f\) 都加一，那 \(f'\) 就會加上 \(r-l\)，那么有 \(f_{l,r,k}\Rightarrow f_{l,r,k-(r-l)}\) 那么可以記 \(g_{l,r,k}\) 為最大的 $p\equiv k \pmod {r-l} $ 使得 \(f_{l,r,k}=1\)，這樣使得狀態數降為了 \(\mathcal{O}(n^3)\)

如何轉移？枚舉 \(i,p,q\)，將 \(g_{l,i,p}\) 和 \(g_{i+1,r,q}\) 合并，我們要做的就是找到最小的 \(x\) 使得 $x\equiv g_{l,i,p}\pmod{l-i} $ 同時 $x\equiv g_{i+1,r,q}\pmod{r-i+1} $，并且滿足 \(x\ge \max(g_{l,i,p},g_{i+1,r,q})\)，\(x\) 可以快速求出

令 \(t=\text{lcm}(i-l,r-i+1)\)，則會對于所有的 \(k\ge 0\)，\(g_{l,r,(x+k\times t)\mod (r-l)}\) 對 \(x+k\times t\) 取 \(\max\)，可以用同余最短路轉移做到 \(\mathcal{O}(n^5)\)

5.22

模擬賽

困

T1

直接考慮一手 cayley，如果已經有環，那我們的答案就是 \(\prod\limits_{i=1}^{k}siz_i\times n^{k-2}\)，\(k\) 是連通塊個數，\(siz_i\) 是每個連通塊的大小

然后考慮沒有環的情況，這時候我們需要造出來一個環，那把這個環連接起來的其他的連通塊當成一個大的連通塊，接著做沒有環的情況的計數就行了

于是可以記 \(f_{i,j}\) 表示我當前環上有 \(i\) 個點，這個環連成連通塊的 \(siz\) 之和為 \(j\)，轉移是簡單的，這樣可以做到 \(\mathcal{O}(n^3)\)

我們發現只有最后算答案的時候會用到第二維，直接記一維這個顯然是有點浪費，于是考慮記 \(g_{i}=\sum f_{i,j}\times j\)，\(h_i=\sum f_{i,j}\)，然后轉移就變成了 \(g_i\leftarrow g_i+g_{i-1}\times siz+h_{i-1}\times siz^2\)，\(h_i\leftarrow h_i+h_{i-1}\times siz\)

那就優化到 \(\mathcal{O}(n^2)\) 了，感覺這一步還是挺自然的，為什么沒想到呢？

T2

換維，換維，換維，換維，換維，換維

考慮交換時間維和下標維，那我們的操作就變成了在 \(l\) 時間對 \(i\) 處的位置加上一個 \(x\)，并在 \(r+1\) 處撤銷掉，詢問時就是問在 \(x\) 時刻查詢長度為 \(i\) 的前綴的答案，用括號序列去刻畫兩種操作，把第一種操作看成 \((\)，第二種看成 \()\)，并且第一種有權值，那么我們要求的實際上就是最后前綴 \(1\sim i\) 組成的括號序列最后無法匹配的括號的權值之和，可以用單側遞歸線段樹解決

思路可能確實比較自然，怎么被黃翊軒秒了？

T3

先不寫了，感覺還挺有意思，可能沒那么難

補了，loj 沒過，有一些 YES 1 YES 2 啥的判錯了，回來再改吧

(一)

若 \(\text{dis}(u,v)=k\)，則有 \(\text{color}_u=\text{color}_v\)

證明顯然，若 \(u\rightarrow v\) 的路徑是形如 \(u\rightarrow x\rightarrow y\rightarrow v\)，其中 \(u\)、\(x\) 之間有連邊，\(y\)、\(v\) 之間有連邊，則必須滿足 \(\text{sum}(u,y)=1,\text{sum}(x,v)=1\)，其中 \(\text{sum}(a,b)\) 是樹上 \(a\) 到 \(b\) 的 \(\text{color}\) 之和，則有 \(\text{sum}(x,y)+\text{color}_u=\text{sum}(x,y)+\text{color}_v\)，則有 \(\text{color}_u=\text{color}_v\)

那么考慮拉出來一個直徑 \((p,q)\)，那么這個直徑上 \(\text{dis}(p,i)\) 膜 \(k\) 相同的點顏色都是相同的，那么可以把這條直徑劃分成 \(k\) 個等價類，我們染色肯定是選擇其中一個等價類把這個等價類中的所有點染黑

(二)

對于一個包含 \(k\) 個點的限制路徑 \((u,v)\)，要求 \(\text{sum}(u,v)=1\)，若 \((u,v)\cap(p,q)\ne \emptyset\) 且 \(u\notin (p,q)\) 且 \(v\notin (p,q)\)，則 \((u,v)\) 的限制是沒用的，或者說 \((u,v)\) 的限制可以用其他的限制去表示

可以記 \(\text{top}(u)\) 為與 \(u\) 距離最近的那個點，如果存在一條路徑形如 \(u\rightarrow \text{top}(u)\rightarrow \text{top}(v)\rightarrow v\)，\(u\) 在左側，\(v\) 在右側，那么肯定在直徑上存在一條路徑 \(u'\rightarrow v'\)，\(u'\) 在 \(\text{top}(u)\) 左側，\(v'\) 在 \(\text{top}(v)\) 右側，記 \(\text{sum}(u',\text{top}(u))=a\)，\(\text{sum}(\text{top}(u),\text{top}(v))-\text{color}_{\text{top}(u)}-\text{color}_{\text{top}(v)}=b,\text{sum}(v',\text{top}(v))=c,\text{sum}(u,\text{top}(u))=d,\text{sum}(v,\text{top}(v'))=e\)，則有 \(a+b+c=1,d+b+c=1,a+b+e=1\)，可以得出 \(d+b+e=1\)，也就說明了我們只需要考慮一個端點在直徑上的或者無交的路徑

那么我們可以首先考慮第一類路徑，即有且僅有一個端點在直徑上的路徑

(三)

剛才給直徑上的點劃分了等價類，現在考慮把其他的點也劃分上等價類，先考慮給每個點分類，記 \(c_u=[h_u+\text{dis}(u,p)\ge k-1]+[h_u+\text{dis}(u,q)\ge k-1]\)，其中 \(h_u\) 是 \(u\) 子樹（越靠近直徑深度越淺）中，與 \(u\) 的最遠距離

• 若 \(c_u=0\)，則 \(u\) 是無用的，把 \(u\) 刪掉，把所有答案都 \(\times 2\) 即可
• 若 \(c_u=1\)，那么稱 \(u\) 為“一度點”
• 若 \(c_u=2\)，那么稱 \(u\) 為“二度點”

以下其實可以把一度點看成是“計數”，二度點看成是“限制”

然后考慮有用的點劃分等價類，注意到若 \(\max(\text{dis}(u,q),\text{dis}(u,p))\ge k-1\)，那么 \(u\) 可以每次向上跳 \(k\)，一直跳到直徑上，這樣 \(k\) 會有相應的等價類，于是對于點 \(u\)，記 \(\text{class}_p(u)=\text{dis}(u,p) \bmod k\)，記 \(\text{class}_q(u)=(\text{dis}(p,q)-\text{dis}(u,q) )\bmod k\)

發現其實 \(\text{class}_p(u)\) 和 \(\text{class}_q(u)\) 可能會不同，會導致我們的 \(\text{class}\) 并不是一個良定義，這是因為當我們再跳一步跳到直徑上的時候，可以往 \(p\) 跳也可以往 \(q\) 跳，那 \(u\) 就有可能同時屬于兩個類，那這兩個類其實也是等價的，也就是說他們最后的顏色肯定得相同，而我們顏色為 \(1\) 的等價類最多只有一個，那只要強制這兩個類的顏色都為 \(0\) 即可

接下來對于一度點和二度點分別考慮就行了

(四)

對于一度點，去掉所有的零度點之后，一度點在樹上肯定是一些子樹，我們現在去考慮其中一顆子樹，為了方便，我們先認為對于這個子樹中的每個點 \(x\)，都有 \(\text{dis}(x,p)\ge \text{dis}(x,q)\)

考慮一個一度點 \(u\)，如果 \(\text{dis}(u,p) = k-1\)，那么 \((u,p)\) 這條路徑上有且僅有一個黑點，而且我們可以說明，對于 \(\text{dis}>k-1\) 的那些點，這些點的顏色都是可以被 \(\text{dis}\le k-1\) 的那些點以及 \(p\) 到這個一度點的子樹的根的路徑唯一確定的，這個比較顯然，直接往上跳就行了

那么我們現在只去考慮 \(\text{dis}\le k-1\) 的那些點，現在我們要滿足，對于所有的葉子，其到 \(p\) 的那條鏈上有且僅有一個黑點，而且對于這個子樹中所有的距離為 \(k-1\) 的點對，他們的路徑上也有且僅有一個黑點

現在我們說，第二種路徑根本不存在，證明也是簡單的

記這顆子樹的根為 \(rt\)，記 \(\text{dis}(rt,p)=x\)，考慮子樹中的任意一個點 \(u\)，記 \(\text{dis}(rt,u)=y\)，則此時有 \(x+y\le k-1,x-1\ge y+1\)，而如果存在一種這樣的路徑，那必然存在一個 \(y\) 滿足 \(2y\ge k-1\)，由 \(2y\ge k-1,x+y\le k-1\) 可以推出 \(x\le k-1\)，此時則不滿足 \(x-1\ge y+1\)，則不存在第二種路徑

這樣計算答案也是簡單的，若 \((p,fa_{rt})\) 上存在一個黑點，那染色方案是唯一確定的，那現在就是要數一顆樹中，對于所有的葉子，其到根鏈上都有且僅有一個黑點，也就是黑點之間不存在祖孫關系，計數是容易的，記這個方案數為 \(F\)，那么 \(F\) 會造成貢獻的等價類不可能在 \((p,fa_{rt})\) 中出現，由于 \(\text{dis}(p,rt)\le k-1\)，而且這些等價類又是連續的，所以我們的 \(F\) 的貢獻肯定是一段膜意義下的區間，注意，這里只有一段，我們打區間乘法標記可以輕松解決

這樣一度點就討論完了，接下來討論二度點的部分

(五)

這里對于一個二度點，我們說他要么屬于一個等價類，要么他必須染白，也就是說若要染色的等價類已經確定，那這個點要染的顏色實際上也被唯一確定

如果一個點 \(u\) 滿足 \(u\) 的子樹內存在一個點 \(v\)，其中 \(\text{dis}(p,v)\ge k-1\) 且 \(\text{dis}(q,v)\ge k-1\)，而且 \(\text{dis}(\text{top}(v),v)\le \left\lfloor\frac{k-1}{2} \right \rfloor\)，則 \(u\) 必須染白

考慮 \(v\) 向 \(p\) 延伸到的點 \(p'\)，滿足 \(\text{dis}(v,p')=k-1\)，\(v\) 向 \(q\) 延伸到的點 \(q'\)，滿足 \(\text{dis}(v,q')=k-1\)，這時若 \(u\) 為黑色，則 \((u,p')\)，\((u,q')\) 上的其他點肯定都是白色，而因為 \(\text{dis}(\text{top}(v),v)\le \left\lfloor\frac{k-1}{2} \right \rfloor\)，所以肯定有 \(\text{dis}(p',q')\ge k-1\)，這時候連續 \(k\) 個點都是白色，不合法，所以 \(u\) 顯然不能染黑色

現在考慮證明最上面的結論，直接進行分討

• 若 \(\text{dis}(\text{top}(u),u)> \left\lfloor\frac{k-1}{2} \right \rfloor\)，那么 \(u\) 會屬于某一個等價類

\(\text{dis}(u,p)\ge 2\times \left\lfloor\frac{k-1}{2} \right \rfloor> k-1\)，\(u\) 可以向上跳到一個等價類

• 若 \(\text{dis}(\text{top}(u),u)\le \left\lfloor\frac{k-1}{2} \right \rfloor\)，那么 \(u\) 必須染白

不再贅述，已經提及此方面的證明

這樣我們就說明了每個二度點都是可以被唯一確定的

(六)

上面好像只考慮了與直徑有交的那些路徑，與直徑無交的路徑怎么辦呢

容易說明，與直徑無交的路徑上的點都是二度點

直接考慮任意一個葉子 \(u\)，他的 \(h\) 值肯定為 \(0\)，而此時若存在另一個點 \(v\) 滿足 \(\text{dis}(u,v)=k-1\)，為了滿足 \((p,q)\) 為直徑，則肯定有 \(\text{dis}(p,u)\ge \text{dis}(u,v)=k-1,\text{dis}(q,u)\ge \text{dis}(u,v)=k-1\)，加上 \(h_u\) 肯定一樣，而其父親的 \(h_u+\text{dis}(u,p/q)\) 肯定更大，得證

這時候對于一個二度點 \(u\)，記其子樹中的非嚴格最長鏈為 \(f\)，次長鏈為 \(s\)，若 \(f+s>k-1\)，他向下可以伸出兩條在不同子樹中的路徑，如果其中一條路徑上的等價類組成的集合為 \(S\)，則此時肯定要對于染色的等價類 \(i\)（另一條路徑上的等價類是對稱的），滿足 \(i\notin S\)，考慮最嚴的限制，如果我們有這兩條路徑長度不同，肯定不會考慮更長的那個路徑上的只存在了一次的等價類，這時我們取次長鏈肯定限制是最緊的，這樣會對 \(\mathcal{O}(1)\) 個區間產生限制，也是容易做的

注意上述情況還要分別考慮 \(\text{class}_p\) 和 \(\text{class}_q\)

可能這一部分還有細節問題

(七)

做法，對所有點分類，對于零度點，讓答案乘二，對于一度點，計算 \(F\) 并進行一個區間乘法，對于二度點，限制一些區間不能選

細節有很多

CF1870G MEXanization

只會根號，先把根號說了吧

首先考慮二分，轉成判定性問題，然后我們從后往前掃，如果我們想要構造出一個 \(x\)，那么必須在最后的時候存在 \(0\sim x-1\)，首先把與當前值域無關的數都變成 \(0\) 肯定是最優的，可以考慮從后往前掃，記 \(n_i\) 表示需要多少個 \(i\) 才能構造出 \(x\)，記 \(c_i\) 表示我們現在有多少個 \(i\)

我們掃到一個 \(i\) 時，按一下幾種情況討論

• 若 \(c_i<n_i\)，則令 \(\forall j<i,n_j\leftarrow n_j+n_i-c_i\)
• 若 \(c_i\ge n_i\)，則令 \(c_0\leftarrow c_0+c_i-n_i\)

最后判斷一下 \(c_0\) 與 \(n_0\) 的大小關系就行了

那這樣可以做到 \(\mathcal{O}(n^2\log n)\) ？

二分沒必要，因為答案除了第一個以外顯然是單調的，然后又發現其實 \(c_i<n_i\) 的情況只有 \(\mathcal{O}(\sqrt{n})\) 個，這是因為我們每次會給 \(\sum\limits_{j<i} n_j\) 至少加上 \(i\)，但是我們 \(\sum\limits_{j<i} n_j>n\) 的話肯定是不合法的，那這樣就是自然根號

這樣直接用線段樹維護，check 的時候，每次找到一個滿足 \(c_i<n_i\) 的位置，一直做這個過程，復雜度就是 \(\mathcal{O}(n\sqrt n\log n)\)，過不去

使用一些在線段樹上 dfs 剪枝的方法可以做到把 \(\log n\) 去掉，若 \(n_r\times r>n\)，直接停止遞歸然后終止過程，若 \(n_r\le mn_{l,r}\)，\(mn_{l,r}\) 即當前區間中的最小值，那么這時候我們直接返回就行，先遞歸右兒子再遞歸左兒子，這樣每層遞歸的節點不超過 \(\mathcal{O}(\sqrt{\frac{n}{2^d}})\)，因為如果對于第 \(d\) 層的第 \(p\) 個節點，如果這個節點中存在關鍵點，那么至少會給 \(\sum n_j\) 加上 \(p\times 2^d\)，這樣一層復雜度就是 \(\mathcal{O}(\sqrt{\frac{n}{2^d}})\) 級別，求和就是 \(\mathcal{O}(\sqrt n)\)

5.23

CF1610G AmShZ Wins a Bet

好題啊

首先我們每次刪除的一對相鄰的括號肯定更優，因為考慮對于一個右括號，如果存在多個左括號與他匹配，如 ()(() 這時我們考慮最右邊那個右括號，有三個左括號可以和他配對并刪除，刪除越靠前的左括號并不優，因為這時候右邊存在一個其他的 )，我們刪除之后會使得這個括號左移，造成了字典序變大，肯定是不優的，那我們肯定刪除靠后的左括號更優，然后對于 ())) 這種情況，我們讓任何一個右括號與左括號匹配都是等價的，那不妨直接讓最左邊的右括號消除掉，這樣每次刪除的就是相鄰的括號了

那這樣我們最后的串肯定是原串刪除一些連續的括號匹配串，于是可以考慮 dp，記 \(f_i\) 為從后往前考慮到了第 \(i\) 個位置，字典序最小的串是什么，接著記 \(r_i\) 為 \(i\) 到 \(r_i\) 為一段合法的括號匹配，那么有轉移 \(f_i=\max(f_{r_i},s_i+f_{i+1})\)，其中 \(+\) 表示的是字符串的拼接，\(s_i\) 為 \(i\) 處的字符，這樣我們可以輕松做到 \(\mathcal{O}(n^2)\)，考慮優化

如果直接做，需要一個可持久化平衡樹維護哈希值，復雜度是 \(\mathcal{O}(nlog^2n)\) 的，但是我們還可以考慮一個經典的技巧，把可持久化結構建成樹，可以發現 \(f_i\) 就是這樣一個樹形結構，而且每次只會添加一個字符

容易考慮到樹上倍增維護哈希值，本來要做的平衡樹上二分可以直接倍增跳父親，這樣復雜度是 \(\mathcal{O}(n\log n)\) 的

[ABC306Ex] Balance Scale

簡單題，檢驗學習成果的時候到了

考慮沒有 = 的情況，實際上就是定向數 DAG，加上 = 實際上就是把一些點縮起來了

我們做這類計數的時候都是先枚舉出度為 \(0\) 的獨立集 \(T\) 做分層計數，在這里的容斥系數是 \((-1)^{|T|+1}\)
但是我們枚舉出來的 \(T\) 并不一定是獨立集，其實這其中是有連邊的，那我們實際上是欽定了這些邊是 =，也就是說，我們只需要記錄下來 \(T\) 的導出子圖的連通塊的數量，記作 \(c_{T}\)，直接 dp 就行了

顯然有轉移 \(f_{S}=\sum\limits_{T\subseteq S}(-1)^{C_{T}+1}f_{S-T}\)，直接做是 \(\mathcal{O}(3^n)\)，也容易做一個半在線的子集卷積做到 \(\mathcal{O}(2^nn^2)\)

5.24

模擬賽

T1

幽默了

對于階乘，有 \(i!=i(i-1)!\)，即 \(i!\) 是 \((i-1)!\) 的倍數，所以可以考慮一個進制狀物，每一個數都有唯一的表示方法，那我們發現答案肯定就是形如 \(1!+2!+2!+3!+3!+3!+4!+4!+4!+4!...\)，可以二分出最大的那個數，這個數是 \(\mathcal{O}(n^{\frac{1}{3}})\) 級別的，接著二分這個數出現了多少次，可以預處理出來 \(\sum\limits_{i=1}^k i!\times i\)，總復雜度容易做到 \(\mathcal{O}(T\log n)\)，做到線性也很簡單，不詳說了

T2

。

結論：對于一條路徑 \(i\rightarrow j\)，他最后的高度肯定是形如一些高度相同的連續段拼起來，而這個高度肯定是這個連續段中的某一個

于是可以記 \(f_{i,j}\) 表示從 \(i\) 開始，高度都為 \(h_i\)，走到 \(j\) 的最短路

怎么把這些 \(f\) 拼起來？有一個經典的方法，我們只考慮那些 \(h_i\) 不動的點之間的轉移，把不動點 \(i\) 走到不動點 \(j\) 的最小代價記為 \(c_{i,j}\)，這樣我們可以簡單地把 \(c\) 拼接起來

需要注意的是，我們的起點和終點不一定是不動點

這樣可以做到 \(\mathcal{O}(n^3)\)

T3

不會

P9839 四暗刻單騎

想打雀了，感覺不是難題

首先發現贏牌肯定靠自摸，因為如果是對家打給的，那肯定手中的兩張牌是一樣的，這時候對家已經能自摸了

只考慮自摸，可以發現我們最后的策略一定是手里握著一張牌一直不動，發現這時候對家如果摸到一張一樣的，他一定不會打出去，這樣的話兩家的策略都是固定的，只需要等到第三張出現，這時候便可以判斷是贏/輸/平局

這樣 \(\mathcal{O}(nq)\) 的做法就呼之欲出了，直接從前往后遍歷，查詢贏牌的最小時刻即可

但是這樣會出現問題，如果某人想贏牌而導致輸牌，肯定是不優的，那可以考慮另外一個人盡量平局，若前者還能贏，那肯定是必勝的，若兩者不存在必勝則是平局

優化到 \(\mathcal{O}((n+q)\log n)\) 其實是簡單的，直接掃描線掃右端點，考慮每個點 \(i\) 不動，能贏牌的最小時刻，然后查詢區間最小值就行了，這樣我們每張牌其實只有 \(\mathcal{O}(1)\) 次變化，每次要做的就是單點修改，查詢區間最小值，可以用線段樹簡單維護

5.26

講了很多背包

[THUPC 2023 初賽] 背包

令人感慨，當年做這題還是賀的題解

完全背包是否有解，即 \(\sum a_ix_i=M\)，其中 \(a_i,M\) 給定，問是否存在一組 \(x\) 滿足 \(x_i\in [0,\infty]\)，有同余最短路做法，找出來最小的 \(a_i\)，記為 \(m\)，直接做膜 \(m\) 意義下的最短路，復雜度就是 \(\mathcal{O}(nm\log )\)

這里介紹一種同余最短路上的轉圈技巧，如果我們松弛的時候不會連續松弛同一個點，那么就可以用這個轉圈技巧，也就是說，圖上不存在負環，當我們加入物品 \(a_i\) 時，這時候可以拉出來那 \(\gcd(m,a_i)\) 個環，直接繞著這個環走兩圈，便可以全都轉移到了，這樣復雜度是 \(\mathcal{O}(nm)\) 的

回到這個題，加上權值，也就是求 \(\sum x_iv_i\) 最大，我們可以考慮把性價比最高的物當成基準物品，也就是 \(\frac{v_i}{a_i}\) 最大的，記基準物品的 \(a_i\) 為 \(m\)，其 \(v_i\) 為 \(val\)，我們便不會重復松弛同一個點，而且這時候對于詢問 \(q\)，若 \(q\equiv p\pmod{m}\)，其中 \(0\le p< m\)，那么 \(f_q=f_p+\frac{q-p}{m}\times val\)，這樣只需要找到這個 \(p\) 的最長路即可，那么有轉移 \(f_j+v_i-\left\lfloor \frac{j+a_i}{m}\times val\right\rfloor \rightarrow f_{(j+a_i)\bmod m}\)，這樣帶權的情況我們也可以輕松做到 \(\mathcal{O}(nm)\)

P4389 付公主的背包

有點無聊

\(\forall j\in [1,m]\)，求 \([x^j]F=\prod\limits_{i=1}^{n} \frac{1}{1-x^{a_i}}\)

取對數，則

考慮 \(\ln(1+x)\) 的泰勒展開，即 \(\ln(1+x)=\sum\limits_{i\ge 1}(-1)^{i+1} \frac{x^i}{i}\)，那就有 \(\ln(1-x)=-\sum\limits_{i\ge1}\frac{x^i}{i}\)

那么則有

而我們只需要求前 \(m+1\) 項的系數值，因此只需要計算 \(\ln F\) 在膜 \(x^{m+1}\) 意義下的系數，即 \(\ln F\equiv \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\left\lfloor\frac{m}{i}\right\rfloor} x^{ij}\times \frac{cnt_i}{j} \pmod x^{m+1}\)，其中 \(cnt_i=\sum\limits_{j=1}^n [a_j=i]\)，求 \(\ln F\) 容易做到 \(\mathcal{O}(m\log m)\)，只需要計算 \(\ln F\) 的 \(\exp\) 即可，這樣復雜度就是 \(\mathcal{O}(m\log m)\) 的

CF1290F Making Shapes

這個數位 dp 還是挺有啟發性的

有一個顯然的事情，能確定最后凸包形狀的，只和每個向量的數量有關，因為對這些向量進行極角排序之后，其在凸包上的順序是確定的

那么我們只需要統計所有合法的序列 \(c\)，其中 \(c_i\) 是第 \(i\) 個向量的出現次數，滿足 \(\sum c_ix_i=0,\sum c_iy_i=0\)，而且還要滿足 \(x\) 方向和 \(y\) 方向上的極差 \(\le m\)，其實就是 \(-\sum\limits_{x_i<0} c_ix_i\le m,-\sum\limits_{y_i<0} c_iy_i\le m\)，而 \(\sum c_ix_i=0,\sum c_iy_i=0\) 可以進一步表示成 \(\sum\limits_{x_i<0} c_ix_i=\sum\limits_{x_i>0} c_ix_i,\sum\limits_{y_i<0} c_iy_i=\sum\limits_{y_i>0} c_iy_i\)

由于我們的 \(nV\) 只有 \(20\)，那么可以考慮數位 dp，考慮去對每一個二進制數 \(c\) 計數，則我們需要記錄的信息有：

• 當前枚舉到的位
• \(\sum\limits_{x_i>0}c_ix_i\) 的進位
• \(\sum\limits_{y_i>0}c_iy_i\) 的進位
• \(\sum\limits_{x_i<0}c_ix_i\) 的進位
• \(\sum\limits_{y_i<0}c_iy_i\) 的進位
• 只考慮所有枚舉過的位 \(\sum\limits_{x_i<0}c_ix_i\) 是否 \(\le m\)
• 只考慮所有枚舉過的位 \(\sum\limits_{y_i<0}c_iy_i\) 是否 \(\le m\)

轉移時，我們只需要枚舉每個二進制數 \(c\) 當前位的值是多少就行了，這樣總復雜度是 \(\mathcal{O}(2^n(nV)^4\log m)\)

PermuTree (hard version)

好題！

首先每個子樹的問題顯然是獨立的，因為我們只關心子樹內的相對順序，那這時候我們實際上是要解決若干個子問題，每個子問題都形如把所有點元素劃分到兩個集合中，原來在同一個集合中的元素互相沒有貢獻，原先不在同一個集合中且劃分后不在同一個集合中的元素對有 \(1\) 的貢獻，要求答案最大

我們可以說明的是，每個原集合中的元素在劃分之后肯定還是屬于同一個集合，可以通過調整來簡單說明

這樣就是讓我們求 \(\max (\sum\limits_{i\in S} a_i)(\sum\limits_{i\in T} a_i)\)

考慮直接背包，我們不同的 \(a_i\) 是自然根號級別的，直接二進制拆分然后做部分背包看起來是 \(\mathcal{O}(\frac{n\sqrt{n}\log n}{w})\) 的，但是我們可以說明這個做法不帶 \(\log\)

記 \(S_j\) 為能拆分出來 \(2^j\) 的那些物品的下標集合，則有 \(\sum\limits_{i\in S_j}2^j\times a_i\le n \Rightarrow \sum\limits_{i\in S_j}a_i\le \frac{n}{2^j}\)，又因為 \(a_i\) 互不相同，所以 \(|S_j|\le \sqrt{\frac{2n}{2^j}}\)，那 \(\sum\limits_{j}|S_j|\le \sum\limits_{j}\sqrt{\frac{2n}{2^j}}=\sqrt{2n}\times \sum\limits_{j}\frac{1}{\sqrt{2^j}}\)，容易說明，后面那個級數是收斂的，那我們就證明了一共只有 \(\mathcal{O}(n\sqrt n)\) 個物品

這樣我們對于每個子問題可以做到 \(\mathcal{O}(\frac{n\sqrt n}{w})\)，多個問題該怎么辦呢？

容易發現，如果對于一個子樹 \(u\)，存在一個兒子 \(v\)，滿足 \(siz_v\times 2\ge siz_u-1\)，那么我們最優的方案肯定是把這個兒子劃分到一個集合中，其他的所有兒子劃分到另一個集合中，這樣我們每次的 \(siz\) 肯定會減半，那這樣我們復雜度最壞的情況下其實就是 \(T(n)=2T(\frac{n}{2})+\mathcal{O}(\frac{n\sqrt n}{w})=\mathcal{O}(\frac{n\sqrt n}{w})\) 容易用主定理分析得到

這樣就做完了，總復雜度是 \(\mathcal{O}(\frac{n\sqrt n}{w})\) 的

gym101064L

經典題了

完全背包，但是 \(V\) 比較小，若要求 \(f(n)\)，我們肯定可以把 \(n\) 分成兩半，然后再合并，這樣兩邊的容量是在區間 \([\frac{n}{2}-V,\frac{n}{2}+V]\) 之間的，這樣我們去遞歸求解，最后求出來容量小于等于 \(3V\) 的完全背包就行了，這樣復雜度是 \(\mathcal{O}(V^2\log m)\) 的

qoj9870

直接給所有的 \(a_i\) 減去 \(\left\lfloor\frac{m}{n} \right\rfloor\)，然后 \(m\) 減去 \(n\times\left\lfloor\frac{m}{n} \right\rfloor\)，這樣之后 \(m\in [0,n]\)，而 \(a_i\in [-n,n]\)，大大減小了 \(m\) 的范圍，顯然存在一種排列方案使得所有前綴和在 \([-n,n]\) 中，于是我們在做多項式快速冪的時候只需要保留 \(\mathcal{O}(n)\) 個值做卷積就可以了，復雜度 \(\mathcal{O}(n\log^2 n)\)

qoj6462

發現 \(w\) 只有 \(300\)，那我們可以把 \(w\) 相同的放到一起，每次是一個 \(\max+\) 卷積的形式，像 qoj9112 那題一樣，對于同一個 \(w\)，我們在膜 \(w\) 意義下做卷積是有凸性的，直接決策單調性轉移即可，復雜度 \(\mathcal{O}(n \log n+mW\log m)\)