QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5962|回复: 8
打印 上一主题 下一主题

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

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

0

主题

0

听众

0

积分

升级  0%

该用户从未签到

自我介绍
技术圈里的非技术人
跳转到指定楼层
1#
发表于 2013-7-18 09:37 |只看该作者 |正序浏览
|招呼Ta 关注Ta
本帖最后由 zuoninger 于 2013-7-18 09:39 编辑 # z, Z( |' S4 N% B+ z5 B0 c; Z

) J+ d* F9 _, @2 |) n# g8 X/ x, Z- M世界顶级程序设计高手的经验总结
& O: _$ Z7 \& u: K【ACM-ICPC全球总冠军】巫泽俊主译
2 ~6 _9 d% Y9 E- Y, ]+ N6 f5 ?# L$ l日本ACM-ICPC参赛者人手一册
- ]( ^5 }3 o/ u% P# B
/ {  R. L5 p5 U; \0 g6 i5 d/ @

" h. m: J! v% H1 a/ c: t5 {
( e( i& H; A  M0 h  B- W+ @先来介绍一下我们这本应该人手一册的《挑战程序设计竞赛》(第2版)译者,这颗闪耀在编程竞赛中的明星巫泽俊,就在2011年的5月30下午2时,他获得了第35届ACM国际大学生程序设计竞赛全球总决赛冠军,媒体称他为“世界最聪明的人”。(见下图)4 y. w" f# f( O9 e( [
8 N% V) h7 Y1 L' S4 P3 Y/ D9 n" N

/ T% v3 A3 R8 _$ I8 R- `
3 ^2 F% ?- K: @
4 I8 L# M' n/ \! `; [/ ]
2 w, F+ g7 {) H; M5 A9 F巫泽俊平时训练的实验室/ f4 K( P' y( N- i' z) \3 z% F  f

/ `3 |! O0 q) [* A1 X& Y, @' J3 @3 i

+ W; Q' m( b. C) {/ |4 V巫泽俊
; j& q6 o& h% }. M
) V( z3 o5 a7 P8 T. e让我们看顶级ACM-ICPC总冠军是如何来介绍这本译作的!5 T: S* N$ x- G$ F

1 N( @1 v9 y; `' O程序设计竞赛因其涉及的知识面广,比赛形式激烈有趣,吸引了越来越多的学生参与其中。参赛者不但可以从中锻炼算法设计能力,还能够提高代码编写能力。其中的佼佼者也受到了越来越多国际知名公司的重视和欢迎。 本书的几位作者是世界公认的顶尖选手,在竞赛和学术领域都取得了令人瞩目的成就。他们结合自己的专业知识和比赛经验,将自己的心得和技巧集结成书。( |3 V% v$ w& e+ ?+ F: `
9 z) T0 [7 X3 f' y) h
全书将不同的算法和例题按专题编排成小节,再将不同的小节由易到难分成四章,这样即便是初出茅庐的新手也不会有太大的阅读障碍。书中涵盖了在程序设计竞赛中会用到的大多数算法和技巧,并在附录中补充了书中未介绍但也比较有用的算法。在题材的安排上,作者取舍得当,主次分明,循序渐进,不以华而不实的奇技淫巧误导读者,又具有一定深度,相信即便是经验丰富的老将同样能从书中有所斩获。本书在结合例题进行讲解时,不是简单地堆砌问题和代码,而是注重引导读者更好地理解和运用算法来分析解决问题。对于正在学习数据结构与算法的读者而言,把它作为一本练习和拓展的参考书也是很好的选择。
2 @* A; C6 ^( r6 P6 W1 ]  U) d) ?2 x
本书在日本广受好评,还先后在台湾地区和韩国出版。近年来程序设计竞赛在亚洲发展很快,在中国大陆也出版了不少相关书籍,但鲜见高质量的佳作。所以,在读到此书时,我们非常惊喜,迫切希望中国大陆也能引进这样的好书。2012年初,我们通过作者的推特了解到了本书第二版的出版,一些前辈们踊跃翻译计算机专业书籍的经历也鼓舞了我们,让我们萌生了亲自翻译此书的念头并联系了图灵教育。非常幸运的是,图灵教育也正考虑引进此书,于是有了今天呈现在各位读者面前的简体中文版。
4 d3 ?# f& a9 M6 g% _+ S0 P6 F, z$ U0 k# N4 x1 X, S
在翻译上,我们力求做到既尊重国内选手的习惯,又符合计算机专业的表述。在修正原书中的一些笔误的同时,加入了一些译者注,以方便国内读者理解。但由于译者水平有限,不足之处在所难免,还望读者多多包涵,并不吝提出意见和建议。
  D  Z& c6 h* f, i1 J+ N; G- b
