acm竞赛的算法

A. acm必备知识都有哪些

备战ACM资料
一：知识点
数据结构：
1，单，双链表及循环链表
2，树的表示与存储，二叉树（概念，遍历）二叉树的
应用（二叉排序树，判定树，博弈树，解答树等）
3，文件操作（从文本文件中读入数据并输出到文本文
件中）
4，图（基本概念，存储结构，图的运算）
数学知识
1，离散数学知识的应用（如排列组合、简单的图论，数
理逻辑）
2，数论知识
3，线性代数
4，组合代数
5，计算几何
二 算法
1，排序算法（冒抛法，插入排序，合并排序，快速排
序，堆排序）
2，查找（顺序查找，二分发）
3，回溯算法
4，递归算法
5，分治算法
6，模拟法
7，贪心法
8，简单搜索算法（深度优先，广度优先），搜索中的
剪枝，A*算法
9，动态规划的思想及基本算法
10，高精度运算
三、ACM竞赛的题型分析
竞赛的程序设计一般只有16种类型，它们分别是：
Dynamic Programming （动态规划）
Greedy （贪心算法）
Complete Search （穷举搜索）
Flood Fill （不知该如何翻译）
Shortest Path （最短路径）
Recursive Search Techniques （回溯搜索技术）
Minimum Spanning Tree （最小生成树）
Knapsack （背包问题）
Computational Geometry (计算几何学)
Network Flow （网络流）
Eulerian Path （欧拉回路）
Two-Dimensional Convex Hull （不知如何翻译）
BigNums （大数问题）
Heuristic Search （启发式搜索）
Approximate Search （近似搜索）
Ad Hoc Problems （杂题）
四 ACM竞赛参考书
《实用算法的分析与程序设计》 （吴文虎，王建德着，电子工业出版社，竞赛类的黑宝书）
《青少年国际和全国信息学（计算机）奥林匹克竞赛指导）――组合数学的算法
和程序设计》（吴文虎，王建德着，清华大学出版社，参加竞赛组合数学必学）
《计算机算法设计与分析》 （王晓东编着，最好的数据结构教材）
《数据结构与算法》 （傅清祥，王晓东编着，我所见过的最好的算法教材）
《信息学奥林匹克竞赛指导――1997-1998竞赛试题解析》（吴文虎，王建德着，清华大学出版社）
《计算机程序设计技巧》 D.E.Kruth着，算法书中最着名的《葵花宝典》，大师的作品，难度大）
《计算几何》周陪德着
《ACM国际大学生程序设计竞赛试题与解析（一）》 （吴文虎着，清华大学出版社）
《数学建模竞赛培训教材》 共三本 叶其孝主编
《数学模型》 第二版 姜启源
《随机规划》
《模糊数学》
《数学建模入门》 徐全智
《计算机算法设计与分析》 国防科大
五 常见的几个网上题库
常用网站：
1）信息学初学者之家：http://oibh.ioiforum.org/
（2）大榕树编程世界：http://www.fjsdfz.org/~drs/program/default.asp
（3）中国教育曙光网：http://www.chinaschool.org/aosai/
（4）福建信息学奥林匹克：http://www.cfcs.com.cn/fjas/index.htm
（5）第20届全国青少年信息学奥林匹克竞赛：http://www.noi2003.org/
（6）第15届国际青少年信息学奥林匹克竞赛：http://www.ioi2003.org/
（7）全美计算机奥林匹克竞赛：http://ace.delos.com/usacogate
（8）美国信息学奥林匹克竞赛官方网站：http://www.usaco.org/
（9）俄罗斯Ural州立大学：http://acm.timus.ru/
（10）西班牙Valladolid大学：http://acm.uva.es/problemset
（11）ACM-ICPC：http://icpc.baylor.e/icpc/
（12）北京大学：http://acm.pku.e.cn/JudgeOnline/index.acm
（13）浙江大学：http://acm.zju.e.cn/
（14）IOI：http://olympiads.win.tue.nl/ioi/
（15）2003年江苏省信息学奥林匹克竞赛夏令营：http://jsoi.czyz.com.cn
（16）http://acm.zju.e.cn
（17）http://acm.zsu.e.cn
（18）www.shumo.com
（19）http://www.bepark.com/downldmanag/index.asp
（20）http://www.yh01.com colin_fox/colin_fox
五 如何备战ACM/ICPC
1，个人准备（算法书，习题集，网上做题和讨论）
2，1000题=亚洲冠军=世界决赛
3，做好资料收集和整理工作

B. 什么叫acm程序设计与算法分析

acm程序设计与算法分析
这不复杂,

