板刷 CF

ds

CF1899G *1900

想到的：考慮先求出 dfs 序，然后用主席樹去維護(hù)排列 \(p\)，每次查詢就相當(dāng)于問 \(l\sim r\) 中有沒有節(jié)點(diǎn)的 dfs 序在 \(dfn_u\sim dfn_u+sz_u-1\) 中。

沒想到的：主席樹做法無，可以樹狀數(shù)組離線、dsu on tree 做。

分治

CF1917C *1600

想到的：若 \(a\) 全為 \(0\)，那最優(yōu)策略必為每次操作一后跟操作二，所以只需要判斷在第一次進(jìn)行操作二之前能獲得的最大值是多少即可。同時(shí) \(n\le 2000\)，所以可以 \(n^2\)？

沒想到的：在 \(a\) 數(shù)組不全為 \(0\) 的情況下，最開始最多有 \(n\) 的貢獻(xiàn)。一開始直接進(jìn)行操作二，然后一直進(jìn)行最優(yōu)策略。在總共操作了 \(2\times n + 1\) 次后就可以得到 \(n\) 的貢獻(xiàn)。所以在 \(d<2\times n\) 時(shí)直接暴力，否則因?yàn)樵?\(2\times n\) 次操作后必然可以得到 \(n\) 的貢獻(xiàn)，所以枚舉到 \(2\times n\) 即可。

構(gòu)造

CF1899F *1600

想到的：直接構(gòu)造一條鏈，然后如果 \(d = n-1\) 就輸出 -1 -1 -1，否則將 \(n\) 與 \(n-1\) 號(hào)節(jié)點(diǎn)之間的邊斷開，然后將 \(n\) 與 \(d\) 相連。

沒想到的：題目的操作會(huì)延續(xù)到后面（但沒有很大的影響）。

思維

CF1709D *1700

想到的：對(duì)于每次詢問，如果縱坐標(biāo)相減的絕對(duì)值不是 \(k\) 的倍數(shù)就輸出 NO，否則用 st 表查詢區(qū)間 \(a\) 數(shù)組中的最大值，判斷繞過最大值需要往上走多少步，如果超出了 \(n\) 就輸出 NO，否則判斷在走完之后和終點(diǎn)橫坐標(biāo)的差的絕對(duì)值是否是 \(k\) 的倍數(shù)。是則輸出 YES，否則輸出 YES。要特判區(qū)間最大值小于橫坐標(biāo)的情況。

過題過程：第一發(fā)因?yàn)闆]特判 WA 了。

沒想到的：無。

CF2085C *1600

想到的：

11
01

或

11
10

這樣的顯然可以通過加的操作完成，于是直接模擬？細(xì)節(jié)太多，還有兩種情況。

沒想到的：容易發(fā)現(xiàn)，如果 \(2^k\oplus x,x\in \N\)，有 \(2^k\oplus x=2^k+x\)，所以把 \(x\)、\(y\) 中較大的那個(gè)數(shù)改成 \(2^k\) 即可。注意到當(dāng) \(x=y\) 時(shí)是顯然不行的。

CF1851F *1800

沒想到的：《觀察·注意·啟示》。

CF1851G *2000

沒想到的：要淺推式子啊。如果路線如此 \(i\rightarrow j\rightarrow k\) 要滿足 \(h_j-h_i\le e\)、\(h_k-h_j\le e - h_j+h_i\)，所以 \(h_k\le e + h_i\) 所以路徑上的每一個(gè)點(diǎn)都要滿足這個(gè)條件。此時(shí)我們可以對(duì)詢問離線并按 \(h_u+e\) 從小到大排序，然后將每條邊的邊權(quán)視作 \(\max(h_u, h_v)\)，然后雙指針加邊即可。（這種套路很板啊）

CF2131G *2000

想到的：發(fā)現(xiàn)在操作時(shí)會(huì)有很多重復(fù)的操作，也就是說有重疊子問題，考慮 dp。接著手玩一下發(fā)現(xiàn)：

