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

前言

ACM國際大學(xué)生程序設(shè)計競賽（ACM International Collegiate Programming Contest，簡稱ACM／ICPC）是由國際計算機界歷史悠久、頗具權(quán)威性的組織ACM學(xué)會（Associationfor Computer Machinery）主辦的，是世界上公認的規(guī)模最大、水平最高的國際大學(xué)生程序設(shè)計競賽，其目的旨在使大學(xué)生運用計算機來充分展示自己分析問題和解決問題的能力。該項競賽從1970年舉辦至今已歷32屆，因歷屆競賽都薈萃了世界各大洲的精英，云集了計算機界的“希望之星”，而受到國際各知名大學(xué)的重視，并受到全世界各著名IT企業(yè)的高度關(guān)注，成為世界各國大學(xué)生最具影響力的國際級計算機類的賽事。ACM所頒發(fā)的獲獎證書也為世界各知名大學(xué)、各著名IT企業(yè)所認可。該項競賽分為區(qū)域預(yù)賽和世界決賽兩個階段進行，各預(yù)賽區(qū)第一名自動獲得參加世界決賽的資格，世界決賽安排在每年的3～4月舉行，而區(qū)域預(yù)賽安排在上一年的9～12月在各大洲舉行。ACM／ICPC的區(qū)域預(yù)賽是規(guī)模很大、范圍很廣的賽事。以2007年為例，全世界有83個國家和地區(qū)、182l所大學(xué)、超過6700支參賽隊在六大洲的37個賽站中爭奪世界決賽的100個名額，其激烈程度可想而知。與其他編程競賽相比，ACM／ICPC題目難度更大，更強調(diào)算法的高效性，不僅要解決一個指定的命題，而且必須以最佳的方式解決指定的命題。它涉及的知識面廣，與大學(xué)計算機系本科及研究生的課程直接關(guān)聯(lián)，如程序設(shè)計、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、人工智能、算法分析與設(shè)計等課程；對數(shù)學(xué)要求更高；由于采用英文命題，對英語要求較高；ACM／ICPC采用3人合作、共用一臺電腦，所以它更強調(diào)團隊協(xié)作精神；由于許多題目并無現(xiàn)成的算法，需要具備創(chuàng)新的精神，ACM／ICPC不僅強調(diào)學(xué)科的基礎(chǔ)，更強調(diào)全面素質(zhì)和能力的培養(yǎng)；由于ACM／ICPC是采用5小時全封閉式競賽，參賽隊員與外界完全隔離，獨立完成，是參賽隊員實際能力的真實表露，其成績可信度甚高。.ACM／ICPC又是一種“開卷考試”，可以帶任何書籍、資料甚至源程序代碼清單（但不能帶電子媒體），不需要死背算法，而強調(diào)的是算法的靈活運用；與其他計算機競賽（如軟件設(shè)計，網(wǎng)站設(shè)計等）相比，ACM／ICPC有嚴謹而客觀的評判規(guī)則（嚴格的數(shù)據(jù)測試），排除了因評委的主觀因素而造成評審不公平的現(xiàn)象，所以，ACM／ICPC對成績的爭議較少。

內(nèi)容概要

　　本書收錄了2006—2007年廣東省大學(xué)生程序設(shè)計競賽（GDCPC 20（0--2007，即ACM／ICPC廣東省賽）的全部試題、完整的測試數(shù)據(jù)和答案，以及2004年中山大學(xué)ACM集訓(xùn)隊內(nèi)部選拔賽題目、完整的測試數(shù)據(jù)和答案。為了方便讀者學(xué)習，本書對每個題目作了詳盡的題目分析，并詳細地講解其算法實現(xiàn)的原理，同時提供了完善的參考程序及程序分析，供讀者參考。書中提供了競賽時評判用的基本測試數(shù)據(jù)，以方便讀者測試自行完成上述題目的結(jié)果。隨書附帶的光盤中存放了競賽時評判用的全部測試數(shù)據(jù)，以便于有更高、更嚴格要求的同學(xué)能利用規(guī)模更大的測試數(shù)據(jù)進行訓(xùn)練和學(xué)習?！　”緯峁┑念}目都是原創(chuàng)題，題目構(gòu)思新穎，內(nèi)容有趣。所涉及到的算法知識面廣，基本上覆蓋大學(xué)計算機類本科專業(yè)所學(xué)到的基本算法。本書可以作為高等院校有關(guān)專業(yè)的研究生和本科學(xué)生參加國際大學(xué)生程序設(shè)計競賽的輔導(dǎo)教材，也可作為高等院校有關(guān)專業(yè)相關(guān)課程的教學(xué)參考書與例題集，也特別適用于作為中學(xué)青少年信息學(xué)奧林匹克競賽省級及省級以上優(yōu)秀選手備戰(zhàn)信息學(xué)奧林匹克競賽的培訓(xùn)教材及訓(xùn)練題集。

