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

章节摘录

版权页：   插图：   试题解析 对于每个接收到的信号，根据信号的传输时间以及信号的传输速度可以确定信号的传输距离；再根据信号源的原位置和移动速度及方向就可以确定信号发出的位置。以信号发出的位置为圆心，信号的传输距离为半径作一个圆，则接收者的可能位置位于圆周上。根据每个信号的传输时间、传输速度和方向均可以确定一个圆。如果所有的圆周有且只有一个公共点，那么就可以完全确定接收者的位置。如果所有的圆周不止一个公共点，就不能完全确定接收者的位置。如果圆周没有公共点，就说明收到的信息有误。 设信号源的原位置为（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中国赛区指导委员会（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）

编辑推荐

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

作者简介

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

图书封面

---

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

---