ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽

前言

寫(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)?！敝g的“對(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月于上海

內(nèi)容概要

　　ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM-ICPC）是國(guó)際上公認(rèn)的水平最高、規(guī)模最大、影響最深的計(jì)算機(jī)專業(yè)競(jìng)賽，目前全球參與人數(shù)達(dá)20多萬(wàn)?！禔CM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM-ICPC）系列叢書(shū)·ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：算法與實(shí)現(xiàn)》作者將76年的教練經(jīng)驗(yàn)與積累撰寫(xiě)成本系列叢書(shū)，全面、深入而系統(tǒng)地將ACM-ICPC展現(xiàn)給讀者。本系列叢書(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è)，其中《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：知識(shí)與入門(mén)》介紹了ACM-ICPC的知識(shí)及其分類、進(jìn)階與角色、在線評(píng)測(cè)系統(tǒng)；《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：算法與實(shí)現(xiàn)》介紹了ACM-ICPC算法分類、實(shí)現(xiàn)及索引；《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：題目與解讀》為各類算法配備經(jīng)典例題及題庫(kù)，并提供解題思路；《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：比賽與思考》介紹了上海交通大學(xué)ACM-ICPC的訓(xùn)練及比賽，包括訓(xùn)練札記、賽場(chǎng)風(fēng)云、賽季縱橫、冠軍之路、崢嶸歲月。
　　《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM-ICPC）系列叢書(shū)·ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽：算法與實(shí)現(xiàn)》適用于參加ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的本科生和研究生，對(duì)參加青少年信息學(xué)奧林匹克競(jìng)賽的中學(xué)生也很有指導(dǎo)價(jià)值。同時(shí)，作為程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法等相關(guān)課程的拓展與提升，本叢書(shū)也是難得的教學(xué)輔助讀物。

作者簡(jiǎn)介

　　俞勇，1961年生于上海，現(xiàn)為上海交通大學(xué)教授、博士生導(dǎo)師。1986年畢業(yè)于華東師范大學(xué)計(jì)算機(jī)科學(xué)系，獲碩士學(xué)位。畢業(yè)后在上海交通大學(xué)任教至今。1996年至今擔(dān)任上海交通大學(xué)ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽領(lǐng)隊(duì)、主教練，3次率隊(duì)奪得ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽世界冠軍，上海交通大學(xué)成為該賽事亞洲第一個(gè)獲得冠軍、全球第三個(gè)“三冠王”的大學(xué)，2002、2012年相繼獲得“杰出教練獎(jiǎng)”、“功勛教練獎(jiǎng)”。
　　俞勇教授曾主編教材或著作4本、譯著3本，先后主持教育部教育教學(xué)改革項(xiàng)目2項(xiàng)，獲得國(guó)家級(jí)和上海市教學(xué)成果獎(jiǎng)7項(xiàng)，上海市優(yōu)秀教材獎(jiǎng)2項(xiàng)，并為國(guó)家精品課程“數(shù)據(jù)結(jié)構(gòu)”、上海市“程序設(shè)計(jì)類基礎(chǔ)課程教學(xué)團(tuán)隊(duì)”主持人。從事Web搜索與挖掘研究，先后主持國(guó)家自然科學(xué)基金、863計(jì)劃等十余項(xiàng)，發(fā)表重要國(guó)際會(huì)議和期刊學(xué)術(shù)論文百余篇。
　　俞勇教授曾獲得國(guó)務(wù)院特殊津貼、“全國(guó)師德標(biāo)兵”、“寶鋼優(yōu)秀教師特等獎(jiǎng)”、“上海市教學(xué)名師”、“上海市五一勞動(dòng)獎(jiǎng)?wù)隆?、“上海市模范教師”、“上海交通大學(xué)校長(zhǎng)獎(jiǎng)”、“上海交通大學(xué)最受學(xué)生歡迎教師”、“上海交通大學(xué)最受研究生歡迎導(dǎo)師”等榮譽(yù)。曾被中央電視臺(tái)新聞聯(lián)播、上海教育臺(tái)、光明日?qǐng)?bào)、文匯報(bào)等十多家媒體報(bào)道。

書(shū)籍目錄