• 要把 \(\{2\}\) 變?yōu)榭招枰?\(2\) 次操作。
• 要把 \(\{3\}\) 變?yōu)榭招枰?\(4\) 次操作。
• 要把 \(\{4\}\) 變?yōu)榭招枰?\(8\) 次操作。

這也就意味著如果有一個(gè) \(s_i\ge 31\) 那就一定取不完了。有用嗎？所以可以按照這樣一個(gè)方式預(yù)處理出來要消掉每一個(gè)數(shù)所需要的花費(fèi)，然后模擬？Coding……無聊的題……

沒想到的：無。

dp

CF1841C *1800

想到的：考慮倒序枚舉然后 dp，可以直接暴力枚舉每個(gè)位置會(huì)改成什么字符。但這樣卻不能判斷后綴最大值？那把狀態(tài)改成三維 \(f_{i,0/1,k}\) 表示處理完后 \(i\) 位，\(1\) 表示已經(jīng)修改；\(0\) 反之，后綴最大值為 \(k\) 的答案。轉(zhuǎn)移顯然。

沒想到的：要初始化為極小值……。

CF1841D *2000

想到的：dp。

沒想到的：對(duì)于線段覆蓋問題，考慮按右端點(diǎn)排序。要大膽想 dp，不要畏難。

CF2086D *1700

想到的：將 \(\%2=0\) 和 \(\%2=1\) 的分開考慮，然后問題就轉(zhuǎn)變成背包，最后好像還要用組合數(shù)算一下剩下的方案數(shù)。這東西顯然可以先排列一下，然后再去重，即 \(ans = \frac{len1!\times len2!}{\prod c_i!}\)。接下來直接乘上背包的答案即可。

CF2005C *1800

想到的：\(n^2\) 枚舉進(jìn)行 dp？\(f_{i,j}\) 表示前 \(i\) 個(gè)串以及以 \(j\) 結(jié)尾的最大差值。但實(shí)際上可以把 \(i\) 給壓掉，因?yàn)槲覀冎魂P(guān)心前面的最大 dp 值。

沒想到的：dp 的一些細(xì)節(jié)，比如初始化要和 \(0\) 比較。

CF2053E *1900

想到的：這不顯然往最近的葉子節(jié)點(diǎn)走嗎？從葉子節(jié)點(diǎn) bfs dp 預(yù)處理每個(gè)點(diǎn)到葉子節(jié)點(diǎn)的最短距離，然后排個(gè)序，對(duì)于每個(gè)點(diǎn)到葉子節(jié)點(diǎn)的距離，找有多少個(gè)嚴(yán)格大于它的點(diǎn)即可。\kk，看錯(cuò)題了，沒有那么簡單。因?yàn)槊x的長度是不變的，所以答案中必然先會(huì)有葉子節(jié)點(diǎn)的個(gè)數(shù)乘上非葉子節(jié)點(diǎn)的個(gè)數(shù)，然后就是在先手走了一步后后手剛好到一個(gè)葉子節(jié)點(diǎn)的旁邊，然后這樣就也能獲勝，否則平局。這顯然是一個(gè)實(shí)現(xiàn)較為麻煩的樹形 dp 了。

考慮定義 \(f_u\) 表示以 \(u\) 為根的子樹內(nèi)在往上走一步后會(huì)到達(dá)葉子節(jié)點(diǎn)旁邊的點(diǎn)的個(gè)數(shù)。則其轉(zhuǎn)移為：

\(distance_u\) 表示點(diǎn) \(u\) 到最近的葉節(jié)點(diǎn)的距離。

再定義 \(dp_u\) 表示以 \(u\) 為根的子樹內(nèi)距離葉子節(jié)點(diǎn)的距離為大于 \(1\) 的點(diǎn)的個(gè)數(shù)，轉(zhuǎn)移顯然。

考慮定義 \(g_u\) 表示當(dāng)點(diǎn) \(u\) 為子樹的根時(shí)的答案數(shù)量。則其轉(zhuǎn)移為：

最終答案即為：\(g_{root}\)。

沒想到的：原來有簡便的換根寫法。

CF2060F *2200

