算法競賽入門經典：訓練指南（簡體書）

本書是《算法競賽入門經典》的重要補充，旨在補充原書中沒有涉及或者講解得不夠詳細的內容，從而構建一個較完整的知識體系，並且用大量有針對性的題目，讓抽象複雜的算法和數學具體化、實用化。
本書共6章，分別為算法設計基礎、數學基礎、實用數據結構、幾何問題、圖論算法與模型和更多算法專題，全書通過近200道例題深入淺出地介紹了上述領域的各個知識點、經典思維方式以及程序實現的常見方法和技巧，並在章末和附錄中給出了豐富的分類習題，供讀者查漏補缺和強化學習效果。
本書題目多選自近年來ACM/ICPC區域賽和總決賽真題，內容全面，信息量大，覆蓋了常見算法競賽中的大多數細分知識點。書中還給出了所有重要的經典算法的完整程序，以及重要例題的核心代碼，既適合選手自學，也方便教練組織學習和訓練。

劉汝佳，1982年12月生，高中畢業于重慶市外國語學校。
2000年3月獲得NOI2000全國青少年信息學奧林匹克競賽一等獎第四名，進入國家集訓隊，並因此保送到清華大學計算機科學與技術系。大一時獲2001年ACM/ICPC國際大學生程序設計競賽亞洲-上海賽區冠軍和2002年世界總決賽銀牌（世界第四），2005年獲學士學位，2008年獲碩士學位。
學生時代曾為中國計算機學會NOI科學委員會學生委員，擔任IOI2002-2008中國國家隊教練，並為NOI系列比賽命題十餘道。現為NOI競賽委員會委員，並在NOI 25周年時獲得中國計算機學會頒發的“特別貢獻獎”。
2004年至今共為ACM/ICPC亞洲賽區命題二十餘道，擔任6次裁判和2次命題總監，並應邀參加IOI和ACM/ICPC相關國際研討會，發表論文兩篇。
2004年初作為第一作者出版專著《算法藝術與信息學競賽》，2009年出版譯著《編程挑戰》，2009年出版《算法競賽入門經典》。
多年來在全國二十餘個城市進行中學生競賽培訓工作，為北京、上海、吉隆坡等地的著名高校授課與宣講，並多次與TopCoder、百度和網易有道等知名企業合作舉辦比賽，讓更多的IT人才獲得展示自我的平臺。
陳鋒，1982年9月生。畢業于華北水利水電學院機械設計專業。曾就職於微軟全球技術支持中心，負責.net虛擬機以及Visual Studio開發技術支持。後進入金融IT行業，專注於銀行網點平臺的產品研發，曾分別負責基於.net和Eclipse的兩代網點平臺產品的開發以及架構設計。現就職于北京宇信易誠科技，任前端產品技術經理及架構師。