作者簡介

郭嵩山，男，1945年4月出生，1967年畢業(yè)于上海交通大學(xué)無線電技術(shù)專業(yè)，中山大學(xué)信息科學(xué)與技術(shù)學(xué)院計算機科學(xué)系教授，主要從事計算機操作系統(tǒng)的教學(xué)和研究。主要著作有電子工業(yè)出版社出版的《BIO結(jié)構(gòu)分析教程》、《DOS內(nèi)核結(jié)構(gòu)分析教程》、《COMMAND結(jié)構(gòu)分析教程》、《Windows 98 IO結(jié)構(gòu)分析教程》、《國際大學(xué)生程序設(shè)計競賽例題解（一）——數(shù)論、計算幾何、搜索算法專集》、《國際大學(xué)生程序設(shè)計競賽例題解（二）——廣東省大學(xué)生程序設(shè)計競賽試題解（2003-2005年）》、《國際大學(xué)生程序設(shè)計競賽例題解（三）——圖論、動態(tài)規(guī)劃算法、綜合題專集》、《國際大學(xué)生程序設(shè)計競賽例題解（四）——廣東省信息學(xué)奧林匹克競賽試題選解（2003-2006年）》，2008年2月，人民郵電出版社出版的《數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用》，中山大學(xué)出版社出版的《青少年信息學(xué)奧林匹克競賽廣東試題及解答（1986一1994）》，北京大學(xué)出版社出版的《國際大學(xué)生程序設(shè)計競賽輔導(dǎo)教程》等。郭嵩山主持廣東省信息學(xué)奧林匹克競賽20余年，制定了公開、公正、公平的，科學(xué)化、規(guī)范化的廣東省信息學(xué)奧林匹克競賽條例，廣東省一直被公認為是信息學(xué)奧林匹克競賽全國普及活動開展最好的省份之一，也是全國競賽水平最好的省份之一。近10年來，郭嵩山擔任ACM國際大學(xué)生程序設(shè)計競賽中山大學(xué)隊主教練，中山大學(xué)隊在1999-2001、2003-2008年9次獲得全球總決賽的決賽權(quán)，并在全球總決賽中取得好成績。近幾年，郭嵩山擔任ACM國際大學(xué)生程序設(shè)計競賽（ACM／ICPC）廣東省賽區(qū)執(zhí)行主席，主持2003-2008年連續(xù)6屆的ACM／ICPC廣東省賽。在科研方面，郭嵩山指導(dǎo)多名碩士研究生在人工智能算法研究方面取得較好的成果。張子臻，男，1984年8月出生，2003年9月被保送入中山大學(xué)計算機科學(xué)系攻讀學(xué)士學(xué)位，2007年9月被保送入中山大學(xué)計算機科學(xué)系攻讀碩士學(xué)位。在學(xué)期間，曾多次代表中山大學(xué)參加ACM國際大學(xué)生程序設(shè)計競賽（ACM／ICPC）。榮獲：2004年第29屆ACM／ICPC亞洲臺北賽區(qū)第6名，北京賽區(qū)第8名（銀牌）；2006年第31屆ACM／ICPC亞洲河內(nèi)賽區(qū)亞軍（金牌）；2007年第31屆ACM／ICPC全球總決賽（東京）第26名；2007年第32屆ACM／ICPC亞洲首爾賽區(qū)亞軍，北京賽區(qū)第5名（金牌）。王磊，男，1984年3月出生，2003年9月考入中山大學(xué)計算機科學(xué)系攻讀學(xué)士學(xué)位，2007年9月被保送入中山大學(xué)計算機科學(xué)系攻讀碩士學(xué)位。在學(xué)期間，曾多次代表中山大學(xué)參加ACM國際大學(xué)生程序設(shè)計競賽（ACM／ICPC）。榮獲：2005年第30屆ACM／ICPC亞洲臺北賽區(qū)第7名，北京賽區(qū)第5名（金牌）；2006年第31屆ACM／ICPC亞洲河內(nèi)賽區(qū)亞軍（金牌）；2007年第3l屆ACM／ICPC全球總決賽（東京）第26名；2007年第32屆ACM／ICPC亞洲硯港賽區(qū)冠軍；2008年第32屆ACM／ICPC全球總決賽（班夫）第23名。湯振東，男，1984年2月出生，2003年9月考入中山大學(xué)計算機科學(xué)系攻讀學(xué)士學(xué)位，2007年9月被保送入中山大學(xué)計算機科學(xué)系攻讀碩士學(xué)位。在學(xué)期間，曾多次代表中山大學(xué)參加ACM國際大學(xué)生程序設(shè)計競賽（ACM／ICPC）。榮獲：2006年第31屆ACM／ICPC亞洲北京賽區(qū)銀牌；2007年第32屆ACM／ICPC亞洲南京賽區(qū)金牌；2007年第32屆ACM／ICPC亞洲北京賽區(qū)銀牌。

