ACM-ICPC世界总决赛试题解析

出版时间：2012-8  出版社：机械工业出版社  作者：吴永辉,王建德  页数：371  
Tag标签：无  

内容概要

　　《ACM/ICPC世界总决赛试题解析（2004-2011年）》给出2004～2011年ACM国际大学生程序设计竞赛世界总决赛的所有试题的解析。本书将总决赛试题按年度划分，每一年度的总决赛试题为一章，而每一道试题作为一节。试题全部翻译成中文，试题解析以解题策略为主轴，给出详尽、细致的解析和带有详尽注解的程序代码。这样做使得本书可以面向各个阶层的广大读者，不仅要让编程高手从中受益，而且也要让刚入门的同学能轻松地学习，有效地提高通过编程解决问题的能力。

作者简介

吴永辉，博士，复旦大学计算机科学与工程系副教授，ACM—ICPC中国赛区指导委员会（ACM—ICPC Council China）成员，复旦大学ACM程序设计竞赛队教练。作者自2001年起连续带队进入ACM—ICPC世界总决赛，并取得过世界第6名的佳绩。他的主要研究方向为数据库，在《计算机研究与发展》、《软件学报》以及重大学术会议上发表过多篇论文，参与翻译出版了《数据通信与网络》和《数据通信、计算机网络与开放系统》。 王建德，著名的信息学奥林匹克竞赛金牌教练，国务院特殊津贴专家，中学特级教师。他所辅导的学生在国际奥林匹克信息学竞赛（IOI）中获7金、3银、2铜的优异成绩，先后出版了24本关于程序设计和算法的学术专著，其中《实用算法的分析与程序设计》广受好评，长期以来是国内各类程序设计竞赛的必备教程。

书籍目录

前言
第1章 2004 ACM-ICPC
世界总决赛试题解析
试题1-1 蚂蚁Carl（Carl the Ant）
试题1-2 直升机机场（Heliport）
试题1-3 六面视图
（Image Is Everything）
试题1-4 危险的布拉格城
（Insecure in Prague）
试题1-5 相交的时间段
（Intersecting Dates）
试题1-6 拼接地图
（Merging Maps）
试题1-7 导航（Navigation）
试题1-8 道路绿化
（Tree-Lined Streets）
试题1-9 悬吊！（Suspense！）
试题1-10 地面飞行控制中心
（Air Traffic Control）
第2章 2005 ACM-ICPC
世界总决赛试题解析
试题2-1 眼球弯曲
（Eyeball Benders）
试题2-2 GSM网络的简化模型
（Simplified GSM Network）
试题2-3 裁判员的旅行问题（The
Traveling Judges Problem）
试题2-4 纸牌戏法
（cNteSahruPfefrlefe）
试题2-5 阳光普照
（Lots of Sunlight）
试题2-6 交叉的街道
（Crossing Streets）
试题2-7 铺满平面
（Tiling the Plane）
试题2-8 长城游戏
（The Great Wall Game）
试题2-9 讨论会（Workshops）
试题2-10 通信服务区（Zones）
第3章 2006 ACM-ICPC
世界总决赛试题解析
试题3-1 最小费用的飞机旅行
（Low Cost Air Travel）
试题3-2 订购冰激凌薄饼片！
（Remember the A La Mode！）
试题3-3 稳态的雕塑
（Ars Longa）
试题3-4 二段数（Bipartite Numbers）
试题3-5 压缩二进制消息
（Bit Compressor）
试题3-6 构造一个时钟
（Building a Clock）
试题3-7 朝圣（Pilgrimage）
试题3-8 口袋数（Pockets）
试题3-9 隔离度
（Degrees of Separation）
试题3-10 通信路线（Routing）
第4章 2007 ACM-ICPC
世界总决赛试题解析
试题4-1 基因计算（Consanguine Calculations）
试题4-2 集装箱（Containers）
试题4-3 宏大的平面图
（Grand Pix）
试题4-4 提花电路
（Jacquard Circuits）
试题4-5 领取行李
（Collecting Luggage）
试题4-6 小球游戏
（Marble Game）
试题4-7 网络（Network）
试题4-8 可视的屋顶部分
（Raising the Roof）
试题4-9 水箱（Water Tanks）
试题4-10 隧道（Tunnels）
第5章 2008 ACM-ICPC
世界总决赛试题解析
试题5-1 空调机械公司（Air
Conditioning Machinery）
试题5-2 都是整数解（Always an Integer）
试题5-3 传送带（Conveyor Belt）
试题5-4 猎犬追兔游戏（The Hare
and the Hounds）
试题5-5 哈夫曼编码
（Huffman Codes）
试题5-6 Glenbow博物馆
（Glenbow Museum）
试题5-7 神经网络（Net Loss）
试题5-8 画家（Painter）
试题5-9 可疑的密码（Password Suspects）
试题5-10 天空是极限
（The Sky is the Limit）
试题5-11 蒸汽压路机
（Steam Roller）
第6章 2009 ACM-ICPC
世界总决赛试题解析
试题6-1 一个周全的调度
（A Careful Approach）
试题6-2 判别电路故障
（My Bad）
试题6-3 蚂蚁Carl又回来了
（The Return of Carl）
试题6-4 管道内径
（Conduit Packing）
试题6-5 运费稳定
（Fare and Balanced）
试题6-6 防鹿围栏
（Deer-Proof Fence）
试题6-7 纸牌的房屋
（House of Cards）
试题6-8 多数部长的投票（The
Ministers' Major Mess）
试题6-9 弹簧撑杆
（Struts and Springs）
试题6-10 地铁的时间估算
（Subway Timing）
试题6-11 后缀替换语法
（Suffix-Replacement
Grammars）
第7章 2010 ACM-ICPC
世界总决赛试题解析
试题7-1 求值apl表达式！
（APL Lives！）
试题7-2 条形码（Barcodes）
试题7-3 生物机器人的轨迹
（Tracking Bio-bots）
试题7-4 城堡（Castles）
试题7-5 渠道（Channel）
试题7-6 等高线地图
（Contour Mapping）
试题7-7 岛屿（The Islands）
试题7-8 下雨（Rain）
试题7-9 冰上机器人
（Robots on Ice）
试题7-10 分享巧克力
（Sharing Chocolate）
试题7-11 镇纸（Paperweight）
第8章 2011 ACM-ICPC
世界总决赛试题解析
试题8-1 加或乘
（To Add or to Multiply）
试题8-2 仿射的混乱
（Affine Mess）
试题8-3 古代的象形符号
（Ancient Messages）
试题8-4 芯片的难题
（Chips Challenge）
试题8-5 咖啡枢纽
（Coffee Central）
试题8-6 机器公司
（Machine Works）
试题8-7 魔杖（Magic Sticks）
试题8-8 你心爱的采矿业（Mining Your Own Business）
试题8-9 疯狂木乃伊
（Mummy Madness）
试题8-10 金字塔（Pyramids）
试题8-11 垃圾迁移
（Trash Removal）
……

章节摘录

版权页：   插图：   试题解析 对于每个接收到的信号，根据信号的传输时间以及信号的传输速度可以确定信号的传输距离；再根据信号源的原位置和移动速度及方向就可以确定信号发出的位置。以信号发出的位置为圆心，信号的传输距离为半径作一个圆，则接收者的可能位置位于圆周上。根据每个信号的传输时间、传输速度和方向均可以确定一个圆。如果所有的圆周有且只有一个公共点，那么就可以完全确定接收者的位置。如果所有的圆周不止一个公共点，就不能完全确定接收者的位置。如果圆周没有公共点，就说明收到的信息有误。 设信号源的原位置为（px，py），信号源的移动方向为degree，信号源的移动时间为ti，则信号源的移动距离dis等于ti*100。求信号发出的位置时，先将degree化为弧度，则信号发出的位置（ox，oy）=（px+dis*cos（degree），py+dis*sin（degree））。设接收信号的时间是t，则信号的传输时间为（t—ti），信号发出的位置离接收者的距离为350*（t—ti）。对于每个信号，以（ox，oy）为圆心，350*（t—ti）为半径作一个圆，求所有圆的公共点。 实际上，只要从中任意选取两个不重叠的圆就可以大致地把解的情况确定下来： 1）若两个圆没有交点，则无解。 2）若两个圆相交，则只要检查两个交点是否在别的圆上即可。 3）若两个圆相切，则也需要检查一下切点是否在别的圆上。 如果找不到两个不重叠的圆，则说明所有的圆都重叠在一起了，有多解。

编辑推荐

《华章教育•ACM-ICPC世界总决赛试题解析(2004-2011年)》给出的试题解析详尽而细致，每道试题的程序代码都带有详尽的注解。《华章教育•ACM-ICPC世界总决赛试题解析(2004-2011年)》可以面向各个层次的读者，不仅可以让编程高手受益良多，而且让入门不久的同学也能比较轻松地学习，有效地提高通过编程解决问题的能力。在《华章教育•ACM-ICPC世界总决赛试题解析(2004-2011年)》中，所有的总决赛试题都给出中文的题面描述，有助于读者在使用和训练中对试题的理解。《华章教育•ACM-ICPC世界总决赛试题解析(2004-2011年)》是备战ACM—ICPC等各类程序设计竞赛的指导教材，也是大学计算机专业数据结构课程和算法课程的优秀参考书。

用户评论 (总计23条)

•   ACM世界总决赛题目。
•   虽然已经毕业多年，但是作为一个程序设计人员，灵活的头脑和数学的思维是不能少的，买来拿来锻炼思维用的
•   好， 竞赛同学的参考书，题目全，你值得拥有
•   提高智商，从算法开始。
•   这本书不错的，应该看一下
•   很好的书，很适合提高算法设计的能力。
•   好书经典书好书经典书
•   有点深 最近才开始看算法
•   今年刚出来的，貌似不错很多人推荐
•   好书，比多点难题，拓展思维用的
•   真心难，数据结构和算法不好的先不要买，买了也是一头雾水！
•   内容比较新，书的整体质量很好。 有参考价值，值得一读。
•   ACM世界总决赛的试题解析，让我对于final中的解题思路有了一些实际的了解。
•   期待质量好~
•   看来还是买早了，建议有一定实力的人再买
•   书的厚度超过我的想象，相比这个价钱来说还是蛮不错的。题解都很详细、很完整，分析也很到位。另外发现世界总决赛的题也不是那么地难，有一些我这种菜鸟也会做的~~O(∩_∩)O~
•   适合ACM/ICPC的选手仔细阅读。可惜带源代码的光盘。
•   如果有光盘就好了，分析的同时应该有应用就好了，举一反三，年龄层越大书越没有想象力了，我还是喜欢当年的ioi的教辅书籍。
•   不错的书~~！喜欢！
•   很厚实，纸很好，还没看
•   纸质很好看起来很舒服，值得拥有
•   书不错，全面，提高思维能力。
•   内容十分充实。也有许多知识点的讲解。