( z3 f1 K9 D; s1 O9 l在翻译过程中,秋叶拓哉、岩田阳一和北川宜稔三位作者耐心地对我们的一些疑问和笔误给予了一一解答和确认。浙江大学的陈越、王灿和翁恺三位老师不但将我们领进了“快乐”竞赛的大门,还拨冗审阅了译稿并提出了宝贵的意见。网上不少同好也对本书的出版给予了关切和支持。在此谨对他们表示感谢。
) e" b  }2 N7 q+ F# ~9 }+ v
8 ?# }1 V3 Q; h0 E3 d7 L从目录中了解这本书是否符合你的需求& q1 g' S# l; L2 n+ y, _) ?& o  b
0 O  S2 j/ U" v0 L/ @

7 S1 Z( ^" t2 ]  c第1章 蓄势待发——准备篇1 L9 [+ {8 v) p5 q
1.1  何谓程序设计竞赛
& I5 _2 q  {! H( \: J1.2  最负盛名的程序设计竞赛) N+ H# Y) E- ^
1.2.1  世界规模的大赛——Google Code Jam(GCJ)3 A; {4 s+ X8 d
1.2.2  向高排名看齐!——TopCoder
1 C* y2 P/ v4 l8 ?1.2.3  历史最悠久的竞赛—— ACM-ICPC, [8 d6 Y; ]5 N
1.2.4  面向中学生的信息学奥林匹克竞赛——JOI-IOI$ E# ]* ]. b% n/ \
1.2.5  通过网络自动评测——Online Judge(OJ)
! i. |# B, A- }+ g! }1.3  本书的使用方法$ d- T1 p3 @" c
1.3.1  本书所涉及的内容
6 `& a) O2 k/ z1.3.2  所用的编程语言
, j4 T! U8 c7 W! J1.3.3  题目描述的处理( p( M* K8 y% Z# g# O
1.3.4  程序结构2 l  t" [4 a3 q0 Q' k
1.3.5  练习题
% |4 Z) [8 {. U  a  g1.3.6  读透本书后更上一层楼的练习方法
2 k+ Z  b' N& O1.4  如何提交解答
5 d; V1 U$ Y2 Z1.4.1  POJ的提交方法# J6 @2 ?7 _$ L. x* T- {5 U
1.4.2  GCJ的提交方法7 G$ z/ q5 `# B4 n* K1 W! \( }: m3 w
1.5  以高效的算法为目标, z5 T+ @+ @( n+ Y9 E1 e& v( `) M9 E
1.5.1  什么是复杂度
" T1 c5 F& J6 X0 n) ~$ h# d) E1.5.2  关于运行时间. j" g) ~9 a; k- A: V4 a5 ?: d
1.6  轻松热身" ]9 X0 |: N+ K2 k/ y" k  G8 D2 x$ Y2 J
1.6.1  先从简单题开始
. ~( F1 ?2 ?* c0 ]" S# a1.6.2  POJ的题目Ants3 {9 }; l* w7 ^, A9 g  t6 D  _; T
1.6.3  难度增加的抽签问题6 k9 H  k! k! a1 _
阅读
: m  Z/ O1 I( H* R% @1 _第2章 初出茅庐——初级篇
0 W9 ~. N  h/ L: t# l! L' {2.1  最基础的“穷竭搜索”- Z' ?, X4 K4 f2 f/ A( O
2.1.1  递归函数
" H; a, Z. f- i1 H  n2.1.2  栈& I+ P5 O3 B) s" W0 u, ]
2.1.3  队列
5 t4 v+ h, b: \$ x, W  X2.1.4  深度优先搜索
: [) m6 K  i1 P. `2 N! ]# E* o) U2.1.5  宽度优先搜索
* A9 \! [+ l# t2.1.6  特殊状态的枚举' N' @# E* `/ r9 C4 i/ v. R$ V. i
2.1.7  剪枝
2 n% f0 P: l& Y, N2.2  一往直前!贪心法8 b# Y. F' I8 n# r( b) |; J
2.2.1  硬币问题
/ U( `2 B4 M4 N2.2.2  区间问题
: ~7 E/ L- L  w; n; ^% w3 d2.2.3  字典序最小问题' z- s$ _2 q! E# h4 c, p4 q% g9 S
2.2.4  其他例题/ [0 [/ }% y, Z
2.3  记录结果再利用的“动态规划”
- ]) ~" [8 {2 v6 O2.3.1  记忆化搜索与动态规划
; {" _; P$ J; c2 S7 s8 Y2.3.2  进一步探讨递推关系
' R( B# X/ ]2 {) B) a) X) _2.3.3  有关计数问题的DP
  {; e# a' Z  K% j8 S0 S& _6 N2.4  加工并存储数据的数据结构
+ ]  M% Z# w2 `2 l2.4.1  树和二叉树# ~  K6 X" `1 u% B  C* e' \
2.4.2  优先队列和堆* ^3 _3 ^5 z1 Q* v$ R
2.4.3  二叉搜索树+ L0 D/ U6 u0 c: c
2.4.4  并查集% y/ r9 ]! c4 ?# X! ?
2.5  它们其实都是“图”4 v) e! D! a! g# H3 @* l& W& C
2.5.1  图是什么
8 P$ E4 V- F2 |9 T2.5.2  图的表示
8 a* R' _* N- s4 w) d2.5.3  图的搜索4 E2 b+ [  E: E; J+ D
2.5.4  最短路问题9 ]1 z& W4 I/ e7 m" b/ |
2.5.5  最小生成树
! @' v7 c5 J- `3 U; L; i2.5.6  应用问题+ n* U+ N& V/ ]1 H' n
2.6  数学问题的解题窍门6 k- z, O6 k3 `1 u* {4 j$ N3 C0 Y# N
2.6.1  辗转相除法
8 b! i, ?9 I& s2 A2.6.2  有关素数的基础算法
$ A: a. K0 v+ i) k% c2.6.3  模运算
) R4 Q7 \& j* O4 b& v$ _. m% D2.6.4  快速幂运算3 J3 Z7 u. u4 y4 B
2.7  一起来挑战GCJ的题目(1)
# Z% o' a7 f1 s* `2.7.1  Minimum Scalar Product
- B( |: [4 g& P; n2.7.2  Crazy Rows+ M* E' B# v& n! s3 n" M/ Z
2.7.3  Bribe the Prisoners
% }& K" t; b1 X( H% j- k2.7.4  Millionaire8 g' A' h- r, I8 n/ r8 W- U
阅读' r. M. ~$ r* r6 _' Z9 X: D
第3章 出类拔萃——中级篇
: j% S+ y6 F% W3.1  不光是查找值!“二分搜索”
+ p8 ]  l; \& [" U& A2 {$ V3.1.1  从有序数组中查找某个值& X9 ?( G+ r/ `+ m# {9 }* E
3.1.2  假定一个解并判断是否可行7 Q& H0 c1 U8 B5 M% l1 P. y
3.1.3  最大化最小值
' {" V. c; Q! H4 j3.1.4  最大化平均值2 S0 [& t% q" \) t; t/ s' F
3.2  常用技巧精选(一)& u0 a4 f$ V. F5 Q
3.2.1  尺取法& n2 o; {: C8 O6 k/ I
3.2.2  反转(开关问题)
' F3 g" D+ t% |+ r  K% ~3.2.3  弹性碰撞
) C1 @& _! @' \9 V5 n- C$ D% B: @3.2.4  折半枚举(双向搜索)
8 R6 W( a& W4 h9 W) F( e; K3.2.5  坐标离散化+ ^8 p2 o' D0 a/ ^6 h
3.3  活用各种数据结构- X% v; f; N  q  R; G4 m
3.3.1  线段树
7 o6 l) t- ]; C7 p1 y. e, v3.3.2  Binary Indexed Tree
+ z. y1 R5 r6 Q) \0 u7 Y7 ~3.3.3  分桶法和平方分割4 L! \. l1 k1 a# T, A
3.4  熟练掌握动态规划/ \& m- z1 V) |  n% t
3.4.1  状态压缩DP
% |5 P+ g5 h4 ]1 L0 F+ g7 x% O3.4.2  矩阵的幂- J- ~* {5 ~9 c
3.4.3  利用数据结构高效求解0 v- |4 m5 E  A9 f0 t
3.5  借助水流解决问题的网络流4 g! ]* E1 i( E3 ^6 n2 ?
3.5.1  最大流
- K4 x# Q$ w' G1 [/ k- h# Y3.5.2  最小割; u' d5 F! q4 a  s
3.5.3  二分图匹配
: m7 S" V' e. P3.5.4  一般图匹配) _; `5 D& Q: g, Y
3.5.5  匹配、边覆盖、独立集和顶点覆盖
/ @0 w8 H; c; r! F3.5.6  最小费用流
; ]+ |  F" C$ p8 O$ b- K3.5.7  应用问题
5 Q+ C' K% i. J0 O) a; O* [3.6  与平面和空间打交道的计算几何
! n. j. p$ `/ u$ P3.6.1  计算几何基础2 g) D5 D: I6 T6 D9 z! w
3.6.2  极限情况) }/ |3 a2 [6 i
3.6.3  平面扫描' f0 H2 T* \4 p  M' f. M( a
3.6.4  凸包
: e! y% H$ K! d) q7 }3.6.5  数值积分" \8 z) a1 u- g: p5 ~
3.7  一起来挑战GCJ的题目(2)$ ]$ N. i8 n' P. O
3.7.1  Numbers- C% h2 h/ e( s
3.7.2  No Cheating
2 e" m0 z: K+ S% B% e; u3.7.3  Stock Charts/ _0 V' j' K& O2 g6 {
3.7.4  Watering Plants
- d& ^4 l1 v) O5 D2 S3.7.5  Number Sets
( r+ ^" e3 B7 M/ r' {3.7.6  Wi-fi Towers
9 G8 \9 L; T: f' x& a第4章 登峰造极——高级篇
  ~  m; P# o2 k4 T! ^6 M4.1  更加复杂的数学问题
( ]- Y# u7 q; Z* d4 U4.1.1  矩阵1 \6 ~4 w& n: ^. x8 H
4.1.2  模运算的世界
% r' l4 o- f# N  s4.1.3  计数, }$ L( p6 ]2 _2 Q/ t
4.1.4  具有对称性的计数% J1 Z1 V+ |! S$ {& P9 u3 Z; ?
4.2  找出游戏的必胜策略
% [+ T2 U+ a  H4.2.1  游戏与必胜策略1 Y" F) \3 `$ g* G3 `  R
4.2.2  Nim
( J3 n! j- s% K9 P+ Y  F4.2.3  Grundy数4 h1 m0 s! h( h. n8 M" C- j$ e
4.3  成为图论大师之路/ q. z# {5 q( s6 _; R- W8 [  f8 l. C+ F( Q
4.3.1  强连通分量分解% z. P* B5 F% B' A$ S- @
4.3.2  2-SAT
" `2 P' g+ o5 Z4.3.3  LCA$ m& n  n) K% j; e
4.4  常用技巧精选(二)
% l6 _8 [' v% v& W4.4.1  栈的运用
% ?4 [6 [" ~6 W" p/ _6 w1 C( V4 I4.4.2  双端队列的运用1 X1 G, s+ q6 @7 p- J8 l9 A
4.4.3  倍增法
, ]# x' Z) V! c$ U" B$ Z4.5  开动脑筋智慧搜索' e9 `4 k/ W' A3 M2 b: E3 e
4.5.1  剪枝& |0 A0 h* _" k4 d% @; s, ?) ~
4.5.2  A*与IDA*
# H# ^  ]6 n  E3 }6 g0 a4.6  划分、解决、合并:分治法
! ^2 x, N) q7 l+ G) n4.6.1  数列上的分治法
4 \: T. _' ^4 V4 _. z  o4.6.2  树上的分治法6 D  {+ L0 `! u2 o7 O6 ?
4.6.3  平面上的分治法) X) m  I& m3 p8 a) ^
4.7  华丽地处理字符串
5 s; z0 _" F, U9 @4.7.1  字符串上的动态规划算法6 F% p$ Q1 e- b$ \5 T' w& b
4.7.2  字符串匹配
8 _9 {9 x& k" k; }2 E+ a" Z4.7.3  后缀数组, M. g' Q1 b0 k7 Z
4.8  一起来挑战GCJ的题目(3)
" S1 V0 w) V( p" L6 `" [8 m& P) z4.8.1  Mine Layer
' }, B% k& t2 J" ^  K, N# H4.8.2  Year of More Code Jam& `. D/ W7 w1 D) u( x6 K, o
4.8.3  Football Team! f3 G$ R+ V9 ^' i. B' B
4.8.4  Endless Knight
, u* ]- L  r$ U4 o+ e4 V4.8.5  The Year of Code Jam; p5 R, W1 g5 W( I+ p* I. F
1 a( R" B' Z5 x! A( H5 r
稍后会上传迷你书!!!
zan
转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
木__易        

4

主题

10

听众

907

积分

升级  76.75%

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

    [LV.7]常住居民III

    社区QQ达人

    群组2015年美赛冲刺

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

    群组国赛讨论

    回复

    使用道具 举报

    0

    主题

    7

    听众

    51

    积分

    升级  48.42%

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

    [LV.4]偶尔看看III

    群组第四届cumcm国赛实训

    群组2013年数学建模国赛备

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

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

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

    回复

    使用道具 举报

    0

    主题

    6

    听众

    104

    积分

    升级  2%

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

    [LV.3]偶尔看看II

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

    使用道具 举报

    26

    主题

    30

    听众

    1400

    积分

    升级  40%

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

    [LV.7]常住居民III

    新人进步奖

    群组数学建摸协会

    群组2013年数学建模国赛备

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

    群组第三届数模基础实训

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

    回复

    使用道具 举报

    kk_310        

    1

    主题

    5

    听众

    77

    积分

    升级  75.79%

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

    [LV.4]偶尔看看III

    自我介绍
    热爱数学~
    回复

    使用道具 举报

    Rain326        

    0

    主题

    5

    听众

    42

    积分

    升级  38.95%

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

    [LV.3]偶尔看看II

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

    使用道具 举报

    _kk        

    0

    主题

    6

    听众

    713

    积分

    升级  28.25%

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

    [LV.7]常住居民III

    自我介绍
    hi

    群组2012HIMCM培训群组

    回复

    使用道具 举报

    2

    主题

    8

    听众

    226

    积分

    升级  63%

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

    [LV.6]常住居民II

    自我介绍
    我是一名工科生

    社区QQ达人

    回复

    使用道具 举报

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

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2025-7-23 10:00 , Processed in 0.801921 second(s), 100 queries .

    回顶部