1.

CF708E Student's Camp

考慮連通，即為存在從上到下的路徑。對路徑 dp，我們從左上開始走，若能向下直接向下，否則往左或往右直到第一個能下去的位置下去。狀態(tài)即為 \(f_{i, j, 0 / 1 / 2}\) 表示當(dāng)前在 \((i, j)\)，是從左邊 / 上面 / 右邊過來的的方案數(shù)。轉(zhuǎn)移可以前綴和優(yōu)化。

2.

洛谷 P10716 簡單的字符串問題

判掉 \(k = 1\)。

顯然合法的串是 border，先 kmp 建出 fail 樹，則合法的是從根下來的鏈的一段前綴。樹上倍增一下，需要檢查合法性，即一個串的第 \(k\) 次出現(xiàn)位置。這類似于一個后綴和原串的 LCP，考慮 Z 函數(shù)。從小往大枚舉長度，先把所有 Z 函數(shù)比當(dāng)前長度小的位置刪掉，然后只需要暴力往后找未刪除位置即可。并查集維護(hù)，這里的復(fù)雜度是 \(n \alpha(n)\ln n\) 的。總復(fù)雜度一個 \(\log\)。

3.

P5289 皮配

注意到獨(dú)立性，先把沒有限制的統(tǒng)一分兩維做掉。如果一個學(xué)校的城市存在限制學(xué)校，但這個學(xué)校本身不限制，則也在這里做掉。然后考慮所有限制，由于值域很小，這里直接暴力 \(\mathcal{O}(mks)\)。然后考慮合并，枚舉最后一個 dp 數(shù)組，則對于另一邊兩個的限制分別是一個區(qū)間，前綴和一下即可。

4.

P4827 Crash 的文明世界

普通冪轉(zhuǎn)下降冪，得到 \(\binom{dist(i, j)}{k}\) 狀物。直接 dp 根據(jù)組合意義轉(zhuǎn)移即可。

換根 dp，可以用鏈?zhǔn)角跋蛐牵顟B(tài)記在每條單向邊上，采用記憶化搜索的寫法，就不用寫詭異東西了。

5.

ARC104E Random LIS

直接欽定所有大小關(guān)系，只需要求出有多少方案滿足之。將值域劃分為若干段，設(shè) \(f_{i, j}\) 表示考慮到第 \(i\) 個，處于第 \(j\) 個值域段，每次統(tǒng)一轉(zhuǎn)移位于同一個值域段的即可。

6.

LOJ #6041 事情的相似度

考慮從小往大加入每個 ht，并合并兩個集合的過程。我們關(guān)注的是在這個過程中，區(qū)間 \([l, r]\) 中的后綴什么時候第一次存在兩個位于同一個集合中的東西。那么每次合并集合，只需要在小的扔進(jìn)大的的過程中把扔進(jìn)去的東西和其前一個和后一個作為關(guān)鍵區(qū)間拎出來，最后只需要對所有關(guān)鍵區(qū)間和詢問區(qū)間二維數(shù)點(diǎn)即可。

7.

HDU 6566 The Hanged Man

考慮按 dfs 序加點(diǎn)。但是在新點(diǎn)不是上一個點(diǎn)兒子的時候，沒法知道祖先的點(diǎn)是否選。因此考慮重鏈剖分，每次先遞歸輕兒子，這樣就可以狀壓所有輕鏈頂?shù)母赣H的狀態(tài)了。

也可以使用點(diǎn)分樹。性質(zhì)是和一個點(diǎn)在原樹上相鄰的點(diǎn)一定是其點(diǎn)分樹上的祖先或子樹內(nèi)的點(diǎn)。因此在點(diǎn)分樹上按 dfs 序加點(diǎn)，就可以直接狀壓所有祖先了。

8.

洛谷 P9839 四暗刻單騎

容易發(fā)現(xiàn)和牌只能靠自摸。接下來發(fā)現(xiàn)一個人手上的牌如果有用，不管是要自己和還是截對面，那他一定會摸切。因此考慮某個人拿著一張牌一直摸切會發(fā)生什么。容易發(fā)現(xiàn)這之后要么平了，要么自己贏，要么對面贏。我們將拿著一張牌一直摸切會發(fā)生的事記作這張牌的收益。收益的計算只需要考慮這張牌的后兩次出現(xiàn)，對著討論出現(xiàn)位置的奇偶性即可。那么由于玩家的目標(biāo)在不能贏時是守平，因此當(dāng)且僅當(dāng)一個人在對面采取守平時必勝才是必勝。那么可以有平方暴力，就是掃過去然后每個人貪心選取手中收益優(yōu)的一張保留。如果某個時刻收益產(chǎn)生了則判斷勝負(fù)。

