　　本係列含有《ACM國際大學生程序設計競賽：知識與入門》、《ACM國際大學生程序設計競賽：算法與實現》、《ACM國際大學生程序設計競賽：題目與解讀》等3冊。
　　《ACM國際大學生程序設計競賽：知識與入門》介紹瞭ACM-ICPC的知識及其分類、進階與角色、在綫評測係統；
　　《ACM國際大學生程序設計競賽：算法與實現》介紹瞭ACM-ICPC算法分類、實現及索引；
　　《ACM國際大學生程序設計競賽：題目與解讀》為各類算法配備經典例題及題庫，並提供解題思路；

內容簡介

　　ACM國際大學生程序設計競賽（ACM-ICPC）是國際上公認的水平zui高、規模zui大、影響zui深的計算機專業競賽，目前全球參與人數達20多萬。《ACM國際大學生程序設計競賽（ACM-ICPC）係列叢書·ACM國際大學生程序設計競賽：算法與實現》作者將76年的教練經驗與積纍撰寫成本係列叢書，全麵、深入而係統地將ACM-ICPC展現給讀者。本係列叢書包括《ACM國際大學生程序設計競賽：知識與入門》、《ACM國際大學生程序設計競賽：算法與實現》、《ACM國際大學生程序設計競賽：題目與解讀》、《ACM國際大學生程序設計競賽：比賽與思考》等4冊，其中《ACM國際大學生程序設計競賽：知識與入門》介紹瞭ACM-ICPC的知識及其分類、進階與角色、在綫評測係統；《ACM國際大學生程序設計競賽：算法與實現》介紹瞭ACM-ICPC算法分類、實現及索引；《ACM國際大學生程序設計競賽：題目與解讀》為各類算法配備經典例題及題庫，並提供解題思路；《ACM國際大學生程序設計競賽：比賽與思考》介紹瞭上海交通大學ACM-ICPC的訓練及比賽，包括訓練劄記、賽場風雲、賽季縱橫、冠軍之路、崢嶸歲月。
　　《ACM國際大學生程序設計競賽（ACM-ICPC）係列叢書·ACM國際大學生程序設計競賽：算法與實現》適用於參加ACM國際大學生程序設計競賽的本科生和研究生，對參加青少年信息學奧林匹剋競賽的中學生也很有指導價值。同時，作為程序設計、數據結構、算法等相關課程的拓展與提升，本叢書也是難得的教學輔助讀物。

作者簡介

　　俞勇，1961年生於上海，現為上海交通大學教授、博士生導師。1986年畢業於華東師範大學計算機科學係，獲碩士學位。畢業後在上海交通大學任教至今。1996年至今擔任上海交通大學ACM國際大學生程序設計競賽領隊、主教練，3次率隊奪得ACM國際大學生程序設計競賽世界冠軍，上海交通大學成為該賽事亞洲第一個獲得冠軍、全球第三個“三冠王”的大學，2002、2012年相繼獲得“傑齣教練奬”、“功勛教練奬”。
　　俞勇教授曾主編教材或著作4本、譯著3本，先後主持教育部教育教學改革項目2項，獲得國傢ji和上海市教學成果奬7項，上海市優秀教材奬2項，並為國傢精品課程“數據結構”、上海市“程序設計類基礎課程教學團隊”主持人。從事Web搜索與挖掘研究，先後主持國傢自然科學基金、863計劃等十餘項，發錶重要國際會議和期刊學術論文百餘篇。
　　俞勇教授曾獲得國務院特殊津貼、“全國師德標兵”、“寶鋼優秀教師特等奬”、“上海市教學名師”、“上海市五一勞動奬章”、“上海市模範教師”、“上海交通大學校長奬”、“上海交通大學zui受學生歡迎教師”、“上海交通大學zui受研究生歡迎導師”等榮譽。曾被中央電視颱新聞聯播、上海教育颱、光明日報、文匯報等十多傢媒體報道。

內頁插圖

