HDU ACM Steps攻略 ACM Steps的全部内容

原位址：http://www.byywee.com/page/M0/S607/607452.html

總結了一下ACM STEPS的各章内容，趁便附上我的Steps題号（每人的不一樣）。

别的，此文首要目标是為了裝逼；

大牛請疏忽；

摸索欲鬥勁強的請疏忽；

其實不樂于從A+B刷起的可以找到須要的響應題号操練～～

1.1

根蒂根基輸入輸出：LCY的 A+B 8題

（1089~1096）

1.2

C說話根蒂根基：根蒂根基入門題

（2104，2088，1076，2095，1061，1170，3361，1197）

1.3

排序，貪婪：

1052 很惡心的一道貪婪題

3177 我推薦的這題貌似卡了不少人，遵守內插補點排序

（1236，1084，2093，2111，2187，1157）

2.1

簡單數學題：GCD和素數生成占了很大一項目組

1071 積分題

1717 這題鬥勁麻煩

（1108，2138，2504，1215，1286，1060）

2.2

遞歸：Fibonacci，約瑟夫環，漢諾塔什麼的，說是遞歸，for一下就好了，或者是找規律

1005 感觸感染找規律有題目，建議用矩陣

（1568，1443，1997，1222，1032，1013，1018）

2.3

大數，卡塔蘭數：Java什麼的最高興了

（1002，1063，1212，1130，1133，1131，1134，1267）

3.1

遞推：推推題

2604 這題要用矩陣

（2041，2044，2046，2018，2050，2501，2563）

3.2

簡單dp：數塔什麼的

（1003，1159，1087，1058，1069，2084，1176，2571）

3.3

背包：各類背包

（2602，1114，1171，2844，1059，2955，1203，3466）

4.1

二分，三分：感觸感染這不克不及算是搜刮

（2199，2899，1969，2298，2438，3400，1551，2178）

4.2

bfs：入門級的搜刮

1175 連連看，dfs+減枝最快了

2531 以前想過這種模型，做steps才發明已經有人出過了，先掃一遍圖，轉化成單點景象

（1241，1242，1548，1372，1312，1495）

4.3

dfs：hh加了很多多少惡心的搜刮進來，這關卡了不少人

1010 入門級的dfs，減枝很首要

1426 dlx水過～～

2553 我那險惡的十層for打表，Matrix67部落格有狀況緊縮版

2610 2611 這兩題都在這一章，很少人過，不過也不是很難，dfs很快，我是bfs做的

（1016，3290，2821，2514）

5.1

并查集：并查集的題目還是很給力的

1598 列舉下界，判上界

2473 要删點的并查集，虛拟節點作為每個真實節點的父節點，對虛拟節點進行操縱

（1829，1325，1558，3635，3047，3038）

5.2

字典樹，拓撲排序，哈夫曼樹：各類雜算法

1800 int就可以水過 - -|||

3518 比賽時hh用字典樹過了這題，就加在這裡了，卡了很多多少人，正解字尾數組

3231 一道很好的拓撲排序，每個立方體的每一個次元都拆成兩個量來做，三個次元之間沒有接洽

（1075，1251，1285，1053，2527）

5.3

樹狀數組，RMQ，LCA：持續雜

2874 用Tarjan鬥勁卡記憶體，兩個圖都用靜态鄰接表可以過，RMQ_LCA就很輕松了

3486 網上的二分辦法是水過的

2688 abs（E-S）<=1000 這裡用暴力的

（1166，1541，3584，2586，2838）

6.1

最小生成樹：通順工程

3367 也就這題鬥勁給力了，并查集加一個變量記錄有沒有環

（1102，1162，1232，1233，1879，1301，3371）

6.2

最短路及相幹：又被hh搞了幾個惡心題在裡面

2544 模闆題，然則資料鬥勁水，不克不及測模闆來着

1142 題目意思還能再蛋疼一點嗎

1596 求最大積，取log，因為都是0～1的直接乘也可以

3191 求次短路和次短路的條數，dijkstra

（2066，2722，1690，3339）

6.3

二分比對：神奇的二分比對，跪拜starfall大神全用收集流秒了

1151 最巷子徑覆寫

1507 很不錯的一題，請求比對規劃

（1068，1150，1281，1498，1528/1962，3360）

7.1

簡單策畫幾何：叉乘，多邊形面積，凸包，從頭翻出LCY課件來學了

2215 這題資料水

3661 這題加錯處所了

（2108，1086，1115，1392，1147，2202）

7.2

簡單數論：被小麗姐加了很多惡心題，後來看太BT了還删了幾個

數學盲默示這節隻切題号

（2824，1787，1757，3579，3307，1299，3802，1573）

7.3

母函數，高斯消元：母函數用dp更輕易，高斯消元默示不會，隻切題号

2451 打表，分景象評論辯論，然後再怎麼搞，忘了

1028 卡塔蘭數，應當是加錯了

1027 - - 應當也是加錯了

（1085，3571，1398，1709，3364）

