挑战编程 程序设计竞赛训练手册


Programming Challenges The Programming Contest Training Manual 挑 战 编 程 程序设计竞赛训练手册 Steven S. Skiena Miguel A. Revilla 著 刘汝佳 译 清华大学出版社 北 京 English reprint edition copyright © 2009 by Springer-Verlag and TSINGHUA UNIVERSITY PRESS. Original English language title from Proprietor’s edition of the Work. Original English language title: Programming Challenges: The Programming Contest Training Manual by Steven S. Skiena, Miguel A. Revilla, Copyright © 2009. All Rights Reserved. This edition has been authorized by Springer-Verlag (Berlin/Heidelberg/New York) for sale in the People’s Republic of China only and not for export therefrom. 本书影印版由 Springer-Verlag 授权给清华大学出版社出版发行。 本书封面贴有清华大学出版社防伪标签,无标签者不得销售。 版权所有,侵权必究。侵权举报电话:010−62782989 13701121933 图书在版编目(CIP)数据 挑战编程:程序设计竞赛训练手册/(美)斯基纳(Skiena, S. S.), (西)雷维拉(Revilla, M. A.) 著; 刘汝佳译. —北京: 清华大学出版社,2009.7 书名原文:Programming Challenges:The Programming Contest Training Manual ISBN 978−7−302−19797−3 Ⅰ. 挑… Ⅱ. ① 斯… ② 雷… ③ 刘… Ⅲ.程序设计 Ⅳ.TP311.1 中国版本图书馆 CIP 数据核字(2009)第 045370 号 责任编辑: 啟龙铭 责任校对:徐俊伟 责任印制: 出版发行:清华大学出版社 地 址:北京清华大学学研大厦 A 座 http://www.tup.com.cn 邮 编:100084 社 总 机:010−62770175 邮 购:010−62786544 投稿与读者服务:010−62776969, c-service@tup.tsinghua.edu.cn 质量反馈:010−62772015, zhiliang@tup.tsinghua.edu.cn 印 刷 者: 装 订 者: 经 销:全国新华书店 开 本:185×230 印 张:20.25 字 数:450 千字 版 次:2009年7月第1版 印 次: 2009 年 7 月第 1 次印刷 印 数: 定 价:0.00元 本书如存在文字不清、漏印、缺页、倒页、脱页等印装质量问题,请与清华大学出版社出 版部联系调换。联系电话:010−62770177 转3103 产品编号:030502−01 仅以此书献给我们的妻子们 Renee 和 Carmela , 以 及 孩 子 们 Bonnie , Emilio 还 有 Miguel。和书中的难题相比,抽出时间来陪伴这些 我们所爱的人更具挑战。                ( )                                        Steven S. Skiena   UVaOJ  Miguel A. Revilla                                                       “ ”                                   Valladolid   (http://uva.onlinejudge.org/)    27 000                ( )                                                                     · vi ·        •  •  •   ACM/ICPC(ACM )  IOI(  )                  “”                                       • ——        ()           • ——              C  C++  Java   !     • ——             http://www.programming-challenges.com        • ——                    (A, B,  C)  !  (low high  )      ( 1  4  )      · vii ·             ACM/ICPC      CC++Pascal  Java              ——ACM  (ICPC)  (IOI)TopCoder  ——      "  #     $   80%  ACM/ICPC  Valladolid   ICPC     %   %         http://www.programming-challenges.com           ()  Valladolid  http:// uva.onlinejudge.org/       ID              ! 17    Gordon Cormack  Shahriar Manzoor Sam Loyd  H. E. Dudeney1    Gordon Cormack (38 ), Shahriar Manzoor (28), Miguel Revilla (10), Pedro Demasi (8), Manuel Carro (4), Rujia Liu( ) (4), Petko Minkov (4), Owen Astrakan (3), Alexander Denisjuk (3), Long Chong( ) (2), Ralf Engels (2), Alex Gevak (1), Walter Guttmann (1), Arun Kishore (1), Erick Moreno (1), Udvranto Patik (1)  Marcin Wojciechowski (1)    1      · viii ·         &     Ciriaco Garc´ıa     Fernando P. N´ajera     Carlos M. Casas      Jos´e A. Caminero  Jes´us Pa´ul        Miguel Revilla, Jr  http://www.programming-challenges.com   Stony Brook 2002  Vinhthuy Phan  Pavel Sumazin       (Larry Mak, Dan Ports, Tom Rothamel, Alexey Smirnov, Jeffrey Versoza  Charles Wright)   Haowen Zhang        Springer-Verlag  Wayne Yuhasz, Wayne Wheeler, Frank Ganz, Lesley Poliner  Rich Putter      Gordon Cormack, Lauren Cowles, David Gries, Joe O’Rourke, Saurabh Sethia, Tom Verhoeff, Daniel Wright  Stan Wagon    Fulbright Foun- dation  Valladolid      Citigroup CIB Peter Remch  Debby Z. Beckman  Stony Brook  ACM ICPC     Steven S. Skiena Stony Brook, NY Miguel A. Revilla Valladolid, Spain      1   .............................................................................1 1.1   ...............................................................1 1.1.1  ..............................................................1 1.2  ....................................................................3 1.2.1 ..............................................................3 1.2.2   ......................................................4 1.2.3  ''..............................................................5 1.3  .........................................................................6 1.4   ....................................................................8 1.5  .......................................................................10 1.6  ............................................................................11 1.6.1 3n +1  (3n+1 Problem)..............................................11 1.6.2  (Minesweeper).......................................................12 1.6.3  (The Trip)...........................................................13 1.6.4  (LC-Display) .................................................14 1.6.5    (Graphical Editor) .........................................15 1.6.6 ( (Interpreter) ......................................................16 1.6.7  (Check the Check)...................................................17 1.6.8   (Australian Voting) ........................................19 1.7  ............................................................................20 1.8 ............................................................................20  2   .......................................................................22 2.1  ...................................................................22 2.1.1  ........................................................................22 2.1.2  ......................................................................23 2.1.3  ......................................................................25 2.1.4  .................................................................26 · x ·   2.1.5  ......................................................................26 2.2  ..........................................................................27 2.2.1 C++   .........................................................27 2.3    .......................................................28 2.4   .......................................................................29 2.5 '' ................................................................30 2.6   .......................................................................32 2.7  .....................................................................33 2.8  ............................................................................35 2.8.1  (Jolly Jumper) .............................................35 2.8.2   (Poker Hands) ..................................................35 2.8.3  (Hartals) ............................................................36 2.8.4  (Crypt Kicker) ......................................................37 2.8.5   (Stack’em Up)................................................38 2.8.6 Erd¨os  (Erd¨os Numbers) ................................................41 2.8.7  (Contest Scoreboard).........................................42 2.8.8 Yahtzee (Yahtzee) ...................................................43 2.9  ............................................................................45 2.10 ...........................................................................45  3   .........................................................................47 3.1  .......................................................................47 3.2  ...................................................................49 3.3   .......................................................49 3.4  .......................................................................51 3.5  .....................................................................52 3.6  .....................................................................54 3.7   ...................................................................54 3.8  ............................................................................56 3.8.1 WERTYU  (WERTYU) ..............................................56 3.8.2  (WheresWaldorf?)...........................................57 3.8.3  (Common Permutation).........................................58 3.8.4  II(Crypt Kicker II) ..................................................59 3.8.5   (Automated Judge Script) .................................60 3.8.6  (File Fragmentation)............................................62 3.8.7 Doublet  (Doublets) ..................................................63   · xi · 3.8.8 Fmt  (Fmt) ..........................................................63 3.9  ............................................................................65 3.10 ...........................................................................65  4   ............................................................................66 4.1  .....................................................................66 4.2  .......................................................................67 4.3  ) .....................................................69 4.4   ............................................................71 4.5 ) .....................................................................72 4.6  ............................................................................75 4.6.1 Vito  (Vitos Family)................................................75 4.6.2  (Stacks of Flapjacks)..............................................75 4.6.3  (Bridge) .............................................................76 4.6.4  (Longest Nap) .............................................77 4.6.5 ! (ShoemakersProblem)......................................79 4.6.6 CDVII  (CDVII) ................................................80 4.6.7  (ShellSort)......................................................81 4.6.8  (Football (aka Soccer)) ..............................................82 4.7  ............................................................................84 4.8 ............................................................................85  5  .....................................................................86 5.1  .......................................................................86 5.1.1   ...............................................................86 5.2   .....................................................................87 5.3   .....................................................................88 5.4  ...................................................................94 5.5  ............................................................................96 5.5.1   ............................................................97 5.5.2  ......................................................................97 5.5.3   ...............................................................98 5.6  ............................................................................98 5.6.1    ...............................................................98 5.6.2   ...............................................................99 5.7  ...........................................................................100 5.8  ....................................................................101 · xii ·   5.9  ...........................................................................101 5.9.1  (Primary Arithmetic) .......................................101 5.9.2  (Reverse and Add) ............................................102 5.9.3   (The Archeologists Dilemma) .........................103 5.9.4  1  (Ones) .................................................104 5.9.5  (A Multiplication Game) ......................................104 5.9.6   (Polynomial Coefficients) .................................105 5.9.7 Stern-Brocot  (The Stern-Brocot Number System) ..............105 5.9.8  (Pairsumonious Numbers) .....................................106 5.10  ..........................................................................107 5.11 ..........................................................................108  6   ......................................................................109 6.1  ..................................................................109 6.2   ......................................................................110 6.3   ....................................................................111 6.4 ..................................................................113 6.5  .............................................................115 6.6  ...........................................................................116 6.6.1  (How Many Fibs?) ........................................116 6.6.2  (How Many Pieces of Land?) ..................................116 6.6.3  (Counting) .........................................................117 6.6.4  (Expressions)................................................118 6.6.5  * (Complete Tree Labeling) ...................................119 6.6.6   (The Priest Mathematician) .................................119 6.6.7   (Self-describing Sequence) ...................................120 6.6.8   (Steps) ........................................................121 6.7  ...........................................................................122 6.8 ...........................................................................122  7  ...........................................................................123 7.1  ...........................................................................123 7.1.1  ................................................................123 7.1.2 ..............................................................124 7.2 .........................................................................125 7.2.1 ..............................................................125 7.2.2 ..............................................................127   · xiii · 7.3 .........................................................................127 7.4  ...........................................................................129 7.4.1   ................................................................129 7.4.2    .........................................................130 7.4.3   ................................................................131 7.5  ....................................................................131 7.6  ...........................................................................132 7.6.1   (Light, More Light) .........................................132 7.6.2 Carmichael  (Carmichael Numbers) ....................................132 7.6.3   (Euclid Problem) .........................................133 7.6.4  (Factovisors) ................................................134 7.6.5  (Summation of Four Primes) ................................134 7.6.6 Smith  (Smith Numbers) ..............................................135 7.6.7 !! (Marbles) ..........................................................135 7.6.8  (Repackaging) .................................................136 7.7  ...........................................................................137 7.8 ...........................................................................137  8   ........................................................................138 8.1  .........................................................................138 8.2 ..................................................................140 8.3 ..................................................................141 8.4   ....................................................143 8.5  "..................................................................144 8.6  ...........................................................................147 8.6.1  (Little Bishops) .............................................147 8.6.2 15  (15-Puzzle Problem) ........................................148 8.6.3  (Queue) ............................................................149 8.6.4  (Servicing Stations) ..............................................150 8.6.5  (Tug of War) .......................................................150 8.6.6 " (Garden of Eden) ................................................151 8.6.7  (Color Hash)..............................................153 8.6.8   (Bigger Square Please...) ....................................154 8.7  ...........................................................................156 8.8 ...........................................................................156 · xiv ·    9   ........................................................................157 9.1 +..................................................................157 9.2 ..................................................................158 9.3    ...........................................................162 9.3.1   ...........................................................162 9.3.2 ..............................................................163 9.3.3  ................................................................164 9.4    ...........................................................165 9.4.1  ..................................................................166 9.4.2  ................................................................167 9.5  ......................................................................168 9.6  ...........................................................................170 9.6.1  (Bicoloring)......................................................170 9.6.2  (Playing With Wheels) ........................................171 9.6.3 # (The Tourist Guide)................................................173 9.6.4 "  (Slash Maze) ..................................................174 9.6.5   (Edit Step Ladders) ...........................................175 9.6.6   (Tower of Cubes)............................................176 9.6.7  (From Dusk till Dawn)....................................177 9.6.8 !(Hanoi Tower Troubles Again!) ........................179 9.7  ...........................................................................179  10   .......................................................................181 10.1  ..........................................................................181 10.1.1  ...............................................................181 10.1.2  .................................................................182 10.1.3 .............................................................182 10.1.4 .................................................................183 10.2 * ...................................................................183 10.3 ........................................................................186 10.3.1 Dijkstra  ...........................................................186 10.3.2  .................................................188 10.4   .........................................................191 10.5  ..........................................................................195 10.5.1  (Freckles) .........................................................195 10.5.2  (The Necklace)....................................................195   · xv · 10.5.3  (Fire Station) ...................................................197 10.5.4  (Railroads)........................................................198 10.5.5  (War) .............................................................199 10.5.6 # (Tourist Guide) ...................................................201 10.5.7 ,! (The Grand Dinner) .......................................202 10.5.8  (The Problem With the Problem Setter) .................203 10.6  ..........................................................................205  11  .....................................................................206 11.1 - ...................................................................206 11.2  " .....................................................................207 11.3  .....................................................................211 11.4  " ..............................................................212 11.5  .....................................................214 11.6  ..........................................................................218 11.6.1 (Is Bigger Smarter?) ......................................218 11.6.2  (Distinct Subsequences)..................................219 11.6.3  (Weights and Measures)....................................219 11.6.4  TSP(Unidirectional TSP) .........................................220 11.6.5  (Cutting Sticks)............................................221 11.6.6 $ (Ferry Loading) ..............................................222 11.6.7  (Chopsticks) ......................................................223 11.6.8    (Adventures in Moving: Part IV)..................224 11.7  ..........................................................................225 11.8 ..........................................................................225  12   .........................................................................226 12.1 # .....................................................................226 12.1.1 ....................................................................227 12.1.2  ........................................................228 12.2 ".....................................................229 12.2.1 .............................................................229 12.2.2 ".............................................................230 12.3 !% ................................................232 12.4 ! .....................................................................234 12.5   ...................................................................236 12.6  ..........................................................................236 · xvi ·   12.6.1  (Ant on a Chessboard)...................................236 12.6.2  (The Monocycle)................................................237 12.6.3 # (Star)...........................................................239 12.6.4  Maja(Bee Maja) ..................................................240 12.6.5 $ (Robbery) ......................................................241 12.6.6 (2/3/4)-  ((2/3/4)-D Sqr/Rects/Cubes/Boxes?) ..............242 12.6.7 Dermuba  (Dermuba Triangle) .....................................243 12.6.8  (Airlines)..........................................................244 12.7  ..........................................................................246  13   .........................................................................247 13.1  ..........................................................................247 13.2  ..............................................................250 13.2.1  ! .................................................251 13.2.2  ...............................................................251 13.2.3  ...............................................................252 13.3 ! ............................................................................253 13.4  ...................................................255 13.5  ...................................................................257 13.6  ..........................................................................259 13.6.1 ". (Dog and Gopher)............................................259 13.6.2 / (Rope Crisis in Ropeland!) ...........................260 13.6.3 ! (The Knights of the Round Table) ............................260 13.6.4  (Chocolate Chip Cookies)................................261 13.6.5 & (Birthday Cake) ..............................................262 13.6.6 / # (The Largest/Smallest Box ...) .......................263 13.6.7 (Is This Integration?) .....................................264 13.6.8 (How Big Is It?).............................................265 13.7  ..........................................................................266  14  .....................................................................277 14.1 ' ................................................................277 14.2 "$ ............................................................278 14.3  ..........................................................................270 14.4  ...................................................274 14.4.1 Van Gogh  .........................................................274 14.4.2  ...............................................................276   · xvii · 14.4.3  .................................................................277 14.5  ................................................................278 14.5.1 % ...............................................................278 14.5.2 " Pick  ................................................279 14.6  ...................................................................280 14.7  ..........................................................................280 14.7.1  (Herding Frosh) ..............................................280 14.7.2 %  (The Closest Pair Problem)..............................281 14.7.3 &' (Chainsaw Massacre) .........................................282 14.7.4  (Hotter Colder)...............................................283 14.7.5  (Useless Tile Packers) ............................284 14.7.6   (Radar Tracking).............................................285 14.7.7 (* (Trees on My Island) .........................................286 14.7.8   (Nice Milk) ................................................287 14.8  ..........................................................................288  A ..................................................................................290 A.1 ACM  ...............................................290 A.1.1  ....................................................................290 A.1.2  ...............................................................292 A.2  ..........................................................293 A.2.1   ...............................................................293 A.2.2  ...............................................................294 A.2.3  ....................................................................295 A.3 Topcoder.com .................................................................295 A.4   .................................................................296 A.5  ......................................................................297  ................................................................................300  1            1.1   Miguel Revilla    (The Programming Challenges judge)http://www.programming-challenges.com  Valladolid  (The Universidad de Valladolid judge)http://uva. onlinejudge.org/                      1            (http://www.programming-challenges.com)      Valladolid  (http:// uva.onlinejudge.org/)      Web     1.1.1   “”   (problem specification)     1 Valladolid           · 2 ·  1              ACM  (ACM/ICPC)       • Accepted (AC )—       • Presentation Error (PE)—         • Accepted (PE)—                 • Wrong Answer (WA)—         • Compile Error (CE)—             • Runtime Error (RE)—  (segmentation fault)  (floating point exception)            (invalid pointer reference)  (division by zero) • Time Limit Exceeded (TL)—         • Memory Limit Exceeded (ML)—     • Output Limit Exceeded (OL)—        • Restricted Function (RF)—      fork() fopen()  • Submission Error (SE)—         ID                      1.2   · 3 ·           1.2       CC++Pascal  Java           (problem-solving)               1.2.1         • Pascal —  20  80    Pascal            • C—  UNIX    C          20  90   C    ··· • C++ —     C       C++  20  90       ··· • Java —                      Java   2002 12    1 250 000   C++   C    Java   2001 11   Java  1.1     C   1999  C++      · 4 ·  1   1.1 2002 12    1-1 2002  12    AC PE WA CE RE TL ML OL RF C 451447 31.9% 6.7% 35.4% 8.6% 9.1% 6.2% 0.4% 1.1% 0.6% C++ 639565 28.9% 6.3% 36.8% 9.6% 9.0% 7.1% 0.6% 1.0% 0.7% Java 16373 17.9% 3.6% 36.2% 29.8% 0.5% 8.5% 1.0% 0.5% 2.0% Pascal 149408 27.8% 5.5% 41.8% 10.1% 6.2% 7.2% 0.4% 0.4% 0.5%  1256793 29.7% 6.3% 36.9% 9.6% 8.6% 6.8% 0.5% 1.0% 0.6% 1.2.2        http://www.programming-challenges.com            C   C  C++   Java        C     !         •  —C  (call-by-value)                       x   &x  p   ∗p “ ”    1.2   · 5 ·  •  —C    intfloat  char    long  double   int  •  —C  0  n − 1 n      1    n +1 C           0  C   1           •  —C       ( )  %    (logical-and)  (logical-or)    &&  || 1.2.3  UNIX                  “ ”    (graphical user interface)     “  - ”           “ ”    ACM/ICPC    (standard input)     (standard output)    2  (standard input/output)   CC++  Pascal     1.2                    I/O       " (manual)    (parsing)  (formatting) Java http://www.programming-challenges.com   35   Java   http://uva. 2      ONLINE JUDGE    · 6 ·  1   onlinejudge.org/ 1.2 C ( )C++ ()Pascal ( )  1.3            (variable)  ( if-then-else, case)  ( for-do, while-do, repeat-until) (subroutine)  (function)                 “ ”         !           •  —            #   #     " # 1.3  · 7 · $    •  — %  #                 •  —     (    )                    & ··· •  —   (  (true, false))      (club) (diamond) (heart)  (spade) switch(cursuit) { case ’C’: newcard.suit = C; break; case ’D’: newcard.suit = D; break; case ’H’: newcard.suit = H; break; case ’S’: newcard.suit = S; ...    (’C’,’D’,’H’,’S’)    (C,D,H,S)      •  —       ... while (c != ’0’) { scanf("%c", &c); if (c == ’A’) { if (row-1 >= 0) { · 8 ·  1   temp = b[row-1][col]; b[row-1][col] = ’ ’; b[row][col] = temp; row = row-1; } } else if (c == ’B’) { if (row+1 <= BOARDSIZE-1) { temp = b[row+1][col]; b[row+1][col] = ’ ’; b[row][col] = temp; row = row+1; } } ...             +  −      “ ”    •  —                    &        (object-oriented program- ming)         (  )        1.4  '    !  1.4   · 9 · "         (  ! (Ebola virus)  ) (bubonic plague)   (aspiron)  * (balanced binary search tree)  (exception handling)  (parallel processing)  (object inheritance)      "                        •  —       !        (record)3       (sentinel)    +"       n   a  x      i=n; while ((a[i]>=x) && (i>=1)) { a[i+1] = a[i]; i=i-1; } a[i+1] = x; i=n; a[0] = SMALLINT while (a[i] >= x) { a[i+1] = a[i]; i=i-1; } a[i+1] = x;    a[0]    SMALLINT +"  +"        •  —  #    $ (homogeneous)  x − y  n   n × 2  A[i][j]   (0 1)     x  y  3  Pascal  C/C++    · 10 ·  1   •  — $ (heterogeneous)                       x − y    ( )  struct point { int x, y; };  ' p.x  p.y       ##             x  y   z #        typedef int point[DIMENSION]; double distance(point a, point b) { int i; double d=0.0; for (i=0; i
还剩26页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

chao121

贡献于2013-09-18

下载需要 8 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf