ACM-ICPC世界總決賽試題解析

內容概要

　　《ACM/ICPC世界總決賽試題解析（2004-2011年）》給出2004～2011年ACM國際大學生程序設計競賽世界總決賽的所有試題的解析。本書將總決賽試題按年度劃分，每一年度的總決賽試題為一章，而每一道試題作為一節(jié)。試題全部翻譯成中文，試題解析以解題策略為主軸，給出詳盡、細致的解析和帶有詳盡注解的程序代碼。這樣做使得本書可以面向各個階層的廣大讀者，不僅要讓編程高手從中受益，而且也要讓剛入門的同學能輕松地學習，有效地提高通過編程解決問題的能力。

作者簡介

吳永輝，博士，復旦大學計算機科學與工程系副教授，ACM—ICPC中國賽區(qū)指導委員會（ACM—ICPC Council China）成員，復旦大學ACM程序設計競賽隊教練。作者自2001年起連續(xù)帶隊進入ACM—ICPC世界總決賽，并取得過世界第6名的佳績。他的主要研究方向為數據庫，在《計算機研究與發(fā)展》、《軟件學報》以及重大學術會議上發(fā)表過多篇論文，參與翻譯出版了《數據通信與網絡》和《數據通信、計算機網絡與開放系統(tǒng)》。 王建德，著名的信息學奧林匹克競賽金牌教練，國務院特殊津貼專家，中學特級教師。他所輔導的學生在國際奧林匹克信息學競賽（IOI）中獲7金、3銀、2銅的優(yōu)異成績，先后出版了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?。?br />試題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 通信服務區(qū)（Zones）
第3章 2006 ACM-ICPC
世界總決賽試題解析
試題3-1 最小費用的飛機旅行
（Low Cost Air Travel）
試題3-2 訂購冰激凌薄餅片！
（Remember the A La Mode?。?br />試題3-3 穩(wěn)態(tài)的雕塑
（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 運費穩(wěn)定
（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?。?br />試題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 鎮(zhèn)紙（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 你心愛的采礦業(yè)（Mining Your Own Business）
試題8-9 瘋狂木乃伊
（Mummy Madness）
試題8-10 金字塔（Pyramids）
試題8-11 垃圾遷移
（Trash Removal）
……

章節(jié)摘錄

版權頁：   插圖：   試題解析 對于每個接收到的信號，根據信號的傳輸時間以及信號的傳輸速度可以確定信號的傳輸距離；再根據信號源的原位置和移動速度及方向就可以確定信號發(fā)出的位置。以信號發(fā)出的位置為圓心，信號的傳輸距離為半徑作一個圓，則接收者的可能位置位于圓周上。根據每個信號的傳輸時間、傳輸速度和方向均可以確定一個圓。如果所有的圓周有且只有一個公共點，那么就可以完全確定接收者的位置。如果所有的圓周不止一個公共點，就不能完全確定接收者的位置。如果圓周沒有公共點，就說明收到的信息有誤。 設信號源的原位置為（px，py），信號源的移動方向為degree，信號源的移動時間為ti，則信號源的移動距離dis等于ti*100。求信號發(fā)出的位置時，先將degree化為弧度，則信號發(fā)出的位置（ox，oy）=（px+dis*cos（degree），py+dis*sin（degree））。設接收信號的時間是t，則信號的傳輸時間為（t—ti），信號發(fā)出的位置離接收者的距離為350*（t—ti）。對于每個信號，以（ox，oy）為圓心，350*（t—ti）為半徑作一個圓，求所有圓的公共點。 實際上，只要從中任意選取兩個不重疊的圓就可以大致地把解的情況確定下來： 1）若兩個圓沒有交點，則無解。 2）若兩個圓相交，則只要檢查兩個交點是否在別的圓上即可。 3）若兩個圓相切，則也需要檢查一下切點是否在別的圓上。 如果找不到兩個不重疊的圓，則說明所有的圓都重疊在一起了，有多解。

編輯推薦

《華章教育?ACM-ICPC世界總決賽試題解析(2004-2011年)》給出的試題解析詳盡而細致，每道試題的程序代碼都帶有詳盡的注解。《華章教育?ACM-ICPC世界總決賽試題解析(2004-2011年)》可以面向各個層次的讀者，不僅可以讓編程高手受益良多，而且讓入門不久的同學也能比較輕松地學習，有效地提高通過編程解決問題的能力。在《華章教育?ACM-ICPC世界總決賽試題解析(2004-2011年)》中，所有的總決賽試題都給出中文的題面描述，有助于讀者在使用和訓練中對試題的理解?！度A章教育?ACM-ICPC世界總決賽試題解析(2004-2011年)》是備戰(zhàn)ACM—ICPC等各類程序設計競賽的指導教材，也是大學計算機專業(yè)數據結構課程和算法課程的優(yōu)秀參考書。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    ACM-ICPC世界總決賽試題解析 PDF格式下載

---