8.1

隊列，棧：STL給力的一節

1387 這題鬥勁惡心

3328 這題很不錯

1870 這個for一遍就好了

（1702，1022，1237，1873，1509）

8.2

簡單博弈：簡單的組合遊戲，根蒂根基都不消求sg的

1907 anti-nim

（1846，1847，1848，1850，2149，2188，1851）

8.3

矩陣乘法：全能的矩陣

2254 這題描述很亂的說，不過很經典

2276 這題很神奇，竟然是矩陣

（1575，1757，2294，1588，2971，3519）

9.x 小結：這一章每小我都一樣的，hh選的題目都很給力

9.1

2054 坑爹題，Java無壓力

1789 簡單的依附背包模型

2159 二維背包

1401 雙廣，我的搜刮專題裡有題解

2818 并查集

3465 樹狀數組求逆序數對

2433 最短路，我暴力的

3524 矩陣

9.2

2052 水題

1871 貪婪

1254 dfs+bfs

3350 遞歸

3234 并查集裡面最煩的一題了

2642 二維樹狀數組

2833 最短路+dp

3483 矩陣，矩陣不太好推

9.3

2832 數學題

2604 矩陣，這題和前面重了

1429 搜刮bfs

2782 搜刮dfs，膽量題

1298 字典樹，我寫挫了，中心用一個dfs把字母樹轉為數字 樹

2363 最短路，列舉高低界

3389 鬥勁高等一點的博弈題

1496 把ab和cd分隔打表，然後列舉一遍判另一邊

10.1

最大團，穩定婚配，強連通，雙連通：又是各類雜算法

1530 最大團模闆題

1914 穩定婚配

3639 1827 1269 3072 強連通

2242 雙連通

3594 Tarjan的活用，之前有該題的題解

10.2 2-sat，差分束縛：持續各類雜算法

1824 3062 3622 直接看我的2-sat專題好了

2444 二分比對+圖染色

2666 差分束縛，鬥勁難

1534 3440 3592 差分束縛

10.3 收集流：一切皆收集流

1532 入門題

3313 很煩的一題，解法很多

1269 經典模型

3035 轉化為對偶圖後求最短路

3046 最小割模型

3251 流過之後從源點和彙點分别染色判割邊

1733 慢慢加層做收集流，EK鬥勁快

3061 費用流

11.1 線段樹：這一節的線段樹還是鬥勁簡單的，可以去看hh的線段樹專題

1199 區間染色，離散化時加點離散

1543 離散+暴力，不會有人去寫二維線段樹吧

1828 求矩形并周長

1698 區間更新區間乞降

1754 單點更新區間求最值

2795 忘了

1823 二維線段樹

3458 被曉宇哥DP過了，線段樹不會

11.2 線段樹，字尾數組：較難的線段樹，不過跟如今比賽中的線段樹比起來簡單多了，字尾數組都是論文題了

1403 簡單字尾數組

2459 鬥勁煩的一道

2890 離散化，論文裡說用二分判可行，貌似不消也行，但要批改high函數

2665 劃分樹

2871 很麻煩的線段樹了

3016 線段樹+dp

1255 求矩形交

3333 離線+線段樹/樹狀數組

11.3 KMP，AC主動機：KMP不知道為什麼放在這麼後面，還有幾個AC主動機，看hh的AC主動機專題

1711 KMP入門題，或者RK

1358 fail（或叫next）數組活用

3336 同上

3374 最小默示

2222 AC主動機入門題

2825 AC主動機+狀況緊縮dp

3341 AC主動機+dp

3247 AC主動機+狀況緊縮dp+最短路，隻取關鍵點的做法DBL

12.1

進階搜刮：底本認為搜刮做的很多了，成果發明貼了兩道之後就囧了

2757 簡單的bfs

2128 要hash全圖的bfs

3681 很牛逼的一題，先bfs出随便率性兩個特别點之間的最短路，然後隻取幾個特别點狀況緊縮dp/搜刮

1226 鬥勁簡單的bfs

1043 傳說中的八數位

3085 雙廣，我的搜刮專題有題解

3533 看似很麻煩的一道題

2471 bfs，題目太抽象了

12.2

A*，IDA*，預處理懲罰搜刮

2691 1813 1430 1667 2234 我的搜刮專題裡都有題解

1664 若是知道兩個數可以生成随便率性數的倍數就好做了，列舉1個數字的所有景象，若是沒有再去列舉兩個數字的所有景象，之後取此中字典序最小值

1067 膽量題，敢做就敢A，要hash全圖

2259 随機水過了

12.3

DLX，進階博弈：兩道巨惡心的dlx都在，然後是博弈

2295 dlx反複覆寫

2518 這道惡心題居然都在

3156 很牛逼的一道dlx，和2295不合的，要列舉所有可能點，重視減枝

3498 dlx反複覆寫

3660 敵對搜刮？

1809 博弈

3514 還沒做

3197 Game

13 動歸

14 幾何

15 神題

16 綜合