新書推薦:
《
失衡与重塑——百年变局下的中国与世界经济
》
售價:HK$
135.7
《
不被定义的年龄:积极年龄观让我们更快乐、健康、长寿
》
售價:HK$
79.4
《
南方谈话:邓小平在1992
》
售價:HK$
82.8
《
纷纭万端 : 近代中国的思想与社会
》
售價:HK$
109.8
《
中国古代文体形态研究(第四版)(中华当代学术著作辑要)
》
售價:HK$
172.5
《
朋党之争与北宋政治·大学问
》
售價:HK$
102.4
《
甲骨文丛书·波斯的中古时代(1040-1797年)
》
售價:HK$
90.9
《
以爱为名的支配
》
售價:HK$
64.4
|
編輯推薦: |
本书利用程序设计竞赛模式和在线评测系统的特点,采用经典例题讲解,将抽象的算法理论应用到解决程序设计的竞赛试题中,给算法设计和分析课程带来了新的生机。
|
內容簡介: |
随着大专院校参加ACMICPC热情的高涨,迫切需要有关介绍ACM国际大学生程序设计竞赛题解的书籍。本书在浙江大学和杭州电子科技大学的在线题库中精选了部分题目,进行分析和解答,比较详细且深入浅出地分析、讲解了解题的方法和用到的算法。精选的题目算法特征明显、具有代表性,题目类型包括基础编程与技巧、模拟算法、字符串处理、大整数运算、数据结构、搜索算法、动态规划、贪心、回溯算法、图论算法、几何和数学题。 本书可作为高等院校有关专业的本科和大专学生参加国际大学生程序设计竞赛的辅导教材,也可作为高等院校数据结构、CC++程序设计或算法设计与分析等相关课程的教学参考书。
|
目錄:
|
目录
第1章基础编程技巧题1
HDOJ1056HangOver1
HDOJ1735字数统计2
ZJU1058Currency Exchange6
ZJU1067Color Me Less8
ZJU1078Palindrom Numbers10
ZJU1090The Circumference of the Circle12
ZJU1095Humble Numbers13
ZJU1105FatMouses Tour16
ZJU1151Word Reversal17
ZJU1154Niven Numbers19
第2章模拟编程技巧题21
HDOJ1035Robot Motion21
HDOJ1172猜数字23
HDOJ2908Grey Area26
HDOJ4462Scaring the Birds28
HDOJ5933ArcSofts Office Rearrangement31
ZJU1003Crashing Balloon33
ZJU1006Do the Untwist36
ZJU1016Parencodings39
ZJU1039Number Game44
ZJU1042Ws Cipher48
ZJU1051A New Growth Industry52
ZJU1056The Worm Turns56
ZJU1057Undercut60ZJU1073Round and Round We Go62
ZJU1088System Overload66
ZJU1098Simple Computers70
ZJU1144Robbery73
ZJU1160Biorhythms78
第3章字符串处理技巧题81
HDOJ2895Edit distance81
ZJU1014Operand83
ZJU1044Index Generation89
ZJU1046Double Vision96
ZJU1050Start Up the Startup102
ZJU1109Language of FatMouse106
ZJU1116A WellFormed Problem110
ZJU1126BioInformatics115
ZJU11594873279118
第4章大整数运算技巧题123
HDOJ2940Hex Factorial123
ZJU1205Martian Addition124
ZJU1210Reciprocals127
ZJU1962How Many Fibs131
第5章基本数据结构题135
HDOJ3682To Be an Dream Architect135
ZJU1004Anagrams by Stack137
ZJU1061Web Navigation140ZJU1062Trees Made to Order142
ZJU1094Matrix Chain Multiplication147
ZJU1097Code the Tree152
ZOJ1156Unscrambling Images156
第6章搜索算法题161
HDOJ1010Tempter of the Bone161
HDOJ1016Prime Ring Problem164
HDOJ1175连连看167
HDOJ1241Oil Deposits172
HDOJ1242Rescue176
HDOJ1312Red and Black180
HDOJ1539Shredding Company182
HDOJ2266How Many Equations Can You Find186
HDOJ2952Counting Sheep188
HDOJ4403A very hard Aoshu problem190
ZJU1002Fire Net193
ZJU1008Gnome Tetravex196
ZOJ1047Image Perimeters201
ZJU1075Set Me205
ZJU1079Robotic Jigsaw208
ZJU1084Channel Allocation212
ZJU1091Knight Moves216
ZJU1136Multiple221
ZJU1148The Game225
第7章动态规划算法题229
HDOJ1087Super Jumping! Jumping! Jumping!229HDOJ1231最大连续子序列231
HDOJ1257最少拦截系统232
HDOJ1505City Game234
HDOJ1506Largest Rectangle in a Histogram236
HDOJ1520Anniversary Party238
HDOJ1864最大报销额240
HDOJ1950Bridging Signals242
HDOJ1978How Many Ways245
HDOJ2167Pebbles247
HDOJ2196Computer250
HDOJ2476String Painter253
HDOJ2602Bone Collector255
HDOJ2955Robberies257
HDOJ3001Travelling259
HDOJ3450Counting Sequences262
HDOJ3530Subsequence265
HDOJ3689Software CRC267
HDOJ4359Easy Tree DP?269
HDOJ4374One Hundred Layer271
HDOJ4571Travel in Time274
HDOJ5418Victor and World277
HDOJ5773The Allpurpose Zero280
第8章贪心算法题283
HDOJ1598Find the Most Comfortable Road283
HDOJ1789Doing Homework Again286
HDOJ1912Highway288HDOJ2037今年暑假不AC290
HDOJ2544最短路292
HDOJ2570迷瘴294
HDOJ2863Top Shooter296
HDOJ2904Warfare299
HDOJ3177Crixaliss Equipment303
HDOJ3697Selecting Courses305
HDOJ3730Chain308
HDOJ3979Monster309
HDOJ4221Greedy?312
HDOJ4296Buildings313
HDOJ4415Assassins Creed315
HDOJ4647Another Graph Game318
HDOJ4726Kias Calculation319
HDOJ4864Task322
HDOJ5821Ball324
第9章回溯算法题329
HDOJ1015Safecracker329
HDOJ1181变形课332
HDOJ1258Sum It Up334
HDOJ1456Transportation336
HDOJ1584蜘蛛牌339
HDOJ1627Krypton Factor341
HDOJ2553N皇后问题344
HDOJ4228Flooring Tiles346
HDOJ4499Cannon348HDOJ4536XCOM Enemy Unknown350
HDOJ4770Lights Against Dudely354
HDOJ5004KAMI358
HDOJ5355Cake362
HDOJ5723Abandoned Country365
HDOJ5887Herbs Gathering369
第10章图论算法题371
HDOJ2962Trucking371
HDOJ3018Ant Trip375
ZJU1060Sorting It All Out377
ZJU1186Street Directions383
ZJU1197Sorting Slides388
ZJU1203Swordfish1392
ZJU1221Risk397
ZJU1232Adventure of Super Mario400
ZJU1542Network405
ZJU1935XYZZY408
ZJU2797106 Miles to Chicago411
ZJU2832Efficient Codes414
ZJU3010The Lamp Game417
第11章几何题423
HDOJ2907Diamond Dealer423
ZJU1010Area427
ZJU1030Farmland433
ZJU1032Area 2440ZJU1041Transmitters444
ZJU1081Points Within447
ZJU1104Leaps Tall Buildings452
ZJU1114Problem Bee456
ZJU1123Triangle Encapsulation460
ZJU1128Atlantis464
ZJU1158Treasure Hunt469
第12章数学题477
ZJU1007Numerical Summation of a Series477
ZJU1026Modular Multiplication of Polynomials481
ZJU1110Dick and Jane484
ZJU1125Floating Point Numbers486
ZJU1133Smith Numbers489
参考文献493
|
內容試閱:
|
编审委员会
顾问: 李澎林潘海涵
主任: 张聚
副主任: 宋国琴蔡铁峰赵端阳朱新芬
编委: 按姓氏笔画为序
王洁王荃冯志林成杏梅
刘均刘文程刘勤贤吕圣军
杜丰杜树旺吴艳何文秀
应亚萍张建奇陈伟杰郑利君
宗晓晓赵建锋郝平金海溶
姚晶晶徐欧官郭伟青曹平
曹祁傅永峰鲍卫兵潘建电子信息技术和计算机软件等技术的快速发展,深刻地影响着人们的生产、生活、学习和思想观念。当前,以工业4.0、两化深度融合、智能制造和互联网 为代表的新一代产业和技术革命,把信息时代的发展推到一个对于国家经济和社会发展影响更为深远的新阶段。
在新的产业和技术革命的背景下,社会对高校人才的培养模式、教学改革以及高校的转型发展都提出了新的要求。2015年,浙江省启动应用型高校示范学校建设。通过面向应用型高校的转型建设增强学生的就业创业和实践能力,提高学校服务区域经济社会发展和创新驱动发展的能力。通过坚持面向需求、产教融合、开放办学、共同发展的高校发展理念,围绕一流的应用型大学建设和一流的应用型人才培养目标,我们做了一系列的探索和实践,取得了明显实效。
作为应用型高校转型建设的重要举措之一和应用型人才培养的主要载体,本套规划教材着眼于应用型、工程型人才的培养和实践能力的提高,是在应用型高校建设中一系列人才培养工作的探索和实践的总结和提炼。在学校和学院领导的直接指导和关怀下,编委会依据社会对电子信息和计算机学科人才素质和能力的需求,充分汲取国内外相关教材的优势和特点,组织具有丰富教学与实践经验的双师型高校教师成立编委会,编写了这套教材。
本套系列教材具有以下几个特点:
1 教材具有创新性。本系列教材内容体现了基本技术和近年来的新技术,注重技术方法、仿真例子和实际应用案例的结合。
2 教材注重应用性。避免复杂的理论推导,通俗易懂,便于学习、参考和应用。注重理论和实践的结合,加强应用型知识的讲解。3 教材具有示范性。教材中体现的应用型教学理念、知识体系和实施方案,在电子信息类和计算机类人才的培养以及应用型高校相关专业人才的培养中具有广泛的辐射性和示范性。
4 教材具有多样性。本系列教材既包括基本理论和技术方法的课程,也包括相应的实验和技能课程,以及大型综合实践性学科竞赛方面的课程。注重课程之间的交叉和衔接,从不同角度培养学生的应用和实践能力。
5 本套教材的编著者具有丰富的教学和实践经验。他们大多是从事一线教学和指导的、具有丰富经验的双师型高校教师。他们多年的教学心得为本教材的高质量出版提供了有力保障。
本套系列教材的出版得到浙江省教育厅相关部门、浙江工业大学教务处和之江学院领导以及清华大学出版社的大力支持和广大骨干教师的积极参与,得到学校教学改革和重点教材建设项目的资助,在此一并表示衷心的感谢。
希望本套教材的出版能够在转变教学思想,推动教学改革,更新知识体系,增强学生实践能力,培养应用型人才等方面发挥重要作用,并且为应用型高校的转型建设提供课程支撑。由于电子信息技术和计算机技术的发展日新月异,以及各方面条件的限制,本套教材难免存在不足之处,敬请专家和广大师生批评指正。
高等学校计算机类创新与应用型规划教材编审委员会
2016年10月ACM国际大学生程序设计竞赛ACM International Collegiate Programming Contest, ACMICPC由国际计算机界历史悠久、颇具权威性的组织ACMAssociation for Computing Machinery,美国计算机协会主办,是世界上公认的规模最大、水平最高的国际大学生程序设计竞赛,旨在使大学生运用计算机充分展示自己分析问题和解决问题的能力。1970年,美国德克萨斯A&M大学举办了首次区域竞赛,从而拉开了国际大学生程序设计竞赛的序幕。1977年,在ACM计算机科学会议期间举办了首次总决赛,并演变成为一年一届的多国参与的国际性比赛。因历届竞赛都荟萃了世界各大洲的精英,云集了计算机界的希望之星,而受到国际知名大学的重视,并受到全世界众多著名计算机公司的高度关注,成为世界各国大学生最具影响力的国际级计算机类的赛事。
此项赛事的主办目的不单是培养参赛选手的创造力、团队合作精神以及他们在软件程序开发过程中的创新意识,同时也是检测选手们在压力下进行开发活动的能力。因此,ACM国际大学生程序设计竞赛是参赛选手展示计算机才华的广阔舞台,是大学计算机教育成果的直接体现,是信息企业与世界顶尖计算机人才对话的最好机会。
ACM国际大学生程序设计竞赛1996年进入中国,上海交通大学作为我国内地高校最早的参赛队之一,曾7次进军总决赛,并于2002年将ACM金杯首次带到亚洲,打破了几十年来欧美国家对这一赛事的绝对统治地位,更震惊了世界。
2005年4月6日,在上海举办的第29届ACM国际大学生程序设计竞赛总决赛中,上海交通大学团队成功解答8道题,以一题的领先优势力克来自世界六大洲29个国家和地区的78支参赛队,捧获世界上最聪明的人的冠军奖杯。时隔3年,ACM全球总决赛冠军奖杯再次回到上海交通大学。2018年4月,ACMICPC在北京举行,由北京大学承办,而北京大学在最后时刻完成G题夺得金牌。
国际ACM比赛是世界上规模最大、历史最长、影响最深的全球性计算机专业竞赛,它要求每一名队员不仅具有扎实的数学功底、非凡的算法设计能力、娴熟的编程技巧,而且具备很好的协作精神、稳定的心理素质和快速的临场应变能力。
为了帮助各个大专院校的大学生们了解国际大学生程序设计竞赛,了解其程序设计的方法,提高参与校级、省级和亚洲区国际大学生程序设计竞赛的兴趣,特编写本书。
全书共12章。
第1章: 基础编程技巧题。主要是比较容易的题目,也称简单题,尤其适合刚开始熟悉ACM大学生程序设计竞赛题的同学。通过这些题目的练习,熟悉数据的输入、输出格式,基本编程方法,在线提交系统的使用,常见错误及其对策。
第2章: 模拟编程技巧题。根据题目的要求逐步实现目标,虽然没有经典的算法可以使用,正确理解题目是关键的要素。例如,题目Parencodings等。
第3章: 字符串处理技巧题。主要是字符串的处理,这也是考察参赛者细心的一类题目,需要对各种情况进行仔细分析,如题目A WellFormed Problem等。
第4章: 大整数运算技巧题,如题目Martian Addition、Reciprocals等。
第5章: 基本数据结构题,如题目Trees Made to Order等。
第6章: 搜索算法题。通常有深度优先搜索算法和广度优先搜索算法,如The Game等。
第7章: 动态规划算法题。这些题目使用动态规划算法,会使运行时间较短、效率较高,如题目City Game和How Many Ways等。
第8章: 贪心算法题。使用贪心算法的题目,如题目Highway和Warfare等。
第9章: 回溯算法题。使用回溯算法的题目,如题目Anagrams by Stack等。
第10章: 图论算法题。主要包含拓扑排序、Floyd算法和二分图等,如Street Directions等。
第11章: 几何题。主要是几何计算题目,如题目Farmland等。
第12章: 数学题。主要是数学计算题目,如题目Smith Numbers等。
本部分通过大量实例介绍了竞赛中常用的算法,并对如何灵活应用这些算法进行了比较详细的分析和深入浅出的讲解。
本书所用的语言是CC,并在MinGW Developer Studio或Code Blocks编译器中调试通过。在运行时间和内存占用的性能方面,C并不比C语言优越,只是C有丰富的模板库函数,输入输出语句简单,编写的代码看起来格式更工整而已。在有大量输入输出数据的题目中,书中会特别提醒读者需要使用C语言的输入输出。
显然,Accepted是我们的目标,算法是我们不断探索的道路,好的算法让我们容易达到目标。本书中的算法,虽然作者经过反复斟酌,不断优化和简化,但仍然不敢认为是最优的。因为对算法的探索,正如金庸笔下的大侠们苦练武功一样,是没有止境的。
本书中虽然描述的是ACM国际大学生程序设计竞赛中最基本的算法,但它也已经超出了一般本科教科书讲授的范围。清华大学计算机科学与技术系博士生导师、国际信息学奥林匹克中国队总教练吴文虎教授认为,算法的确是艺术,艺术与科学是相通的,都会给人以美的享受。①希望读者能从本书中体会到这一点。
本书可以作为高等院校有关专业的本科和大专学生参加国际大学生程序设计竞赛的辅导教材,或者作为高等院校数据结构、CC程序设计或算法设计与分析等相关课程的教学参考书,旨在培养和提高学生参加ACM国际大学生程序设计竞赛的兴趣。
本书获得浙江省高等教育课堂教学改革kg2013524,kg20160558、浙江工业大学精品课程2015年、浙江工业大学首届SPOC课程建设项目2016年和绍兴市精品课程建设项目2015年的大力支持,并得到清华大学出版社编辑张玥、常建丽的热情帮助,在此表示感谢。
由于作者水平所限,书中难免有不足之处,恳请广大读者批评指正。
作者
2019年4月于杭州
①吴文虎,孙贺.程序设计中的组合数学[M].北京: 清华大学出版社,2005.
|
|