ACM程序设计

《ACM程序设计(第2版)》详细讲解了ACM国际大学生程序设计竞赛(ACM/ICPC)编程、调试方法，以及提高时间、空间性能的策略，并充分利用了C++泛型编程的高效率、规范化的特性，全部采用C++泛型编程。第1章讲解了ACM程序设计入门知识；第2章讲解了C++泛型编程的容器、迭代器和常用算法；第3章讲解了ACM程序设计的基本编程技巧；第4章讲解了50道原版ACM竞赛题的解题思路，并配有C++泛型编程参考答案和题目的中文翻译。《ACM程序设计(第2版)》是一本专门针对ACM国际大学生程序设计竞赛而编写的入门教程，适合参加ACM/ICPC的大学生和C++编程爱好者学习，对ACM/ICPC竞赛教练也前言ACM国际大学生程序设计竞赛( ACM International Collcgiatc Programming Contest,ACMICPO)由ACM( Association for Computing Machinery,美国计算机协会)主办,是世界上公认的规模最大、水平最高、影响最广的国际大学生程序设计竞赛。由于ACM大学生程序设计竞赛能迅速提高学生的程序设计能力和团队协作水平,又能有效地提升学校程序设计教学水屮和质量,促进校际交流与竟争,近年来,ACM大学牛稈序设计竞赛在我国得到了大规模的推广,各个高校都十分重视。然而,由于该赛事是个新鲜事物,且ACM程序设计有其特殊的规律,很多晑校难以适应。为了尽快解决这个问题,笔者将近三年来潜心钻研ACM竞赛的相关资料整理出来,供大家分享。经实践证实,本书能在两个月内将程序设计的初学者培养成ACM竞赛高手。本书以C++泛型编程的应用为主线,一步一步带领读者登上ACM程序设计的殿堂第1章讲解了ACM稈序设计入门知识;第2章讲解了C艹+泛型编稈的容器、迭代器和常用算法;第3章讲解了ACM程序设计的基夲编程技巧;第4章讲解了50道原版ACM竞赛题的解题思路,并配有C艹+泛型编程参考答案和题口的中文翻译。本书的出版,首先得感谢我的导师浙江师范大学数理信息学院王基一教授和丁革建高工、浙江工业大学信息学院钱能教授对笔者学术工作的不断启发与鼓励;感谢北京大学出版社的人力支持!ACM程序设计要求很高,由于时间仓促,笔者水平有限,书中定有许多不足甚至错误之处,恳请广大专家、读者批评指正!笔者邮箱zjnuken@126.com,个人主http://www.zzg.3126.net曾棕根2008年10月目录第1章ACM程序设计入门227使用 reverse反向排列算法…221.1 ACMICPC简介22.8仗用sort算法对向量元素1.1历史排序231.1.2简要规贝…9向量的大小1.1.3区域和全球决赛23 string基字符系列容器261.14历届冠军…23.1创建 string对象261.1.5在线评测系统23.2给 string对象赋值.…263从 string对象尾部添加字符1.1.6试题样例234从 string对象尾部追加12用VC++编写控制台程序……4字符串1.2.1例题…5给 string对象入字符1.22操作23.6访问 string对象的元素1.3ACM竞赛本机调试方法23.7删除 string对象的元素.291.3.1竟竞赛样题23.8返回 string对象的长度1.3.,2本机调试步骤.23.9替換 string对象的字符…314浙江大学在线评测系统(ZOJ23.10搜索sing对象的元素或在线实验…12子串14.1竞赛样题23.11 string对象的比较142提交代码…132312用 reverse反向排序 string对象第2章C++STL泛型编程..….162313 string对象作为 vector元素332.1C++STL概述1623.14 string类型的数字化处理……3321.1C++STL的实现版本315 string对象与字符数组互2.1.2 CHISTI组件操作342.1.3C++STL泛型编程示例.…1723.16 string对象与 sscanf函数…32.1.4ⅤC++6.0泛型编程1823.17 string对象与数值相互转换.362 vector向量容器..824set集合容器…37221创建 vector对象241创剑建set集合对象222尾部元素扩张19242元素的插入与中序遄历2.2.3下标方式访问 vector元素..20243元素的反向遍历.38224用迭代器访问 vector元素……20244元素的删除2.2.5元素的插入21245元素的检索22.6元素的删除……21246自定义比较函数ACM程序设计25 multiset多重集合容器.432.12 queue队列容器2.5.1 multiset元索的插入213 priority queue优先队列容器252 multiset元素的删除2.13.1伏先队列的使用方法2.53查找元素2.13.2重载“<操作符来定义26map映照容器46优先级79261map创建、元素插入和遍历2133重载“(”操作符来定义访问优宄级262删除元素…第3章ACM程序设计基础26.3元素反向遍历.2.6.4元素的搜索.…3.1读入一个参数2.6.5白定义比较函数…493.1.1链接地址266用map实现数字分离…513.1.2题目内容26.7数字映照字符的map写法.…,531.3参考答案27 multimap多重映照容器32读入两个参数27.1 multimap对象创建、元素3.2.1链接地址.083插入322题目内容.2.7.2元素的删除...543.2.3参考答案.27.3元素的查找53.31到n!的和28 dique双端队列容器..563.3.1链接地址.28.1创建 deque对象57332题目内容.28.2拓入元素333参考答案.83前向遍历34等比数列2.8.4反向遍历…341链接地址.2.8.5删除元素342题目内容.8429list双向链表容器.6329.1创建list对象….34.3参考答案2元素插入和遍历3.5菲波那契数3.5.1链接地址29.3反冋遍历6529.4元素删除352题日内容参考答案.29.5元素查找3.6最大公约数296元素排序….702.9.7剔除连续重复元素3.6.1链接地址.…….87700 bitset位集合容器36.2题目内谷712.10.1创建 bitset对象参考答案.02设置元素值3.7最小公倍数371链接地址2.10.3输出元素74tack堆栈容器.372题目内容.89767.3参考答案I录3.8平均数…903.17.2题目内容1023.81链接地址903.173参考答案1033.8.2题目内容90第4章ACM程序设计实战…1043.8.3参考答案3.9对称三位数素数914.1 Quicksun...…,1043.9.1链接地址:∴9141.1链接地址104392题目内容914.L.2时空阪制393参老答案.914.1.3题目内容1043.10十进制转换为二进制924.1.4题日来源1053.10.1链接地址…924.1.5解题思烙.3.10.2题目内容…4.1.6参考答案…3103参考答案4.1.7汉语翻译.…1063.11列出完数.∴934.2 IBM Minus one1073.1.1链接地址42.1链接地址…1073.1.2题目内容422时空限制1073.113参考答案4.2.3题目内容…1073.1212!配对954.2.4题目来源1083.121链接地址954.2.5解题思路.83.122题目内容954.2.6参考答案…3.12.3参考答案954.2.7汉语翻译l093.13五位以内的对称素数9643 Binary Numbers………103.13.1链接地址3.1链接地址3.13.2题目内容…4.3.2时空限制1103.13.3参考答案4.3.3题目内容.1103.1401串排序974.34题目来源.III3.141链接地址…4.3.5解题思路.…3.142题目内谷4.3.6参考答案.l113.143参考答案4.3.7汉语翻译.1123.15排列对称串984.4 Encodingl123.15.1链接地址44l链接地坤3.152题日内容442时空阪制.1123.15.3参考答案44.3题目内容1133.16按绩点排名……100444题目来源.1133.16.1链接地址.10044.5解题思路.1133.16,2题目内容IOC446参考答案l133.163参考答案1014.4.7汉语翻译1143.17按1的个数排序1024.5 Look and say.…1153.17.1链接地址1024.5.1链接地址ACM程序设计4.5.2时空限制…………1154.10 Gcomctry Madc Simplc4.53题目内容1154.10.1链接地址1314.5.4题目来源.1164.10.2时空限制….131解题思路……4.103题目内容4.56参考答案11164.104题目来源…1324.5.7汉语翻译1174.10.5解题思路…1324.6 Abbreviation4.106参考答案1326.1链接地止4.10.7汉语翻译1344.6.2时空限制l18411 Reverse text4.63题目内容4.111链接地址……4.6.4题目来源…4.11.2时空限制.…1354.6.5解题思路119411.3题目内容46.6参老答案1194114题日来源.135汉语翻译1204.11.5解题思路.4.7 The Seven Percent Solution1.6参考答案…1364.7.1链接地址4.117汉语翻译4.7.2时空限制l224.12 Word reversal137473题口内容4.12.1链接地址4.7.4题目来源4.12.2时空限制1374.7.5解题思路1234.12.3题目内容1376参考答案1234.124题目来源1384.77汉语翻译1244.12.5解题思路1384.8 Digital Roc4.12.6参考答案4.8.1链接地址4.12.7汉语翻译4.8.2时空限制1254.13 A Simple Question of Chemistry…….1404.83题口内容4.13.1链接地址48.4题目来源4.13.2时空限制1404.8.5解题思路……..1264.13.3题目内容.1404.8.6参考答案…1264.13.4题目来源…1414.8.7汉话翻译1274.13.5解题思路1414.9 Box of bricks4.13.6参考答案…4.9.1链接地1284.13.7汉语翻译.1424.9.2时空限制1284.14 Adding reversed Numbers.……143493题目内容…1284.14.1链接地址….…14349.4题目来源4.14.2时空限制495解题思路….129414.3题日内容…14349.6参考答案1294.144题目米源1444.9.7汉诘翻译4.14.5解题思路144录4.14.6参考答案1444.194题目来源1624.14.7汉语翻译1464.19.5解题思路1624.15 Image transformation4.19.6参考答案……1624.15.链接地址…4.19.7汉语翻译.4.15.2时空限制1474.20 Martian addition1644.153题目内容….….1474,20.1链接地址……1644.154题目来源0.2时空限制4.15.5解题思路420.3题日内容…16515.6参考答案1464204题目来源l654.15.7汉语翻译4.20.5解题思路.1654.16 Bcautiful mcadow.150420.6参考答案…4.161链接地址….…150420.7汉语翻译1684.16.2时空限制1504.21 FatMouse’ Trade…169416.3题目内容.1504.,21.1链接地址1694.164题目来源4,212时空限制.4.16.5解题思路…152421.3题目内容…1694.66参考答案1524214题目来源…4.16.7汉语翻译153421.5解题指导…,1704.l7 DNA Sorting……1554.21.6参考答案1704.171链接地址1554,217汉语翻译4.17.2时空限制1554.22 List the books473题目内容…1554,22.1链接地址4.174题目来源15642.2时空限制1724.17.5解题思路4223题目内容.1724.176参考答案1564224题目来源1734.177汉语翻译.15742.5解题指导…1734. 18 Daffodil number1584.22.6参考答案4.18.1链接地址….…1584,22.7汉语翻译1754.18,2时空限制4159423 lead-to-I lead matchl764183题目内容1594,23.1链接地址4.184题日来源423.2时空限制4.18.5解题指导4.23.3题目内容.1774.18.6参考答案…423.4题目来源.1774.18.7汉语翻译∴…….1604.23.5解题指导4. 19 Error Correction4,23.6参考答案…4.19,1链接地址…1604237汉语翻译…1784.19.2时空限制1614.24 Windows Message Queuel794.193题目内容16l4,24.1链接地址179ⅤIIACM程序设计4.24.2时空限制1794.28.7汉语翻译1944.243题目内容1794.29Semi- Prime∴4244题目来源…180429.1链接地址….…1954.24.5解题指导l804,29.2时空限制4.24.6参考答案1804,293题目内容.4.24.7汉语翻译∴18l4.,294题目来源……1964.25 Language of Fatmouse182429.5解题思路251链接地址…∴182429.6参考答案1974.25.2时空限制1824,297汉语翻译l984.25.3题目内容1824, 30 Beautiful number4.254题目来源1834.30.1链接地址..1994.25.5解题思路1834.30.2吋空限制4.25.6参考答案183430.3题日内容…1994.25.7汉语翻译.1844.30.4题目米源1994.26 Palindromes ..w... 1854.30.5解题思路.1994.26.1链接地址…430.6参考答案4.26.2时空限制1854.30.7汉语翻译2004.26.3题目内容1854.31 Phone list………2014.264题日来源1864.31.1链接地址20l4.26.5解题思路.1864.312时空限制4.26.6参考答案1874.313题目内容2014.26.7汉语翻译1884.314题目来源2024.31.5解题思路4.27 Root of the problem4.27.l链接地址431.6参考答案…189431.7汉语翻译2054.27.,2时空限制..1894.32 Calendar4.273题目内容189432.1链接地址2064.274题目来源1894.32.2时空限制2064.27.5解题思路432.3题目内容…2064.27.6参考答案1904324题目来源2074.277汉语翻译…190432.5解题思路207e& Magic Squarel914.32.6参考答案2074.28.1链接地址191432.7汉语翻译2104.282时空限制191433 No Brainer2114.28.3题目内容191433.1链接地址……4.28.4题目来源19243.2时空限制.12114.28.5解题思路.1924.333题目内容.2114.28.6参考答案4.334题目来源…211录4.33.5解题思路2114.38.3题目内容.2264.33.6参考答案2124384题目来游2274.3.7汉语翻译…4.38.5解题思路….274.34 Quick change…438.6参考答案…4.34.1链接地址…2134.38.7汉语翻译…2284.34.2时空限制………2134.39 Champion of thc Swordsmanship..2294.34.3题目内容439.1链接地址4344题日来源4392时空限制4.34.5解题思路2144393题目内容2294.34.6参考答案…2144.394题目来溽4.34.7汉语翻译…215439.5解题思路4.35 Total amount2154396参考答案……230435.1链接地址.2154397汉语翻译………2314.35,2时空限制.2154 40 Doubles2314.353题目内容440.1链接地址…4354题目来源4.40.,2时空限制.4.35.5解题思路216440.3题目内容234.35.6参考答案217440.4题日来源…4.35.7汉语翻译……24194.40.5解题思路.2324.36 Electrical outlets4406参考答案2334.36.1链接地址440.7汉语翻译4.36.2时空限制20441 File Searching2344.36.3题目内容…441.1链接地址…4.36.4题目米源…221441.2时空限制…2344.36.5解题思路221441.3题目内容2344.36.6参考答案2214414题目来源……2364.367汉语翻译441.5解题思路.37 Speed Limit2234.41.6参考答案…4.37.1链接地址∴.223441.7汉语翻译239.37,2时空限制4.42 old bill2404373题日内容…442.1链接地址2404.374题目米源2244.42.2时空限制.…4.37.5解题思路….442.3题目内容4.37.6参考答案…2244.37.7汉语翻译….4424题目米源2414.38 Beat the Spread12.5解题思路.4.38.1链接地址226442.6参考答案……2414.38.2时空限制442.7汉语翻译.243IX