寫在最前面的話
　　自從上海交通大學(xué)2002年第一次、2005年第二次獲得ACM國際大學(xué)生程序設(shè)計競賽（ACM International Collegiate Programming Contest，簡稱ACM-ICPC或ICPC）世界冠軍以來，總有記者邀請編者撰寫冠軍之路類的文章，也總有出版社希望編者出版ACM-ICPC競賽類的書籍，因為沒有想清楚怎么寫，所以一直沒動筆。直到2010年上海交通大學(xué)第三次獲得ACM-ICPC世界冠軍后，編者決定出版一套系列叢書，包括《ACM國際大學(xué)生程序設(shè)計競賽：知識與入門》、《ACM國際大學(xué)生程序設(shè)計競賽：算法與實現(xiàn)》、《ACM國際大學(xué)生程序設(shè)計競賽：題目與解讀》及《ACM國際大學(xué)生程序設(shè)計競賽：比賽與思考》4冊書籍，全面、深入而系統(tǒng)地將ACM-ICPC展現(xiàn)給讀者，把上海交通大學(xué)十多年來對ACM-ICPC競賽的感悟分享給讀者。
　　編寫此系列叢書的另一個重要原因是ACM-ICPC競賽在中國大陸的迅猛發(fā)展。自從1996年ACM-ICPC引入中國大陸，前六屆僅設(shè)立1個賽區(qū)，目前每年一般設(shè)立5個賽區(qū)，并已有30所高校承辦過亞洲區(qū)預(yù)賽；參賽學(xué)校從不滿20所，到如今已達200多所；參賽人數(shù)從不到100人，到如今已超過12萬人次；總決賽名額從起初的3個，到如今已超過15個。同時，中國大陸在ACM-ICPC競賽上所取得的成績也舉世矚目。清華大學(xué)9次獲得總決賽獎牌（3金5銀1銅），位居獎牌榜之首，是實力最強、表現(xiàn)最穩(wěn)定的高校；上海交通大學(xué)8次獲得總決賽獎牌（4金3銀1銅），3次奪得世界冠軍，算是目前國內(nèi)成績最好的高校；中山大學(xué)4次獲得總決賽獎牌（2銀2銅），在生源不占優(yōu)勢的情況下，這一成績令人敬佩；復(fù)旦大學(xué)3次獲得總決賽獎牌（1銀2銅），是公認的強校；浙江大學(xué)2次獲得總決賽獎牌（1金1銀），1次奪得世界冠軍，再次讓國人歡欣鼓舞；北京大學(xué)1次獲得總決賽獎牌（1銅），隊員的綜合實力堪稱一流；最難能可貴的是，華南理工大學(xué)也獲得過總決賽的獎牌（1銅），它告訴我們，ACM-ICPC不僅僅是“強�！敝�間的“對話”，只要堅持參與就會斬獲成果。另外，至今已有37所大陸高校參加過全球總決賽，且不論成績?nèi)绾�，他們在賽場上的奮斗亦值得稱道。

　　本系列叢書的第一冊《ACM國際大學(xué)生程序設(shè)計競賽：知識與入門》分為三個部分。知識點部分基本涵蓋了競賽中所涉及的主要知識點，包括數(shù)學(xué)基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、圖論、計算幾何、論題選編、求解策略等六個大類內(nèi)容。入門與進階部分介紹了包括如何快速入門、如何提高自身以及團隊水平等，主要根據(jù)上海交通大學(xué)ACM-ICPC隊多年參賽經(jīng)驗總結(jié)而來。在線資源部分對一些常用的在線評測系統(tǒng)和網(wǎng)上比賽進行了介紹。
　　本系列叢書的第二冊《ACM國際大學(xué)生程序設(shè)計競賽：算法與實現(xiàn)》涵蓋了大部分ACM-ICPC競賽常用的經(jīng)典算法，包括數(shù)學(xué)、圖論、數(shù)據(jù)結(jié)構(gòu)、計算幾何、論題選編五個大類，對每個算法的代碼實現(xiàn)，都配有接口說明以及簡略的算法闡述，并提供算法的完整程序。并收集了一些實用的知識點及積分表，方便讀者查找使用。
　　本系列叢書的第三冊《ACM國際大學(xué)生程序設(shè)計競賽：題目與解讀》分為兩個部分。例題精講部分針對第二冊《ACM國際大學(xué)生程序設(shè)計競賽：算法與實現(xiàn)》中的算法配備經(jīng)典例題，并提供細致的解題思路，讀者可以通過這一部分學(xué)習(xí)和掌握算法；海量題庫部分按照算法分類羅列出大量習(xí)題，并提供相應(yīng)的題解，讀者可以利用這一部分的題目進行訓(xùn)練，更加熟練地運用各類算法。
　　本系列叢書的第四冊《ACM國際大學(xué)生程序設(shè)計競賽：比賽與思考》從120多名隊員、2400余篇文檔中精心挑選、編纂而成的文集，包括訓(xùn)練札記、賽場風(fēng)云、賽季縱橫、冠軍之路、崢嶸歲月，集中展現(xiàn)了上海交通大學(xué)ACM-ICPC隊16年的奮斗歷程，記載了這些隊員為了實現(xiàn)自己的夢想而不懈努力、勇于拼搏的故事。
　　這是一套全面、系統(tǒng)地學(xué)習(xí)ACM-ICPC競賽的知識類書籍；
　　這是一套詳盡、深入地熟悉ACM-ICPC競賽的算法及題目的手冊類書籍；
　　這是一套程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、算法等相關(guān)課程的拓展與提升類書籍；
　　這是一部上海交通大學(xué)ACM-ICPC隊的成長史；
　　這是一部激勵更多學(xué)子勇敢追尋并實現(xiàn)自己最初夢想的勵志書。
　　歷時2年零5個月，終于完成了本系列叢書，編者與隊員有一種如釋重負的感覺，因為我們把出版這套叢書看得很重，這是我們16年的經(jīng)驗與積累，希望對廣大讀者有用。
　　值此ACM-ICPC進入中國大陸16周年、上海交通大學(xué)獲得ACM-ICPC世界冠軍10周年之際，謹以此系列叢書——
　　紀念我們曾經(jīng)走過的路、度過的歲月；
　　獻給所有支持、幫助過我們的人……
　　　　
　　俞 勇
　　2012年10月于上海
　　
　　前 言

