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

內(nèi)容概要

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

作者簡(jiǎn)介

吳永輝，博士，復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)與工程系副教授，ACM—ICPC中國(guó)賽區(qū)指導(dǎo)委員會(huì)（ACM—ICPC Council China）成員，復(fù)旦大學(xué)ACM程序設(shè)計(jì)競(jìng)賽隊(duì)教練。作者自2001年起連續(xù)帶隊(duì)進(jìn)入ACM—ICPC世界總決賽，并取得過(guò)世界第6名的佳績(jī)。他的主要研究方向?yàn)閿?shù)據(jù)庫(kù)，在《計(jì)算機(jī)研究與發(fā)展》、《軟件學(xué)報(bào)》以及重大學(xué)術(shù)會(huì)議上發(fā)表過(guò)多篇論文，參與翻譯出版了《數(shù)據(jù)通信與網(wǎng)絡(luò)》和《數(shù)據(jù)通信、計(jì)算機(jī)網(wǎng)絡(luò)與開(kāi)放系統(tǒng)》。 王建德，著名的信息學(xué)奧林匹克競(jìng)賽金牌教練，國(guó)務(wù)院特殊津貼專家，中學(xué)特級(jí)教師。他所輔導(dǎo)的學(xué)生在國(guó)際奧林匹克信息學(xué)競(jìng)賽（IOI）中獲7金、3銀、2銅的優(yōu)異成績(jī)，先后出版了24本關(guān)于程序設(shè)計(jì)和算法的學(xué)術(shù)專著，其中《實(shí)用算法的分析與程序設(shè)計(jì)》廣受好評(píng)，長(zhǎng)期以來(lái)是國(guó)內(nèi)各類程序設(shè)計(jì)競(jìng)賽的必備教程。

書(shū)籍目錄

前言
第1章 2004 ACM-ICPC
世界總決賽試題解析
試題1-1 螞蟻Carl（Carl the Ant）
試題1-2 直升機(jī)機(jī)場(chǎng)（Heliport）
試題1-3 六面視圖
（Image Is Everything）
試題1-4 危險(xiǎn)的布拉格城
（Insecure in Prague）
試題1-5 相交的時(shí)間段
（Intersecting Dates）
試題1-6 拼接地圖
（Merging Maps）
試題1-7 導(dǎo)航（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網(wǎng)絡(luò)的簡(jiǎn)化模型
（Simplified GSM Network）
試題2-3 裁判員的旅行問(wèn)題（The
Traveling Judges Problem）
試題2-4 紙牌戲法
（cNteSahruPfefrlefe）
試題2-5 陽(yáng)光普照
（Lots of Sunlight）
試題2-6 交叉的街道
（Crossing Streets）
試題2-7 鋪滿平面
（Tiling the Plane）
試題2-8 長(zhǎng)城游戲
（The Great Wall Game）
試題2-9 討論會(huì)（Workshops）
試題2-10 通信服務(wù)區(qū)（Zones）
第3章 2006 ACM-ICPC
世界總決賽試題解析
試題3-1 最小費(fèi)用的飛機(jī)旅行
（Low Cost Air Travel）
試題3-2 訂購(gòu)冰激凌薄餅片！
（Remember the A La Mode?。?br />試題3-3 穩(wěn)態(tài)的雕塑
（Ars Longa）
試題3-4 二段數(shù)（Bipartite Numbers）
試題3-5 壓縮二進(jìn)制消息
（Bit Compressor）
試題3-6 構(gòu)造一個(gè)時(shí)鐘
（Building a Clock）
試題3-7 朝圣（Pilgrimage）
試題3-8 口袋數(shù)（Pockets）
試題3-9 隔離度
（Degrees of Separation）
試題3-10 通信路線（Routing）
第4章 2007 ACM-ICPC
世界總決賽試題解析
試題4-1 基因計(jì)算（Consanguine Calculations）
試題4-2 集裝箱（Containers）
試題4-3 宏大的平面圖
（Grand Pix）
試題4-4 提花電路
（Jacquard Circuits）
試題4-5 領(lǐng)取行李
（Collecting Luggage）
試題4-6 小球游戲
（Marble Game）
試題4-7 網(wǎng)絡(luò)（Network）
試題4-8 可視的屋頂部分
（Raising the Roof）
試題4-9 水箱（Water Tanks）
試題4-10 隧道（Tunnels）
第5章 2008 ACM-ICPC
世界總決賽試題解析
試題5-1 空調(diào)機(jī)械公司（Air
Conditioning Machinery）
試題5-2 都是整數(shù)解（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 神經(jīng)網(wǎng)絡(luò)（Net Loss）
試題5-8 畫(huà)家（Painter）
試題5-9 可疑的密碼（Password Suspects）
試題5-10 天空是極限
（The Sky is the Limit）
試題5-11 蒸汽壓路機(jī)
（Steam Roller）
第6章 2009 ACM-ICPC
世界總決賽試題解析
試題6-1 一個(gè)周全的調(diào)度
（A Careful Approach）
試題6-2 判別電路故障
（My Bad）
試題6-3 螞蟻Carl又回來(lái)了
（The Return of Carl）
試題6-4 管道內(nèi)徑
（Conduit Packing）
試題6-5 運(yùn)費(fèi)穩(wěn)定
（Fare and Balanced）
試題6-6 防鹿圍欄
（Deer-Proof Fence）
試題6-7 紙牌的房屋
（House of Cards）
試題6-8 多數(shù)部長(zhǎng)的投票（The
Ministers' Major Mess）
試題6-9 彈簧撐桿
（Struts and Springs）
試題6-10 地鐵的時(shí)間估算
（Subway Timing）
試題6-11 后綴替換語(yǔ)法
（Suffix-Replacement
Grammars）
第7章 2010 ACM-ICPC
世界總決賽試題解析
試題7-1 求值apl表達(dá)式！
（APL Lives?。?br />試題7-2 條形碼（Barcodes）
試題7-3 生物機(jī)器人的軌跡
（Tracking Bio-bots）
試題7-4 城堡（Castles）
試題7-5 渠道（Channel）
試題7-6 等高線地圖
（Contour Mapping）
試題7-7 島嶼（The Islands）
試題7-8 下雨（Rain）
試題7-9 冰上機(jī)器人
（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 古代的象形符號(hào)
（Ancient Messages）
試題8-4 芯片的難題
（Chips Challenge）
試題8-5 咖啡樞紐
（Coffee Central）
試題8-6 機(jī)器公司
（Machine Works）
試題8-7 魔杖（Magic Sticks）
試題8-8 你心愛(ài)的采礦業(yè)（Mining Your Own Business）
試題8-9 瘋狂木乃伊
（Mummy Madness）
試題8-10 金字塔（Pyramids）
試題8-11 垃圾遷移
（Trash Removal）
……

章節(jié)摘錄

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

編輯推薦

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

圖書(shū)封面

圖書(shū)標(biāo)簽Tags

無(wú)

評(píng)論、評(píng)分、閱讀與下載

---

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

---