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

前言

ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM International Collegiate Programming Contest，簡(jiǎn)稱ACM/ICPC）是由國(guó)際計(jì)算機(jī)界歷史悠久、頗具權(quán)威性的組織ACM學(xué)會(huì)（Association for Computer Machinery）主辦的，是世界上公認(rèn)的規(guī)模最大、水平最高的國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽，其目的旨在使大學(xué)生運(yùn)用計(jì)算機(jī)來充分展示自己分析問題和解決問題的能力。該項(xiàng)競(jìng)賽從1970年舉辦至今已歷32屆，因歷屆競(jìng)賽都薈萃了世界各大洲的精英，云集了計(jì)算機(jī)界的“希望之星”，而受到國(guó)際各知名大學(xué)的重視，并受到全世界各著名IT企業(yè)的高度關(guān)注，成為世界各國(guó)大學(xué)生最具影響力的國(guó)際級(jí)計(jì)算機(jī)類的賽事。ACM所頒發(fā)的獲獎(jiǎng)證書也為世界各知名大學(xué)、各著名IT企業(yè)所認(rèn)可。該項(xiàng)競(jìng)賽分為區(qū)域預(yù)賽和世界決賽兩個(gè)階段進(jìn)行，各預(yù)賽區(qū)第一名自動(dòng)獲得參加世界決賽的資格，世界決賽安排在每年的3-4月舉行，而區(qū)域預(yù)賽安排在上一年的9-12月在各大洲舉行。ACM/ICPC的區(qū)域預(yù)賽是規(guī)模很大、范圍很廣的賽事。以2009年為例，全世界有82個(gè)國(guó)家和地區(qū)、1931所大學(xué)、7319支參賽隊(duì)在六大洲的37個(gè)賽站中爭(zhēng)奪世界決賽的103個(gè)名額，其激烈程度可想而知。與其他編程競(jìng)賽相比，ACM/ICPC題目難度更大，更強(qiáng)調(diào)算法的高效性，不僅要解決一個(gè)指定的命題，而且必須以最佳的方式解決指定的命題。它涉及的知識(shí)面廣，與大學(xué)計(jì)算機(jī)系本科及研究生的課程直接關(guān)聯(lián)，如程序設(shè)計(jì)、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、人工智能、算法分析與設(shè)計(jì)等課程；對(duì)數(shù)學(xué)要求更高；由于采用英文命題，對(duì)英語(yǔ)要求較高；ACM/ICPC采用3人合作、公用一臺(tái)電腦，所以它更強(qiáng)調(diào)團(tuán)隊(duì)協(xié)作精神；由于許多題目并無現(xiàn)成的算法，需要具備創(chuàng)新的精神，ACM/ICPC不僅強(qiáng)調(diào)學(xué)科的基礎(chǔ)，更強(qiáng)調(diào)全面素質(zhì)和能力的培養(yǎng)；由于ACM/ICPC是采用5小時(shí)全封閉式競(jìng)賽，參賽隊(duì)員與外界完全隔離，獨(dú)立完成，是參賽隊(duì)員實(shí)際能力的真實(shí)表露，其成績(jī)可信度甚高。ACM/ICPC又是一種“開卷考試”，可以帶任何書籍、資料甚至源程序代碼清單（但不能帶電子媒體），不需要死背算法，而強(qiáng)調(diào)的是算法的靈活運(yùn)用；與其他計(jì)算機(jī)競(jìng)賽（如軟件設(shè)計(jì)，網(wǎng)站設(shè)計(jì)等）相比，ACM/ICPC有嚴(yán)謹(jǐn)而客觀的評(píng)判規(guī)則（嚴(yán)格的數(shù)據(jù)測(cè)試），排除了因評(píng)委的主觀因素而造成評(píng)審不公平的現(xiàn)象，所以，ACM/ICPC對(duì)成績(jī)的爭(zhēng)議較少。中山大學(xué)自1997年首次參加ACM/ICPC亞洲區(qū)預(yù)賽以來的13年中，每年都派出多支隊(duì)共參加過52次亞洲區(qū)預(yù)賽，成績(jī)有45次排在前6名，6次排在前10名，1次排在前12名；其中有25次進(jìn)入三甲，奪得5次冠軍（1999年臺(tái)北，2002、2003年高雄，2007年峴港，2009年合肥）、9次亞軍（2000年香港、筑波，2003年北京、廣州，2006年河內(nèi)，2007年首爾，2008年雅加達(dá)、首爾，2009年寧波）、11次季軍（1998-2000年上海、2001年達(dá)卡、2002年北京，2003年高雄，2004年馬尼拉，2005年臺(tái)北、北京，2006年首爾，2007年成都）；中山大學(xué)的參賽隊(duì)11次進(jìn)入全球總決賽（1999-2001年、2003-2008年）：2000年在美國(guó)佛羅里達(dá)州奧蘭多市舉行的第24屆全球總決賽中取得了第11名的好成績(jī)；2001年在加拿大溫哥華市舉行的第25屆全球總決賽中首獲銅牌（世界第14名）；2003年在美國(guó)洛杉磯市好萊塢舉行的第27屆全球總決賽中取得世界第8名并首獲銀牌的好成績(jī)，躋身世界八強(qiáng)之列；2004年在捷克布拉格市舉行的第28屆全球總決賽中獲得世界第11名并再獲銅牌，且在中國(guó)內(nèi)地高校中排名第一；2005年在上海市舉行的第29屆全球總決賽中獲得世界第17名；2006年在美國(guó)得克薩斯州圣安東尼奧市舉行的第30屆全球總決賽中獲得世界第19名；2007年在日本東京市舉行的第31屆全球總決賽中獲得世界第26名；2008年在加拿大班夫市舉行的第32屆全球總決賽中獲得世界第23名；2009年在瑞典斯德哥爾摩市舉行的第33屆全球總決賽中獲得世界第20名；并取得將在2010年舉行的第34屆全球總決賽的參賽資格。為了幫助高等院校的大學(xué)生們備戰(zhàn)國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽，幫助他們提高程序設(shè)計(jì)水平和培養(yǎng)更強(qiáng)的分析問題與解決問題的能力，我們編寫了這套《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解》。本書是這套《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解》的第七冊(cè)，編程所用的語(yǔ)言版本是MicrosoftVisualC++6.0。全書共分10章，本書收錄了2005-2006年中山大學(xué)ICPC集訓(xùn)隊(duì)內(nèi)部選拔賽的全部試題、完整的測(cè)試數(shù)據(jù)和答案。為了方便讀者學(xué)習(xí)，本書對(duì)每個(gè)題目作了詳盡的題目分析，并詳細(xì)地講解其算法實(shí)現(xiàn)的原理，同時(shí)提供了完善的參考程序及其程序分析，供讀者參考。書中提供了基本測(cè)試數(shù)據(jù)，以方便讀者測(cè)試自行完成上述題目的結(jié)果。隨書附帶的光盤中存放所有例題中完整的測(cè)試數(shù)據(jù)，以便于有更多需求的同學(xué)能利用規(guī)模更大的測(cè)試數(shù)據(jù)進(jìn)行訓(xùn)練和學(xué)習(xí)。參與上述競(jìng)賽命題的有：蔡文志、黎俊瑜、莫瑜、關(guān)沛勇、林祺穎、梁鋒等，他們均為碩士碩士研究生，都是參加過世界決賽或亞洲多個(gè)賽站區(qū)域預(yù)賽并取得很好成績(jī)的中山大學(xué)隊(duì)的主力隊(duì)員。讀者從附錄A中可以看到，中山大學(xué)ACM/ICPC隊(duì)13年來取得不俗的成績(jī)。究其原因，除了有完善的選拔機(jī)制外，集訓(xùn)隊(duì)內(nèi)部個(gè)人選拔賽（俗稱“4+2”）的作用也是十分重要的。本書再次公開了中山大學(xué)ICPC集訓(xùn)隊(duì)內(nèi)部選拔賽的題目和題解，以便加強(qiáng)與讀者的交流。在附錄B中，介紹了中山大學(xué)集訓(xùn)隊(duì)選拔流程。不難看出，集訓(xùn)隊(duì)是面向全校的，一年內(nèi)每個(gè)同學(xué)都有多次機(jī)會(huì)參加集訓(xùn)隊(duì)選拔，從而在校園里形成良好的學(xué)術(shù)氛圍，這也是中山大學(xué)開展ICPC的活動(dòng)成功的秘決。