觀察這個過程，發(fā)現(xiàn)發(fā)生答案判定的時候?qū)е屡卸ǖ谋厝徊皇且粋€輸牌，因若一個人手上有兩張輸牌，那他一定可以選擇輸?shù)耐淼囊粡埍Ａ簟亩恍枰P(guān)注贏牌與平牌導(dǎo)致的勝負(fù)判定。而對于這兩種牌玩家一定會選取最早的那一張，并在那個時候取得收益。因此只需要線段樹維護(hù)每張牌的收益，查詢的時候求區(qū)間最小值即可。

• 固定的行為模式？嘗試考慮。

9.

P6773 命運(yùn)

對限制容斥，\(f_{i, j}\) 表示 \(i\) 子樹中最上的限制飛到了深度為 \(j\) 的祖先的染色方案乘以容斥系數(shù)的和。注意到這個東西可以線段樹合并優(yōu)化，只需要合并時實(shí)時記一個后綴和。于是做完了。

也可以不容斥，直接 \(f_{i, j}\) 表示當(dāng) \(i\) 的祖先中最下的染色邊在深度 \(j\) 時子樹的方案數(shù)。這個東西在葉子的時候需要做區(qū)間加。實(shí)際上是可以做的，考慮合并時若兩個節(jié)點(diǎn)都非空，則正常下傳標(biāo)記。否則，因為這里的合并是對位乘，就給非空的那個點(diǎn)打一個區(qū)間乘法 tag。當(dāng)然其他類型的合并（對位加之類）應(yīng)該也可以這么做。

10.

CF802O April Fool's Problem

費(fèi)用流建模是容易的，因此具有凸性。考慮 wqs 二分，每次 chk 的時候，考慮從后往前掃 \(a_i\)，每次的決策是把這個 \(a_i\) 匹配一個新的 \(b_i\)，或者換掉之前的一個 \((a, b)\) 對。可以證明當(dāng)采取第二種決策時，拆散后用 \(a_i\) 被拆散出來的 \(b\) 仍會是在剩余所有決策中的最優(yōu)決策。于是只需要用一個 pq 維護(hù)所有決策，每次如果堆頂決策的收益小于 \(0\)，就做就好了。

11.

CF917D Stranger Trees

將 \(c\) 個大小為 \(a_i\) 的連通塊用邊連成一棵樹的方案數(shù)為 \((\sum a_i)^{c - 2}\prod a_i\)。于是直接 dp 最后容斥就好了。使用 product trick，將連通塊乘積變?yōu)樵诿總€連通塊中選出一個點(diǎn)的方案數(shù)，就不用記根連通塊大小了，總復(fù)雜度平方。

12.

P5644 獵人殺

轉(zhuǎn)化為隨機(jī)開槍，直到打死一個人。顯然和原本等價。然后可以想到容斥，欽定一個集合 \(S\) 中的人在 \(1\) 之后死。枚舉第一個人死的時間可以列出這種情況的概率：\(\sum\limits_{i = 0}^{\infty}(\frac{S - sum - w_1}{S})^i\frac{w_1}{S}\)，其中 \(sum = \sum\limits_{i \in S} w_i\)。容易發(fā)現(xiàn)這就是 \(\frac{w_1}{sum + w_1}\)。于是只需要帶容斥系數(shù)求出湊出 \(sum\) 的方案數(shù)。分治 NTT 即可。

-

邊

• （經(jīng)典？）問題：有向圖要求環(huán)的方案，利用拆點(diǎn)二分圖完美匹配構(gòu)造。

13.

LOJ #575 不等關(guān)系

對大于容斥。被容斥的大于就是小于，因此限制只在未定的大于。對這些東西 dp，\(f_i\) 從前面的被未定的大于號轉(zhuǎn)移，系數(shù)只和 \(i - j\) 有關(guān)（所有未定之間的段相當(dāng)于多重組合數(shù)，因此系數(shù)是階乘逆），分治 NTT 即可。

14.

P6775 制作菜品

如果將一個菜品視為其所用的兩種原料中的一條邊，那么不難發(fā)現(xiàn)一定存在一種方案使得最終圖中不存在環(huán)。那么若 \(m \ge n - 1\)，則只需要每次選出最小的，如果比 \(k\) 大就減掉 \(k\)，否則用當(dāng)前最大的原料湊夠 \(k\) 克。容易發(fā)現(xiàn)這是一定合法的。而如果 \(m = n - 2\)，則至少會有兩個連通塊，每個連通塊都必須滿足 \(\sum d \ge (sz - 1) \times k\)，其中 \(sz\) 為該連通塊大小。將 \(d_i\) 統(tǒng)一減 \(k\)，變成 \(\sum (d_i - k) = -k\)。只需要 01 背包即可。再加 bitset 優(yōu)化即可通過。

