P7390

先考慮什么樣的子結構是合法的，因為題目沒有無解，得出條件應該為

• \(\sum a_i=2(n-1)\)
• \(1\leq a_i\leq n\)

考慮歸納證明，首先肯定存在 \(a_i=1\) 否則 \(\sum a_i\geq n\)，其實肯定存在 \(a_i>1\) 否則 \(\sum a_i=n-1\)。我們拼湊這兩個點，并將其視作一個新的點，新的圖仍然滿足上述條件。

所以我們操作的時候只要保證連接了兩個不同的連通塊、以及組成的新點仍然有額外的度數即可，最后一條邊除外。我們考慮貪心，大的跟大的乘，按 \(b\downarrow\) 枚舉點，考慮怎么加邊，首先子結構一定是若干度數為 \(d_1,\dots,d_m\) 的連通塊，因為歷史上能加就加所以肯定不存在兩個 \(d_i>1\) 的，不妨令 \(d_1\geq 1\)，\(d_2,\dots,d_m=1\)，然后用兩個隊列 \(L/R\) 分別順序維護連通塊 \(1/2\to m\) 的出邊。加邊的話，特判 \(L\) 為空的，此時直接加入，之后先盡量連 \(R\) 中比 \(L\) 中最大邊更大的，然后考慮能不能連一條 \(L\)，然后盡量連 \(R\) 中比初始的 \(L\) 最大值小的，最后把剩下的邊加進 \(L\) 即可。

P3734

如果沒有障礙物的話我們只關心二進制的位數，設 \(f[i][j][k]\) 表示 \(x/y/z\) 做 \(i/j/k\) 位的方案數，轉移顯然是 \(f[i][j][k]=\sum_{d=0}^{i}f[i-d][j][k]+\sum_{d=0}^{j-1}f[i][j-d][k]+\sum_{d=0}^{k-1}f[i][j][k-d]\)。

如果有障礙物的話我們可以考慮容斥，設障礙集合為 \(diff\)，答案就是 \(\sum_{s \subseteq diff}(-1)^{|s|}f(s)\)。現在考慮欽定路過 \(s\) 的答案，首先 \(s\) 一定是 \(s_1\subseteq s_2\subseteq ...\subseteq s_m\) 形態的東西，不然沒有貢獻，誒那我們可以按照這個順序 dp 帶 \(-1\) 的方案數了，類似于 dag 圖路徑計數。

CF1476F

我求我了，不要虛構不夠優的貪心好不好，惱火了。

（去戾氣版）雖然題解只有一篇沒有直接聲稱設計狀態為前 \(i\) 個燈最大完全覆蓋前綴，并且這個狀態非常的符合直覺，但是這樣子直接聲稱或許遺漏了某些必要的思考步驟，也完整跳過了這道題目的精髓，不管怎么說聲稱之后只剩下一個普及組 dp。

這里嘗試給出一些更加自然的思考角度，比較機械的，首先如果不按照某種順序依次電燈，未來就很難去重，不妨先試試按照燈的順序去考慮位置。點亮前 \(i\) 盞燈，之后我們關心一個二元組 \((i,j)\)，表示最左邊的還沒有點亮的燈是 \(l\)，向右一直覆蓋到 \(r\)，考慮加入 \(i\) 會產生的變化：

• 向左走，\((i,j)\to (0,j)/(i,j)\)，條件是 \(x-p_x\leq i\)。
• 向右走，\((i,j)\to (i,x+p_x)/(i,j)\)，條件是 \(x+p_x>j\)。

\((0,j)\) 的特殊狀態要求我們維護點亮前 \(i\) 盞燈能完整覆蓋的最大前綴，剩下的二元組只有第二維會變化，所以不妨對所有的 \(i\) 維護 \(\max\{j\}\)，就是區間取 \(\max\) 了，剩下的都是分類討論。但是進一步的，這些轉移中，一個二元組出生起 \(i\) 就定死了直到碰到一個向左走的覆蓋，意思是 \(j\) 其實是可以用區間 rmq 更新的，你只要從剛誕生的 \((i,j)\) 轉移，一方面這個東西合法性肯定是先不行、再行的、答案也是單調的，你可以二分那個位置，另一方面剛誕生的 \((i,j)\) 等價于 \(i-1\) 燈前綴能覆蓋出的最大前綴長度，因為這邊肯定沒有向后覆蓋的邊了大哥哥，不然就不是最大前綴長度了。所以設 \(f_i\) 表示點亮前 \(i\) 盞燈的最大完全覆蓋前綴，分類討論新燈往左還是往右，因為 \(f\) 單調寫個二分 dp 上去。

或者你不想這么機械，你先考慮最終的情況是什么樣的，若干相交、不包含、完全覆蓋的區間，貢獻可能來自區間左一個點、或者右一個點，你考慮去拆一個 dp 順序，還是跟上文所述的那樣按照 \(i\) 的順序拆，拆除來的過程就跟題目的 dp 一致了哦。