國(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 forComputer Machinery）主辦的，是世界上公認(rèn)的規(guī)模最大、水平最高的國(guó)際大學(xué)生程序設(shè)競(jìng)賽，其目的旨在使大學(xué)生運(yùn)用計(jì)算機(jī)來充分展示自己分析問題和解決問題的能力。該項(xiàng)競(jìng)賽從1970年舉辦至今已歷32屆，因歷屆競(jìng)賽都薈萃了世界各大洲的精英，云集了計(jì)算機(jī)界的“希望之星”，而受到國(guó)際各知名大學(xué)的重視，并受到全世界各著名Ⅱ企業(yè)的高度關(guān)注，成為世界各國(guó)大學(xué)生最具影響力的國(guó)際級(jí)計(jì)算機(jī)類的賽事?！　CM所頒發(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ī)模很大、范圍很廣的賽事。以2008年為例，全世界有88個(gè)國(guó)家和地區(qū)、1838所大學(xué)、超過7100支參賽隊(duì)在六大洲的37個(gè)賽站中爭(zhēng)奪世界決賽的100個(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é)作精神；由于許多題目并無(wú)現(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)議較少?！　≈猩酱髮W(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名。

內(nèi)容概要

　　 本書是該套例題解的第六本，所用的語(yǔ)言是C++。全書共分6章，收錄了2008-2009 廣東省大學(xué)生程序設(shè)計(jì)競(jìng)賽（GDCPC2008-2009、即ACM/ICPC廣東省賽）以及第33屆ACM/ICPC亞洲成都賽區(qū)預(yù)選賽（由西南民族大學(xué)承辦、由中山大學(xué)命題）的全部試題、完整的測(cè)試數(shù)據(jù)和答案。為了方便讀者學(xué)習(xí)，本書對(duì)每個(gè)題目作了詳盡的題目分析并詳細(xì)地講解其算法實(shí)現(xiàn)的原理，同時(shí)提供了完善的標(biāo)準(zhǔn)程序及其程序分析供讀者參考，我們?cè)跁羞€提供了基本測(cè)試數(shù)據(jù)以方便讀者測(cè)試自行完成上述題目的結(jié)果。

作者簡(jiǎn)介

　　郭嵩山，男，1945年4月出生，1967年畢業(yè)于上海交通大學(xué)無(wú)線電技術(shù)專業(yè)，中山大學(xué)信息科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)系教授，主要從事計(jì)算機(jī)操作系統(tǒng)的教學(xué)和研究。主要著作有電子工業(yè)出版社出版的《BIO結(jié)構(gòu)分析教程》、《DOS內(nèi)核結(jié)構(gòu)分析教程》、《COMMAND結(jié)構(gòu)分析教程》、《Windows98IO結(jié)構(gòu)分析教程》、《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解（一）——數(shù)論、計(jì)算幾何、搜索算法專集》、《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解（二）——廣東省大學(xué)生程序設(shè)計(jì)競(jìng)賽試題（2003-2005年）》、《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解（三）——圖論、動(dòng)態(tài)規(guī)劃算法、綜合題專集》、國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解（四）——廣東省信息學(xué)奧林匹克競(jìng)賽試題（2003-2006年）》、《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽例題解（五）——廣東省大學(xué)生程序設(shè)計(jì)競(jìng)賽試題（2006-2007年）》，人民郵電出版社出版的《數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用》，中山大學(xué)出版社出版的《青少年信息學(xué)奧林匹克競(jìng)賽廣東試題及解答（1986-1994）》，北京大學(xué)出版社出版的《國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽輔導(dǎo)教程》等?！　」陨街鞒謴V東省信息學(xué)奧林匹克競(jìng)賽20余年，制定了公開、公正、公平的，科學(xué)化、規(guī)范化的廣東省信息學(xué)奧林匹克競(jìng)賽條例，廣東省一直被公認(rèn)為是信息學(xué)奧林匹克競(jìng)賽全國(guó)普及活動(dòng)開展最好的省份之一，也是全國(guó)競(jìng)賽水平最高的省份之一。近12年來，郭嵩山擔(dān)任ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽中山大學(xué)隊(duì)主教練，中山大學(xué)隊(duì)在1999-2001、2003-2009年10次獲得全球總決賽的決賽權(quán)，并在全球總決賽中取得好成績(jī)。近幾年，郭嵩山擔(dān)任ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM／ICPC）廣東省賽區(qū)執(zhí)行主席，主持7屆ACM／ICPC廣東省賽。在科研方面，郭嵩山指導(dǎo)多名碩士研究生在人工智能算法研究及應(yīng)用方面取得較好的成果。　　翁雨鍵，男，1986年2月出生，2004年9月考入中山大學(xué)計(jì)算機(jī)科學(xué)系攻讀學(xué)士學(xué)位，2008年9月被保送入中山大學(xué)計(jì)算機(jī)科學(xué)系攻讀碩士學(xué)位。在校期間，曾多次代表中山大學(xué)參加ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM／ICPC）。榮獲：2006年第31屆ACM／ICPC亞洲上海賽區(qū)銀獎(jiǎng)。2007年第32屆ACM／ICPC亞洲南京賽區(qū)第7名（金牌），北京賽區(qū)銀獎(jiǎng)。2008年第33屆ACM／ICPC亞洲雅加達(dá)賽區(qū)并列第2名（金牌），杭州賽區(qū)銀獎(jiǎng)。在2009年廣東省第7屆大學(xué)生程序設(shè)計(jì)競(jìng)賽（GDCPC2009）擔(dān)任命題組負(fù)責(zé)人?！　×褐緲s，男，1984年8月出生，2004.年9月考入中山大學(xué)計(jì)算機(jī)科學(xué)系攻讀學(xué)士學(xué)位，2008年9月被保送入中山大學(xué)計(jì)算機(jī)科學(xué)系攻讀碩士學(xué)位。在校期間，曾多次代表中山大學(xué)參加ACM國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽（ACM／ICPC）。榮獲：2005年第30屆ACM／ICPC亞洲杭州賽區(qū)銀獎(jiǎng)。2006年第31屆ACM／ICPC亞洲上海賽區(qū)銀獎(jiǎng)。