C. 参加acm竞赛，请问需要掌握哪些算法请行家指点，谢谢

看你要到什么层次了？
搜索，动态规划，数论，组合数学，计算几何，图论，博弈，数据结构...

D. 请教做ACM的常用算法..还是菜鸟

初期:
一.基本算法:
(1)枚举. (poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295)
(6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)
(6)最大流的增广路算法(KM算法). (poj1459,poj3436)
三.数据结构.
(1)串 (poj1035,poj3080,poj1936)
(2)排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)
(3)简单并查集的应用.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
(5)哈夫曼树(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (poj2513)
四.简单搜索
(1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)
(3)简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)
五.动态规划
(1)背包问题. (poj1837,poj1276)
(2)型如下表的简单DP(可参考lrj的书 page149):
1.E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)
(poj3176,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
(2)数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
(4)凸包. (poj2187,poj1113)
中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)
二.图算法:
(1)差分约束系统的建立和求解. (poj1201,poj2983)
(2)最小费用最大流(poj2516,poj2516,poj2195)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点.(poj2186)
(5)图的割边和割点(poj3352)
(6)最小割模型、网络流规约(poj3308, )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6)KMP算法. (poj1961,poj2406)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)

五.动态规划
(1)较为复杂的动态规划(如动态规划解特别的施行商问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
(2)记录状态的动态规划. (POJ3254,poj2411,poj1185)
(3)树型动态规划(poj2057,poj1947,poj2486,poj3140)
六.数学
(1)组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.

(2)数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
(4)随机化算法(poj3318,poj2454)
(5)杂题.
(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.
(1)坐标离散化.
(2)扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用).
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
(3)多边形的内核(半平面交)(poj3130,poj3335)
(4)几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)
高级:
一.基本算法要求:
(1)代码快速写成,精简但不失风格
(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)
(2)保证正确性和高效性. poj3434
二.图算法:
(1)度限制最小生成树和第K最短路. (poj1639)
(2)最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
(3)最优比率生成树. (poj2728)
(4)最小树形图(poj3164)
(5)次小生成树.
(6)无向图、有向图的最小环
三.数据结构.
(1)trie图的建立和应用. (poj2778)
(2)LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法
(RMQ+dfs)).(poj1330)
(3)双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的
目的). (poj2823)
(4)左偏树(可合并堆).
(5)后缀树(非常有用的数据结构,也是赛区考题的热点).
(poj3415,poj3294)
四.搜索
(1)较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)
(2)广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)
(3)深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)
五.动态规划
(1)需要用数据结构优化的动态规划.
(poj2754,poj3378,poj3017)
(2)四边形不等式理论.
(3)较难的状态DP(poj3133)
六.数学
(1)组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
(2)博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.
(1)半平面求交(poj3384,poj2540)
(2)可视图的建立(poj2966)
(3)点集最小圆覆盖.
(4)对踵点(poj2079)
八.综合题.
(poj3109,poj1478,poj1462,poj2729,poj2048,poj3336,poj3315,poj2148,poj1263)

Dp状态设计与方程总结

1.不完全状态记录

<1>青蛙过河问题

<2>利用区间dp

2.背包类问题

<1> 0-1背包，经典问题

<2>无限背包，经典问题

<3>判定性背包问题

<4>带附属关系的背包问题

<5> + -1背包问题

<6>双背包求最优值

<7>构造三角形问题

<8>带上下界限制的背包问题(012背包)

3.线性的动态规划问题

<1>积木游戏问题

<2>决斗（判定性问题）

<3>圆的最大多边形问题

<4>统计单词个数问题

<5>棋盘分割

<6>日程安排问题

<7>最小逼近问题(求出两数之比最接近某数/两数之和等于某数等等)

<8>方块消除游戏(某区间可以连续消去求最大效益)

<9>资源分配问题

<10>数字三角形问题

<11>漂亮的打印

<12>邮局问题与构造答案

<13>最高积木问题

<14>两段连续和最大

<15>2次幂和问题

<16>N个数的最大M段子段和

<17>交叉最大数问题

4.判定性问题的dp(如判定整除、判定可达性等)

<1>模K问题的dp

<2>特殊的模K问题，求最大(最小)模K的数

<3>变换数问题

5.单调性优化的动态规划

<1>1-SUM问题

<2>2-SUM问题

<3>序列划分问题(单调队列优化)

6.剖分问题(多边形剖分/石子合并/圆的剖分/乘积最大)

<1>凸多边形的三角剖分问题

<2>乘积最大问题

<3>多边形游戏(多边形边上是操作符,顶点有权值)

