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

前言

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