第一部分算法
第1章數學
1.1 矩陣
1.1.1 矩陣類
1.1.2 Gauss消元
1.1.3 矩陣的逆
1.1.4 常係數綫性齊次遞推
1.2 整除與剩餘
1.2.1 歐幾裏得算法
1.2.2 擴展歐幾裏得
1.2.3 單變元模綫性方程
1.2.4 中國剩餘定理
1.2.5 求原根
1.2.6 平方剩餘
1.2.7 離散對數
1.2.8 N次剩餘
1.3 素數與函數
1.3.1 素數篩法
1.3.2 素數判定
1.3.3 質因數分解
1.3.4 歐拉函數計算
1.3.5 Mobius函數計算
1.4 數值計算
1.4.1 數值積分
1.4.2 高階代數方程求根
1.5 其他
1.5.1 快速冪
1.5.2 進製轉換
1.5.3 格雷碼
1.5.4 高精度整數
1.5.5 快速傅立葉變換
1.5.6 分數類
1.5.7 全排列散列
第2章圖論
2.1 圖的遍曆及連通性
2.1.1 前嚮星
2.1.2 割點和橋
2.1.3 雙連通分量
2.1.4 極大強連通分量Tarjan算法
2.1.5 拓撲排序
2.1.6 2SAT
2.2 路徑
2.2.1 Dijkstra
2.2.2 SPFA
2.2.3 Floyd-Warshall
2.2.4 無環圖最短路
2.2.5 第k短路
2.2.6 歐拉迴路
2.2.7 混閤圖歐拉迴路
2.3 匹配
2.3.1 匈牙利算法
2.3.2 Hopcroft-Karp算法
2.3.3 KM算法
2.3.4 一般圖最大匹配
2.4 樹
2.4.1 LCA
2.4.2 最小生成樹Prim算法
2.4.3 最小生成樹Kruskal算法
2.4.4 單度限製最小生成樹
2.4.5 最小樹形圖
2.4.6 最優比例生成樹
2.4.7 樹的直徑
2.5 網絡流
2.5.1 最大流Dinic算法
2.5.2 最小割
2.5.3 無嚮圖最小割
2.5.4 有上下界的網絡流
2.5.5 費用流
2.6 其他
2.6.1 完美消除序列
2.6.2 弦圖判定
2.6.3 最大團搜索算法
2.6.4 極大團的計數
2.6.5 圖的同構
2.6.6 樹的同構
第3章計算幾何
3.1 多邊形
3.1.1 計算幾何誤差修正
3.1.2 計算幾何點類
3.1.3 計算幾何綫段類
3.1.4 多邊形類
3.1.5 多邊形的重心
3.1.6 多邊形內格點數
3.1.7 凸多邊形類
3.1.8 凸多邊形的直徑
3.1.9 半平麵切割多邊形
3.1.10 半平麵交
3.1.11 凸多邊形交
3.1.12 多邊形的核
3.1.13 凸多邊形與直綫集交
3.2 圓
3.2.1 圓與綫求交
3.2.2 圓與多邊形交的麵積
3.2.3 最小圓覆蓋
3.2.4 圓與圓求交
3.2.5 圓的離散化
3.2.6 圓的麵積並
3.3 三維計算幾何
3.3.1 三維點類
3.3.2 三維直綫類
3.3.3 三維平麵類
3.3.4 三維嚮量鏇轉
3.3.5 長方體錶麵兩點最短距離
3.3.6 四麵體體積
3.3.7 最小球覆蓋
3.3.8 三維凸包
3.4 其他
3.4.1 三角形的四心
3.4.2 最近點對
3.4.3 平麵最小曼哈頓距離生成樹
3.4.4 最大空凸包
3.4.5 平麵劃分
第4章數據結構
4.1 二叉堆
4.2 並查集
4.3 樹狀數組
4.4 左偏樹
4.5 Tne
4.6 Treap
4.7 伸展樹
4.8 RMQ綫段樹
4.9 ST錶
4.10 動態樹
4.11 塊狀鏈錶
4.12 樹鏈剖分
第5章論題選編
5.1 字符串
5.1.1 KMP
5.1.2 擴展KMP
5.1.3 串的最小錶示
……
第二部分貼士

前言/序言

　　在ACM國際大學生程序設計競賽（ACM International Collegiate Programming Contest，ACM-ICPC或ICPC）中，實現算法的能力是非常重要的。尤其是對新手來說，在瞭解到一個新的算法後，有時會對如何實現該算法産生睏惑，也許並不能一下想到很好的實現，這時就需要參考一些已有的實現。
　　另外，ACM-ICPC比賽中允許選手將一定量的（一般為25頁）紙質資料帶入比賽現場進行參考。隊伍往往會將一些相對較難實現的常用算法的代碼整理為SCL（Standard Code Library，標準代碼庫）帶入賽場，在需要的時候可以直接抄寫已有代碼，既節省時間，也保證瞭正確性。
　　因此我們齣版這本收集瞭大量經典常用算法的用C++語言實現的代碼庫，希望可以幫助讀者學習算法以及準備比賽用的SCL。
　　本書分為兩個部分。第一部分為代碼庫，涵蓋瞭大部分比賽常用的經典算法，包括數學、圖論、數據結構、計算幾何、論題選編五個大類，對每個算法的代碼實現，都配有接口說明以及簡略的算法闡述，便於讀者理解。第二部分為貼士，收集瞭一些實用的知識點以及積分錶，適閤於帶入賽場進行參考。
　　本書編寫工作曆時兩年左右，參與編寫工作的人員全部為上海交通大學ACM-ICPC隊的現役隊員。代碼大多來自於往年上海交通大學ACM-ICPC隊使用的SCL以及隊員的日常訓練。同時，本書的編寫也得到上海交通大學ACM-ICPC隊的退役隊員大力幫助，他們參與瞭代碼庫的收集、整理、校驗等工作。
　　參與本書寫稿、審稿的人員主要有（按姓氏筆畫為序）：?尹天蛟，烏辰洋，任春旭，劉奇，劉彥，壽鶴鳴，李說，楊思逸，吳卓傑，張捷鈞，陳明騁，陳澤佳，陳彬毅，陳爽，林承宇，金斌，鄭，鬍張廣達，郭曉旭，曹雪智，康南茜，章雍哲，商靜波，彭上夫，譚天，繆沛晗，瞿鈞等。
　　在此，衷心感謝所有為此書齣版做齣直接或間接貢獻的人！也真心祝願此書能夠在算法實現和SCL的準備上給讀者帶來幫助。
　　由於時間倉促，作者水平有限，疏漏、不當和不足之處在所難免，真誠地希望專傢和讀者朋友們不吝賜教。如果您能在閱讀和使用此書過程中發現任何問題或有任何建議，懇請發郵件，我們將不勝感激。
　　編者
　　2012年10月於上海

ACM國際大學生程序設計競賽（ACM-ICPC）係列叢書·ACM國際大學生程序設計競賽：算法與實現下載 mobi epub pdf txt 電子書格式