10.11

#8185. Emerging Tree

每個點(diǎn)維護(hù)其兒子的相對順序，記 \(L(u)\) 和 \(R(u)\) 兩個有序集合，存儲 \(u\) 的兒子的順序，\(L(u)\) 表示在 \(u\) 的前面，\(R(u)\) 表示在 \(u\) 的后面，為了方便 倒序存儲，記 \(L(u)\) 的大小為 \(kl\)，\(R(u)\) 的大小為 \(kr\)，那么我們最終的序列形如 \(L(u)_{kl},L(u)_{kl-1},\cdots,L(u)_1,u,R(u)_1,R(u)_2,\cdots,R(u)_{kr}\)，以此順序做 dfs 輸出就是答案

現(xiàn)在考慮假如 \(u\rightarrow v\) 這條邊，如果 \(u\) 目前 dfs 出來的序列是 \([x_1,x_2,\cdots,x_{k_1}]\)，\(v\) 目前 dfs 出來的序列是 \([y_1,y_2,\cdots ,y_{k_2}]\)，那么我們肯定是讓 \(x_1\) 或 \(x_{k_1}\) 和 \(y_1\) 或 \(y_{k_2}\) 拼在一起，也就是說要么讓 \(v\) 拼在目前 \(u\) 所有兒子的最右邊，要么拼在最左邊，否則拼在中間肯定就爆了，因?yàn)檫@樣就不滿足之前的限制了

假如兩個端點(diǎn)分別是 \(x\) 和 \(y\)，\(x\) 和 \(y\) 在其對應(yīng)聯(lián)通塊的左邊還是右邊并無關(guān)系，因?yàn)槲覀兛梢酝ㄟ^翻轉(zhuǎn)一棵子樹來使其合法，其中 \(x\) 在 \(u\) 的兒子 \(u'\) 的子樹中，\(y\) 在 \(v\) 的兒子 \(v'\) 的子樹中，我們發(fā)現(xiàn)。\(u'\) 的子樹此時必須是滿的，即 \(u'\) 子樹中的點(diǎn)都已經(jīng)在同一個連通塊里，或者 \(x=u\)，要不然你再拼東西的時候就爆了，同理，\(v'\) 的子樹此時也必須是滿的，或者 \(y=v\)

直接維護(hù)即可，我們還要注意如果我們拼上了 \(u+v\)，此時多出來一條邊 \(v\rightarrow w\)，那么我們就不能拼 \(w+v\)，所以需要打個標(biāo)記來記錄 \(v\) 的哪邊不能再拼東西了

復(fù)雜度線性

#6546. Greedy Bipartite Matching

掃描 \(w\)，每次加入權(quán)值為 \(w\) 的邊，求出當(dāng)前的最大匹配，然后把之后所有包含當(dāng)前點(diǎn)覆蓋的邊都去掉，當(dāng)前所有兩端點(diǎn)都在點(diǎn)覆蓋中的邊去掉，再接著這個過程做就行，答案即為每次最大匹配的前綴和

為啥是對的，對于每種邊權(quán)，其最小點(diǎn)覆蓋和原圖中的肯定一樣，匹配大小也相同，所以只需要求 \(q\) 次最大匹配

每次的殘量網(wǎng)絡(luò)相當(dāng)于一張 \(\mathcal{O}(m_i)\) 個點(diǎn) \(\mathcal{O}(m)\) 條邊的圖，故復(fù)雜度 \(\mathcal{O}(\sum m\sqrt m_i)\le \mathcal{O}(m\sqrt {qm})\)

可以匈牙利分析到 \(\mathcal{O}(matching(n,m)+nq)\)

匈牙利咋跑最小點(diǎn)覆蓋？將左部點(diǎn)中沒有匹配的點(diǎn)的集合稱作 \(U\)，那么從 \(U\) 中每個點(diǎn)出發(fā)跑一邊 bfs，每條 bfs 的路徑都沿著組交錯路，記經(jīng)過的點(diǎn)集為 \(Z\)，就能得到點(diǎn)覆蓋 \(C=(L/ Z)\cup(R\cap Z)\)

#8184. Different Summands Counting

考慮貢獻(xiàn)，二項(xiàng)式反演，答案即為

后面那個組合數(shù)前綴和是一個最多 \(m\) 次多項(xiàng)式，拉插即可

#8086. Cloyster

！？強(qiáng)強(qiáng)？！

考慮所有行的 \(\max\)，我們發(fā)現(xiàn)這些最大值是單峰的，即存在一個行 \(i\) 使得 \([1,i]\) 行的最大值單調(diào)遞增，\([i,n]\) 行的最大值單調(diào)遞減，所以我們可以考慮分治，具體來說，詢問中間行，并找到其最大值，查詢它周圍的 \(6\) 個點(diǎn)，如果比他大的在上面就向上遞歸，否則向下遞歸

如果直接遞歸子矩形，會出現(xiàn)大問題，因?yàn)檫@時候邊界上的點(diǎn)周圍會沒有比它大的，咋辦，我們把我們已知的那一圈拿出來，然后從那一圈的最大值 \(x\) 開始，順次給每個點(diǎn)賦權(quán)值 \(x-i\times \epsilon\)，這樣子矩形內(nèi)一圈周圍肯定有比它大的，再詢問中間行最大值的時候也算上最大值的那一圈，這樣就對完了

