求ACM的一个通用算法..还是新手。
一、基本算法:
(1)枚举。(poj1753，poj2965)
(2)贪婪(POJ 1328，POJ 2109，POJ 2586)
(3)递归和分治法。
(4)递归。
(5)结构方法。(poj3295)
(6)模拟法。(POJ 1068，POJ 2632，POJ 1573，POJ 2993，POJ 2996)
2.图形算法:
(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)字符串(POJ 1035，POJ 3080，POJ 1936)
(2)排序(快速排序、并行排序(与反数有关)和堆排序)(poj2388，poj2299)
(3)简单并集的应用。
(4)高效的搜索方法，例如哈希表和二分搜索法(数字哈希、字符串哈希)
(poj3349、poj3274、POJ2151、poj1840、poj2002、poj2503)
(5)霍夫曼树(poj3253)
(6)堆
(7)trie树(静态树，动态树)(poj2513)
四。简单搜索
(1)深度优先搜索(POJ 2488，POJ 3083，POJ 3009，POJ 1321，POJ 2251)
(2)广度优先搜索(POJ 3278，POJ 1426，POJ 3126，POJ 3087。POJ 3414)
(3)简单的搜索技巧和剪枝(POJ 2531，POJ 1416，POJ 2676，1129)
动词 （verb的缩写）动态规划
(1)背包问题。(poj1837，poj1276)
(2)下表的简单DP(参考lrj的书第149页):
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]+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.求解单调函数的二分法。(POJ 3273，POJ 3258，POJ 1905，POJ 3122)
七。计算几何。
(1)几何公式。
(2)叉积和点积的应用(如判断线段的交点、点到线段的距离等。).(poj2031，poj1039)
(3)多边形的简单算法(求面积)及相关判断(点是否在多边形内)
(poj1408，poj1584)
(4)凸包。(POJ 2187，POJ 1113)
中级:
一、基本算法:
(1)C++标准模板库的应用。(poj3096、poj3007)
(2)更复杂模拟题的训练(POJ 3393，POJ 1472，POJ 3371，POJ 1027，POJ 2706)。
2.图形算法:
(1)微分约束系统的建立与求解。(poj1201，poj2983)
(2)最小费用最大流量(POJ 2516，POJ 2516，POJ 2195)
(3)双连接组件(poj2942)
(4)强连通分支及其收缩点。(poj2186)
(5)图形的切割边和切割点(poj3352)
(6)最小割模型和网络流协议(poj3308，)
三。数据结构。
(1)段树。(POJ 2528，POJ 2828，POJ 2777，POJ 2886，POJ 2750)
②静态二叉查找树。(poj2482、poj2352)
(3)树组(POJ1195，POJ3321)
④RMQ。(poj3264、poj3368)
(5)并行搜索集的高级应用。(poj1703，2492)
(6)KMP算法。(poj1961，poj2406)
四。搜索
(1)最佳修剪和可行性修剪
(2)搜索技巧和优化(POJ3411，POJ1724)
(3)内存搜索(poj3373，poj1691)
动词 （verb的缩写）动态规划
(1)更复杂的动态规划(如解决特殊算子问题的动态规划等。)
(poj1191，poj1054，poj3280，poj2029，poj2948，poj1925，poj3034)
(2)记录状态的动态规划。(POJ3254，POJ2411，POJ1185)
(3)树形动态规划(POJ 2057，POJ 1947，POJ 2486，POJ 3140)
不及物动词数学
(1)组合数学:
1.排斥原则。
鸽笼原则。
3.置换群和Polya定理(POJ 1286，POJ 2409，POJ 3270，POJ 1026)。
4.递归关系与生成函数。
(2)数学。
高斯消去法(POJ 2947，POJ 1487，POJ 2065，POJ 1166，POJ 1222)。
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)几何工具的综合应用。(POJ 1819，POJ 1066，POJ 2043，POJ 3227，POJ 2165，POJ 3429)
高级:
1.基本算法要求:
(1)代码写得很快，简洁但不失风格。
(poj2525，poj1684，poj1421，poj1048，poj2050，poj3306)
(2)保证正确性和效率。poj3434
2.图形算法:
(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+外勤部))。(poj1330)
(3) deque及其应用(维护一个单调的队列在动态规划中优化状态转移往往起着重要的作用。
目的)。(poj2823)
(4)左倾树(可组合堆)。
(5)后缀树(非常有用的数据结构，也是赛区考题热点)。
(poj3415，poj3294)
四。搜索
(1)难搜题训练(POJ 1069，POJ 3322，POJ 1475，POJ 1924，POJ 2049，POJ 3426)
(2)宽搜索的状态优化:用M进制数存储状态，转化为哈希表判断重复，逐位压缩存储状态，双向宽搜索，A*算法。(POJ 1768，POJ 1184，POJ 1872，POJ 65438+。
(3)深度搜索的优化:尽量使用位运算，一定要加剪枝，函数参数尽量少，层数不容易太大。可以考虑双向搜索或旋转搜索和IDA*算法。(POJ3131，POJ2870，POJ2286)
动词 （verb的缩写）动态规划
(1)需要数据结构优化的动态规划。
(poj2754、poj3378、poj3017)
(2)四边形不等式理论。
(3)困难状态DP(poj3133)
不及物动词数学
(1)组合数学。
1.莫比乌斯反演(poj2888，poj2154)
2.偏序关系理论。
(2)博弈论。
1.极大极小过程(poj3317，poj1085)
2.尼姆问题。
七。计算几何。
(1)半平面(poj3384，poj2540)的交点
(2)可视视图的建立(poj2966)
(3)点集的最小圆覆盖。
(4)鞋跟校准(poj2079)
八。综合题。
(poj3109，poj1478，poj1462，poj2729，poj2048，poj3336，poj3315，poj2148，poj1263)
Dp状态设计和方程总结
1.不完整状态记录
& lt1 & gt；青蛙过河
& lt2 & gt使用区间dp
2.背包问题
& lt1 & gt；0-1背包，经典问题
& lt2 & gt无限背包，经典问题
& lt3 & gt确定性背包问题
& lt4 & gt有从属关系的背包问题
& lt5 & gt+-1背包问题
& lt6 & gt最优值的双背包
& lt7 & gt结构三角形问题
& lt8 & gt具有下界的背包问题(012背包)
3.线性动态规划问题
& lt1 & gt；积木游戏问题
& lt2 & gt决斗(决定性问题)
& lt3 & gt圆的最大多边形问题
& lt4 & gt计算单词数量的问题
& lt5 & gt棋盘分割
& lt6 & gt排定问题
& lt7 & gt最小逼近问题(求两个数之比最接近某数/两个数之和等于某数等。)
& lt8 & gt方块消除游戏(一个间隔可以连续消除，以获得最大利益)
& lt9 & gt资源分配问题
& lt10 >数字三角问题
& lt11 & gt；漂亮的印刷
& lt12 >邮局问题和结构化答案
& lt13 >最高积木问题
& lt14 & gt；两段连续和最大
& lt15 >二次幂和问题
& lt16 >n个数的最大m段和
& lt17 >交叉最大数问题
4.确定性问题的dp(如判断整除性、判断可达性等。)
& lt1 & gt；模k问题的Dp
& lt2 & gt特殊模K问题，求最大(最小)模K的个数。
& lt3 & gt变换数问题
5.单调性优化的动态规划
& lt1 & gt；1和问题
& lt2 & gt2-和问题
& lt3 & gt序列划分问题(单调队列优化)
6.划分问题(多边形划分/石头合并/圆形划分/最大乘积)
& lt1 & gt；凸多边形的三角剖分
& lt2 & gt最大产品问题
& lt3 & gt多边形游戏(算子在多边形的边上，顶点有权重)
& lt4 & gt石头合并(N ^ 3/N ^ 2/NLOGN优化)
7.贪婪动态规划
& lt1 & gt；最优装载问题
& lt2 & gt部分背包问题
& lt3 & gt船的问题
& lt4 & gt贪婪策略
& lt5 & gt双机调度问题的Johnson算法
8.状态dp
& lt1 & gt；牛仔射击问题(游戏类)
& lt2 & gt哈密顿路径的状态dp
& lt3 & gt两点平衡的平衡问题
& lt4 & gt有向图的最近二部图
9.采油树dp
& lt1 & gt；完美服务器问题(每个节点有3种状态)
& lt2 & gt小胖守宫的问题
& lt3 & gt网络收费问题
& lt4 & gt在树上漫游
& lt5 & gt树上的游戏
& lt6 & gt树的最大独立集问题
& lt7 & gt树的最大平衡值问题
& lt8 & gt构造树的最小环