15.

P5327 語言

考慮對每個點(diǎn)算貢獻(xiàn)。固定一個點(diǎn)之后，與其能貿(mào)易的點(diǎn)，顯然是所有經(jīng)過它的路徑的并中的點(diǎn)。動態(tài)維護(hù)包含某個點(diǎn)集的最小連通塊大小是容易的，只需要每次加入 / 刪除 \(x\) 時和 dfs 序相鄰的兩個點(diǎn)取 LCA 較深的點(diǎn)，這個點(diǎn)到 \(x\) 的直鏈就是這次修改改變的答案。

注意到一條路徑經(jīng)過一點(diǎn)，必要條件是其有至少一個端點(diǎn)在這個點(diǎn)的子樹中。于是只需要對每個點(diǎn) \(x\) 維護(hù)所有至少一個端點(diǎn)在其子樹中的路徑的并（當(dāng)然，要去掉這些中 LCA 比 \(x\) 深的，這是容易的）。dsu on tree 即可。似乎也可以線段樹合并。反正都能過。

• 過一個點(diǎn)的路徑一定有端點(diǎn)在其子樹中。

16.

CF1515E Phoenix and Computers

連續(xù)段 dp。\(f_{i, j}\) 表示加入到 \(i\)，有 \(j\) 個相隔 \(\ge 2\) 的連續(xù)段的方案數(shù)。

• 連續(xù)段 dp 中每個數(shù)的位置是由合并決定的。類似把原序列從最大值拆開，然后變成子問題。連續(xù)段之間實(shí)際上是獨(dú)立的。

-

P4218 珠寶商（字符串專題）

首先對全局，有平凡的 \(\mathcal{O}(n^2)\) 做法， 利用 SAM。然后我們還可以通過點(diǎn)分治做到 \(\mathcal{O}(nm + n \log n)\)。于是我們考慮對點(diǎn)分治的子樹大小根號分治。子樹大小 \(\ge B\) 的，跑暴力；否則點(diǎn)分治。可以證明這樣的復(fù)雜度是 \(\mathcal{O}((n + m) \sqrt{n})\) 的。

• 對點(diǎn)分治的子樹大小根號分治。

• “由于無論子樹多大，都要跑一遍 \(\mathcal{O}(m)\)，太浪費(fèi)，于是考慮根號分治。”本質(zhì)還是用手段平衡復(fù)雜度。

-（*）

CF1276F Asterisk Strings（字符串專題）

只考慮 \(\texttt{s*t}\) 的情況。可以視為一個前綴的后綴拼上一個后綴的前綴。那么嘗試枚舉 \(s\)，容易發(fā)現(xiàn)出現(xiàn)位置相同的 \(s\) 本質(zhì)相同。也就是 \(\text{endpos}\) 一樣的串可以放一起考慮。那么枚舉 \(\text{endpos}\)，就要求一些后綴一共有多少本質(zhì)不同子串。

而實(shí)際上這就是這些后綴在反串 parent 樹上到根路徑并的總長度。啟發(fā)式合并或者線段樹維護(hù)即可。

• parent 樹上的祖先，是自己的全部后綴。因此 SAM 的存儲實(shí)際上是所有“前綴的后綴”。這在 SA 的笛卡爾樹上也是一樣的（只不過反過來）。因此一個串的本質(zhì)不同子串?dāng)?shù)，就是 parent 樹上整棵樹的邊權(quán)和。而 SA 上就是 \(\frac{n(n + 1) / 2}{2} - \sum ht\)，因為 \(ht\) 存的就是 parent 樹上 dfn 相鄰兩點(diǎn)的 LCA 深度。這也是為什么 ht 的笛卡爾樹可以用于替代 parent 樹（即 SAM 的大部分用處）。

-（*）

CF1038F Wrap Around（字符串專題）

\(f_{i, j, k, l}\) 表示填了 \(i\) 個字符，當(dāng)前在自動機(jī)的第 \(j\) 個位置，若初始狀態(tài)在 \(k\)，則現(xiàn)在在 \(l\) 的方案數(shù)。轉(zhuǎn)移是 \(\mathcal{O}(1)\) 的，統(tǒng)計答案容易。總復(fù)雜度四次方。

• 將需要知道的信息直接放進(jìn) dp 狀態(tài)，就像這樣。

17.

CF1416E Split