第1章 算法設計基礎
1.1 思維的體操
1.2 問題求解常見策略
1.3 高效算法設計舉例
1.4 動態規劃專題
1.5 小結與習題
第2章 數學基礎
2.1 基本計數方法
2.2 遞推關係
2.3 數論
2.3.1 基本概念
2.3.2 模方程
2.4 組合遊戲
2.5 概率與數學期望
2.6 置換及其應用
2.7 矩陣和線性方程組
2.8 數值方法簡介
2.9 小結與習題
第3章 實用數據結構
3.1 基礎數據結構回顧
3.1.1 抽象數據類型（ADT）
3.1.2 優先隊列
3.1.3 並查集
3.2 區間信息的維護與查詢
3.2.1 二叉索引樹（樹狀數組）
3.2.2 RMQ問題
3.2.3 線段樹（1）：點修改
3.2.4 線段樹（2）：區間修改
3.3 字符串（1）
3.3.1 Trie
3.3.2 KMP算法
3.3.3 Aho-Corasick自動機
3.4 字符串（2）
3.4.1 後綴數組
3.4.2 最長公共前綴（LCP）
3.4.3 基於哈希值的LCP算法
3.5 排序二叉樹
3.5.1 基本概念
3.5.2 用Treap實現名次樹
3.5.3 用伸展樹實現可分裂與合併的序列
3.6 小結與習題 244第4章 幾何問題
4.1 二維幾何基礎
4.1.1 基本運算
4.1.2 點和直線
4.1.3 多邊形
4.1.4 例題選講
4.1.5 二維幾何小結
4.2 與圓和球有關的計算問題
4.2.1 圓的相關計算
4.2.2 球面相關問題
4.3 二維幾何常用算法
4.3.1 點在多邊形內判定
4.3.2 凸包
4.3.3 半平面交
4.3.4 平面區域
4.4 三維幾何基礎
4.4.1 三維點積
4.4.2 三維叉積
4.4.3 三維凸包
4.4.4 例題選講
4.4.5 三維幾何小結
4.5 小結與習題
第5章 圖論算法與模型
5.1 基礎題目選講
5.2 深度優先遍曆
5.2.1 無向圖的割頂和橋
5.2.2 無向圖的雙連通分量
5.2.3 有向圖的強連通分量
5.2.4 2-SAT問題
5.3 最短路問題
5.3.1 再談Dijkstra算法
5.3.2 再談Bellman-Ford算法
5.3.3 例題選講
5.4 生成樹相關問題
5.5 二分圖匹配
5.5.1 二分圖最大匹配
5.5.2 二分圖最佳完美匹配
5.5.3 穩定婚姻問題
5.5.4 常見模型
5.6 網絡流問題
5.6.1 最短增廣路算法
5.6.2 最小費用最大流算法
5.6.3 建模與模型變換
5.6.4 例題選講
5.7 小結與習題
第6章 更多算法專題
6.1 輪廓線動態規劃
6.2 嵌套和分塊數據結構
6.3 暴力法專題
6.3.1 路徑尋找問題
6.3.2 對抗搜索
6.3.3 精確覆蓋問題和

第4章 幾 何 問 題

幾何問題是高水平算法競賽中不可或缺的題型。由於背景知識多，內容雜亂，因此《算法競賽入門經典》幾乎沒有涉及真正意義上的幾何問題。本章通過介紹一些幾何中的常見問題和算法，力圖讓讀者具備一定的幾何解題能力，並感受到幾何的美。
4.1 二維幾何基礎

圖 4-1

簡單地說，向量（vector）就是有大小和方向的量，如速度、位移等物理量都是向量。向量最基本的運算是加法，滿足平行四邊形法則，如圖4-1所示。
在平面坐標系下，向量和點一樣，也用兩個數x、y表示。它等於向量的起點到終點的位移，也相當於把起點平移到坐標原點後，終點的坐標。儘管如此，請讀者不要在概念上把點和向量弄混。比如，點-點=向量，向量+向量=向量，點+向量=點，而點+點是沒有意義的。在第6章中，我們會介紹齊次坐標的概念，從而在程序上區分開點和向量，但在本章中，點和向量都用兩個數x、y表示。
下面是它們的常用定義。
 
struct Point {
double x, y;
Point(double x=0, double y=0):x(x),y(y) { } //構造函數，方便代碼編寫
};
 
typedef Point Vector; //從程序實現上，Vector只是Point的別名
 
//向量+向量=向量，點+向量=點
Vector operator + (Vector A, Vector B) { return Vector(A.x+B.x, A.y+B.y); }
//點-點=向量
Vector operator - (Point A, Point B) { return Vector(A.x-B.x, A.y-B.y); }
//向量*數=向量
Vector operator * (Vector A, double p) { return Vector(A.x*p, A.y*p); }
//向量/數=向量
Vector operator / (Vector A, double p) { return Vector(A.x/p, A.y/p); }
 