<4>石子合并(N^3/N^2/NLogN各种优化)

7.贪心的动态规划

<1>最优装载问题

<2>部分背包问题

<3>乘船问题

<4>贪心策略

<5>双机调度问题Johnson算法

8.状态dp

<1>牛仔射击问题(博弈类)

<2>哈密顿路径的状态dp

<3>两支点天平平衡问题

<4>一个有向图的最接近二部图

9.树型dp

<1>完美服务器问题(每个节点有3种状态)

<2>小胖守皇宫问题

<3>网络收费问题

<4>树中漫游问题

<5>树上的博弈

<6>树的最大独立集问题

<7>树的最大平衡值问题

<8>构造树的最小环

E. ACM常用的经典算法

1.明白内存在算法中的用处
2.二分查找 二分冥（a^b）
3.如果是计算机的，学数据结构的时候花点时间在二叉树上
4.递归
5.广搜 深搜 做点隐式图的题目 顺便学下状态的hash
6.最短路（spfa dij floyd） 我感觉可以当做搜索的优化
7.简单动态规划 背包等
8.要是你喜欢几何的话也可以看看几何中的一些基础知识 我感觉几何比较难拿分

接下可以学下线段树等一些数据结构（线段树可以优化很多问题，二叉树知道了，二分思想有了，线段树的基本操作可以秒杀）

接下去可以深入动态规划了。

接下去不归路在向你招手。

F. acm要学习哪些算法

最基本的、也是最核心的，掌握各种数据结构及其对应的高效算法，比如线性结构（顺序表、链表等）的查找、排序算法，树（二叉树、搜索树）的原理、基础的遍历、查找算法，图的原理、算法、应用场景。
学完之后就可以开始到各种OJ刷题了。

G. ACM动态规划问题（算法竞赛入门经典）

递归就不说了，明显是需要栈的逻辑结构维护的。简单说说对递推和DP的个人见解，只供参考。

DP=状态+状态转移方程
状态的关键特点是无后效性，简单地举例：奥运会某项目淘汰赛1/N决赛，成绩只跟以后的比赛有关，之前的成绩不带入（只考虑赛制）。如果你发现一个状态后面阶段决策需要用到前面阶段的状态信息，那么这就不是一个标准的DP。比如：
A - B1 - C1 - D
\-- EX ------/
如果将EX归为B段或C段，那么EX-D或者A-EX就跨越了跳跃了一个阶段，对于这个阶段来说他后面的阶段就用到了前面阶段的状态信息
当然这并不意味着不能采用DP算法，对于上面的例子，可以将EX本身拆为B2 - C2就可以满足DP条件了，对于连续状态的DP，类似的调整更多。

状态转移方程是状态到状态的决策
简单地说，就是贪心的那一部分，多条路你选择一条路的过程

很多时候，递推和DP难以区分，一般情况，状态转移决策明显是“选择”的时候，会当做DP，而如果计算比重较大，会当做递推；状态调整比较多时，可能认为是递推；连续状态可以归为DP。
例：M*N的的带权格子，从左上走到右下，每次只能向右或下移动一格，求权值加和最大（小）的路径条数。

还有一个相关词叫做“递推规划”，有兴趣的话可以自己看下相关资料

解释之后答案很明显：DP要有状态转移方程。甚至可以说DP的关键就是状态转移方程。
你的第一个问题，希望你把书名报一下，我貌似没有白皮的

H. ACM 中常用的算法有哪些

排序（选择，冒泡，快速，归并，堆，基数，桶排序等）
递归，回溯
概率，随机
公约数，素数
因数分解
矩阵运算
线性规划
最小二乘
微积分
多项式分解和级数
图论算法：
哈夫曼树（即最优二叉树）
哈希表
Prim,Kruskal算法（即最小生成树算法）
红黑树
a-B剪枝法
深、广度搜索
拓扑排序
强连通分量
Dijkstra,Bellman-Ford,Floyd-Warashall算法（最短路径算法）
计算几何（线段相交，凸包，最近点对）

I. 关于ACM竞赛

ACM考的是算法设计,编程,理解能力.
基本上ACM的题目都是英文的,所以你的英文要到火候,这个lz
应该没问题吧.

还有最主要的就是算法了,你可以去肯"算法导论"这本牛书.

第三就是编程能力,ACM竞赛中,时间也是一项衡量指标,怎样在最快的时间内解决问题,编译通过,并且运行正确.

最后,我觉得考虑问题的全面性也是很重要的,ACM的题目,很多都会有临界情况,如何让你的程序能够通过这些临界值的检验,很考察一个人思考问题的全面性的.