第一部分 算法
第1章 數(shù)學(xué)
1.1 矩陣
1.1.1 矩陣類
1.1.2 Gauss消元
1.1.3 矩陣的逆
1.1.4 常系數(shù)線性齊次遞推
1.2 整除與剩余
1.2.1 歐幾里得算法
1.2.2 擴(kuò)展歐幾里得
1.2.3 單變?cè)＞€性方程
1.2.4 中國(guó)剩余定理
1.2.5 求原根
1.2.6 平方剩余
1.2.7 離散對(duì)數(shù)
1.2.8 N次剩余
1.3 素?cái)?shù)與函數(shù)
1.3.1 素?cái)?shù)篩法
1.3.2 素?cái)?shù)判定
1.3.3 質(zhì)因數(shù)分解
1.3.4 歐拉函數(shù)計(jì)算
1.3.5 Mobius函數(shù)計(jì)算
1.4 數(shù)值計(jì)算
1.4.1 數(shù)值積分
1.4.2 高階代數(shù)方程求根
1.5 其他
1.5.1 快速冪
1.5.2 進(jìn)制轉(zhuǎn)換
1.5.3 格雷碼
1.5.4 高精度整數(shù)
1.5.5 快速傅立葉變換
1.5.6 分?jǐn)?shù)類
1.5.7 全排列散列
第2章 圖論
2.1 圖的遍歷及連通性
2.1.1 前向星
2.1.2 割點(diǎn)和橋
2.1.3 雙連通分量
2.1.4 極大強(qiáng)連通分量Tarjan算法
2.1.5 拓?fù)渑判?br />2.1.6 2SAT
2.2 路徑
2.2.1 Dijkstra
2.2.2 SPFA
2.2.3 Floyd-Warshall
2.2.4 無(wú)環(huán)圖最短路
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 樹(shù)
2.4.1 LCA
2.4.2 最小生成樹(shù)Prim算法
2.4.3 最小生成樹(shù)Kruskal算法
2.4.4 單度限制最小生成樹(shù)
2.4.5 最小樹(shù)形圖
2.4.6 最優(yōu)比例生成樹(shù)
2.4.7 樹(shù)的直徑
2.5 網(wǎng)絡(luò)流
2.5.1 最大流Dinic算法
2.5.2 最小割
2.5.3 無(wú)向圖最小割
2.5.4 有上下界的網(wǎng)絡(luò)流
2.5.5 費(fèi)用流
2.6 其他
2.6.1 完美消除序列
2.6.2 弦圖判定
2.6.3 最大團(tuán)搜索算法
2.6.4 極大團(tuán)的計(jì)數(shù)
2.6.5 圖的同構(gòu)
2.6.6 樹(shù)的同構(gòu)
第3章 計(jì)算幾何
3.1 多邊形
3.1.1 計(jì)算幾何誤差修正
3.1.2 計(jì)算幾何點(diǎn)類
3.1.3 計(jì)算幾何線段類
3.1.4 多邊形類
3.1.5 多邊形的重心
3.1.6 多邊形內(nèi)格點(diǎn)數(shù)
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 三維計(jì)算幾何
3.3.1 三維點(diǎn)類
3.3.2 三維直線類
3.3.3 三維平面類
3.3.4 三維向量旋轉(zhuǎn)
3.3.5 長(zhǎng)方體表面兩點(diǎn)最短距離
3.3.6 四面體體積
3.3.7 最小球覆蓋
3.3.8 三維凸包
3.4 其他
3.4.1 三角形的四心
3.4.2 最近點(diǎn)對(duì)
3.4.3 平面最小曼哈頓距離生成樹(shù)
3.4.4 最大空凸包
3.4.5 平面劃分
第4章 數(shù)據(jù)結(jié)構(gòu)
4.1 二叉堆
4.2 并查集
4.3 樹(shù)狀數(shù)組
4.4 左偏樹(shù)
4.5 Tne
4.6 Treap
4.7 伸展樹(shù)
4.8 RMQ線段樹(shù)
4.9 ST表
4.10 動(dòng)態(tài)樹(shù)
4.11 塊狀鏈表
4.12 樹(shù)鏈剖分
第5章 論題選編
5.1 字符串
5.1.1 KMP
5.1.2 擴(kuò)展KMP
5.1.3 串的最小表示
……
第二部分 貼士

章節(jié)摘錄

版權(quán)頁(yè)：   插圖：   【注釋】 常數(shù)中，maxn為圓的個(gè)數(shù)，maxN為所有事件點(diǎn)的個(gè)數(shù)。 另外，新增了圓類Tcir和中間過(guò)程所需的區(qū)問(wèn)類Tinterval。 【使用范例】 參見(jiàn)程序SPOJ VCIRCLE.CPP。 3.2.6圓的面積并 【任務(wù)】 給定n個(gè)圓，求它們的面積并。 【說(shuō)明】 如圖所示，將圓的面積剖分成若干個(gè)多邊形的面積與若干個(gè)弓形的面積。多邊形的邊就是圓的交點(diǎn)構(gòu)成的不被其他圓覆蓋的弦。計(jì)算有向面積的話，可以看到中間“洞”的面積恰好被順時(shí)針的多邊形包圍，因此會(huì)被減去。請(qǐng)注意，必須去除重復(fù)的圓，否則答案會(huì)有重復(fù)計(jì)算的面積。

編輯推薦

《ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽(ACM-ICPC)系列叢書(shū):ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽:算法與實(shí)現(xiàn)》適用于參加ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽的本科生和研究生，對(duì)參加青少年信息學(xué)奧林匹克競(jìng)賽的中學(xué)生也很有指導(dǎo)價(jià)值。

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

    ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽 PDF格式下載

---