每問 \(\frac{3}{2}n+12\) 個數(shù)可以讓矩形縮小到原來的四分之一，總次數(shù)最多就是 \(3n+12\log n\)，隨便過

#1840. K-onstruction

考慮增量，如果當(dāng)前集合中所有正數(shù)的和為 \(ps\)，所有負(fù)數(shù)的和為 \(ng\)，和為 \(0\) 的子集數(shù)量為 \(x\)，不妨設(shè) \(|ps|>|ng|\)，現(xiàn)在考慮加入若干個 \(ps\) 的倍數(shù)，記這些數(shù)的集合為 \(S\)，如果 \(S\) 中為 \(0\) 的子集數(shù)量為 \(A\)，和為 \(-ps\) 的子集數(shù)量為 \(B\)，那么新的和為 \(0\) 的子集數(shù)量就是 \(Ax+B\)

所以可以考慮隨很多元素和 \(\ge 0\) 的小集合，記錄他們和為 \(0\) 和 \(-1\) 的子集個數(shù)，直接和原來的組合起來，就很有可能構(gòu)造出來小的方案

所以我們可以取大小 \(\le 10\) 且元素 \(\in\left\{-3,-2,-1,1,2,3\right\}\) 的集合作為小集合，如果 \(0\) 和 \(-1\) 的子集數(shù)量一樣就放在一起，記 \(F_x\) 為元素和為 \(0\) 的子集個數(shù)為 \(x\) 的最小的集合，然后跑一個最短路就行了

10.12

敲敲代碼

敲了兩道就不愿意敲了，太懶了

P2483 【模板】k 短路 / [SDOI2010] 魔法豬學(xué)院

我操了，K 短路也寫不動，雖然可能寫起來挺唐的，但我就是寫不動

P4119 [Ynoi2018] 未來日記

序列分塊，并查集維護(hù)每個值有幾個數(shù)

再上個值域分塊幫助查詢，復(fù)雜度 \(\mathcal{O}(n^{1.5})\)

#6551. Forever Young

我們先把序列看成完全單調(diào)的，對于每一個 \(i\) 都有 \(a_i>a_{i+1}\)，然后考慮用一個 \(01\) 序列去刻畫它，在 \(a_i\) 的位置放 \(0\)，其他的位置放 \(1\)，然后把左邊補(bǔ)上無窮多個 \(0\)，右邊補(bǔ)上無窮多個 \(1\)，那我們的操作就變成了，每次必須交換一對相鄰的 \(01\)，然后考慮把 \(0\) 看成石子，\(1\) 看成空地，每次操作就是把石子挪到相鄰的空地上

那么我們記一個字符串 \(S\subseteq\left\{L,R\right\}^{k}\)，其中 \(L\) 表示把石子往左挪，\(R\) 表示把石子往右挪，記 \(f(S)\) 為所有這樣的字符串對應(yīng)的操作序列的方案數(shù)，我們可以觀察到結(jié)論：\(f(RL)=f(LR)+f(\emptyset)\)，因?yàn)槟憧紤]到 \(f(LR)\) 和 \(f(RL)\) 唯一的區(qū)別在于把同一個石子連著挪兩次，否則肯定可以直接交換一下順序，那初始情況下，\(f(RL)\) 能挪的是所有 \(01\) 的位置，而 \(f(LR)\) 能挪的是所有 \(10\) 的位置，由于 \(01\) 和 \(10\) 必定交替出現(xiàn)，而開頭和結(jié)尾都是 \(01\)，所以 \(01\) 的位置正好比 \(10\) 多以，于是結(jié)論得證

那我們可以擴(kuò)展到 \(f(xRLy)=f(xLRy)+f(xy)\)，所以我們可以不停的把 \(RL\) 變成 \(LR\) 以生成一個形如 \(LL\cdots LLRR\cdots RR\) 的串，不妨稱其為簡單串，如果我們能算出來所有簡單串的答案，就能快速計(jì)算所有操作串的答案了

現(xiàn)在考慮怎么計(jì)算一個簡單串的答案，我們發(fā)現(xiàn)簡單串 \(L\) 和 \(R\) 的差值是一定的，也就是說如果知道了 \(L\) 的個數(shù)就一定會知道 \(R\) 的個數(shù)，而一個簡單串就相當(dāng)于，所有石子必須先向左挪一些距離再向右挪一些距離，并且不能存在某個時刻兩個石子的路徑相交，這引導(dǎo)我們考慮 LGV

不妨欽定一個排列 \(p\)，原來為位于 \(ka_i\) 的石子挪到位于 \(kb_{p_i}\) 的地方，我們枚舉中間點(diǎn) \(x\)，乘上容斥系數(shù)，其貢獻(xiàn)就是