內(nèi)容概要

本書收錄了2005-2006年中山大學(xué)ICPC集訓(xùn)隊(duì)內(nèi)部選拔賽的全部試題、完整的測(cè)試數(shù)據(jù)和答案。為了方便讀者學(xué)習(xí)，本書對(duì)每個(gè)題目做了詳盡的題目分析并詳細(xì)地講解其算法實(shí)現(xiàn)的原理，同時(shí)提供了完善的標(biāo)準(zhǔn)程序及其程序分析。書中提供了基本測(cè)試數(shù)據(jù)，便于讀者測(cè)試自行完成上述題目的結(jié)果。隨書附帶的光盤存放所有例題完整的測(cè)試數(shù)據(jù)，便于有更多需求的同學(xué)利用規(guī)模更大的測(cè)試數(shù)據(jù)進(jìn)行訓(xùn)練和學(xué)習(xí)。　　本書所提供的題目都是原創(chuàng)題，題目構(gòu)思新穎，內(nèi)容有趣。所涉及的算法知識(shí)面廣，基本上覆蓋大學(xué)計(jì)算機(jī)類本科專業(yè)的所學(xué)到的基本算法?！　”緯梢宰鳛楦叩仍盒４髮W(xué)生和研究生準(zhǔn)備參加各級(jí)國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽活動(dòng)的輔導(dǎo)教材和訓(xùn)練題集，也可以作為高等院校研究生和本科高年級(jí)學(xué)生學(xué)習(xí)相關(guān)課程的參考書，同時(shí)還可以作為中學(xué)省級(jí)及以上信息學(xué)奧林匹克優(yōu)秀選手備戰(zhàn)高層次程序設(shè)計(jì)競(jìng)賽的參考用書。