想到的：首先注意到一些性質(zhì)，一個(gè)數(shù)的因數(shù)是很少的，所以 \(a\) 數(shù)組中必然有很多 \(1\)。同時(shí)，這個(gè)數(shù)據(jù)范圍是可以 \(O(k\sqrt{k})\) 過的，所以可以直接對(duì)每個(gè) \(x\) 暴力枚舉因數(shù)。因?yàn)橛泻芏嘀丿B子問題，所以考慮 dp。注意到只有在 \(n\le 17\) 才會(huì)對(duì)組成有影響，所以可以在定義狀態(tài)為：\(f_{x,i}, i\le \min(17, n)\) 表示在最短數(shù)組長度為 \(i\) 時(shí)，乘積為 \(x\) 的方案數(shù)。這樣子就需要預(yù)處理一下因數(shù)了。What about transfer?

還沒完，這個(gè)方程顯然沒有去重。不會(huì)了，啊啊啊！！！甲烷了……可以先考慮不包括 \(1\) 的情況，然后式子就有了。

沒想到的：原來有上指標(biāo)求和這種東西……\(\sum_{k=r}^{n}C^r_k=C_{n+1}^{r+1}\)。

貪心

CF2085D *2000

看了 tag：貪心，堆。

想到的：是反悔貪心？哦，吃了幾盤壽司是可以被算出來的；不行，因?yàn)橛锌赡軙?huì)有不操作的情況。那就用一個(gè)變量表示現(xiàn)在還有多少空閑的天，如果還夠吃就把壽司 push 小根堆，否則 pop 并且空閑的天增加。這還是不能保證一定有足夠的天來吃啊！

沒想到的：因?yàn)楹竺娴奶鞌?shù)會(huì)影響現(xiàn)在的取法，所以考慮從后往前貪心。

CF1996F *1900

想到的：好像只能貪心了啊？怎么轉(zhuǎn)化呢，需要發(fā)現(xiàn)一些性質(zhì)。考慮 \(a_i\) 和 \(a_i-b_i\) 發(fā)生了什么轉(zhuǎn)變，即 \(a_i\) 在原數(shù)組中的大小位置變化了。而最樸素貪心的方法便是用大根堆去維護(hù)原數(shù)組中的元素的最大值，然后每次模擬操作。那我們是否可以對(duì)于每個(gè) \(a_i\) 都計(jì)算出它會(huì)對(duì)答案有多少次貢獻(xiàn)呢？可以使用二分來算出每個(gè)數(shù)在進(jìn)行多少次操作后會(huì)變成最大值、變成不是最大值。

沒想到的：竟然是二分答案……假設(shè)我們有一個(gè)最大值 \(x\)，在每次操作時(shí)我們一定不會(huì)取 \(a_i< x\) 的 \(a_i\)，此時(shí)我們就可以對(duì) \(x\) 進(jìn)行二分，找到第一個(gè)使得把所有 \(a_i\ge x\) 的 \(a_i\) 取完后所用的次數(shù) \(\ge k\) 的 \(x\)，然后統(tǒng)計(jì)答案。

算法學(xué)習(xí)

矩陣快速冪

簡而言之，兩個(gè)矩陣只能在列和行數(shù)相等時(shí)進(jìn)行乘法，所以不滿足交換律。然后快速冪就沒什么區(qū)別了，唯一在于重載運(yùn)算符。

一般的題目都是需要快速遞推答案時(shí)用到矩陣快速冪，所以推出初始矩陣是最難的，這需要大量練習(xí)。

Lucas 定理

結(jié)論：\(C^m_n\bmod p = C^{m\div p}_{n\div p}\times C^{m\bmod p}_{n\bmod p}\)。

Master Theorem 主定理

對(duì)于形如 \(T(n)=aT(\lceil \frac{n}{b}\rceil)+O(n^k)\) 的式子的時(shí)間復(fù)雜度分析，有：

• \(\log_b a > n^k\)，時(shí)間復(fù)雜度為：\(O(n^{\log_b a})\)。
• \(\log_b a = n^k\)，時(shí)間復(fù)雜度為：\(O(n^k\log n)\)。
• \(\log_b a < n^k\)，時(shí)間復(fù)雜度為：\(O(n^k)\)。