其中 \(S=\sum ka_i-x_i\)，\(T=\sum kb_i-x_i\)，即 \(L\) 的數(shù)量和 \(R\) 的數(shù)量

那么我們可以直接考慮生成函數(shù) \(G_{x,y}(z)=\sum_{i}z^i\frac{1}{(x-i)!(y-i)!}\)，有 \(m\) 個 \(L\) 的簡單串的方案 \(g_m\) 就是

總方案咋算？每一個操作串都能通過每次交換或者刪除相鄰字符以得到一個簡單串，考慮簡單串的貢獻(xiàn)，我們不妨枚舉刪了幾對 \(RL\) 得到了一個簡單串，那么答案就是

其中 \(l=\frac{k-sumb+suma}{2}-i\)，\(r=k-2i-l\)，\(f_{i}\) 是所有長度為 \(2i\) 的被刪除的 \(LR\) 的方案，滿足相匹配的 \(R\) 在 \(L\) 的前面，則有 \(f_{0}=1\)，\(f_{n}=f_{n-1}\times(2(n-1)+1)\)，即先在最后加入一個 \(L\)，然后從前面 \(2n-1\) 個空里找一個放 \(R\)

這樣就做完了，多項(xiàng)式的次數(shù)只有 \(\max(n,m)\)，直接 NTT 可以求點(diǎn)值，\(L\) 和 \(R\) 不超過 \(suma\) 和 \(sumb\)，復(fù)雜度 \(\mathcal{O}(\max(n,m)^3\max(\sum a_i,\sum b_i)+K)\)

#6555. Sets May Be Good

考慮把問題轉(zhuǎn)化成求解膜 \(2\) 意義下 \(P(x_1,x_2,\cdots,x_n)=0\) 的解，其中所有的項(xiàng)都是形如 \(a_{i,j}x_ix_j\)，滿足 \(i\ne j\)，考慮摘出來某一項(xiàng)，考慮 \(x_1\)，那么 \(P\) 可以被拆成 \(x_1L(x_2,x_3,\cdots,x_n)+Q(x_2,x_3,\cdots,x_n)\) 的形式，\(L\) 只有 \(x_2,x_3,\cdots,x_n\) 的一次項(xiàng)，下面分討一下 \(x_1,L,Q\) 的取值

當(dāng) \(L=1\) 時

• 若 \(x_1=1\)，有 \(P=Q\)
• 若 \(x_1=0\)，有 \(P=1-Q\)
  當(dāng) \(L=0\) 時
• 有 \(P=Q\)

可以發(fā)現(xiàn) \(L=1\) 的時候 \(P=0\) 和 \(P=1\) 的解的個數(shù)是相同的，我們只需要計(jì)算 \(L=1\) 的解，那就是有一個位不自由的，那解的個數(shù)差不多就是一個 \(2\) 的幾次方，那我們只需要計(jì)算 \(L=0\) 且 \(Q=0\) 的情況的解的個數(shù)，處理 \(L=0\) 可以直接消元，那么我們便能遞歸子問題了

#7415. Fast Spanning Tree

！？強(qiáng)強(qiáng)？！

記 \(C_i\) 為 \(i\) 所在連通塊的大小，若 \(C_a+C_b\ge S\)，則 \(C_a\) 和 \(C_b\) 至少有一個 \(\ge \frac{S}{2}\)，所以我們可以把 \((a,b,s)\) 拆成兩個事件 \((a,\left\lceil\frac{S}{2}\right\rceil)\) 和 \((b,\left\lceil\frac{S}{2}\right\rceil)\)，若 \(C_a\) 或者 \(C_b\) 超過 \(\left\lceil\frac{s}{2}\right\rceil\)，就 check 一下是否 \(C_a+C_b\ge S\)，否則將 \(S-C_a-C_b\) 再均分到兩邊，也就是更新為 \((a,C_a+\left\lceil\frac{S-C_a-C_b}{2}\right\rceil)\) 和 \((b,C_b+\left\lceil\frac{S-C_a-C_b}{2}\right\rceil)\)，這樣每個 \(S\) 最多更新 \(\mathcal{O}(\log S)\) 次，用一個堆維護(hù)當(dāng)前能夠合并的最小編號，再每個點(diǎn)開一個堆維護(hù)最小的更新的限制，直接啟發(fā)式合并即可，復(fù)雜度 \(\mathcal{O}(n\log^2n)\)

#7417. Honorable Mention

可以直接串一串然后流出來，所以關(guān)于 \(k\) 是凸的

考慮線段樹維護(hù)，記 \(f_{0/1/2,0/1/2,cnt}\) 表示左端點(diǎn)的狀態(tài)，右端點(diǎn)的狀態(tài)，有多少段，其中 \(0/1/2\) 分別表示當(dāng)前點(diǎn)不選/選了且不是一段的開頭/選了且是一段的開頭，這樣 \(cnt\) 就好維護(hù)了，直接維護(hù)有多少 \(2\) 就行了