　　ACM國際大學(xué)生程序設(shè)計競賽（ACM International Collegiate Programming Contest，簡稱ACM-ICPC或ICPC）的試題覆蓋了計算機科學(xué)以及相關(guān)數(shù)學(xué)領(lǐng)域眾多知識點。這些知識通常會散落在各種書籍和論文之中，學(xué)習(xí)和查找起來相對麻煩。此外，競賽中所考察的內(nèi)容具有一定的特殊性，即使是像由Thomas H. Cormen等編著的Introduction to Algorithms這樣的經(jīng)典書籍，其中介紹的東西也并非都是競賽中的考察點。因此能夠有一本書針對ACM-ICPC競賽所經(jīng)常考察的知識點進行統(tǒng)一的介紹是有必要的。
　　本書分為三個部分，第一部分為入門與進階，第二部分為知識點與求解策略，第三部分為在線資源。第一部分介紹的內(nèi)容包括如何快速入門、如何提高自身以及團隊水平等，主要是編者根據(jù)多年的參賽經(jīng)驗總結(jié)而來。第二部分基本涵蓋了競賽中所涉及的主要知識點，包括數(shù)學(xué)基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、圖論、計算幾何、論題選編、求解策略等6個大類。第三部分對一些常用的在線評測系統(tǒng)和網(wǎng)上比賽進行了介紹。其中，第一部分和第三部分主要針對初學(xué)者。
　　由于ACM-ICPC競賽涉及到的知識點較多，很難在有限的篇幅里做到完全的覆蓋，編者主要根據(jù)重要性和實用性對內(nèi)容進行了篩選。例如，在介紹平衡二叉樹時，一般的數(shù)據(jù)結(jié)構(gòu)書籍往往會介紹AVL樹或是紅黑樹，但本書只介紹了理解和實現(xiàn)起來更為簡單的伸展樹和Treap。
　　本書知識點部分的內(nèi)容采用的是一種類似百科全書的組織方式，所以并不需要一章一章地從前往后閱讀。讀者完全可以選擇一個自己感興趣的知識點進行閱讀，并擴展延伸到與之相關(guān)的其他知識點中。
　　本書編寫工作歷時兩年多，參與編寫工作的人員全部為上海交通大學(xué)ACM-ICPC隊的現(xiàn)役與退役隊員。他們參考了大量的書籍，并結(jié)合了多年的競賽經(jīng)驗，對本書的內(nèi)容進行選擇、撰寫和修改。
　　參與本書寫稿、審稿的人員主要有（按姓氏筆畫為序）：烏辰洋、吳卓杰、張培超、陳彬毅、林承宇、易茜、鄭曌、姜嘯、曹正、曹雪智、商靜波、彭上夫、程宇、譚天。

　　在此，衷心感謝所有為此書出版做出直接或間接貢獻的人！也真心祝愿此書能夠給更多讀者帶來學(xué)習(xí)知識的快樂！
　　由于時間倉促，作者水平有限，疏漏、不當和不足之處在所難免，真誠地希望專家和讀者朋友們不吝賜教。如果您在閱讀和使用此書過程中發(fā)現(xiàn)任何問題或有任何建議，懇請發(fā)郵件，我們將不勝感激。
　　　　
　　編 者
　　2012年10月于上海