顯然有平方 dp：\(f_{i, j}\) 表示到第 \(i\) 個數(shù)，最后一個數(shù)是 \(j\) 的最多相同相鄰次數(shù)。觀察轉(zhuǎn)移，發(fā)現(xiàn)任何時刻所有 dp 值最多只可能有三種數(shù)，而且一定是連續(xù)的，而且如果有三種數(shù)，最大的最多只有一個。那么再觀察這些東西的變化，每一次相當(dāng)于把最大值賦給所有數(shù)，然后那些值為 \(mn + 1\) 的位置會關(guān)于 \(a_i / 2\) 這個位置左右翻轉(zhuǎn)。然后如果 \(a_i\) 為偶數(shù)，則額外給 \(a_i / 2\) 位置加一。那么就可以拿一個 set 維護(hù)所有 \(mn + 1\) 的位置，拿一個 int 維護(hù) \(mn + 2\) 的位置，轉(zhuǎn)移就模擬一下就好了。

• 觀察轉(zhuǎn)移。

18.

ABC201F Insertion Sort

首先容易發(fā)現(xiàn)每個人最多移動一次。然后考慮那些不動的人。首先他們要構(gòu)成上升子序列，然后考慮他們對剩下人的限制。設(shè)不動的人當(dāng)中最小的是 \(x\)，最大的是 \(y\)，那么顯然（編號）\(< x\) 的人要么給他扔最前面，要么扔任意位置。比 \(y\) 大的同理。\(\in (x, y)\) 的，就必須使用扔任意位置了。

• 不僅要考慮動的人之中的限制，也要考慮不動的人的限制。要考慮全。

19. （*）

1528F AmShZ Farm

對于合法的 \(a\) 數(shù)組，可以轉(zhuǎn)化為計數(shù)數(shù)組每個位置的前綴和不能超過其下標(biāo)。那么有經(jīng)典轉(zhuǎn)化：\(n\) 個位置排成環(huán)，并在 \(n + 1\) 位置插入虛點(diǎn)。\(n\) 個人，第 \(i\) 個人會嘗試在 \(a_i\) 落座。若不能則往前找到第一個可行位置落座。則合法的充要條件即為虛點(diǎn)無人。

那么有了這個之后合法序列的數(shù)量就容易統(tǒng)計了，是 \(\frac{(n + 1)^n}{n + 1}\)。而且從這個轉(zhuǎn)化中，我們也會發(fā)現(xiàn)，一個合法序列會對應(yīng) \(n\) 個計數(shù)數(shù)組與之循環(huán)同構(gòu)的非法序列。那么由于我們只關(guān)心計數(shù)數(shù)組（因為算 \(b\) 的答案只用到計數(shù)數(shù)組），因此不妨先把所有序列的答案都統(tǒng)計上，最后再除以 \(n + 1\)。

那么接下來就可以考慮對每個元素算貢獻(xiàn)。考慮一個元素 \(x\) 對答案的貢獻(xiàn)，即為 \(\sum\limits_{c = 0}^n\binom{n}{c}n^{n - c}c^k\)（第二個冪的底數(shù)是 \(n\) 是因為剩下的數(shù)里不能有 \(x\)）。由于所有元素本質(zhì)相同，所以這個要乘 \(n + 1\)。而由于這里算了非法序列，最后又要在除掉 \(n + 1\)，因此兩項抵消，之后不再考慮。

接下來推式子：

到這里就可以直接算了，只需要一行的第二類斯特林?jǐn)?shù)。而行第二類斯特林?jǐn)?shù)是好求的，只需要根據(jù)普通冪轉(zhuǎn)下降冪的式子二項式反演即可：

直接 NTT，復(fù)雜度 \(\mathcal{O}(k \log k)\)。

• 經(jīng)典接鏈為環(huán)，而環(huán)上由于元素的對稱性，就會有美妙的事情。

20. （*）

ARC120F Wine Thief

首先容易想到對每個元素算貢獻(xiàn)。但是欽定了一個元素選之后，剩下的不太好做。那么，拼成環(huán)。

設(shè) \(f(n, k)\) 為 \(n\) 個點(diǎn)的環(huán)上，大小為 \(k\) 的獨(dú)立集有多少個（再設(shè) \(g(n, k)\) 為序列）。那么由于環(huán)上每個元素的對稱性，每個數(shù)被選到的概率都是 \(\frac{k}{n}\)。也就是說每個點(diǎn)被選中的方案數(shù)都是 \(\frac{kf(n, k)}{n}\)。但是這樣我們少算了方案，少算的方案是鏈的兩端都被選的那些。而扣掉兩端之后，發(fā)現(xiàn)剩下的是一個序列上的子問題！而這個子問題的方案數(shù)（\(g(n, k)\)）又恰好就是 \(a_1, a_n\) 的系數(shù)。那么我們直接向子問題用同樣的方法遞歸計算即可。終止條件是當(dāng)前子問題規(guī)模 \(\le 3\)，此時的計算是容易的。