書籍目錄

本書試題涉及知識點的說明第1章 第9屆中山大學(xué)程序設(shè)計競賽預(yù)選賽（2006年）試題分析1.1 信息泛濫（難度：★★★☆☆）1.1.1 試題1.1.2 題目分析與算法實現(xiàn)1.1.3 參考程序與程序分析1.1.4 部分測試數(shù)據(jù)與輸出結(jié)果1.2 求和（難度：★★★★☆）1.2.1 試題1.2.2 題目分析與算法實現(xiàn)1.2.3 參考程序與程序分析1.2.4 部分測試數(shù)據(jù)與輸出結(jié)果1.3 沖突（難度：★★★★★）1.3.1 試題1.3.2 題目分析與算法實現(xiàn)1.3.3 參考程序與程序分析1.3.4 部分測試數(shù)據(jù)與輸出結(jié)果1.4 旅館（難度：★★★☆☆）1.4.1 試題1.4.2 題目分析與算法實現(xiàn)1.4.3 參考程序與程序分析1.4.4 部分測試數(shù)據(jù)與輸出結(jié)果1.5 字符串子串（難度：★★☆☆☆）1.5.1 試題1.5.2 題目分析與算法實現(xiàn)1.5.3 參考程序與程序分析1.5.4 部分測試數(shù)據(jù)與輸出結(jié)果1.6 最大公約數(shù)（難度：★★★★☆）1.6.1 試題1.6.2 題目分析與算法實現(xiàn)1.6.3 參考程序與程序分析1.6.4 部分測試數(shù)據(jù)與輸出結(jié)果1.7 木棒（難度：★☆☆☆☆）1.7.1 試題1.7.2 題目分析與算法實現(xiàn)1.7.3 參考程序與程序分析1.7.4 部分測試數(shù)據(jù)與輸出結(jié)果1.8 總體題目分析與比賽情況1.8.1 題目總結(jié)分析1.8.2 比賽情況第2章 第4屆廣東省大學(xué)生程序設(shè)計競賽暨第9屆中山大學(xué)程序設(shè)計競賽（2006年）試題分析2.1 過剩數(shù)（難度：★☆☆☆☆）2.1.1 試題2.1.2 題目分析與算法實現(xiàn)2.1.3 參考程序與程序分析2.1.4 部分測試數(shù)據(jù)與輸出結(jié)果2.2 L形覆蓋（難度：★★☆☆☆）2.2.1 試題2.2.2 題目分析與算法實現(xiàn)2.2.3 參考程序與程序分析2.2.4 部分測試數(shù)據(jù)與輸出結(jié)果2.3 立方塊（難度：★★★★☆）2.3.1 試題2.3.2 題目分析與算法實現(xiàn)2.3.3 參考程序與程序分析2.3.4 部分測試數(shù)據(jù)與輸出結(jié)果2.4 螺旋方陣（難度：★★☆☆☆）2.4.1 試題2.4.2 題目分析與算法實現(xiàn)2.4.3 參考程序與程序分析2.4.4 部分測試數(shù)據(jù)與輸出結(jié)果2.5 電子書狂熱者（難度：★★★★☆）2.5.1 試題2.5.2 題目分析與算法實現(xiàn)2.5.3 參考程序與程序分析2.5.4 部分測試數(shù)據(jù)與輸出結(jié)果2.6 柵格網(wǎng)絡(luò)流（難度：★★★★★）2.6.1 試題2.6.2 題目分析與算法實現(xiàn)2.6.3 參考程序及程序分析2.6.4 部分測試數(shù)據(jù)與輸出結(jié)果2.7 連續(xù)邊長多邊形（難度：★★★☆☆）2.7.1 試題2.7.2 題目分析與算法實現(xiàn)2.7.3 參考程序與程序分析2.7.4 部分測試數(shù)據(jù)與輸出結(jié)果2.8 饑餓的母牛（難度：★★★☆☆）2.8.1 試題2.8.2 題目分析與算法實現(xiàn)2.8.3 參考程序與程序分析2.8.4 部分測試數(shù)據(jù)與輸出結(jié)果2.9 解析程序（難度：★★★★☆）2.9.1 試題2.9.2 題目分析與算法實現(xiàn)2.9.3 參考程序與程序分析2.9.4 部分測試數(shù)據(jù)與輸出結(jié)果2.10 網(wǎng)絡(luò)探測（難度：★★★☆☆）^2.10.1 試題2.10.2 題目分析與算法實現(xiàn)2.10.3 參考程序與程序分析2.10.4 部分測試數(shù)據(jù)與輸出結(jié)果2.11總體題目分析與比賽情況2.11.1 題目總結(jié)分析2.11.2 比賽情況第3章 第10屆中山大學(xué)程序設(shè)計競賽預(yù)選賽（2007年）試題分析3.1 圣誕節(jié)（難度：★★★☆☆）3.1.1 試題3.1.2 題目分析與算法實現(xiàn)3.1.3 參考程序與程序分析3.1.4 部分測試數(shù)據(jù)與輸出結(jié)果3.2 導(dǎo)彈（難度：★★☆☆☆）3.2.1 試題3.2.2 題目分析與算法實現(xiàn)3.2.3 參考程序與程序分析3.2.4 部分測試數(shù)據(jù)與輸出結(jié)果3.3 兒童節(jié)快樂（難度：★★★★☆）3.3.1 試題3.3.2 題目分析與算法實現(xiàn)3.3.3 參考程序與程序分析3.3.4 部分測試數(shù)據(jù)與輸出結(jié)果3.4 排列（難度：★★★☆☆）3.4.1 試題3.4.2 題目分析與算法實現(xiàn)3.4.3 參考程序與程序分析3.4.4 部分測試數(shù)據(jù)與輸出結(jié)果3.5 兵排隊（難度：★★☆☆☆）3.5.1 試試題3.5.2 題目分析與算法實現(xiàn)3.5.3 參考程序與程序分析3.5.4.部分測試數(shù)據(jù)與輸出結(jié)果3.6 我的總結(jié)（難度：★☆☆☆☆）3.6.1 試題3.6.2 題目分析與算法實現(xiàn)3.6.3 參考程序與程序分析3.6.4.部分測試數(shù)據(jù)與輸出結(jié)果3.7 準備工作（難度：★★★★★）3.7.1 試題3.7.2 題目分析與算法實現(xiàn)3.7.3 參考程序與程序分析3.7.4 部分測試數(shù)據(jù)與輸出結(jié)果3.8 總體題目分析與比賽情況3.8.1 題目總結(jié)分析3.8.2 賽情況第4章 第5屆廣東省大學(xué)生程序設(shè)計競賽暨第lO屆中山大學(xué)程序設(shè)計競賽（2007年）試題分析4.1 遙遠的距離（難度：★★★★☆）4.1.1 試題4.1.2 題目分析與算法實現(xiàn)4.1.3 參考程序與程序分析4.1.4 部分測試數(shù)據(jù)與輸出結(jié)果4.2 分數(shù)（難度：★☆☆☆☆）4.2.1 試題4.2.2 題目分析與算法實現(xiàn)4.2.3 參考程序與程序分析4.2.4 部分測試數(shù)據(jù)與輸出結(jié)果4.3 并行（難度：★★★☆☆）4.3.1 試題4.3.2 題目分析與算法實現(xiàn)4.3.3 參考程序與程序分析第5章 中山大學(xué)集訓(xùn)隊內(nèi)部選拔賽（2004年）試題分析附錄A 中國內(nèi)地高校舉辦ACM/CPC亞洲區(qū)預(yù)賽的情況附錄B 中國內(nèi)地高校參加ACM/CPC全球總決賽的成績附錄C 中山大學(xué)隊參加ACM/CPC亞洲區(qū)域賽歷年成績表（1997－2007年）附錄D 中山大學(xué)隊參加ACM/CPC總決賽歷年成績表（1999——2008年）參考文獻作者簡介

章節(jié)摘錄

插圖：

編輯推薦

《國際大學(xué)生程序設(shè)計競賽例題解5:廣東省大學(xué)生程序設(shè)計競賽試題(2006-2007年)》所提供的題目都是原創(chuàng)題，題目構(gòu)思新穎，內(nèi)容有趣。所涉及到的算法知識面廣，基本上覆蓋大學(xué)計算機類本科專業(yè)所學(xué)到的基本算法?！秶H大學(xué)生程序設(shè)計競賽例題解5:廣東省大學(xué)生程序設(shè)計競賽試題(2006-2007年)》可以作為高等院校有關(guān)專業(yè)的研究生和本科學(xué)生參加國際大學(xué)生程序設(shè)計競賽的輔導(dǎo)教材，也可作為高等院校有關(guān)專業(yè)相關(guān)課程的教學(xué)參考書與例題集，也特別適用于作為中學(xué)青少年信息學(xué)奧林匹克競賽省級及省級以上優(yōu)秀選手備戰(zhàn)信息學(xué)奧林匹克競賽的培訓(xùn)教材及訓(xùn)練題集。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---