信息學進階（簡體書）

《信息學進階》為創客教育系列叢書的高中第三冊，共分為7 章，涵蓋了高中信息學競賽的所有知識點。內容描述力求化繁為簡，深入淺出，針對每個重要的知識點配以經典實例進行精心剖析，結合清晰的代碼及生動的文字、畫龍點睛的注解，力求通俗易懂。 《信息學進階》由全國著名信息學國際金牌教練、NOI 鑽石教師宋新波老師主筆，NOI 金牌教師熊超等老師參與編寫，與創客教育教材初中第三冊《信息學初步》一脈相承，是初中版基礎上的深化與拓展，屬￿發展性課程及研究性課程範疇，因而本書不再重複信息學基本知識，主要側重於算法、數據結構專題，假如你是一名初學者，強烈建議先閱讀《信息學初步》。 《信息學進階》為創客教育系列叢書高中第三冊，適合高中三年級學生閱讀使用。

第１章 深度優先搜索的優化
1.1 剪枝優化
【知識講解】
【實踐鞏固】
1.2 迭代加深優化
【知識講解】
【實踐鞏固】
第2章 廣度搜索的優化
2.1 雙向廣度優先搜索
2.2 優先隊列廣度優先搜索
2.3 Hash判重
第3章 動態規劃進階
3.1 區間類動態規劃
3.2 樹形動態規劃
3.3 數位DP
3.3.1 數位DP的基本思想
3.3.2 數位DP的應用
3.4 狀態壓縮DP
3.4.1 狀態壓縮DP的基本思想
3.4.2 狀態壓縮DP的應用
3.5 單調隊列優化
3.6 斜率優化動態規劃
3.6.1 知識講解
3.6.2 實踐鞏固
第4章 圖論
4.1 圖的基本概念
4.1.1 圖的一些定義和概念
4.1.2 圖的存儲結構
4.2 圖的遍歷
4.2.1 深度優先遍歷和廣度優先遍歷
4.2.2 一筆劃問題
4.3 最短路徑算法
4.3.1 Bellman-Ford算法的實現及運用
4.3.2 SPFA算法的實現及運用
4.3.3 Dijkstra算法的實現及運用
4.3.4 Floyd算法的實現及運用
4.4 圖的連通性
4.4.1 無向圖的割點與橋
4.4.2 無向圖的雙連通分量
4.4.3 有向圖的強連通分量
4.5 最小生成樹
4.5.1 Prim算法
4.5.2 Kruskal算法
4.6 拓撲排序與關鍵路徑
4.6.1 AOV網
4.6.2 拓撲排序算法的基本思想與應用
4.6.3 關鍵路徑
第5章 字符串算法
5.1 哈希和哈希表
5.2 KMP算法
5.3 Trie字典樹
5.3.1 Trie字典樹的思想
5.3.2 Trie字典樹的應用
第6章 高級數據結構
6.1 並查集
6.2 樹狀數組
6.3 RMQ
6.4 快速冪與矩陣乘法
6.4.1 快速冪
6.4.2 矩陣乘法
6.4.3 LCA
6.5 線段樹
6.5.1 線段樹的基本思想
6.5.2 線段樹的單點修改
6.5.3 線段樹的區間查詢
6.5.4 區間修改和標記
6.6 平衡樹
6.6.1 二叉查找樹的基本思想與應用
6.6.2 Treap的基本思想與應用
第7章 數學基礎
7.1 GCD與拓展GCD
7.1.1 最大公約數GCD的求法
7.1.2 擴展歐幾裡得算法的基本思想與應用
7.2 同余定理
7.2.1 同余定理概述
7.2.2 線性同余方程的求解
7.3 逆元問題
7.3.1 逆元問題的求解
7.3.2 逆元的應用
7.4 容斥原理