關(guān)于 \(f, g\) 的計算，有 \(g(n, k) = \binom{n + 1 - k}{k}\)，\(f(n, k) = g(n - 1, k) + g(n - 3, k - 1)\)（通過討論第一個元素）。那么整個題復(fù)雜度就是 \(\mathcal{O}(n)\)。

• 接鏈為環(huán)，利用環(huán)的對稱性考慮。

• 發(fā)現(xiàn)了子問題并遞歸。

21.

1523F Favorite Game

容易發(fā)現(xiàn)，如果當(dāng)前在傳送塔，那么位置是不重要的。容易寫出 dp：\(f_{S, i}\) 表示解鎖了 \(S\) 集合的塔，并完成 \(i\) 個任務(wù)的最小時間。但是這個 dp 不能考慮位置。

容易發(fā)現(xiàn)，如果當(dāng)前在目標(biāo)點(diǎn)，那么時間是可以知道的。容易寫出 dp：\(g_{S, i}\) 表示解鎖了 \(S\) 集合的塔，當(dāng)前在第 \(i\) 個目標(biāo)點(diǎn)，最多能完成幾個任務(wù)。但是這個 dp，看起來不太好轉(zhuǎn)移。

那么我們直接把這兩個 dp 一起做。如果當(dāng)前在傳送塔，我們采用 \(f\)。如果當(dāng)前在目標(biāo)點(diǎn)，我們采用 \(g\)。

然后就可以用這兩個 dp 互相轉(zhuǎn)移。于是就做完了。

• dp 可以不只有一個。此題中可能是由于兩個 dp 互補(bǔ)的性質(zhì)。

22.

ARC121F Logical Operations on Tree

考慮 0 和 1 的個數(shù)，我們希望 0 的個數(shù)歸零。那么先把 0 連通塊縮起來。接下來要減少 0，必須用 0 去撞 or 邊才能消掉。那這樣就發(fā)現(xiàn) and 邊是不是沒啥用，那么也全部縮起來。那么此時就會發(fā)現(xiàn)，如果我們把所有 and 邊先縮起來，那么合法當(dāng)且僅當(dāng)此時樹中存在一個 1。證明是顯然的。然后就可以直接樹形 dp 了。

• \((\neg q \rightarrow \neg p) \rightarrow (p \rightarrow q)\)。

23.

CF1534G A New Beginning

顯然先轉(zhuǎn)曼哈頓，那么種植只會在某個土豆的橫坐標(biāo)。平凡的 dp 是 \(f_{i, j}\) 表示到第 \(i\) 個土豆的橫坐標(biāo)，縱坐標(biāo)在 \(j\) 時的最小代價。轉(zhuǎn)移是每個點(diǎn)變?yōu)猷徲虻?\(\min\)，最后整體加（平移的）絕對值函數(shù)。那么顯然可以 slope trick，每個點(diǎn)變?yōu)?\(d\) 鄰域 \(\min\) 等價于水平線左邊的轉(zhuǎn)折點(diǎn)統(tǒng)一左移 \(d\)，右邊的統(tǒng)一右移 \(d\)，整體加絕對值相當(dāng)于在某個橫坐標(biāo)插入兩個轉(zhuǎn)折點(diǎn)。fhqtreap開兩個 pq 分別維護(hù)水平線左右的轉(zhuǎn)折點(diǎn)，然后額外維護(hù)一下水平線的值即可。這些都是容易的，總復(fù)雜度 \(\mathcal{O}(n \log n)\)。

24.

CF1481E Sorting Books

先縮連續(xù)段。考慮對不動的東西 dp。發(fā)現(xiàn)不動的顏色對應(yīng)的出現(xiàn)位置區(qū)間一定不會交。而特殊情況只有最后一種不動的顏色，它可以選擇一個后綴不動，而讓這個顏色前面的出現(xiàn)都往后動。前面的 dp 是容易的，后面的稍微討論一下就可以了。總復(fù)雜度 \(\mathcal{O}(n)\)。

25.

CF1517F Reunion

