算法競賽入門經典訓練指南.pdf

是《算法藝術與信息學競賽》的學習指導。所謂學習指導，是告訴讀者學什 么，如何學。算法包羅萬象，很難在一中的篇幅覆蓋很多內容的通知對每個知識 點進行細致講解，因此更多的是作為一本導引、工具、手冊或者學習大綱，給 讀者以宏觀上的學習指導。和原《算法藝術與信息學競賽》相比，的特點有： ² 大量知識講解。 ² 更多循序漸進的習題。 ² 重要算法的源代碼。 從知識結構上看，的覆蓋面比原更廣，補充了原沒有涉及到在知識點， 包括計算理論中的NP完全理論和圖靈機的基本概念、數(shù)據結構中的伸展樹、Treap，左 偏樹、二項堆、Fibonacci堆、數(shù)論中的指數(shù)和原根、分解因數(shù)的快速算法、數(shù)值計算 中的高斯消元法和FFT、組合游戲論初步、更多序列經典問題和線段樹、后綴數(shù)組等 數(shù)據結構的應用、樹更多經典問題、多模式串匹配算法、后綴樹構造的Ukkonen算法、 后綴數(shù)組構造的Skew算法、更加詳細的強連通分量/雙連通分量算法、最大流和最小費 用流算法、二分圖和任意圖的最大基數(shù)匹配算法和最大權匹配算法、穩(wěn)定婚姻問題、 線性規(guī)劃在網絡優(yōu)化中的作用、向量代數(shù)基礎、多邊形剖分算法、平面剖分、半平面 交、三維凸包、Voronoi圖和直線排列的構造算法、幾何對偶性的應用、Minkowski和與 簡單運動規(guī)劃問題等。