2020.8.4

P1450 [HAOI2008]硬幣購物

考察：背包dp,容斥原理
主要是一個dp容斥的思想：
用背包處理無數量限制的方案值，減去某些硬幣超出數量限制的方案值，
減去不合規范方案的方法：
直接將總的錢數減去（該硬幣數+1）*該硬幣價值進行dp，確保該硬幣超出限制，
最后套一下容斥原理的公式即可，

P1438 無聊的數列

考察：線段樹，差分
區間求和，區間修改，自然想到線段樹，以等引數列的方式修改，自然想到用相鄰兩數之差（即差分的思想）進行建樹，查詢時即為1-i的區間和，
幾乎是個線段樹差分的模板題，

P2279 [HNOI2003]消防局的設立

考察：樹形dp
看到樹，看到求最小值，自然想到樹形dp.
樹形dp就是從子孫的狀態向父親的狀態推，根據題意，兩個消防局之間可以至多空4個點，因此想到設狀態為子樹中離自己最近的消防局的距離，從1-4不同的狀態轉移到父節點，
樹形dp的準板子題

P1463 [POI2002][HAOI2007]反素數

考察：搜索
題意即為1-N區間內找約數最多的數
看到N的范圍，這里用質數篩，用約數公式，用dp都不好使
想到每個數分解成質因數的數量是log級別的
于是篩出1-20之間的素數，暴力列舉每個質數的個數，用約數個數公式比較計算，
一種全新的計算約數個數的思維，

P1490 買蛋糕

考察：搜索
題意為用最小個數的正整數去表示 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)

2020.8.5

P1641 [SCOI2010]生成字串

考察：卡特蘭數
卡特蘭數應用的經典例題，
詳細見：卡特蘭數，折線定理，
這里給出公式： ( m n + m ) ? ( m ? 1 n + m ) \dbinom{m}{n+m}?\dbinom{m-1}{n+m} (n+mm?)?(n+mm?1?)，
詳細證明見百度

P1492 猩猩散步

考察：組合數
式子很好列，關鍵是答案的輸出，
肯定是要用到高精(python)
這里我們考慮一種非常樸素的計算答案的方法，
對組合數進行約分
如何約分？
對 1 ? m + n 1-m+n 1?m+n的所有數進行素因數分解（其實只需要一個最小質因數的值）
若在分子上，就將這個素因數的出現次數+1，若在分母上，出現次數-1.最后把所有的素因數乘起來，高精100位陣列即可，

2020.8.6

P1005 矩陣取數游戲

考察：區間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?的值，
對于每一行分別處理再相加即可，
至于高精，多載運算子后正常算就好，

P1278 單詞游戲

考察：搜索
看到這個N的范圍就知道用搜索了，
先預處理每個單詞能往后接的所有單詞，用向量存一下，
然后大力搜，列舉每一個單詞作為開頭的單詞，
注意:
對于每一個搜索到的狀態壓縮存盤起來，空間復雜度是 O （ 2 N ） O（2^ N） O（2N），時間復雜度 O （ 2 N ） O（2^ N） O（2N）.

2020.8.7

P2261 [CQOI2007]余數求和

考察：數論分塊
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