轉(zhuǎn)化為答案 \(\ge i\) 的概率，還是不好做。但是反過來考慮，答案 \(< i\) 的概率。這相當(dāng)于要求每個點(diǎn)的 \(i\) 鄰域內(nèi)至少要有一個黑點(diǎn)。相當(dāng)于選擇黑點(diǎn)覆蓋所有點(diǎn)。于是就可以直接 dp 了，\(f_{i, j}, g_{i, j}\) 表示若 \(i\) 子樹完全覆蓋，向上延伸 \(j\) 的概率，或者若沒有完全覆蓋，最深的未覆蓋點(diǎn)在 \(j\) 的概率。這樣直接暴力可能是四次方，但是容易用前綴和優(yōu)化到三次。

26.

CF1517G Starry Night Camping

考慮將點(diǎn)按照橫縱坐標(biāo)的奇偶性分成四類，則容易發(fā)現(xiàn)一個非法的圖案一定是一個經(jīng)過四種點(diǎn)的長度為四的路徑。于是最小割即可。

• 網(wǎng)絡(luò)流中，嘗試考慮對點(diǎn)分類。

27.

CF1495F Squares

可以考慮將每個點(diǎn)連向前面第一個比它大的點(diǎn)，這樣每個點(diǎn)的行為要么是進(jìn)入子樹，要么是直接跳過子樹。那么所有的限制就相當(dāng)于是說它們的祖先都不能采用跳過子樹的決策。那么剩下的東西就應(yīng)該是簡單的了。

還有另一種做法。考慮詢問時我們要求的是若干 \((x \rightarrow y)\) 的最短路的和，因此可以把所有詢問的最短路離線下來分別求。這個就可以按右端點(diǎn)掃描線，由于所有跳過構(gòu)成的區(qū)間都是不交或包含，因此對于一個右端點(diǎn)，只需要枚舉所有跳到它的位置，然后若這個地方當(dāng)前維護(hù)的最短路比直接跳過來劣，就直接跳過來，并更新前面所有點(diǎn)的最短路。

• 各種連邊方法都要試一試，盡管看起來可能沒啥道理。

• 第二種做法：離線處理。

28.

CF1392H ZS Shuffle Cards

考慮 \(\min - \max\) 容斥計算 \(n\) 張牌中最晚抽出的輪數(shù)。枚舉 \(|S|\)，相當(dāng)于抽到 \(S\) 中的牌就下班。而一輪結(jié)束時有 \(\frac{|S|}{m + |S|}\) 的概率是抽到 \(|S|\) 中牌，因此期望要 \(\frac{|S| + m}{|S|}\) 這么多輪才能下班。求出了期望最大輪數(shù)之后只需要再乘以一輪的期望時間即可。這是容易計算的。

29.

CF771E Bear and Rectangular Strips

考慮按順序取出最后方案中的每個矩形。按照橫坐標(biāo)的起始位置升序來取。

設(shè) \(f_{i, j}\) 表示第一行的前 \(i\) 列，第二行的前 \(j\) 列的答案，\(g_i = f_{i, i}\)，那么由我們剛才的取法，不難發(fā)現(xiàn)只有 \(f_{i, j} \le g_{\min\{ i, j \}} + 1\) 的 \(f_{i, j}\) 是有用的。而且對于一些都符合這個條件的 \(f_{i, j}\)，我們也只需要保留 \(\max \{ i, j \}\) 最小的那個。那么這樣的話，總狀態(tài)數(shù)就只有 \(\mathcal{O}(n)\) 了，那么只需要對每個狀態(tài)直接轉(zhuǎn)移就好了。

• 欽定順序，不考慮無用狀態(tài)。

30.（*）

CF1450G Cummunism

可以把合并的過程視為一棵樹。那么首先容易想到直接狀壓 \(f_{S}\) 表示 \(S\) 是否能歸為同一顏色（注意，并不是說真的就要都是同一種顏色）。轉(zhuǎn)移也很簡單，一種是枚舉一種新的顏色變過去，要求變過去之后的集合是可變的（滿足題目中給出的條件），相當(dāng)于給這個集合中的子樹找一個根；另一種是枚舉分成兩個子集，如果兩個子集的 \(f\) 都是 \(1\)，則 \(f_S\) 也為 \(1\)，相當(dāng)于把兩個子樹集合拼起來。這樣的復(fù)雜度是 \(3^{\Sigma}\) 的，過不去。

考慮怎樣的轉(zhuǎn)移是沒有用的。會發(fā)現(xiàn)若合并的兩個集合在原序列上對應(yīng)的區(qū)間有交，則這樣的轉(zhuǎn)移是無用的。證明就考慮左邊那個區(qū)間最右的子樹和右邊那個區(qū)間最左的子樹，它們的區(qū)間是交的。那么就可以把兩棵子樹中的一棵合并到另一棵上，顯然這樣不會改變合法性，也就是新的子樹仍然滿足題目中的條件。于是有了這個條件之后，這一種轉(zhuǎn)移就也是 \(\mathcal{O}(\Sigma2^{\Sigma})\) 的了。