書籍目錄

本書試題涉及知識(shí)點(diǎn)的說明　　第1章  第11屆中山大學(xué)程序設(shè)計(jì)競(jìng)賽預(yù)選賽（2008年）試題分析　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 旅行（難度：★★★☆☆）　　　　 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 圍棋（難度：★★★★☆）　　　　 1.5.1試題　　　　 1.5.2題目分析與算法實(shí)現(xiàn)　　　　 1.5.3參考程序與程序分析　　　　 1.5.4部分測(cè)試數(shù)據(jù)與輸出結(jié)果　　　1.6 字符串序列（難度：★★★☆☆）　　　 1.6.1試題　　　　 1.6.2題目分析與算法實(shí)現(xiàn)　　　　 1.6.3參考程序與程序分析　　　　 1.6.4部分測(cè)試數(shù)據(jù)與輸出結(jié)果　　　1.7 DNA重組（難度：★★★★☆）　  　　 1.7.1試題　　　　 1.7.2題目分析與算法實(shí)現(xiàn)　　　　 1.7.3參考程序與程序分析　　　　 1.7.4部分測(cè)試數(shù)據(jù)與輸出結(jié)果　　 　1.8 小實(shí)的問題（難度：★☆☆☆☆）　　　　 1.8.1試題　　　　 1.8.2題目分析與算法實(shí)現(xiàn)　　　　 1.8.3參考程序與程序分析　　　　 1.8.4部分測(cè)試數(shù)據(jù)與輸出結(jié)果　　　1.9 總體題目分析與比賽情況　　　　 1.9.1題目分析　　 　　 1.9.2比賽情況　　 第2章  第6屆廣東省大學(xué)生程序設(shè)計(jì)競(jìng)賽暨第11屆中山大學(xué)程序　　 設(shè)計(jì)競(jìng)賽（2008）　　 試題分析　　　2.1 表面積（難度：★☆☆☆☆）　　　　 2.1.1試題　　　　 2.1.2題目分析與算法實(shí)現(xiàn)　　　　 2.1.3參考程序與程序分析　　　　 2.1.4部分測(cè)試數(shù)據(jù)與輸出結(jié)果　　　2.2 讀書（難度：★★☆☆☆）　　　　 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試題　　54　　 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é)果　　　2.6 風(fēng)水（難度：★★★☆☆）　……第3章 第12屆中山大學(xué)程序設(shè)計(jì)競(jìng)賽預(yù)選賽（2009）試題分析第4章 第7屆廣東省大學(xué)生程序設(shè)計(jì)競(jìng)賽暨第12屆中山大學(xué)程序設(shè)計(jì)競(jìng)賽（2009）試題分析　第5章 第33屆國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲成都賽區(qū)網(wǎng)絡(luò)預(yù)賽試題分析第6章 第33屆國(guó)際大學(xué)生程序設(shè)計(jì)競(jìng)賽亞洲成都賽區(qū)現(xiàn)場(chǎng)賽試題分析　參考文獻(xiàn)　　作者簡(jiǎn)介　　

圖書封面

圖書標(biāo)簽Tags

無(wú)

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

---

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

---