请选择 进入手机版 | 继续访问电脑版

QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3900|回复: 8

ACM-ICPC参赛者人手一册讲解算法的书,你准备了没?

[复制链接]
字体大小: 正常 放大
zuoninger        

0

主题

0

听众

0

积分

升级  0%

该用户从未签到

自我介绍
技术圈里的非技术人
发表于 2013-7-18 09:37 |显示全部楼层
|招呼Ta 关注Ta
本帖最后由 zuoninger 于 2013-7-18 09:39 编辑
& o5 u. v0 Q6 I
" z2 o0 m" z+ O: I世界顶级程序设计高手的经验总结
7 G3 k  b& a9 K7 Q% [6 a) U9 O, i# V, p【ACM-ICPC全球总冠军】巫泽俊主译 : D( _* w- Y7 l1 I" H
日本ACM-ICPC参赛者人手一册

; g* H, ]; }' m5 X8 W% g# a& S, Y( h# ^" t
3 T+ a. S$ l) m; o6 d

' U0 [* }- k& p- B3 Q3 P0 P先来介绍一下我们这本应该人手一册的《挑战程序设计竞赛》(第2版)译者,这颗闪耀在编程竞赛中的明星巫泽俊,就在2011年的5月30下午2时,他获得了第35届ACM国际大学生程序设计竞赛全球总决赛冠军,媒体称他为“世界最聪明的人”。(见下图)
, o6 [8 s8 l( H+ r4 @- v6 O6 I( w& k

8 T: s! {" F; \# b7 d! C/ ~+ k+ r' v' a9 C- }

# ]% \2 ^' \% t* l* H+ f4 W+ Z6 B* F$ D
巫泽俊平时训练的实验室3 D% Z1 o8 |/ C; B& Y( l$ r- E
% ?6 _, z3 x: N! ]8 U% a
0 |7 W5 K1 _* E4 c# O! M- l
7 M5 r0 g+ Y' _# k. r: O* \
巫泽俊5 H% Q( f6 h$ L% G
4 P8 |  O7 t) a( y% l8 o  @
让我们看顶级ACM-ICPC总冠军是如何来介绍这本译作的!
" _7 [; |1 \8 `+ |+ n- [. ?/ `! M- d0 R, S. ]
程序设计竞赛因其涉及的知识面广,比赛形式激烈有趣,吸引了越来越多的学生参与其中。参赛者不但可以从中锻炼算法设计能力,还能够提高代码编写能力。其中的佼佼者也受到了越来越多国际知名公司的重视和欢迎。 本书的几位作者是世界公认的顶尖选手,在竞赛和学术领域都取得了令人瞩目的成就。他们结合自己的专业知识和比赛经验,将自己的心得和技巧集结成书。# F8 `1 l- s! k

  Z0 i, n; l+ \' R) a* [7 {$ [0 ~6 j$ o9 ]全书将不同的算法和例题按专题编排成小节,再将不同的小节由易到难分成四章,这样即便是初出茅庐的新手也不会有太大的阅读障碍。书中涵盖了在程序设计竞赛中会用到的大多数算法和技巧,并在附录中补充了书中未介绍但也比较有用的算法。在题材的安排上,作者取舍得当,主次分明,循序渐进,不以华而不实的奇技淫巧误导读者,又具有一定深度,相信即便是经验丰富的老将同样能从书中有所斩获。本书在结合例题进行讲解时,不是简单地堆砌问题和代码,而是注重引导读者更好地理解和运用算法来分析解决问题。对于正在学习数据结构与算法的读者而言,把它作为一本练习和拓展的参考书也是很好的选择。. w# r" w& W3 C8 A
- j* J6 x6 `9 G/ \& g
本书在日本广受好评,还先后在台湾地区和韩国出版。近年来程序设计竞赛在亚洲发展很快,在中国大陆也出版了不少相关书籍,但鲜见高质量的佳作。所以,在读到此书时,我们非常惊喜,迫切希望中国大陆也能引进这样的好书。2012年初,我们通过作者的推特了解到了本书第二版的出版,一些前辈们踊跃翻译计算机专业书籍的经历也鼓舞了我们,让我们萌生了亲自翻译此书的念头并联系了图灵教育。非常幸运的是,图灵教育也正考虑引进此书,于是有了今天呈现在各位读者面前的简体中文版。
& t0 O9 C8 b/ y  j" f4 {. l0 w& y
/ ~2 ^8 C' @; q; ^在翻译上,我们力求做到既尊重国内选手的习惯,又符合计算机专业的表述。在修正原书中的一些笔误的同时,加入了一些译者注,以方便国内读者理解。但由于译者水平有限,不足之处在所难免,还望读者多多包涵,并不吝提出意见和建议。
7 |6 v) V. z. B1 S# G; v# m1 M- S/ P5 A& h; f
在翻译过程中,秋叶拓哉、岩田阳一和北川宜稔三位作者耐心地对我们的一些疑问和笔误给予了一一解答和确认。浙江大学的陈越、王灿和翁恺三位老师不但将我们领进了“快乐”竞赛的大门,还拨冗审阅了译稿并提出了宝贵的意见。网上不少同好也对本书的出版给予了关切和支持。在此谨对他们表示感谢。5 z& g* v/ i9 A0 W
! ]$ m6 X0 q1 q9 D
从目录中了解这本书是否符合你的需求+ ?+ i/ o+ k% p4 e' X6 L/ K1 W6 N
5 {" ^2 C0 p$ Z1 z
/ l  |% ]: z+ R- s, s2 J
第1章 蓄势待发——准备篇' V. \5 H5 B' M- g
1.1  何谓程序设计竞赛; e' E0 D) y; x2 F3 |
1.2  最负盛名的程序设计竞赛
1 ?3 ~+ C: d# I1 v: d6 V% R1.2.1  世界规模的大赛——Google Code Jam(GCJ)
# f  D# _. o  k% Z1.2.2  向高排名看齐!——TopCoder
/ ^+ J; z0 w; \( p+ R; x: c1.2.3  历史最悠久的竞赛—— ACM-ICPC
& Q4 g4 X9 `, W( b& H1.2.4  面向中学生的信息学奥林匹克竞赛——JOI-IOI) |5 \" j6 z6 \! ~/ i) Q( h& m. x
1.2.5  通过网络自动评测——Online Judge(OJ)
" }& [; I; k2 J" t1.3  本书的使用方法$ E" j5 [5 C1 _
1.3.1  本书所涉及的内容( X) w8 _: ~- I) `9 [
1.3.2  所用的编程语言
7 l% F8 _9 g6 q% U+ B- P" D1.3.3  题目描述的处理4 Q9 A6 a/ @$ N6 Z" f
1.3.4  程序结构( R1 f& q+ Q' l: y) C$ ]
1.3.5  练习题1 t; Y$ |- d# b. _9 [, p  @  v
1.3.6  读透本书后更上一层楼的练习方法! T/ U$ o8 z. e: L
1.4  如何提交解答7 F! \1 }# t$ Y* w- v4 f
1.4.1  POJ的提交方法
( t% Q2 N4 [, Q: h# i  E1.4.2  GCJ的提交方法
* T: D/ j* |/ L4 y7 c3 Z! h1.5  以高效的算法为目标4 }& p! D0 A2 y- v
1.5.1  什么是复杂度
2 f8 m& K' G- G" r; n1.5.2  关于运行时间
# p0 e  S5 u7 _' d4 Y8 d1.6  轻松热身8 z8 C$ U" f1 O6 q( t3 d, v
1.6.1  先从简单题开始" l: w0 @7 V2 l, G" k5 L
1.6.2  POJ的题目Ants
# M# Z" K3 y- R3 ?1 o! a2 i1.6.3  难度增加的抽签问题
9 P0 w9 b; h$ [# ]; u! n7 g阅读0 F0 f: G, n  d0 u$ T+ b
第2章 初出茅庐——初级篇1 A  y. l" H# i1 V+ x! _) q
2.1  最基础的“穷竭搜索”
: T9 s* r% F6 a! R, e2 V( R( {5 _2.1.1  递归函数7 O* G! j- Y7 L% V- J/ o4 {
2.1.2  栈: Q1 S+ n* \3 P8 s7 P9 Z2 p7 d
2.1.3  队列
. v9 Q8 p  E' w* U! ^! X2.1.4  深度优先搜索
  e! @3 u2 u' c3 V- \2.1.5  宽度优先搜索4 k# `/ @) @2 R0 ?2 x
2.1.6  特殊状态的枚举' P" Z7 i8 T+ p; _' Q* l
2.1.7  剪枝
- m* Z! u0 y/ y/ p  k: s2.2  一往直前!贪心法( P% A! `6 M4 O* V% w& [( ~
2.2.1  硬币问题
* x- m7 l$ M- D- b  Y* b4 L2.2.2  区间问题( ~" `; f9 t6 a# q) [
2.2.3  字典序最小问题( k. y, \% I% O% `; W* U
2.2.4  其他例题& r4 W- }3 H, i: a( H4 d
2.3  记录结果再利用的“动态规划”: _( [6 W5 J- W! Z7 {
2.3.1  记忆化搜索与动态规划  d& A/ v3 g1 \8 |
2.3.2  进一步探讨递推关系) t3 ~( [* @: B- q  y1 e
2.3.3  有关计数问题的DP
- U3 v+ {: @$ @# u2.4  加工并存储数据的数据结构
5 |) Q1 m5 W5 f/ G. T% E# W9 I2.4.1  树和二叉树8 S$ {+ m7 H( l+ F+ G6 K/ \% g8 s
2.4.2  优先队列和堆
, U8 x  @: g) Y/ O: t/ S% x2.4.3  二叉搜索树4 ?9 a; h; o5 Z+ V; a7 B- g
2.4.4  并查集
) U0 J# T6 B. l6 \0 ?( L% ]2 N2.5  它们其实都是“图”
, H, {8 g0 Q( ~1 S$ {2.5.1  图是什么- G, |4 B: q8 {2 u9 B. t; K
2.5.2  图的表示
' W/ f- V/ J, S* q2.5.3  图的搜索
$ l3 {2 d6 @% l8 _8 {2.5.4  最短路问题
) F' a( v  T, [! q2.5.5  最小生成树
. B7 V' m" B0 e/ Z4 u% r6 J2.5.6  应用问题
+ J+ u7 ?9 v: M# ?) }2.6  数学问题的解题窍门2 f5 ?& t9 _1 f# y: r
2.6.1  辗转相除法
$ [! O' h, D7 {+ `' T# W7 c2 I2.6.2  有关素数的基础算法. l. v7 z+ [; Z, K# X% v  Z6 R
2.6.3  模运算
3 r$ O! N; h+ G3 ?! `( v2.6.4  快速幂运算
) O4 Q, V! m& S2.7  一起来挑战GCJ的题目(1)
9 f3 j+ z& ~9 n* [# F2 ~2.7.1  Minimum Scalar Product
. u3 y& s! B2 m/ q1 Z, `- C; J2.7.2  Crazy Rows0 P9 ?8 }) H. Y; q" }- U, d
2.7.3  Bribe the Prisoners
- m( y4 p; U+ l5 B4 ~8 V2.7.4  Millionaire) ]- P) g" q7 Y1 p1 ]
阅读; [) `% g6 @$ h* j5 b: v
第3章 出类拔萃——中级篇
, P; e5 D/ a6 N% E+ Q, z; o- q- v. D3.1  不光是查找值!“二分搜索”% t+ a1 x3 X0 b* c2 D6 g
3.1.1  从有序数组中查找某个值
4 s# Z5 V; M8 c: h. x3.1.2  假定一个解并判断是否可行
( C$ u" q- ]. R6 ]3.1.3  最大化最小值
  p# L- F& r; n6 c' T# Z7 [8 p+ C- [3.1.4  最大化平均值
, l- P9 Z( l& f3.2  常用技巧精选(一)
$ S4 R3 d2 K# Z0 J3 G3.2.1  尺取法
& F* X" L! [4 Y& F, u) k! `3.2.2  反转(开关问题)& ^: a" [) W% |
3.2.3  弹性碰撞
5 e# o4 B4 ~) ^3.2.4  折半枚举(双向搜索)
0 o+ e( u  K1 V" P7 n7 D3.2.5  坐标离散化
9 N/ D* g6 }8 h( Q3.3  活用各种数据结构
+ {5 P$ }/ ?; P3.3.1  线段树
  ^- i' z8 l. i& N) y; Y3.3.2  Binary Indexed Tree% `" r" P) J8 z2 F3 o3 ?0 u4 B7 [
3.3.3  分桶法和平方分割, E9 D  n* ^, D5 [% p
3.4  熟练掌握动态规划. e. m1 Q8 c, v$ a( y8 m9 \, [
3.4.1  状态压缩DP& ^) U& h' u) u
3.4.2  矩阵的幂# \( W. K! w+ u  j& g: B
3.4.3  利用数据结构高效求解
% r) L& j, n) K, W- B5 [* u3.5  借助水流解决问题的网络流
) p6 W9 R0 O% W7 R* b7 K3.5.1  最大流
6 ?! D% _4 Z" X3.5.2  最小割& ~' q  R( f  D7 e$ O9 F
3.5.3  二分图匹配
: M8 ^% C# K8 x. E) C5 c3.5.4  一般图匹配
, x, O. d, [! x& e& G% d  m) T3.5.5  匹配、边覆盖、独立集和顶点覆盖+ T, z+ j' Z9 W' N+ Q
3.5.6  最小费用流1 C% e9 H9 B4 D7 H; y5 F3 X6 {
3.5.7  应用问题
( @( P; p3 o) }- e6 S3.6  与平面和空间打交道的计算几何0 ]5 ~  f4 G3 w1 i2 n& `3 V
3.6.1  计算几何基础. Q& `8 \5 }! a9 @. b. B( D/ y0 n
3.6.2  极限情况: t4 O) Z# ^8 b" @* k4 L& U
3.6.3  平面扫描6 ^7 \/ o* n; c  F" V' h8 f& h7 T! q
3.6.4  凸包
6 e' O6 O' c2 I' g8 @9 A3.6.5  数值积分
; N4 f1 z, h/ K2 `/ C3.7  一起来挑战GCJ的题目(2)7 a( O3 F5 q2 S& y& ]3 k) f
3.7.1  Numbers) z9 b5 [% }' g5 s" @; }  W
3.7.2  No Cheating
6 u1 m$ m" |' |6 f9 W3.7.3  Stock Charts
7 }( a; M, C3 J  }- N0 Z3.7.4  Watering Plants; v. @% {- Z. i4 x9 R# l5 R8 [$ n3 o
3.7.5  Number Sets
7 j, B8 X, Q' R# G9 n3.7.6  Wi-fi Towers* b' o$ r$ Y* m% K* w
第4章 登峰造极——高级篇
4 t3 ]1 n' }5 P+ q4 O. s4.1  更加复杂的数学问题* o6 m- M: |6 e8 t. _! F! ?
4.1.1  矩阵; w7 m) ]& a  r: I' B
4.1.2  模运算的世界
/ }0 Q/ Z: |6 V/ q6 z4 |4.1.3  计数
* z" \' X$ c  [) r  H0 z4.1.4  具有对称性的计数$ m4 z4 V; P& B6 G
4.2  找出游戏的必胜策略6 G" }9 @) q3 ?, X7 n) a
4.2.1  游戏与必胜策略( g9 T1 i! S4 H' _
4.2.2  Nim7 F: b. @6 b7 E* c
4.2.3  Grundy数5 w; m# ^& s) Y
4.3  成为图论大师之路
# Y" h7 R7 \/ |1 ]4.3.1  强连通分量分解, z8 o9 N* q6 W. L* M1 ]
4.3.2  2-SAT
" w" i5 k# A1 P, Q4 |+ ?4.3.3  LCA
- x% B. L# _) N0 j7 n6 w7 M4.4  常用技巧精选(二)
  j. }2 E# S6 ]) V# m4.4.1  栈的运用6 g& [' k+ _) v9 H8 L
4.4.2  双端队列的运用
# o2 Z5 ]; ~# @" f/ B4.4.3  倍增法$ {, [" P+ y, X: S  q, {5 _
4.5  开动脑筋智慧搜索) s1 K- w& a4 \  b  m' {
4.5.1  剪枝
9 x& s+ N; y# J% N4.5.2  A*与IDA*
& X/ S, v% A1 m# ^5 z, z* p5 i4.6  划分、解决、合并:分治法
- f+ F2 J2 V' K, G2 T$ F4.6.1  数列上的分治法
& ~( A5 Q; I7 F* M7 M3 W9 u; V4.6.2  树上的分治法" @8 D( H: ~% Q, |+ G
4.6.3  平面上的分治法( `2 u1 C; x  @0 ~  ]+ d3 F1 P
4.7  华丽地处理字符串3 d$ N/ c* s# Q
4.7.1  字符串上的动态规划算法
/ R( T: n3 H/ ~; \- n' k4.7.2  字符串匹配  E' s* }5 ^: @: i
4.7.3  后缀数组7 u6 M5 _( d8 l4 S
4.8  一起来挑战GCJ的题目(3)
2 C+ N" F& S0 f; @4.8.1  Mine Layer/ H1 X2 \- X! a
4.8.2  Year of More Code Jam- ~- l, R6 O" g1 ^- z- n8 S
4.8.3  Football Team
! z! {& v  T- V4.8.4  Endless Knight4 L/ G/ _  a* ]# v/ C7 T) H
4.8.5  The Year of Code Jam
. P! }" B4 G/ ?9 p
& q0 E7 x9 U" A稍后会上传迷你书!!!
zan

