寫(xiě)在最前面的話
　　自從上海交通大學(xué)2002年第一次、2005年第二次獲得ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM International Collegiate Programming Contest，簡(jiǎn)稱ACM-ICPC或ICPC）世界冠軍以來(lái)，總有記者邀請(qǐng)編者撰寫(xiě)冠軍之路類的文章，也總有出版社希望編者出版ACM-ICPC競(jìng)賽類的書(shū)籍，因?yàn)闆](méi)有想清楚怎么寫(xiě)，所以一直沒(méi)動(dòng)筆。直到2010年上海交通大學(xué)第三次獲得ACM-ICPC世界冠軍后，編者決定出版一套系列叢書(shū)，包括《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：知識(shí)與入門(mén)》、《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：算法與實(shí)現(xiàn)》、《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：題目與解讀》及《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：比賽與思考》4冊(cè)書(shū)籍，全面、深入而系統(tǒng)地將ACM-ICPC展現(xiàn)給讀者，把上海交通大學(xué)十多年來(lái)對(duì)ACM-ICPC競(jìng)賽的感悟分享給讀者。
　　編寫(xiě)此系列叢書(shū)的另一個(gè)重要原因是ACM-ICPC競(jìng)賽在中國(guó)大陸的迅猛發(fā)展。自從1996年ACM-ICPC引入中國(guó)大陸，前六屆僅設(shè)立1個(gè)賽區(qū)，目前每年一般設(shè)立5個(gè)賽區(qū)，并已有30所高校承辦過(guò)亞洲區(qū)預(yù)賽；參賽學(xué)校從不滿20所，到如今已達(dá)200多所；參賽人數(shù)從不到100人，到如今超過(guò)12萬(wàn)人次；總決賽名額從起初的3個(gè)，到如今已超過(guò)15個(gè)。同時(shí)，中國(guó)大陸在ACM-ICPC競(jìng)賽上所取得的成績(jī)也舉世矚目。清華大學(xué)9次獲得總決賽獎(jiǎng)牌（3金5銀1銅），位居獎(jiǎng)牌榜之首，是實(shí)力最強(qiáng)、表現(xiàn)最穩(wěn)定的高校；上海交通大學(xué)8次獲得總決賽獎(jiǎng)牌（4金3銀1銅），3次奪得世界冠軍，算是目前國(guó)內(nèi)成績(jī)最好的高校；中山大學(xué)4次獲得總決賽獎(jiǎng)牌（2銀2銅），在生源不占優(yōu)勢(shì)的情況下，這一成績(jī)令人敬佩；復(fù)旦大學(xué)3次獲得總決賽獎(jiǎng)牌（1銀2銅），是公認(rèn)的強(qiáng)校；浙江大學(xué)2次獲得總決賽獎(jiǎng)牌（1金1銀），1次奪得世界冠軍，再次讓國(guó)人歡欣鼓舞；北京大學(xué)1次獲得總決賽獎(jiǎng)牌（1銅），隊(duì)員的綜合實(shí)力堪稱一流；最難能可貴的是，華南理工大學(xué)也獲得過(guò)總決賽的獎(jiǎng)牌（1銅），它告訴我們，ACM-ICPC不僅僅是“強(qiáng)�！敝�間的“對(duì)話”，只要堅(jiān)持參與就會(huì)斬獲成果。另外，至今已有37所大陸高校參加過(guò)全球總決賽，且不論成績(jī)?nèi)绾�，他們�(cè)谫悎?chǎng)上的奮斗亦值得稱道。
　　本系列叢書(shū)的第一冊(cè)《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：知識(shí)與入門(mén)》分為三個(gè)部分。知識(shí)點(diǎn)部分基本涵蓋了競(jìng)賽中所涉及的主要知識(shí)點(diǎn)，包括數(shù)學(xué)基礎(chǔ)、數(shù)據(jù)結(jié)構(gòu)、圖論、計(jì)算幾何、論題選編、求解策略等六個(gè)大類內(nèi)容。入門(mén)與進(jìn)階部分介紹了包括如何快速入門(mén)、如何提高自身以及團(tuán)隊(duì)水平等，主要根據(jù)上海交通大學(xué)ACM-ICPC隊(duì)多年參賽經(jīng)驗(yàn)總結(jié)而來(lái)。在線資源部分對(duì)一些常用的在線評(píng)測(cè)系統(tǒng)和網(wǎng)上比賽進(jìn)行了介紹。
　　本系列叢書(shū)的第二冊(cè)《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：算法與實(shí)現(xiàn)》涵蓋了大部分ACM-ICPC競(jìng)賽常用的經(jīng)典算法，包括數(shù)學(xué)、圖論、數(shù)據(jù)結(jié)構(gòu)、計(jì)算幾何、論題選編五個(gè)大類，對(duì)每個(gè)算法的代碼實(shí)現(xiàn)，都配有接口說(shuō)明以及簡(jiǎn)略的算法闡述，并提供算法的完整程序，貼士部分收集了一些實(shí)用的知識(shí)點(diǎn)及積分表，方便讀者查找使用。
　　本系列叢書(shū)的第三冊(cè)《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：題目與解讀》分為兩個(gè)部分。例題精講部分針對(duì)第二冊(cè)《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：算法與實(shí)現(xiàn)》中的算法配備經(jīng)典例題，并提供細(xì)致的解題思路，讀者可以通過(guò)這一部分學(xué)習(xí)和掌握算法；海量題庫(kù)部分按照算法分類羅列出大量習(xí)題，并提供相應(yīng)的題解，讀者可以利用這一部分的題目進(jìn)行訓(xùn)練，更加熟練地運(yùn)用各類算法。
　　本系列叢書(shū)的第四冊(cè)《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：?比賽與思考》從120多名隊(duì)員、2400余篇文檔中精心挑選、編纂而成的文集，包括訓(xùn)練札記、賽場(chǎng)風(fēng)云、賽季縱橫、冠軍之路、崢嶸歲月，集中展現(xiàn)了上海交通大學(xué)ACM-ICPC隊(duì)16年的奮斗歷程，記載了這些隊(duì)員為了實(shí)現(xiàn)自己的夢(mèng)想而不懈努力、勇于拼搏的故事。
　　這是一套全面、系統(tǒng)地學(xué)習(xí)ACM-ICPC競(jìng)賽的知識(shí)類書(shū)籍；
　　這是一套詳盡、深入地熟悉ACM-ICPC競(jìng)賽的算法及題目的手冊(cè)類書(shū)籍；
　　這是一套程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法等相關(guān)課程的拓展與提升類書(shū)籍；
　　這是一部上海交通大學(xué)ACM-ICPC隊(duì)的成長(zhǎng)史；
　　這是一部激勵(lì)更多學(xué)子勇敢追尋并實(shí)現(xiàn)自己最初夢(mèng)想的勵(lì)志書(shū)。
　　歷時(shí)2年零5個(gè)月，終于完成了本系列叢書(shū)，編者與隊(duì)員有一種如釋重負(fù)的感覺(jué)，因?yàn)槲覀儼殉霭孢@套叢書(shū)看得很重，這是我們16年的經(jīng)驗(yàn)與積累，希望對(duì)廣大讀者有用。
　　值此ACM-ICPC進(jìn)入中國(guó)大陸16周年、上海交通大學(xué)獲得ACM-ICPC世界冠軍10周年之際，謹(jǐn)以此系列叢書(shū)——
　　紀(jì)念我們?cè)��?jīng)走過(guò)的路、度過(guò)的歲月；
　　獻(xiàn)給所有支持、幫助過(guò)我們的人……
　　
　　
　　俞 勇　
　　2012年10月于上海

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