7月份主要針對于以下幾個類型:搜索,DP,圖論(部分)。
搜索:主要是DFS和BFS,特別一點是注意剪枝。
1010 Tempter of the Bone DFS+奇偶剪枝。
1016 Prime Ring Problem 簡單的DFS,第一次沒看清題目,沒注意尾部和首部相加也要是素數(shù)。可以先用一個數(shù)組把素數(shù)先標(biāo)記好,那DFS就很簡單了。
1181 變形課 簡單的DFS。用鄰接矩陣將首尾字母保存,從字母‘b’開始DFS搜索。注意跳過已經(jīng)搜過的字母。
1195 Open the Lock 2717 Catch That Cow 簡單BFS。注意跳過已經(jīng)搜索過的。
1240 Aseroids! 簡單的BFS。錯了幾次是因為沒把數(shù)據(jù)用多維數(shù)組保存好。
1241 Oil Deposits DFS和BFS都可以。斜線方向也是可以的。
1242 Rescue BFS。但是注意可能由多個Freind,所以從Angle開始搜。
1312 Red and Black 簡單DFS。
1198 Farm Irrigation 可以用BFS,但我是用“并查集”做的。
DP:這個是弱點,所以沒做多少,只做一些簡單的。
1003 MaxSum 最長連續(xù)子序列,經(jīng)典DP,基本DP。
1024 MaxSum Plus Plus 關(guān)鍵是如何降維,將O^3最后變成O^2的,否則會超時。
1114 Piggy-Bank 完全背包問題。
1159 Common Subsequence 最長公共字串,經(jīng)典DP問題。
1203 I NEED A OFFER!0-1背包問題。
1257 最少攔截系統(tǒng) 一個簡單方法,利用vector 開一個動態(tài)數(shù)組,每次讀一個數(shù)據(jù),從前掃描過來,遇到比所讀數(shù)據(jù)大的,就更新那個數(shù)據(jù)為所讀數(shù)據(jù),最后,該數(shù)組長度就是導(dǎo)彈系統(tǒng)個數(shù)。
1559 最大子矩陣 對數(shù)組中的數(shù)據(jù)做下修改,對于a[i][j] 重新更新為 a[1][1]—a[i][j] 子矩陣的和,然后就可以搜一下整個數(shù)組就能得到最大子矩陣了。
1428 漫步校園 先是從終點BFS到起點,把耗費保存在一個表中,然后再從起點DFS終點求的所有路線,但注意要記錄已經(jīng)遍歷過的點,下次遍歷就直接加上上次遍歷所得的路線數(shù)目,否則會超時。
圖論:主要做了 單源最短路徑--Dijkstra算法,所有點的-Floyd算法;最小生成樹--Prim算法,另外那個還沒寫過( = =! ); 最大子團(tuán)--回溯法
1217 Arbitrage 建立一個有向圖,利用Floyd算法,問題也就是求通過其他點到自己有沒有增加。
1596 find the safest road 所有點最短路徑--Floyd可以解決。
1530 Maxumum Clique 最大子團(tuán) 回溯法,就是耗時比較多。
1162 Eddy’s picture 最小生成樹--Prim算法
1232 暢通工程 赤裸裸的并查集。
1301 Jungle Roads 還是最小生成樹