2

主题

8

听众

226

积分

升级  63%

  • TA的每日心情
    无聊
    2014-11-17 15:36
  • 签到天数: 81 天

    [LV.6]常住居民II

    自我介绍
    我是一名工科生

    社区QQ达人

    回复

    使用道具 举报

    _kk        

    0

    主题

    6

    听众

    713

    积分

    升级  28.25%

  • TA的每日心情
    开心
    2014-9-2 23:30
  • 签到天数: 235 天

    [LV.7]常住居民III

    自我介绍
    hi

    群组2012HIMCM培训群组

    回复

    使用道具 举报

    Rain326        

    0

    主题

    5

    听众

    42

    积分

    升级  38.95%

  • TA的每日心情
    郁闷
    2014-12-2 16:24
  • 签到天数: 9 天

    [LV.3]偶尔看看II

    自我介绍
    我爱我师,我更爱真理!为数学疯狂!
    回复

    使用道具 举报

    kk_310        

    1

    主题

    5

    听众

    77

    积分

    升级  75.79%

  • TA的每日心情
    奋斗
    2014-2-7 09:36
  • 签到天数: 24 天

    [LV.4]偶尔看看III

    自我介绍
    热爱数学~
    回复

    使用道具 举报

    26

    主题

    29

    听众

    1398

    积分

    升级  39.8%

  • TA的每日心情
    开心
    2017-9-19 13:48
  • 签到天数: 138 天

    [LV.7]常住居民III

    新人进步奖

    群组数学建摸协会

    群组2013年数学建模国赛备

    群组河南工程学院数学建模

    群组第三届数模基础实训

    群组中国矿业大学数模培训

    回复

    使用道具 举报

    0

    主题

    6

    听众

    104

    积分

    升级  2%

  • TA的每日心情
    郁闷
    2013-12-3 23:14
  • 签到天数: 7 天

    [LV.3]偶尔看看II

    自我介绍
    shanghai university of finance and economics
    回复

    使用道具 举报

    0

    主题

    7

    听众

    51

    积分

    升级  48.42%

  • TA的每日心情
    奋斗
    2014-2-13 12:11
  • 签到天数: 27 天

    [LV.4]偶尔看看III

    群组第四届cumcm国赛实训

    群组2013年数学建模国赛备

    群组第四届数学中国美赛实

    群组2013年电工杯B题讨论群

    群组2013电工杯A题讨论群组

    回复

    使用道具 举报

    木__易        

    4

    主题

    10

    听众

    907

    积分

    升级  76.75%

  • TA的每日心情
    开心
    2017-1-7 12:01
  • 签到天数: 220 天

    [LV.7]常住居民III

    社区QQ达人

    群组2015年美赛冲刺

    群组哈尔滨工业大学建模团

    群组国赛讨论

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2020-5-25 21:52 , Processed in 1.154313 second(s), 99 queries .

    回顶部