- 在线时间
- 0 小时
- 最后登录
- 2010-1-23
- 注册时间
- 2010-1-23
- 听众数
- 3
- 收听数
- 0
- 能力
- 0 分
- 体力
- 27 点
- 威望
- 0 点
- 阅读权限
- 20
- 积分
- 12
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 7
- 主题
- 0
- 精华
- 0
- 分享
- 0
- 好友
- 0
升级   7.37% 该用户从未签到
|
一位高手对我的建议:% p- P S9 n6 u2 A! a. h# `7 u
" G/ m8 T0 `0 G. Q: U* g1 c
一般要做到50行以内的程序不用调试、100行以内的二分钟内调试成功.acm主要是考算法的
5 y ]- M9 K3 K" ]% h,主要时间是花在思考算法上,不是花在写程序与debug上。
$ J* M1 n& W% Q下面给个计划你练练:
5 Q$ b& W1 ~" p" B. S2 `
$ v7 j" B; y# a9 W% O4 r第一阶段:7 B* }) G" A6 i1 D5 w
练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码,
8 ?& d8 X- X( z& l因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打$ }0 w# t4 Y4 D7 t) }
出来. 6 w! o$ O2 m @7 [ {/ C
1.最短路(Floyd、Dijstra,BellmanFord) u; N+ k A. q8 U, b+ [8 M* _
2.最小生成树(先写个prim,kruscal要用并查集,不好写) . F. r9 L. w4 [$ J, a1 s2 v) }
3.大数(高精度)加减乘除
0 }9 V3 W. |; f+ m 4.二分查找. (代码可在五行以内) $ T4 v5 x7 V/ `
5.叉乘、判线段相交、然后写个凸包.
( C/ F% T2 l5 q' I* d 6.BFS、DFS,同时熟练hash表(要熟,要灵活,代码要简)
5 o( {7 o. J7 j/ k# F( \ 7.数学上的有:辗转相除(两行内),线段交点、多角形面积公式. ' }5 \# o" a6 ^4 b. w' M
8. 调用系统的qsort, 技巧很多,慢慢掌握. 6 O1 Y' L) [; f% }
9. 任意进制间的转换 ; X0 i, c9 ^. o* a2 H6 |
! @4 f# M% ~9 w9 u
, B7 z" \, J/ i+ ]
第二阶段:9 r8 B8 f B$ J# e/ z
练习复杂一点,但也较常用的算法。 ; p$ }# p/ J7 A ~2 t; A
如: 5 z, o3 y: \. \5 h* n( J- {8 Q3 g) Q. j
1. 二分图匹配(匈牙利),最小路径覆盖 # A+ [. d6 J# q
2. 网络流,最小费用流。
: G5 }, Z. J' s9 e 3. 线段树. j$ a, _+ g6 Q% z+ k, O8 l0 }
4. 并查集。 4 H: k1 D$ h8 z. x1 j8 f% D' k' j5 O
5. 熟悉动态规划的各个典型:LCS、最长递增子串、三角剖分、记忆化dp , r3 l* s, m. @* U$ d
6.博弈类算法。博弈树,二进制法等。 - F0 C0 G5 K% [% Q
7.最大团,最大独立集。
" |2 Q# W- q7 b$ |- A 8.判断点在多边形内。 3 T8 n s: q! u' U% Y% N: i
9. 差分约束系统.
# Q% I" }; ?5 d; ]! a9 a10. 双向广度搜索、A*算法,最小耗散优先." S) E; J) H [( c I& ^* ]
0 u% b- `- |$ j, z& m
/ l3 c8 C2 O5 d+ C7 D$ W第三阶段:
/ x6 C/ _- a x1 u8 l e 前两个阶段是打基础,第三阶段是锻炼在比赛中可以快速建立模型、想新算法5 l" | l5 I- D! ?" Z8 s$ z0 u* i/ Q
。这就要平时多做做综合的题型了。 & a, x1 R# h) F9 T8 R/ n- d
1. 把oibh上的论文看看(大概几百篇的,我只看了一点点,呵呵)。
4 J% J8 ^% c. w9 D) {: Z2 q [9 y7 e+ X 2. 平时扫扫zoj上的难题啦,别老做那些不用想的题.(中大acm的版主经常说我挑简单的来: c( c) v$ N! e8 T
做:-P )
+ x% K) G. Z& K8 ~& R* X 3. 多参加网上的比赛,感受一下比赛的气氛,评估自己的实力.
; E5 g$ [9 L4 y4 B/ U0 y 4. 一道题不要过了就算,问一下人,有更好的算法也打一下。
4 C5 }5 e* K9 {! r3 g# R 5. 做过的题要记好 :-) |
|