bool operator < (const Point& a, const Point& b) {
return a.x < b.x || (a.x == b.x && a.y < b.y);
}
 
const double eps = 1e-10;
int dcmp(double x) {
if(fabs(x) < eps) return 0; else return x < 0 ? -1 : 1;
}
 
bool operator == (const Point& a, const Point &b) {
return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;
}
 
注意上面的“相等”函數用到了“三態函數”dcmp，減少了精度問題。另外，向量有一個所謂的“極角”，即從x軸正半軸旋轉到該向量方向所需要的角度。C標準庫裏的atan2函數就是用來求極角的，如向量(x,y)的極角就是atan2(y,x)（單位：弧度）。
4.1.1 基本運算

點積。兩個向量v和w的點積等於二者長度的乘積再乘上它們夾角的余弦。如圖4-2所示這裏的θ是指從v到w逆時針旋轉的角，因此當夾角大於90°時點積為負。
余弦是偶函數，因此點積滿足交換率。如果兩向量垂直，點積等於0。不難推導出：在平面坐標系下，兩個向量OA和OB的點積等於xAxB+yAyB。下面是點積計算方法，以及利用點積計算向量長度和夾角的函數。
 
double Dot(Vector A, Vector B) { return A.x*B.x + A.y*B.y; }
double Length(Vector A) { return sqrt(Dot(A, A)); }
double Angle(Vector A, Vector B) { return acos(Dot(A, B) / Length(A) / Length(B)); }
 
叉積。簡單地說，兩個向量v和w的叉積等於v和w組成的三角形的有向面積的兩倍。什麼叫“有向面積”呢（見圖4-3）？

圖 4-2 圖 4-3

順著第一個向量v看，如果w在左邊，那麼v和w的叉積大於0，否則小於0。如果兩個向量共線（方向相同），那麼叉積等於0（三角形退化成線段）。不難發現，叉積不滿足交換率。事實上，cross(v,w)=-cross(w,v)。在坐標系下，兩個向量OA和OB的叉積等於xAyB-xByA。代碼如下。
double Cross(Vector A, Vector B) { return A.x*B.y - A.y*B.x; }
double Area2(Point A, Point B, Point C) { return Cross(B-A, C-A); }
 
 
圖 4-4

兩個向量的位置關係。把叉積和點積組合到一起，我們可以更細緻地判斷兩個向量的位置關係。如圖4-4所示，括號裏的第一個數是點積的符號，第二個數是叉積的符號，第一個向量v總是水平向右，另一個向量w的各種情況都包含在了圖中。比如，當w的終點在下圖左上方的第二象限時點積為負但叉積均為正，用(-,+)表示。
向量旋轉。向量可以繞起點旋轉，公式為x’=xcosa- ysina, y’=xsina+ycosa。其中a為逆時針旋轉的角。代碼如下。
 
//rad是弧度
Vector Rotate(Vector A, double rad) {
return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));
}
 
作為特殊情況，下面的函數計算向量的單位法線，即左轉90°以後把長度歸一化。
 
//調用前請確保A不是零向量
Vector Normal(Vector A) {
double L = Length(A);
return Vector(-A.y/L, A.x/L);
}
 
基於複數的幾何計算。在本節結束前，筆者還想介紹另外一種實現點和向量的方法，即使用C++裏的複數。
 
#include
using namespace std;
typedef complex Point;
typedef Point Vector;
 
這樣定義之後，我們自動擁有了構造函數、加減法和數量積。用real(p)和imag(p)訪問實部和虛部，conj(p)返回共軛複數，即conj(a+bi)=a-bi。相關函數如下。
 
double Dot(Vector A, Vector B) { return real(conj(A)*B); }
double Cross(Vector A, Vector B) { return imag(conj(A)*B); }
Vector Rotate(Vector A, double rad) { return A*exp(Point(0, rad)); }
 
上述函數的效率不是很高，但是相當方便、好記。