ACM国际大学生程序设计竞赛

2012-12  

清华大学出版社  

俞勇 编  

623  

878000  

无  

　　ACM国际大学生程序设计竞赛（ACM-ICPC）是国际上公认的水平最高、规模最大、影响最深的计算机专业竞赛，目前全球参与人数达20多万。《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书：题目与解读》作者将16年的教练经验与积累撰写成本系列丛书，全面、深入而系统地将ACM-ICPC展现给读者、本系列丛书包括《ACM国际大学生程序设计竞赛：知识与入门》、《ACM国际大学生程序设计竞赛：算法与实现》、《ACM国际大学生程序设计竞赛：题目与解读》、《ACM国际大学生程序设计竞赛：比赛与思考》等4册，其中《ACM国际大学生程序设计竞赛：知识与入门》介绍了ACM-ICPC的知识及其分类、进阶与角色、在线评测系统；《ACM国际大学生程序设计竞赛：算法与实现》介绍了ACM-ICPC算法分类、实现及索引；《ACM国际大学生程序设计竞赛：题目与解读》为各类算法配备经典例题及题库，并提供解题思路；《ACM国际大学生程序设计竞赛：比赛与思考》介绍了上海交通大学ACM-ICPC的训练及比赛，包括训练札记、赛场风云、赛季纵横、冠军之路、峥嵘岁月。
　　《ACM国际大学生程序设计竞赛（ACM-ICPC）系列丛书：题目与解读》适用于参加ACM国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奥林匹克竞赛的中学生也很有指导价值。同时，作为程序设计、数据结构、算法等相关课程的拓展与提升，本丛书也是难得的教学辅助读物。

　　俞勇，1961年生于上海，现为上海交通大学教授、博士生导师。1986年毕业于华东师范大学计算机科学系，获硕士学位。毕业后在上海交通大学任教至今，，1996年至今担任上海交通大学ACM国际大学生程序设计竞赛领队、主教练，3次率队夺得ACM国际大学生程序设计竞赛世界冠军，上海交通大学成为该赛事亚洲第一个获得冠军、全球第三个“三冠王”的大学，2002、2012年相继获得“杰出教练奖”、“功勋教练奖”。
　　俞勇教授曾主编教材或著作4本、译著3本，先后主持教育部教育教学改革项目2项，获得国家级和上海市教学成果奖7项，上海市优秀教材奖2项，并为国家精品课程“数据结构”、上海市“程序设计类基础课程教学团队”主持人、、从事Web搜索与挖掘研究，先后主持国家自然科学基金、863计划等十余项，发表重要国际会议和期刊学术论文百余篇，
　　俞勇教授曾获得国务院特殊津贴、“全国师德标兵”、“宝钢优秀教师特等奖”、“上海市教学名师”、“上海市五一劳动奖章”、“上海市模范教师”、“上海交通大学校长奖”、“上海交通大学最受学生欢迎教师”、“上海交通大学最受研究生欢迎导师”等荣誉。曾被中央电视台新闻联播、上海教育台、光明日报、文汇报等十多家媒体报道。

第一部分 例题精讲
第1章 数学
1.1 概率
Coupons
Generator
1.2 代数
1.2.1 Polya
Arifin Dhaka （First Love Part2）
1.2.2 矩阵
Tower
XX Language
1.2.3 线性方程组
Ars Longa
1.2.4 线性规划
Expensive Drink
1.3 组合
1.3.1 基本排列组合
The Unreal Tournament
1.3.2 容斥原理
Jackpot
The Almost Lucky Numbers
1.3.3 生成函数
Vasva's Dad
1.3.4 生成树计数
Organising the Organisation
1.3.5 综合
Hero of Our Time
Permutation
1.4博弈
Battle for the Ring
Fool's Game
Points Game
1.5 数论
1.5.1 模线性方程
Integer Sequences
1.5.2 欧几里得
Wizards
1.5.3 欧拉定理
Strange Limit
1.5.4 欧拉函数
GCD Determinant
1.5.5 平方剩余
Square Root
1.5.6 原根
Fermat's Last Theorem
1.5.7 整除与剩余
Brute-Force Algorithm
Integral Roots
VMan's Problem
1.5.8 中国剩余定理
Voyager 1
1.6 分析
Bridge
第2章 数据结构
2.1 优先队列
The Lazy Programmer
2.2 线性表
Book Pile
2.3 散列表
Censored!
6.1.5 Rabin-Karp
Square Palindrome
6.2 最近公共祖先
The Merchant
Transportation Network
Design the city
6.3 2-SAT
Game with cards
Cipher
6.4 快速傅立叶变换
K-neighbor substrings
第二部分 题库
4 Values Whose Sum is 0
8G Island
A Binary Apple Tree
A Dinner with
Schwarzenegger! ! !
A Foldy but a Goody
A Game with Colored Balls
A Line Painting
A Secret Book
A Simple Pendulum
Abelian Groups
Aerodynamic
Again Palindrome
Aaainst Mammoths
Air Conditioning
Machinery
All Your Bases Belong to Us
Alphabet
Alternating Sum of Digits
Always an Integer
Ampluplulic Carbon
Molecules
Anansi's Cobweb
Anaent decoration
Angry Teacher
Anniversary Party
Another Chocolate Maniac
Another Minimum
Spamung Tree
Antsll
Ants
Apple or Doughnut
Archipelago
Area 51
Arrays
Art ofWar
Asteroids
Astronomy
Autocompletion
Automaton
B-Station
Balance
Barisal Stadium
Battle
Battle of the Triangle
Battle
Be a Smart Raftsman
Be Wary of Roses
Beloved Sons
Best Cow Line, Gold
Bigger is Better
Binary Lexicographic
Sequence
Bingo
Bishops
Bit Compressor
Bitmap
Black & White
……