線段樹上閔和合并，詢問的時候拉出來 \(\mathcal{O}(\log n)\) 個區(qū)間，直接閔和太唐了，所以可以外層 wqs 二分，每個區(qū)間分別二分凸包上的答案再合并，這樣復(fù)雜度是 \(\mathcal{O}(n\log^3n)\) 的

于是考慮整體 wqs 二分，發(fā)現(xiàn)分治樹里，每一層我們所二分的 \(mid\) 都是單調(diào)的，于是對于每一層可以把 \(mid\) 掛在線段樹的節(jié)點(diǎn)上然后做詢問，直接維護(hù)一個指針掃一遍，這樣避免了在線段樹的節(jié)點(diǎn)上二分，整個線段樹全掃一遍的復(fù)雜度是 \(\mathcal{O}(n\log n)\) 的，而總共二分 \(\log n\) 層，所以總復(fù)雜度 \(\mathcal{O}(n\log^2n)\)

10.13

2077 真好玩

10.14

模擬賽

T1

有點(diǎn)弱，，，

T2

這么強(qiáng)？！

T3

我草原

T4

記 \(nxt_i\) 為 \(i\) 后面第一個和他顏色相同的，那么我們要算的就是前綴的 \(maxnxt-i\) 的最大值，這個可以直接單側(cè)遞歸維護(hù)

#2605. Soccer Match

考慮隨便給所有點(diǎn)紅藍(lán)染色，假如我們找到了一種方案，至少有 \(\frac{1}{2}M\) 條邊其兩端分別是紅色和藍(lán)色，那么此時由 \(M\ge2KN\) 可以得到 \(\frac{1}{2}M\ge KN\)，即異色邊的數(shù)量至少是有顏色的頂點(diǎn)的 \(K\) 倍，現(xiàn)在考慮調(diào)整，我們找到一個點(diǎn)，其異色鄰居 \(\le K\)，可以把他調(diào)整成白色，這樣有顏色的頂點(diǎn)會減一，而異色邊的數(shù)量最多減 \(K\)，所以始終有異色邊的數(shù)量至少是有顏色的頂點(diǎn)的 \(K\) 倍

這樣調(diào)整不會寄嗎？如果寄了，我們肯定會調(diào)整到還剩一個有色點(diǎn)，這時候有 \(0\) 條異色邊，和上面的結(jié)論相矛盾，所以這樣調(diào)整一定正確

那么我們現(xiàn)在的目標(biāo)就是找到一種方案，使得異色邊的數(shù)量至少為 \(\frac{1}{2}M\)

考慮隨機(jī)化，我們給每個點(diǎn)隨一個顏色，那么此時期望有 \(\frac{1}{2}M\) 條異色邊，為啥呢，考慮一個一個加點(diǎn)的過程，這時候當(dāng)前點(diǎn)是藍(lán)或者紅的兩種情況中，邊的情況正好相反，所以我們可以認(rèn)為每條邊都是獨(dú)立染色的，記有 \(m\) 條邊的期望為 \(f_m\)，那么有 \(f_{m}=f_{m-1}+\frac{1}{2}\)，考慮 \(E(X^2)\)，有 \(g_{m}=\frac{1}{2}g_{m-1}+\frac{1}{2}(g_{m-1}+2f_{m-1}+1)=g_{m-1}+\frac{m}{2}=\frac{m(m+1)}{4}\)，那么有 \(\sigma^2=DX=E(X^2)-E(X)^2=\frac{m}{4}\)，如果我們最后至少會操作 \(k\) 輪，則有

如果直接取 \(k=c\sqrt m\)，概率就是 \(\frac{1}{4c^2}\)，那可以說 \(k\) 大概率是 \(\mathcal{O}(\sqrt m)\) 級別的（？總感覺這樣說不太舒服啊）

但是直接積出來是一個 \(\mathcal{O}(1)\) 的東西，我其實(shí)沒懂

#12302. Unfair Card Deck

考慮求出任意的 \(\frac{a_iX_i}{a_jX_j}\)，我們可以把這兩種牌拉出來，其他的牌顯然是不影響這兩個牌的，所以可以統(tǒng)計(jì)第一次出現(xiàn)這兩種中的一個的花色的頻率，然后就能算這個比值了

但是在比值很懸殊的情況下這個算的不準(zhǔn)，于是考慮先給 \(a_iX_i\) 排序，可以每次找到第一次出現(xiàn)的次數(shù)最多的卡牌，把這個看作 \(a_iX_i\) 最大的，然后把這個東西刪掉遞歸子問題就行了

復(fù)雜度 \(\mathcal{O}(nm)\)

#7412. Counting Cactus

記 \(f_{i,S}\) 為根為 \(i\) 的方案

記 \(g_{i,S}\) 為根為 \(i\)，根上只接了一個環(huán)的方案

記 \(h_{i,j,S}\) 為環(huán)的起點(diǎn)為 \(i\)，終點(diǎn)為 \(j\) 的方案

有轉(zhuǎn)移：

