算法設計編程實驗（第2版）

本書從ACM-ICPC程序設計競賽等各種程序設計競賽的試題進行了分析和整理，
並精選出典型試題進行分類解析，既可用於高校算法、程序設計課程的實驗和教學，也可以用於競賽選手的系統訓練。

前言
第1章求解Ad Hoc類問題的編程實驗1
1.1 機理分析法的實驗範例1
1.2 統計分析法的實驗範例5
1.3 相關題庫9
第2章模擬法的編程實驗31
2.1 直敘式模擬的實驗範例31
2.2 篩選法模擬的實驗範例46
2.3 構造法模擬的實驗範例56
2.4 相關題庫60
第3章數論的編程實驗72
3.1 素數運算的實驗範例72
3.1.1 使用篩法生成素數72
3.1.2 測試大素數79
3.2 求解不定方程和同餘的實驗範例82
3.2.1 計算*大公約數和不定方程82
3.2.2 計算同餘方程和同餘方程組89
3.2.3 計算多項式同餘方程99
3.3 特殊的同餘式的實驗範例102
3.3.1 威爾遜定理和費馬小定理102
3.3.2 偽素數105
3.3.3 歐拉定理112
3.4 積性函數的實驗範例116
3.4.1 歐拉φ函數φ(n) 116
3.4.2 莫比烏斯函數μ(n) 121
3.4.3 完全數和梅森素數124
3.5 高斯素數的實驗範例129
3.6 相關題庫135
第4章組合分析的編程實驗152
4.1 生成排列的實驗範例152
4.1.1 按字典序思想生成下一個排列152
4.1.2 按字典序思想生成所有排列154
4.2 排列組合計數的實驗範例156
4.2.1 一般的排列組合計數公式156
4.2.2 兩種特殊的排列組合計數公式167
4.2.3 多重集的排列數和組合數174
4.3 鴿籠原理與容斥原理的實驗範例178
4.3.1 利用鴿籠原理求解存在性問題178
4.3.2 容斥原理應用實驗180
4.3.3 Ramsey定理的應用188
4.4 Pólya計數公式的實驗範例190
4.5 生成函數與遞推關係的實驗範例201
4.5.1 冪級數型生成函數201
4.5.2 指數型生成函數204
4.5.3 遞推關係207
4.6 快速傅里葉變換的實驗範例211
4.7 相關題庫216
第5章貪心法的編程實驗229
5.1 體驗貪心法內涵的實驗範例229
5.1.1 貪心法的經典問題229
5.1.2 體驗貪心法內涵236
5.2 利用數據有序化進行貪心選擇的實驗範例241
5.3 在綜合性的P類問題中使用貪心法的實驗範例249
5.4 相關題庫255
第6章動態規劃方法的編程實驗265
6.1 線性DP的實驗範例266
6.1.1 初步體驗線性DP問題266
6.1.2 子集和問題270
6.1.3 *長公共子序列問題271
6.1.4 *長遞增子序列問題273
6.2 0-1背包問題280
6.2.1 基本的0-1背包問題280
6.2.2 完全背包281
6.2.3 多重背包285
6.2.4 混合背包287
6.2.5 二維背包292
6.2.6 分組背包294
6.2.7 有依賴的背包298
6.3 樹形DP的實驗範例300
6.4 狀態壓縮DP的實驗範例305
6.5 單調優化1D/1D DP的實驗範例309
6.5.1 經典模型1：利用決策代價函數w的單調性優化310
6.5.2 經典模型2：利用決策區間下界的單調性優化313
6.5.3 經典模型3：利用*優決策點的凸性優化318
6.6 相關題庫322
第7章高級數據結構的編程實驗353
7.1 後綴數組的實驗範例353
7.1.1 使用倍增算法計算名次數組和後綴數組353
7.1.2 計算*長公共前綴356
7.1.3 後綴數組的應用357
7.2 線段樹的實驗範例370
7.2.1 線段樹的基本概念和基本操作370
7.2.2 線段樹單點更新的維護372
7.2.3 線段樹子區間更新的維護375
7.3 處理特殊圖的實驗範例387
7.3.1 計算歐拉圖387
7.3.2 計算哈密頓圖393
7.3.3 計算*大獨立集402
7.3.4 計算割點、橋和雙連通分支406
7.4 相關題庫414
第8章計算幾何的編程實驗433
8.1 點線面運算的實驗範例433
8.1.1 計算點積和叉積433
8.1.2 計算線段交440
8.1.3 利用歐拉公式計算多面體449
8.2 利用掃描線算法計算矩形的併的面積的實驗範例453
8.2.1 沿垂直方向計算矩形的並面積453
8.2.2 沿水平方向計算矩形的並面積457
8.3 計算半平面交的實驗範例460
8.3.1 計算半平面交的聯機算法461
8.3.2 利用極角計算半平面交的算法466
8.4 計算凸包和旋轉卡殼的實驗範例474
8.4.1 計算凸包474
8.4.2 旋轉卡殼實驗479
8.5 相關題庫482