版权页： 插图： 【题意概述】 有N个守卫站成一个圈，每个守卫需要ai种奖品，两个相邻的守卫不能有一个奖品相同。求最少需要多少种奖品。 数据范围：N≤105。 【算法分析】 首先，如果N是偶数的话，显然答案就是任意两个相邻的人ai的和的最大值。 如果N是奇数，我们先二分一个答案M，表示有M种奖品，下面考虑M种奖品是否可行。先把奖品标号为1..M，一个比较显然的贪心思路： 第一个人首先选取1..A1，剩余的守卫按编号从小到大依次取，编号为偶数的守卫尽量取不与前一个人造成矛盾的前提下编号小的奖品，编号为奇数的守卫尽量选不与前一个人造成矛盾的前提下编号大的奖品。如果当N个人都成功取完，并且第N个人和第1个人的奖品没冲突，则是一种可行方案。 因此判断可行性可以做O（N），最后还要乘上二分的复杂度。 【知识点】 二分，贪心 Body Check 赛区／题库：ZOJ 3334 难度：★★★☆☆ 【题意概述】 由于流感爆发，所以医院有很多人排队体检。医院中有m（m≤1000）个医生。医生只能同时工作，因为如果有人在休息那么工作的医生就会觉得不公平。但也可以让一个医生工作，别的医生都在监视他所以他也不敢偷懒。 现在有n（n≤1000）个病人在排队体检，每个人需要不同的时间Ti（Ti≤106）来完成体检。一个医生可以只检查病人的一部分，然后留给下一个医生继续。也就是说，一个人可以在任意时间找任意医生完成任意部分的检查，只要满足：一个人不能同时被两个医生检查，一个医生也不能同时检查两个人。 给出医生以及病人的人数以及每个病人所需的时间，求完成所有任务的最短时间。 【算法分析】 由于一个人可以在任意时间找任意医生完成任意部分的检查，所以可以将每个人需要的检查时间均分给每个医生。 但是答案并非每个人的时间求和除以医生数，因为一个人不能同时被两个医生检查，所以当有某个病人的时间超过时间求和除以医生数时就不能按这样分配，该病人必然是前一部分时间被均分，后一部分时间让一个医生单独工作完成检查。

《ACM国际大学生程序设计竞赛:题目与解读》适用于参加ACM国际大学生程序设计竞赛的本科生和研究生，对参加青少年信息学奧林匹克竞赛的中学生也很有指导价值。同时，作为程序设计、数据结构、算法等相关课程的拓展与提升，本丛书也是难得的教学辅助读物。

无

ACM国际大学生程序设计竞赛 PDF格式下载

质量好，价格便宜，送货很及时

是一本学习acm-icpc的好书，关键是题多

给五星的理由是题目量好多，虽然没有代码，但是解题思路和分类足以满足自学者的需求。。

内容太糙，太多，太杂 没有详细讲解，印刷错误多，影响阅读心情。

这套书不错，推荐大家买呀

解题思路是最重要的。这本书对于这方面的提高有些帮助。

当当现在真烂，大家别再用当当了，上次买本视频精讲还tm不发光盘，买本习题明明说有答案的到现在我都找不着答案，懒得找他了，以后大家别在当当买了，往日当当已死。

适合ACM的学生使用，通过例题讲解

题目略难 不过好歹是为了国际程序大赛备战嘛 书本身还是很实用的！

这本树内容很棒！含金量很高的题目！只有思路解法不提共源代码！‘起点很高！

程序代码连注释都没有，

书很不错 超级厚 内容超多 适合做头脑风暴

书的内容还是可以的，就是纸张太薄了，值得一看

题目很全，很有深度，只可惜没有代码作参考，哪怕是伪代码

这本书不错，如果有部分核心代码就更好了。