• \(f_{i,S}\times g_{i,T}\rightarrow f_{i,S\cup T}\)，其中 \(S\cap T=\emptyset\) 且 \(\text{lowbit}(S\cup T)\in S\)
• \(h_{i,j,S}\rightarrow g_{i,S},f_{i,S/\{j\}}\rightarrow g_{i,S},g_{i,S}\times\frac{1}{2}\rightarrow g_{i,S}\)，其中 \(\exists (i,j)\in E\)
• \(f_{j,S/\{j\}}\times h_{i,k,T}\rightarrow h_{i,j,S\cup T}\)，其中 \(S\cap T=\emptyset\) 且 \(\exists(k,j)\in E\)

復(fù)雜度 \(\mathcal{O}(n^33^n)\)

#6104. Building Bombing

你轉(zhuǎn)置牛魔呢

前面的不用管，后面的考慮一個 \(dp_{k,i}\) 表示 \(i\) 是第 \(k\) 個前綴 \(\max\) 的最小代價，直接線段樹優(yōu)化轉(zhuǎn)移即可，復(fù)雜度線性對數(shù)

10.15

#1844. Cactus

考慮一個環(huán)怎么做，此時這個環(huán)上所有點(diǎn)的度數(shù)都是偶數(shù)，考慮執(zhí)行一次 \(2\) 操作再刪點(diǎn)，如果環(huán)長 \(n\) 為偶數(shù)，則我們可以構(gòu)造出刪掉 \(2,4,6,\cdots,n,n+3,n+5,n+7,\cdots,2n-1,n+1\)，如果 \(n\) 是奇數(shù)，我們可以構(gòu)造 \(2,4,6,\cdots ,n-1,n+3,n+5,n+7,\cdots,2n,n,n+2,n+1\)

發(fā)現(xiàn)這樣可以把邊刪完，而且最后會刪掉 \((1,n+1)\)，于是考慮對于原仙人掌，找到一個環(huán)，其僅有一個點(diǎn)和其他環(huán)相連，記這個交點(diǎn)為 \(u\)，則可以執(zhí)行上面的操作使得這個環(huán)只剩下 \((u,u+n)\) 這條邊，如果這條邊可以直接刪了，我們就能遞歸子問題，但是如果 \(u\) 在原圖上的度數(shù)為奇數(shù)，直接爆了，所以我們可以在最開始進(jìn)行 \(1\) 操作刪掉度數(shù)為奇數(shù)的邊，如果我們能夠證明，每次刪掉一個環(huán)之后仍然滿足所有點(diǎn)度數(shù)為偶數(shù)，那就做完了

接下來證明這個結(jié)論，給出引理：一個仙人掌上所有點(diǎn)都是偶數(shù) \(\Leftrightarrow\) 這個仙人掌上沒有割邊

證明：

不存在割邊 \(\Rightarrow\) 所有點(diǎn)度數(shù)都是偶數(shù)

• 此時所有點(diǎn)都在若干個環(huán)上，而一個環(huán)有進(jìn)有出，所以所有點(diǎn)度數(shù)都是偶數(shù)
  所有點(diǎn)度數(shù)都是偶數(shù) \(\Rightarrow\) 不存在割邊
• 考慮證明其逆否命題，即存在一條割邊 \(\Rightarrow\) 存在一個點(diǎn)度數(shù)為奇數(shù)，考慮數(shù)學(xué)歸納法，縮邊雙，則每一個邊雙內(nèi)每個點(diǎn)度數(shù)都是偶數(shù)，我們考慮縮出來的樹的一個葉子，其割邊連到葉子的那個點(diǎn)肯定度數(shù)為奇

所以結(jié)論得證，那直接做就行了，復(fù)雜度線性

#10092. Interactive Primality

如果問出了一個質(zhì)數(shù)，他有什么影響，可以發(fā)現(xiàn)此時對于任意的 \(p<x+y\)，都有 \(p\not\mid x+y\)，也就是 \(x\not\equiv -y\pmod p\)

所以可以考慮一些小的質(zhì)數(shù) \(p_1,p_2,\cdots,p_k\)，如果我們確定了 \(x \bmod p_i\) 的值，跟據(jù)中國剩余定理，只要 \(x\in [1,\prod p_i]\)，我們就可以解出 \(x\) 的唯一的值，于是可以取 \(p_1=2,p_2=3,\cdots,p_k=53\)，滿足其乘積 \(>10^{18}\)，我們問出一個質(zhì)數(shù)，就能對于所有的 \(p_i\)，排除一個 \(x \bmod p_i\) 的可能，那么只需要排除 \(p_i-1\) 輪就能確定 \(x\bmod p_i\) 的值

先隨便問一問，問出來一個 \(x+y\) 是質(zhì)數(shù)，然后再隨機(jī)問就太唐了，如果我們已經(jīng)排除了一些空位，那么后面肯定在沒有排除的位置中隨機(jī)是更優(yōu)的，那我們要問 \(p_k-1\) 次質(zhì)數(shù)就能確定 \(x\) 的值了

