CF2048

D

記得 \(\sum\limits_{i=1}^n{n\over i}= n\log n\)，不要記錯了。唐題一個，發現貪心最優于是排序后暴力即可。

E

簡單二分圖構造題。考慮臺階形即可。

F

考慮如果操作一個 \(b_i\)，那么我們會盡量讓區間長。于是考慮一個 \(b_i\) 會支配一個區間，這個可以笛卡爾樹求。求完后我們就可以在樹上 dp 了，設 \(f_{i,j}\) 表示當前在點 \(i\) 最大的數是 \(j\) 所操作最少次數。這個不好做考慮換維 dp，設 \(f_{i,j}\) 表示在點 \(i\) 操作了 \(j\) 使得最大值最小是多少。轉移就是合并一下背包然后更新即可。注意到第二維很小于是直接做就沒了。復雜度 \(\mathcal O(n\log^2V)\)。

G

正難則反，考慮用總方案 \(V^{nm}\) 減去不合法的方案。考慮枚舉不等式兩邊的取值就有：

其中 \(f(x,y)\) 表示左右兩邊的值，考慮修改一下定義，設 \(f(x,y)\) 表示左邊 \(\ge x\) 且右邊 \(\le y\) 的答案，然后答案變成了：

現在考慮單次 \(f(x,y)\) 如何計算。考慮最普通的容斥，思路是我們考慮先求出欽定的答案然后容斥出恰好的答案。比如我們欽定有 \(i\) 行最大值小于 \(x\)，考慮計算方案。我們繼續容斥，用總方案數減去不合法數。注意到每列是獨立的于是我們考慮每一列的情況。答案是 \((x-1)^iV^{n-i}-(x-y-1)^i(V-y)^{n-i}\)。于是我們就能得到 \(f\) 的式子了：

于是答案就可以 \(\mathcal O(nV(\log n+\log m))\) 計算。

H

考慮最后得到的串每個位置的來源。我們設第 \(i\) 個位置的來源是 \([l_i,r_i]\)，初始有 \(\forall i\in[1,n],l_i=r_i=i\)。現在我們考慮一次操作 \(p\) 的影響，假設操作前每個位置的來源分別是 \([l_1,r_1],[l_2,r_2]\dots,[l_m,r_m]\) 那么我們對 \(\forall i[1,p)\) 進行擴展并把第 \(p\) 個位置刪掉侯就會得到 \([l_1,r_2],[l_2,r_3],\dots[l_{p-1},r_p],[l_{p+1},r_{p+1}],\dots,[l_m,r_m]\)。注意到我們一次操作只會刪掉 \(r_1\) 以及一個 \(l_p\)，于是最終的形態一定是若干 \([l,r]\) 的區間滿足，對于 \(l\)，\(l_i\) 構成一個子序列，對于 \(r\)，\(r_i\) 是一段后綴 \([k,n]\)。于是我們可以嘗試對每個串的 \([l,r]\) 序列進行 dp。設 \(f_{i,j}\) 表示串的第一個 \([l,r]\) 為 \([j,i]\) 的答案。注意為了保證計數的時候不會重復計算于是我們僅在最大的合法的 \(j\) 處統計答案。