書籍目錄

本書試題涉及知識(shí)點(diǎn)的說明 第1章　2005年中山大學(xué)內(nèi)部選拔賽第一試試題分析　1.1　原子核研究 　　1.1.1　試題 　　1.1.2　題目分析與算法實(shí)現(xiàn) 　　1.1.3　參考程序與程序分析 　　1.1.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　1.2　腦力游戲 　　1.2.1　試題 　　1.2.2　題目分析與算法實(shí)現(xiàn) 　　1.2.3　參考程序與程序分析 　　1.2.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　1.3　循環(huán)序列 　　1.3.1　題 　　1.3.2　題目分析與算法實(shí)現(xiàn) 　　1.3.3　參考程序與程序分析 　　1.3.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　1.4　舞王之王 　　1.4.1　試題 　　1.4.2　題目分析與算法實(shí)現(xiàn) 　　1.4.3　參考程序與程序分析 　　1.4.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　1.5　Torus大逃亡 　　1.5.1　試題 　　1.5.2　題目分析與算法實(shí)現(xiàn) 　　1.5.3　參考程序與程序分析 　　1.5.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 第2章　2005年中山大學(xué)內(nèi)部選拔賽第二試試題分析　2.1　主題醫(yī)院 　　2.1.1　試題 　　2.1.2　題目分析與算法實(shí)現(xiàn) 　　2.1.3　參考程序與程序分析 　　2.1.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　2.2　帶分?jǐn)?shù)問題 　　2.2.1　試題 　　2.2.2　題目分析與算法實(shí)現(xiàn) 　　2.2.3　參考程序與程序分析　　2.2.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　2.3　三角形 　　2.3.1　試題 　　2.3.2　題目分析與算法實(shí)現(xiàn) 　　2.3.3　參考程序與程序分析 　　2.3.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　2.4　布料相交 　　2.4.1　試題 　　2.4.2　題目分析與算法實(shí)現(xiàn) 　　2.4.3　參考程序與程序分析 　　2.4.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　2.5　掘金 　　2.5.1　試題 　　2.5.2　題目分析與算法實(shí)現(xiàn) 　　2.5.3　參考程序與程序分析 　　2.5.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 第3章　2005年中山大學(xué)內(nèi)部選拔賽第三試試題分析 　3.1　最小差值生成樹 　　3.1.1　試題 　　3.1.2　題目分析與算法實(shí)現(xiàn) 　　3.1.3　參考程序與程序分析 　　3.1.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　3.2　Alice和Bob 　　3.2.1　試題　　3.2.2　題目分析與算法實(shí)現(xiàn) 　　3.2.3　參考程序與程序分析 　　3.2.4　部分測(cè)試數(shù)據(jù)與輸出結(jié)果 　3.3　Collatz難題 　……第4章　2005年中山大學(xué)內(nèi)部選拔賽第四試試題分析第5章　2006年中山大學(xué)內(nèi)部選拔賽第一試試題分析 第6章　2006年中山大學(xué)內(nèi)部選拔賽第二試試題分析 第7章　2006年中山大學(xué)內(nèi)部選拔賽第三試試題分析第8章　2006年中山大學(xué)內(nèi)部選拔賽第四試試題分析第9章　2006年中山大學(xué)內(nèi)部選拔賽第五試試題分析第10章　2006年中山大學(xué)內(nèi)部選拔賽第六試試題分析附錄A　中國(guó)內(nèi)地高校參加ACM/ICPC全球總決賽成績(jī)（1997-2010年）附錄B　中山大學(xué)ACM/ICPC集訓(xùn)隊(duì)選拔流程圖參考文獻(xiàn) 作者簡(jiǎn)介

章節(jié)摘錄

插圖：

編輯推薦

《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解(7):中山大學(xué)ICPC集訓(xùn)隊(duì)內(nèi)部選拔賽試題(2005-2006年)》是由電子工業(yè)出版社出版的。

圖書封面

圖書標(biāo)簽Tags

無

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

---

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

---