每次問出來質(zhì)數(shù)的概率是多少，首先所有沒問出來 \(\equiv -x\pmod p\) 的概率是 \(\prod_{p_j>i} \frac{p_j-i}{p_j-i+1}\)，但是這個并沒有考慮 \(>p_k\) 的質(zhì)數(shù)的影響，所以我們還要乘上其是質(zhì)數(shù)的概率，為 \(\frac{1}{\ln n}\prod _{j}\frac{p_j}{p_j-1}\)，那大概 \(860\) 輪就能做完了，\(10\) 組不超過 \(8750\)

#10094. Slot Machine

我會 \(n^3\)！記 \(f_{l,r,v}\) 為機(jī)器里的數(shù)在 \([l,r]\) 中，顯示的數(shù)為 \(v\) 的最小代價，則有兩種轉(zhuǎn)移，\(f_{l,r,v}\rightarrow f_{l,r,v'}\) 以及 \(\max(f_{l,v-1,v},f_{v+1,r,v})\rightarrow f_{l,r,v}\)，其中 \(s_v=1\)，這個狀態(tài)太唐了，我們發(fā)現(xiàn)轉(zhuǎn)移時要么滿足 \(v=l+1\) 要么滿足 \(v=r-1\)，所以第三維可以直接記 \(0/1\)，仍然難以維護(hù)，考慮有沒有單調(diào)性

引理：\(\forall l<r\)，有 \(f_{l,r,0}\ge f_{l,r-1,0}\) 且 \(f_{l,r,1}\ge f_{l+1,r,1}\)

證明考慮歸納，考慮證明 \(f_{l,r,0}\) 的情況，另一種情況對稱，對于只有一個 \(x\in[l,r]\) 滿足 \(s_{x}=1\)，則結(jié)論顯然成立，否則考慮其最小的轉(zhuǎn)移點(diǎn) \(v\)，有 \(f_{l,r,0}=\max(f_{l,v-1,1},f_{v+1,r,0})+c(l-1,v)\)，其中 \(c(x,y)\) 是 \(x\) 和 \(y\) 不同的數(shù)位個數(shù)，此時轉(zhuǎn)移到 \(r-1\) 應(yīng)該不小于 \(\max(f_{l,v-1,1},f_{v+1,r-1,0})+c(l-1,v)\)，而由歸納假設(shè)有 \(f_{v+1,r-1,0}\le f_{v+1,r,0}\)，所以有 \(f_{l,r-1,0}\le f_{l,r,0}\)

引理：\(f_{l,r,t}\le k\left\lceil\log_2(r-l+1)\right\rceil\)

考慮在 \(\frac{l+r}{2}\) 處轉(zhuǎn)移，每次轉(zhuǎn)移最多加 \(k\)，這樣最多 \(\log\) 個 \(k\)

于是考慮記狀態(tài) \(R_{l,v}\) 表示最大的 \(r\) 滿足 \(f_{l,r,0}\le v\)，記 \(L_{r,v}\) 表示最小的 \(l\) 滿足 \(f_{l,r,1}\le v\)，從小到大掃 \(v\)，考慮 \(f_{l,r,0}\le v\)，需要存在 \(x\in[l,r]\)，滿足 \(\max(f_{l,x-1,1}+f_{x+1,r,0})+c(l-1,x)\le v\)，也就是滿足 \(l\ge L_{x-1,v-c(l-1,x)},r\le R_{x+1,v-c(l-1,x)}\)，所以對于 \(c(l-1,x)\) 相等的 \(l\)，\(x\) 可以轉(zhuǎn)移到其一段前綴，所以考慮枚舉 \(c(l-1,x)\) 的具體情況，我們欽定一些位置不變，而另一些位置任選，這樣能夠轉(zhuǎn)移到的數(shù)我們可以用一個十一進(jìn)制數(shù)來表示，某一位上是 \(10\) 表示這一位可以隨便填，由于轉(zhuǎn)移到的是前綴，所以做一個后綴 \(\min\) 就行了，兩種轉(zhuǎn)移是類似的

狀態(tài)數(shù) \(\mathcal{O}(10^kk\log k)\)，轉(zhuǎn)移復(fù)雜度 \(\mathcal{O}(2^{k})\)，總復(fù)雜度 \(\mathcal{O}(20^kk\log k)\)

#4241. Angle Beats 2.0

考察每一個 \(L\)，發(fā)現(xiàn)其相當(dāng)于上下選一個左右選一個，連邊，那不同連通塊的貢獻(xiàn)是獨(dú)立的

考察一個連通塊，如果其邊數(shù)大于點(diǎn)數(shù)，爆了，如果其邊數(shù)等于點(diǎn)數(shù)，則基環(huán)樹的環(huán)上有兩種方案定向，貢獻(xiàn)為 \(2\)，如果是樹可以隨便定根，貢獻(xiàn)為連通塊大小

復(fù)雜度線性

#4243. Good Coloring

！？強(qiáng)強(qiáng)？！

考慮給每個點(diǎn)一個權(quán)值 \(v\) 為其鄰居顏色的 \(\text{mex}\)，如果 \(v\) 小于其當(dāng)前顏色就把當(dāng)前顏色替換掉，那么一直這樣做下去，每個點(diǎn)的鄰居中肯定有一個點(diǎn)的顏色為他的顏色減一

那么我們給所有的點(diǎn)按原顏色排序，做一遍上述過程就行了，復(fù)雜度線性

#962. Thanks to MikeMirzayanov

把操作看成給整個序列翻轉(zhuǎn)，再把若干個連續(xù)段翻轉(zhuǎn)，那整個序列翻轉(zhuǎn)的操作無關(guān)緊要，我們只需要關(guān)注每次翻轉(zhuǎn)一個段

考慮分治，嘗試按 \(\le \frac{n}{2}\) 和 \(>\frac{n}{2}\) 分類，那現(xiàn)在就是給 `01 排序

考慮把每一段相同的合并起來，那可以看成 01010101010101...，如果第一段是 1，就給第一段前面加上 0，每次把第 \(2i\) 和第 \(2i+1\) 段合起來翻轉(zhuǎn)一下，這樣可以令段數(shù)減半，那么總操作次數(shù)是 \(\sum_{i=1}^{\log n}i\le 120\)

P5416 [CTSC2016] 時空旅行

也就出出這種傻逼題

拆到 dfn 序上，每個點(diǎn)貢獻(xiàn)到 \(\mathcal{O}(1)\) 個 dfn 區(qū)間，所有直線按斜率在外面排序，所有詢問也在外面排序，詢問的時候掃一遍，復(fù)雜度 \(\mathcal{O}(n\log n)\)

P4577 [FJOI2018] 領(lǐng)導(dǎo)集團(tuán)問題

線段樹合并優(yōu)化 dp

#10542. Protecting Kingdom

長剖，記 \(f_{u,i}\) 為 \(u\) 往下伸 \(i\) 個點(diǎn)的最小邊權(quán)，更新答案的時候直接雙指針，復(fù)雜度線性

P3201 [HNOI2009] 夢幻布丁

dsu

P5170 【模板】類歐幾里德算法

學(xué)習(xí)了萬歐做法

CF868G El Toll Caves

首先 \(n,k\) 可以同除 \(\gcd\)，此時 \(n,k\) 互質(zhì)，那么每放 \(n\) 次就有一個周期，設(shè)這個周期的答案為 \(S\)，那么最后的期望 \(E\) 就滿足 \(E=\frac{1}{2^k}(E+n)+S\)

現(xiàn)在考慮算 \(S\)，記 \(f_i\) 為在第 \(i\) 個點(diǎn)被找到的期望，有

• \(f_{i}=f_{i-k}+1\)，其中 \(i\ge k\)
• \(f_{i}=\frac{1}{2}+\frac{1}{2}(f_{i-k+n}+1)\)，其中 \(0\le i<k\)

令 \(f_0\) 為主元，從 \(0\) 開始，每次加 \(k\) 膜 \(n\)，如果 \(\ge n\) 了就會除以二，而加 \(k\) 會加一，這是一個萬歐的形式，即 \(y=\frac{k}{n}x\) 這條線上的答案

用一個幺半群維護(hù)一下一次函數(shù)歷史和，復(fù)雜度 \(\log n\)

10.16

模擬賽

成傻子了

T1

。

T2

。

T3

。

T4

。

#14426. Grid Problem

感受一下，第二個矩陣構(gòu)造的有點(diǎn)刻晴了，所以大概能消成一個簡單的形狀，觀察到左上和右下都是 \(2\)，所以可以在 \((1,1)\) 和 \((2,2)\) 的位置各放一個 \(\begin{bmatrix}2&1\\1&2\end{bmatrix}\)，然后你就能消成 \(\begin{bmatrix}0&4&2\\4&1&4\\2&4&0\end{bmatrix}\)，再在 \((1,2)\) 和 \((2,1)\) 各放兩個，可以消成只有中間是三的矩陣

所以我們可以給每個位置減三，那么多搞幾個矩陣加起來把和搞到正無窮之后再減三就行了，發(fā)現(xiàn)加的矩陣行列加起來都是 \(3\) 的倍數(shù)，所以新的矩陣每行每列加起來也必須是 \(3\) 的倍數(shù)，即求

考慮單位根，反演，則原式等于

令 \(f(x)=\sum_{i=0}^{k}\omega_{3}^{ix}\)，則原式等于

考慮枚舉有多少個 \(r=0/1/2\)，記為 \(d_0,d_1,d_2\)，就變成了算

令 \(g(x)=\prod_{i=0}^{2}f(x+i)^{d_i}\)，則

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

#14432. Cyclic Topsort

先把所有一開始就能用的點(diǎn)都刪了，然后就是每次刪一個點(diǎn)，看它能新拓?fù)涑鰜矶嗌冱c(diǎn)

發(fā)現(xiàn)一個點(diǎn)能拓?fù)涑鰜淼狞c(diǎn)的集合要么不交要么包含

于是可以每次隨機(jī)一個點(diǎn)，然后把他能拓?fù)涞降狞c(diǎn)都刪了，以后不再以他能拓?fù)涞降狞c(diǎn)為起點(diǎn)進(jìn)行隨機(jī)，這樣復(fù)雜度是期望 \(\mathcal{O}(m\log n)\) 的，因?yàn)檫@相當(dāng)于在一棵樹上，每次選擇一個點(diǎn)，然后花費(fèi) \(\mathcal{O}(siz)\) 的代價 ban 掉其子樹，那一個點(diǎn)的貢獻(xiàn)就是其到根鏈上選的點(diǎn)的個數(shù)，是 \(\mathcal{O}(\log n)\) 級別的，總復(fù)雜度就是 \(\mathcal{O}(m\log n)\)

#8085. Bulbasaur

最大流轉(zhuǎn)最小割，記 \(f_{i,S,w}\) 為考慮了前 \(i\) 行，\(S\) 和源點(diǎn)相連，最小割 \(\le w\) 的方案

復(fù)雜度 \(\mathcal{O}(n2^kk^2)\)

#6545. Connect the Dots

這是一個平面圖，考慮把所有的點(diǎn)排一圈，相鄰的盡量連，因?yàn)槠鋵?nèi)部無影響，考慮內(nèi)部，最優(yōu)的方案肯定是一個三角剖分，我們發(fā)現(xiàn)，如果至少有三種顏色，則一定存在一個三角剖分

考慮歸納證明，對于 \(n=3\) 顯然成立，對于 \(n>3\)，我們?nèi)我膺x取兩個顏色不同的點(diǎn)，使得這兩個點(diǎn)剖分出來的兩個新的多邊形中含有一個第三個顏色的點(diǎn)，如果能找到這樣的點(diǎn)對，可以直接歸納得證，否則，不可能存在形如 \(121\) 的連續(xù)三個點(diǎn)，要不然選其中一個點(diǎn)為第二個點(diǎn)，在其他地方選擇第三種顏色的點(diǎn)即可，那么這時候環(huán)肯定形如 \(11...1122...2233...33\)，我們可以選擇第一個 \(1\) 和所有的 \(2\) 和 \(3\) 連邊，再把第一個 \(2\) 和前面的 \(1\) 都連邊，也能構(gòu)造出來一個合法的方案

所以現(xiàn)在就是只有兩種顏色的情況，發(fā)現(xiàn)環(huán)形如 \(1212121...\) 的時候，我們只能構(gòu)造出四角剖分，于是可以猜測答案和相鄰的相同顏色對數(shù)有關(guān)，記這個數(shù)為 \(C\)，手玩幾個情況，發(fā)現(xiàn)答案大概是關(guān)于 \(n\) 和 \(C\) 都是線性的，所以可以猜測答案就是 \((n+C)/2-2\)

可以歸納證明：對于 \(n=3\) 顯然成立，對于 \(n>3\)，任意找到一個 \((1,2)\)，把整張圖分成兩部分 \((n_1,C_1)\) 和 \((n_2,C_2)\)，此時有 \(C_1+C_2=C,n_1+n_2=n+2\)，那么兩邊的答案加起來就是 \(\frac{n_1+C_1}{2}-2+\frac{n_2+C_2}{2}-2+1=\frac{n+C}{2}-2\)，結(jié)論得證，同時我們也可以說明，每次任意選擇一個 \((1,2)\) 都是最大的

感覺這個答案的式子太奇怪了，為啥這樣就對了

復(fù)雜度線性

P7457 [CERC2018] The Bridge on the River Kawaii

值域很小，枚舉權(quán)值最大的邊做 \(v\) 邊線段樹分治，復(fù)雜度 \(\mathcal{O}(vn\log^2n)\)

P3363 Cool loves jiaoyi

雙指針，鏈加鏈 \(\max\)，復(fù)雜度 \(\mathcal{O}(n\log^2n)\)

P4350 [CERC2015] Export Estimate

從大往小加邊，維護(hù)出來二度點(diǎn)、零度點(diǎn)的數(shù)量

特殊情況是一個全是二度點(diǎn)的環(huán)，把這種環(huán)的數(shù)量再用并查集維護(hù)出來

復(fù)雜度 \(\mathcal{O}(n\alpha (n))\)

AT_agc049_d [AGC049D] Convex Sequence

\(A\) 是凸的，于是找到最低點(diǎn)，往左往右加一些 \(1,2,3,4,\cdots\)，那么就相當(dāng)于有無限個體積為 \(n,1,3,6,10,\cdots\) 的物品可以加進(jìn)去，這樣的物品有 \(\sqrt m\) 個，對于每一個最低點(diǎn)都做一遍背包直接爆了，但是這個背包可以撤銷，所以復(fù)雜度就是 \(\mathcal{O}(m\sqrt m)\)

有一個細(xì)節(jié)是，最低點(diǎn)可以有很多個，所以我們要?dú)J定最低點(diǎn)左邊加了 \(1,2,3,4,\cdots\)

AT_abc180_f [ABC180F] Unbranched

瞎幾把差分一下，寫出來環(huán)和鏈的 EGF \(A\) 和 \(B\)，答案就是 \(n![x^n]\frac{A^{n-m}}{(n-m)!}\exp(B)\)

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