摘要： P9108 較火的題。 設 \(f_{i,l,r}\) 表示第 \(i\) 行涂 \([l,r]\) 的方案數，\(sum_i=\sum\limits_l\sum\limits_r f_{i,l,r}\)。轉移 \[f_{i,l,r}=sum_{i-1}-\sum\limits_{R<l}\sum\ 閱讀全文

摘要： [NFLSPC #6] 等差數列 考慮枚舉公差 \(d\)，如何求得最少題數 \(m\)？ 貪心的想，我們希望的等差數列是一條直線，而增加的數最少就相當于讓直線最低且任意點不低過原序列。掃一遍序列，動態維護當先最少需要增加的數 \(f\) 和當前末項大小 \(g\)，如果下一項 \(a_i<g-d\ 閱讀全文

摘要： [NOIP2020] 字符串匹配 枚舉前綴 \(AB\) 和 \(i\)，kmp 判斷是不是周期串。 [COCI2016-2017#4] Rima 押韻條件： 第一位不一樣 去掉第一位 trie 樹掃一掃。 [POI2010] ANT-Antisymmetry 重載馬拉車。 [USACO15FEB] 閱讀全文

摘要： 退位計劃 全部顏色都選的限制很強，考慮對他容斥。 首先我們可以很容易求出 \(n\) 個點最多用 \(k\) 個點的答案為 \(k(k-1)^{n-1}\)。 那么我們此時多算了某個顏色沒選的答案，需要減掉他，于是答案就顯然了。 \(\sum\limits^{k}_{i=1} -1^{k-i}\ti 閱讀全文

摘要： # 概念 DDP，可以理解為轉移會發生改變的動態規劃。 當然這個改變是題目中給的，包括系數，轉移位置的改變。顯然暴力枚舉這些改變是不現實的，我們要把改變體現到其他地方。 最經典的，體現到矩陣上。 我們把轉移寫成矩陣，那么改變轉移就是改變轉移矩陣。 具體的改變會落實到具體的題目上。 ## 廣義矩陣乘法 閱讀全文

摘要： # 概念 對于一個很多詢問的題，假如對于一個詢問可以二分處理，同時一次 check 可以只用 $n$ 的時間處理所有詢問的 check 結果，我們可以使用整體二分來做這個題。 # 思想 設函數 $\operatorname{solve}(S, L, R)$ 為現在正在處理詢問序列 $S$ 里的詢問， 閱讀全文

摘要： ## 概念 虛樹是一棵樹，相對于原樹而言。它刪去原樹上某些點，再按原樹父子關系連邊構成的樹。 它對樹上算法有一定優化。假如一個樹上問題僅與部分節點有關，如樹形DP，DP值僅在部分節點有改變，那么就可以已這部分節點建成虛樹，省略其他部分，復雜度為部分節點總和。 ### 例：[消耗戰](https:// 閱讀全文

摘要： # P3245 [HNOI2016]大數 考慮如何提取區間 $[l,r]$ 組成的數。 設 $SA_i$ 表示 $S[i,n]$ 組成的數值，則 $[l,r]$ 組成的數為 $SU_{l,r}=\frac{SA_l-SA_{r+1}}{10^{n-r}}$ 且統計 $SU_{l,r}\mod P=0 閱讀全文

摘要： 概念 后綴數組，即對于一個串，它的每個后綴按字典序排序后得到的數組。 有兩個數組要求： $SA_i$:排名為 $i$ 的后綴的開頭位置 $RK_i$:以 $i$ 為開頭的后綴的排名 樸素 sort排序一下 優化 倍增優化：我們進行 $\log n$ 次排序，第 $k$ 次取所有后綴的前 $2^k$ 閱讀全文