• 考慮怎樣的轉(zhuǎn)移是無效的。

31.

ABC209E Shiritori

每個字符串視為前三個字符和后三個字符之間的建邊，直接有向圖博弈即可。

32.

CF1034D Intervals of Intervals

二分答案來求前 \(k\) 大和。區(qū)間區(qū)間并的問題考慮染色，掃描線右端點(diǎn) \(i\)，并將區(qū)間 \([l_i, r_i]\) 染上顏色 \(i\)，那么 \([j, i]\) 的區(qū)間并就相當(dāng)于有多少點(diǎn)的顏色 \(\ge j\)。先跑一遍染色求出加入每個右端點(diǎn)之后每個顏色的數(shù)量會如何變化，然后 check 的時候枚舉右端點(diǎn)，容易發(fā)現(xiàn)最大合法的左端點(diǎn) \(j\) 也是單調(diào)的。只需要每次修改的時候考慮對當(dāng)前左端點(diǎn)答案和前 \(j - 1\) 個區(qū)間的答案和的影響即可。

33.

AGC021F Trinity

考慮按列 dp。\(f_{i, j}\) 表示考慮了前 \(i\) 列，已經(jīng)有 \(j\) 個非空行的方案數(shù)。接下來考慮轉(zhuǎn)移。考慮新的這一列中的 \(B_i, C_i\) 是否取在原有的行當(dāng)中。設(shè) \(j \rightarrow k\)，那么分三種情況討論：

1. \(B_i\) 和 \(C_i\) 都在新選的行中。這種情況就是 \(\binom{k}{k - j}\)。

2. 兩個都不在新選的行中。那么考慮從 \(k\) 行中選出 \(k - j + 2\) 行，其中中間的 \(j\) 行作為新選的，第一行和最后一行作為 \(B\) 和 \(C\)，那么這種情況的方案就是 \(\binom{k}{k - j + 2}\)。

3. 有一個在。和上一種類似，這是 \(2\binom{k}{k - j + 1}\)。

三種加起來，一共是 \(\binom{k + 2}{k - j + 2}\)。NTT 優(yōu)化即可。

34.

LOJ #6406 綠寶石之島

按照一顆寶石出現(xiàn)的天數(shù)區(qū)分寶石，通過感性理解（每天每顆寶石以相等的概率分裂）或者推式子證明可以發(fā)現(xiàn)所有的終態(tài)的出現(xiàn)概率是相等的。因此考慮從高往低 dp，\(f_{i, j}\) 表示考慮了最高的 \(i\) 層，一共用了 \(j\) 顆寶石的方案數(shù)，以及 \(g_{i, j}\) 表示此時所有方案的前 \(r\) 大和的和。那么轉(zhuǎn)移就是容易的。最后只需要用所有前 \(r\) 大和的和除以總方案數(shù)即可。

• 所有終態(tài)出現(xiàn)概率相同。

• 按照值域從高往低 dp。

35.

P3643 劃艇

先將值域離散化，\(f_{i, j}\) 表示前 \(i\) 個學(xué)校，最后一個學(xué)校在第 \(j\) 段的方案數(shù)。轉(zhuǎn)移考慮枚舉最后一個和這個學(xué)校不在同一段的學(xué)校，從它的 \(0\) 到 \(j - 1\) 轉(zhuǎn)移過來。中間的東西可能有范圍不包括這一段的，讓他們填 \(0\) 就好。剩下的系數(shù)都可以預(yù)處理，總復(fù)雜度三次方。

36.

AT_joisc2015_f Keys

先離散化時間。我們希望最小化開門時間，那么考慮什么時候一段時間會產(chǎn)生貢獻(xiàn)。發(fā)現(xiàn)當(dāng)且僅當(dāng)這段時間的開頭是沒有鑰匙的出門或者結(jié)尾是沒有鑰匙的進(jìn)門時，這段時間會產(chǎn)生貢獻(xiàn)。那么根據(jù)這個關(guān)系在人之間建邊，現(xiàn)在就是選擇不給一個人鑰匙會產(chǎn)生代價，但是一條邊連接的兩個人如果都沒有鑰匙則這條邊的代價只產(chǎn)生一次。直接做看起來沒法做，但是觀察到圖是一堆鏈，于是只需要對每條鏈分別 dp 就可以了。

• 拆開貢獻(xiàn)。

• 觀察。

37.

HDU 6157 The Karting