具體的，轉移考慮枚舉右端點 \(i\)，考慮不同情況下應該如何轉移。我們考慮原將來的串看成一些 0 和 1 的連續段，我們在這上面走就是在進行 dp 的轉移。如果當前在 1 上面我們就可以正常走，于是可以從 \(f_{i,j}\rightarrow f_{i-1,j-1}\)，如果在 0 上面，我們也可以有相同的操作，這里不重復寫，考慮我們還可以跳過一些 0，轉移到左邊最近的 1 的位置，就有 \(f_{i,j}\rightarrow f_{i-1,las_j}\)。我們發現這個 dp 本質是區間平移，單點修改，于是我們令 \(j'=i-j\)，然后每次從 \(f_i\) 到 \(f_{i-1}\) 就有很多狀態可以繼承。考慮變化的是 \(las_i\) 的東西，于是我們就單獨用一個變量記錄即可。注意到 \(las_i\) 有單調性于是時間復雜度可以做到 \(\mathcal O(n)\)。

I1

考慮從簡單情況入手。我們發現如果最左邊是 L 或者最右邊是 R 那么這個位置的 a 一定是 0，可以遞歸到一個子問題。于是考慮每次處理序列的左右兩端，分討不同情況。具體如下：

• \(s_1=L,s_n=R\)，剛剛說了就是直接扔掉兩邊的，然后剩下的部分整體帶了一個 +1 的標記。
• \(s_1=s_n=L/R\)，以 \(s_1=s_n=L\) 為例，另一種情況同理。考慮 \(a_1=0\) 是顯然的，假設 \(a_n=x\)，考慮 \(a_i,i\in[2,n-1]\) 的取值范圍是 \([1,x)\) 且每種值都存在，證明可以考慮反證法。假設存在大于 \(x\) 的 \(a_i\)，那么考慮 \(a_i\) 如果要合法那么一定就會和 \(a_n\) 的限制沖突，具體不詳細說明。這種情況的處理方式同上即可。
• \(s_1=R,s_n=L\)，此時我們發現序列中所有數一定大于 0，這是顯然的。然后考慮所有數都填 1 就能構造出合法的方案了。注意到我們每次遞歸第二種情況的時候要求了從 0 到一個上界的數都存在，但是這種條件下 0 不存在，于是就不合法了。所以我們只需要判掉第二種情況里面套第三種情況的序列就可以直接遞歸構造了。

CF2066

A

腦筋急轉彎好題！考慮是否全排列，兩種情況分開處理。對于全排列的情況，我們可以去詢問 1 和 \(n\) 然后看正反是否相同且路徑長度大于等于 \(n-1\) 即可；否則我們就考慮不在序列中的一個數，這個數代表的點在 A 類圖中一定沒有出邊，于是詢問這個點和任意一個出現過的點即可。

B

首先考慮有多個 0 的情況一定是保留最前面的 0 最優，然后考慮只有一個 0 的時候，我們從 0 的位置開始往前掃，如果不合法那么說明我一定會進行一次修改。考慮如果不改 0 可能之后還有修改就不優了，如果修改了 0 那么后面一定全部合法，于是選擇后者即可。

C

考慮一個樸素的 dp，設 \(f_{i,j}\) 表示操作完第 \(i\) 個數后，兩個數相同，另外一個相對異或值為 \(j\) 的方案數。轉移狀態數是 \(\mathcal O(1)\) 的但是最后的狀態可能很多，于是滾動數組然后用 map 存第二維即可。

D

對于計數題考慮找充要條件。考慮一個數字能填需要滿足其前面還沒有 \(c\) 個數大于它，注意這個限制是后綴的，所以我們考慮值域的前綴。對于 1 我們只能放在 \([1,c]\)，以此類推，我們能夠得到 \(i\) 能夠放置的區間 \([1,c+\sum\limits_{j<i}\text{cnt}_j]\)，其中 \(\text{cnt}_j\) 是 \(j\) 的數量。于是我們可以對其考慮 dp，設 \(f_{i,j}\) 表示考慮到 \(i\) 填了 \(j\) 個數的方案數。轉移考慮枚舉 \(i\) 放了多少個，設為 \(k\)，其上界是 \(\min(j,c)\)。此時我們能夠知道 \(i\) 填數范圍是 \([1,c+j-k]\)，首先我們需要判斷這個上界是否合法，因為可能存在已經給出的 \(i\) 的最右邊不在區間內的情況。判斷轉移合法性之后就簡單了，現在只需考慮填數的方案數即可。因為之前已經有 \(j-k\) 個數，于是還剩下 \(c\) 個空位，但是考慮到原來的序列本身還有一些數已經確定，于是還要減去這段前綴區間內 \(\ge i\) 的數的個數，設為 \(s\)。考慮我們需要將 \(k\) 個 \(i\) 放進去，但是可能原來序列中也有一些 \(i\) 了，其數量設為 \(t\)，那么我們的方案數就是 \(c-s\choose k-t\)。于是最后的 dp 式子就是：

時間復雜度 \(\mathcal O(nmc)\)。

E

考慮如果有兩個相同重量的桶那么我們就能比較他們，并且比較了之后這兩個桶里面的水我們就能自由調動了。假設我們現在有 \(x\) 的水能夠自由調動，考慮如何拓展。思考不難發現有兩種情況：

1. \(x\ge a_i\)，我們能夠分出恰好 \(a_i\) 的水去比較，于是 \(a_i\) 也能用了。
2. \(a_i<a_j,a_i+x\ge a_j\)，于是我們考慮給少的分一些水然后就可以比較兩個桶了，然后這兩個桶的水就都能用了。

于是我們給 \(a_i\) 排序，從小到大考慮水，每次先找到兩個相同的然后開始拓展。容易得到單次 \(\mathcal O(n)\) 的做法。現在考慮優化。

可以發現每次拓展了一個新的桶之后我們又可以多拓展很多桶，并且考慮上述兩種拓展的方法其 \(x\) 的增長都是 \(\ge 2a_i\) 的。于是我們考慮倍增值域，更進一步，我們能夠聯想到一個東西，叫做倍增值域分塊。現在考慮分塊后如何拓展。

對于一個 \(2^k\le a_i<2^{k+1}\) 的桶，如果我們能夠拓展出它，那么我們一定能夠拓展整個塊內的元素，證明上面已經提過就不贅述了。于是每次我們從小到大去掃這 \(\mathcal O(\log)\) 個塊，分別去看兩種方式是否存在一種能夠拓展這個塊內的一個元素即可。

具體的，我們考慮對于每個塊維護兩個 multiset 分別記錄 \(a_i\) 和 \(\Delta=a_{i+1}-a_i\)，然后每次拿塊內最小的去和 \(x\) 進行比較即可。注意塊間的 \(\Delta\) 不要算漏即可。時間復雜度 \(\mathcal O(n\log V)\)。

CF2115

B

首先倒著考慮每個操作，因為確定一個數不好做于是轉化成確定一個數大于等于多少，然后判合法即可。

C

思考兩種不同的操作在什么時候要做什么時候不做。對于閃耀，如果全局最小值大于 1 那么一定要做；對于普通，如果當前所有數都相同，我們做了之后可能沒有我們等閃耀然后一直全局減更優，這里需要比較一下代價；否則就可以直接做普通的操作。

注意到我們考慮是否做操作取決于全局最小值，于是我們考慮 dp，然后記錄最小值，于是有 \(f_{i,j}\) 表示還有 \(i\) 次操作，全局最小值為 j 的概率。轉移比較困難考慮加入更多的限制。這里有個 trick，具體可以看這道題的題解。就是說我們記錄了最小值后就只用考慮上面的東西。于是就可以正常寫轉移了：

此時 dp 時間復雜度為 \(\mathcal O(nmV^2)\)，會寄，考慮一個優化。就是說當我們的 \(s\) 第一次變成 0 的時候 \(s\) 的上界就是 \(n-1\) 了，所以我們去枚舉 \(s\) 什么時候變成 0 第三維就只用考慮到 \(n\) 了。式子也比較簡單：

其中 \(mi\) 是全局最小值。但是你如果這么寫會炸精度，所以我們需要遞推前面的系數。遞推考慮 \(g_{i,s}\) 表示前面那坨，于是我們拆組合數就可以 \(\mathcal O(1)\) 轉移了。

D

二選一異或有點復雜，所以我們假設先選擇 \(a\)，然后再進行調整。于是每次調整都需要異或上 \(c_i=a_i \oplus b_i\)，所以我們只關注是否調整。對于博弈雙方我們肯定都會按位從高到低考慮，否則一定不優。若考慮到第 \(i\) 位，那么決定最后狀態的一定是最后一個第 \(i\) 位為 1 的，假設為 \(x\)，我們可以進行選與不選的決策來調整。每次簡單判斷一下即可。注意更新答案后要將 \(c_j\) 中最高位是 \(i\) 的給異或上 \(x\)，這個表示如果這一位選進答案，那么 \(x\) 是否選擇的狀態就要改變。每次做完最高位會減一，所以沒有后效性可以大膽寫。

E

對于容量小的我們可以直接做普通的完全背包，如果容量很大我們就可以用一個 trick，具體見 P9140。簡單來說就是我們可以在一定范圍進行貪心，然后在最后調整。注意到貪心選擇的物品可能不對所有點做貢獻，因為我們是在 DAG 上做背包。所以我們可以欽定用哪個作為貪心點然后去拓展即可。

CF2129

B

因為是排列所以我們可以從小到大考慮每個數。對于一個數，如果不變那么貢獻是前面比它大的數個數，如果改變那么貢獻是后面比它大的數的個數，取最小值即可。

C

首先我們得找到一個確定的括號，這樣我們才可以判斷。因為題目保證至少有一個 ( 和一個 ) 所以字符串中至少有一個 () 或者一個 )(，考慮前者貢獻為一，后者無貢獻于是考慮二分找即可。這里需要用掉 \(1+\left\lceil\log_2n\right\rceil=11\) 次查詢。

C1

考慮還有 500 多次查詢所以我們每次確定 2 個位置即可。我們考慮一個形如下面的查詢：

( ( i j ( j i

我們分討一下 4 種取值對應的結果即可。

C2

我們嘗試讓每次詢問確定更多的位置，考慮一組形如 (((iii 的查詢，其取值要么是零要么是長度的一半，我們狀壓一下就可以每次查詢 8 個位置，因為有 \(7+\sum_{i=0}^82^i=518\) 如果再大就超過限制了。這樣一共需要查 \(11+\left\lceil n\over 8\right\rceil=136\) 次。

C3

上面我們考慮括號嵌套的查詢，其實我們還可以讓括號并排，這樣能構造出形如下面的東西：

( i ( i ( i ( ( j ( j ( j ( ( k ( k ( k

每次一個位置所帶來的貢獻要么為零要么為 \(cnt\times(cnt+1) \over 2\)，考慮構造出不同的 cnt 保證每種組合唯一。可以構造出如下的 cnt 序列：

1,2,3,5,7,10,15,21,30,43,61,87,123

最后我們一次查詢能夠確定 13 個位置，總詢問次數為 ：\(11+\left\lceil n\over 13\right\rceil=88\)。

D

神秘計數題我們考慮先去尋找性質，然后通過性質入手。

我們先去考慮一個位置 \(i\) 被貢獻的情況，不考慮其他位置，于是左右對稱，我們考慮左邊。首先染色的位置應該從遠到近，否則就貢獻不到當前考慮的位置。然后考慮我們貢獻的上限能是多少。最近的位置肯定是 \(i-1\)，下一個不能是 \(i-2\)，因為這時我們 \(i-1\) 的貢獻就會給 \(i-2\)，于是下一個位置實際是 \(i-3\)。再下一個呢？經過實踐我們發現是 \(i-7\)。發現了嗎？每次能作貢獻的最右端點形如 \(i-2^k+1\)，所以每個位置的貢獻上界是 \(\log\) 的。

然后我們考慮一個位置被填了后，左邊的位置顯然不能貢獻到右邊去了，所以一個問題就被簡化成了子區間，于是我們肯定是往區間 dp 的方向思考。所以首先我們的狀態有 \(f_{i,j}\) 表示區間 \([i,j]\) 的答案，但是顯然這樣沒法進一步轉移，所以我們需要增加限制。因為我們轉移的時候肯定要去枚舉那個劃分的位置，考慮那個位置對外置位做的貢獻以及那個位置得到貢獻的情況。考慮新劃分出來的兩個子區間肯定對劃分位置有貢獻，于是我們重新定義 dp 狀態。設 \(f_{i,j,x,y}\) 表示考慮到了區間 \([i,j]\) 并且區間內沒有染色，但是 \(i-1\) 和 \(j+1\) 已經被染色，區間對 \(i-1\) 的貢獻為 \(x\)，對 \(j+1\) 的貢獻為 \(y\)。

轉移的時候我們枚舉了劃分位置 \(k\)，考慮 \(k\) 對外置位的貢獻。如果 \(k\) 在區間左半部分，那么會對 \(i-1\) 有 1 的貢獻；否則對 \(j+1\) 有 1 的貢獻。枚舉的時候注意減掉。然后兩個子區間對 \(k\) 的貢獻就枚舉一下即可。注意因為是統計排列數，考慮兩個子區間獨立，于是在排列中只要相對順序正確即可，所以還要帶一個組合數 \(j-i\choose k-i\)。最后轉移就是 \(f_{i,j,x,y}\leftarrow f_{i,k-1,x't}\times f_{k+1,j,q,y'\times{j-i\choose k-i}}\)。時間復雜度 \(\mathcal O(n^3\log^3n)\)。

E

發現單次的修改是簡單的，但是跟邊數有關。注意到 \(n,m\) 同階于是考慮對 \(m\) 分塊跑莫隊。然后注意到正常用平衡樹是 \(\mathcal O(q\sqrt m\log n)\) 的修改加上 \(\mathcal O(q\log n)\) 的查詢，于是考慮值域分塊平衡復雜度。注意如果直接按照度數分塊可能出現很多點度數為零導致塊長爆炸，于是我們按照度數加點數分塊，于是就是 \(\mathcal O(q\sqrt{n+m})\) 的。