考察：揹包dp,容斥原理
主要是一個dp容斥的思想：
用揹包處理無數量限制的方案值，減去某些硬幣超出數量限制的方案值。
減去不合規範方案的方法：
直接將總的錢數減去（該硬幣數+1）*該硬幣價值進行dp，確保該硬幣超出限制。
最後套一下容斥原理的公式即可。
考察：線段樹，差分
區間求和，區間修改，自然想到線段樹，以等差數列的方式修改，自然想到用相鄰兩數之差（即差分的思想）進行建樹，查詢時即為1-i的區間和。
幾乎是個線段樹差分的模板題。
考察：樹形dp
看到樹，看到求最小值，自然想到樹形dp.
樹形dp就是從子孫的狀態向父親的狀態推，根據題意，兩個消防局之間可以至多空4個點，因此想到設狀態為子樹中離自己最近的消防局的距離，從1-4不同的狀態轉移到父節點。
樹形dp的準板子題
考察：搜尋
題意即為1-N區間內找約數最多的數
看到N的範圍，這裡用質數篩，用約數公式，用dp都不好使
想到每個數分解成質因數的數量是log級別的
於是篩出1-20之間的素數，暴力列舉每個質數的個數，用約數個數公式比較計算。
一種全新的計算約數個數的思維。
考察：搜尋
題意為用最小個數的正整數去表示
1
−
n
1-n
1−n中的所有數。
聯絡到經典的貼郵票問題，
n
n
n的範圍
1
0
3
10^3
103，想到搜尋。
每次搜尋，都嘗試在已經選擇的數後再新增一個更大的數，設已選擇數列的最大值為
m
a
x
max
max,可以組成的最大的數為
s
u
m
sum
sum，已經選了
n
u
m
num
num個數。
列舉下一個數i的範圍
[
m
a
x
+
1
,
s
u
m
+
1
]
[max+1,sum+1]
[max+1,sum+1]，容易得到，新增數後
s
u
m
sum
sum應改為
s
u
m
+
i
sum+i
sum+i.
簡而言之：
dfs(num,sum,max)
for i<-max+1 to sum+1 do
dfs(num+1,sum+i,i)
考察：卡特蘭數
卡特蘭數應用的經典例題。
詳細見：卡特蘭數，折線定理。
這裡給出公式：
(
m
n
+
m
)
−
(
m
−
1
n
+
m
)
\dbinom{m}{n+m}−\dbinom{m-1}{n+m}
(n+mm)−(n+mm−1)。
詳細證明見百度
考察：組合數
式子很好列，關鍵是答案的輸出。
肯定是要用到高精(python)
這裡我們考慮一種非常樸素的計算答案的方法。
對組合數進行約分
如何約分？
對
1
−
m
+
n
1-m+n
1−m+n的所有數進行素因數分解（其實只需要一個最小質因數的值）
若在分子上，就將這個素因數的出現次數+1，若在分母上，出現次數-1.最後把所有的素因數乘起來，高精100位陣列即可。
考察：區間DP，高精
容易想到，對於每一行取數的最大值，等於先取左邊數與先取右邊數的較大值。
因此運用區間DP。
轉移方程：
d
p
[
k
]
[
k
+
j
]
=
m
a
x
(
2
∗
d
p
[
k
+
1
]
[
k
+
j
]
+
2
∗
g
r
i
d
1
[
i
]
[
k
]
,
2
∗
d
p
[
k
]
[
k
+
j
−
1
]
+
2
∗
g
r
i
d
1
[
i
]
[
k
+
j
]
)
dp[k][k + j] = max(2 * dp[k + 1][k + j] + 2 * grid1[i][k], 2 * dp[k][k + j - 1] + 2 * grid1[i][k + j])
dp[k][k+j]=max(2∗dp[k+1][k+j]+2∗grid1[i][k],2∗dp[k][k+j−1]+2∗grid1[i][k+j])
其中
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]為
i
−
j
i-j
i−j列取數的最大值，
g
r
i
d
1
[
i
]
[
j
]
grid1[i][j]
grid1[i][j]為矩陣上
a
i
,
j
a_{i,j}
ai,j的值。
對於每一行分別處理再相加即可。
至於高精，過載運運算元後正常算就好。
考察：搜尋
看到這個N的範圍就知道用搜尋了。
先預處理每個單詞能往後接的所有單詞，用向量存一下。
然後大力搜，列舉每一個單詞作為開頭的單詞。
注意:
對於每一個搜尋到的狀態壓縮儲存起來，空間複雜度是
O
（
2
N
）
O（2^ N）
O（2N），時間複雜度
O
（
2
N
）
O（2^ N）
O（2N）.
考察：數論分塊
k
(
m
o
d
i
)
k \pmod i
k(modi)的形式難以計算，考慮最樸素的轉化方式。
k
(
m
o
d
i
)
=
k
−
⌊
(
k
i
)
⌋
∗
i
k \pmod i = k - \lfloor(\frac{k}{i}) \rfloor*i
k(modi)=k−⌊(ik)⌋∗i
右邊的式子直接數論分塊愉快AC