還是觀察，考察每個路段的貢獻(xiàn)次數(shù)。發(fā)現(xiàn)只要相鄰兩個路段的貢獻(xiàn)次數(shù)不超過 \(1\)，我們都可以構(gòu)造合法的路徑。而實(shí)際上每次貢獻(xiàn)變化，就相當(dāng)于使用了關(guān)鍵點(diǎn)。成對的貢獻(xiàn) \(+ / - 1\) 可以視為括號的匹配，則一次匹配會產(chǎn)生 \(d_0\) 的收益。于是可以 dp，\(f_{i, j, k}\) 表示當(dāng)前在 \(i\)，貢獻(xiàn)次數(shù)為 \(j\)，用了 \(k\) 個關(guān)鍵點(diǎn)的最大收益。每次轉(zhuǎn)移是新開一個左括號，或者用一個右括號，或者在這個地方空放一個關(guān)鍵點(diǎn)。其中最后一種轉(zhuǎn)移要求此時的貢獻(xiàn)不為 \(0\)。直接做就好了。

38.

LOJ #521 緋色 IOI（抵達(dá)）

題目要求相當(dāng)于形成基環(huán)樹森林。但是由于這里不可能有長度 \(> 2\) 的環(huán)，也不能有自環(huán)，因此所有環(huán)長只能為 \(2\)，也就是全樹分成若干組兩兩相鄰的匹配。而為了保證這個匹配，點(diǎn)與點(diǎn)的權(quán)值之間會自然形成一些偏序關(guān)系。于是只需要從小到大枚舉權(quán)值，每次選出最小的能用的編號來放當(dāng)前的權(quán)值即可。

39.

P6847 魔法樹

\(f_{i, j}\) 表示 \(i\) 子樹，父邊在 \(j\) 時刻斷掉的最大收益。轉(zhuǎn)移可以直接線段樹合并優(yōu)化，一個 \(\log\)。

但是也可以將狀態(tài)定義為前綴，這樣就是單調(diào)的了。我們維護(hù) dp 值的差分，這樣兩棵子樹合并就是對位相加。加入自己的貢獻(xiàn)時相當(dāng)于單點(diǎn)修改，然后扔掉這個點(diǎn)后面的一段，然后再單調(diào)修改。這個暴力做就好了。使用啟發(fā)式合并，總復(fù)雜度兩個 \(\log\)。

• 對于（單調(diào)的）dp，嘗試維護(hù)差分。

40.

CF573D Bear and Cavalry

先兩邊排序，然后如果沒有限制，肯定是大的匹配大的最優(yōu)。但是有了限制，但是我們也可以通過調(diào)整法證明不會存在 \((i, i \pm 3)\) 這樣的匹配。因為設(shè)匹配 \((i, j)(|j - i| \ge 3)\)，由于 \(|j - i| \ge 3\)，必然有至少三條線和 \((i, j)\) 相交。依次用這三條線嘗試和 \((i, j)\) 調(diào)整，發(fā)現(xiàn)不能調(diào)整的情況必然是碰到了 \(i\) 對應(yīng)的 \(j\) 側(cè)點(diǎn) \(x\)，要么是碰到了 \(j\) 對應(yīng)的 \(i\) 側(cè)點(diǎn) \(y\)。而再來第三條的時候，無論如何這個時候肯定都可以換了。于是匹配的距離不會很遠(yuǎn)。

設(shè) \(f_i\) 表示前 \(i\) 個的最優(yōu)答案，那么更進(jìn)一步的，我們也可以通過調(diào)整法證明 \(f_i\) 只會從 \(f_{i - 1}, f_{i - 2}, f_{i - 3}\) 轉(zhuǎn)移來。于是只需要把轉(zhuǎn)移寫成矩陣的形式，跑 ddp 就好了。

• 調(diào)整。

41.（*）

CF1476F Lanterns

考慮 dp，\(f_i\) 表示前 \(i\) 個點(diǎn)，最遠(yuǎn)能連續(xù)覆蓋到多遠(yuǎn)的前綴。那么轉(zhuǎn)移分幾種：

1. 往右倒。要求 \(f_{i - 1} \ge i\)。\(f_i = \max \{ f_{i - 1}, i + p_i \}\)。

2. 往左倒。此時，我們找到最小的 \(j\) 滿足 \(f_j \ge i - p_i - 1\)，轉(zhuǎn)移就是 \(f_i \leftarrow \max \{ i - 1, \max\limits_{k = j + 1}^{i - 1} \{ k + p_k \} \}\)。如果找不到，那么開擺。

3. 開擺。\(f_i = f_{i - 1}\)。

構(gòu)造方案只需要根據(jù)轉(zhuǎn)移來就好了。

• 挺靈活的。