转载请注明出处:優YoUhttp://blog.csdn.net/lyy289065406/article/details/6642573
改革V1.0
——刷题法则
恭祝Blog.cn开博2012.8.1
较初级:
OJ上的一些水题(可用来练手和增加自信)
(poj1003,poj1004,poj1005,poj1207,poj3299,poj2159,poj2739,poj1083,poj2262,poj2255,poj3094,CF 253A)
线性筛素数(poj3006)
初级:
一.基本算法:
(1)枚举. (poj1018,poj1753,poj2965)
(2)贪心(poj1328,poj2109,poj2586)
(3)递归和分治法.
(4)递推.
(5)构造法.(poj3295,poj3239)
(6)模拟法.(poj1008,poj1068,poj2632,poj1573,poj2993,poj2996,poj3087)
(7)高精度算法(poj1001,poj1503,poj2389,poj2602,poj3982,poj3289,poj2390)
(8)字符串处理(易位构字法)
(9)日期(评委会)
二.图算法:
(1)图的深度优先遍历和广度优先遍历.
(2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240,防御机制)
(3)最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
(4)拓扑排序 (poj1094)
(5.1)二分图的最大匹配 (匈牙利算法) (poj3041,poj1325,poj3020,poj3692,bzoj2547)
(5.2)稳定婚姻系统(The Stable Marriage Problem,zoj1676)
(6)网络流算法(压入重标法,KM算法). (poj1459,poj3436,poj1273,poj1149,CF 237E)
三.数据结构.
(1)串 (poj1016,poj1035,poj3080,poj1936)
(2.1Qsort)排序(快排) (poj2388)
(2.2)归并排序(与逆序数有关)、堆排(poj1007,poj1804,poj2299)
(2.3)桶排(数字卡片)
(3)并查集.
(4)哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj1002,poj3349,poj3274,poj1840,poj2002,poj3432,poj2503)
(5)优先队列(poj3253)
(6)堆
(7)trie树(静态建树、动态建树) (高级打字机,poj2513)
(8)队列(实验误差)
四.简单搜索
(1.1)深度优先搜索 (poj2488,poj3083,poj3009,poj1321)
(1.2)深搜模拟栈(祖孙询问)
(2)广度优先搜索(poj3278,poj1426,poj3126,poj3414,poj2251)
(3)简单搜索技巧和剪枝(poj1010,poj2362,poj1011,poj1416,poj2676,poj1129)
五.动态规划
(1)背包问题. (poj1837,poj1276,poj1014)
(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} (最长公共子序列)
(poj1015,poj3176,poj1163,poj1080,poj1159)
3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学
(1)组合数学:
1.加法原理和乘法原理(数字).
2.排列组合(后院).
3.递推关系.
(poj1012,poj3252,poj1850,poj1496,poj1019,poj1942)
4.卡特兰数(poj2084)
(2)数论.
1.素数与整除问题(Vijos1490,TyvjP2067)
2.进制位(zoj2529).
3.1.同余模运算.
(poj2305,poj2635,poj3292,poj1845,poj2115,poj3844)
3.2.同余模方程(poj2115)
4.逻辑推理.
(poj1013,poj1017)
4.中国余数定理(poj1006)
5.格雷码(poj1832)
(3)计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
(4)随机化算法(poj2531)
(5)概率(poj2151)
七.计算几何学.
(1)几何公式.
(2)叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1269,poj1039)
(3)多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交) (poj1408,poj1584)
(4)凸包. (poj1696,poj2187,poj1113)
中级:
一.基本算法:
(1)C++的标准模版库的应用. (poj3096,poj3007)
(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706,poj1009)
二.图算法:
(1)差分约束系统 (poj1716,poj1201,poj2983)
(3)双连通分量(poj2942)
(4)强连通分支及其缩点(poj2186)
(5)图的割边和割点(poj1523,poj3352,poj3177)
(6)最小割模型、网络流规约(poj3308 )
三.数据结构.
(1)线段树. (poj2528,poj2828,poj2777,poj2886,poj2750,poj3468)
(2)静态二叉检索树. (poj2482,poj2352)
(3)树状树组(poj1195,poj3321)
(4)RMQ. (poj3264,poj3368)
(5)并查集的高级应用. (poj1703,2492)
(6.1)KMP的Next函数(poj1961,poj2752,poj2406,poj1226,poj3080)
(6.2)KMP的覆盖函数(poj2185,poj3461)
四.搜索
(1)最优化剪枝和可行性剪枝
(2)搜索的技巧和优化 (poj1020,poj3411,poj1724)
(3)记忆化搜索(poj3373,poj1691)
(4)搜索与状态压缩(poj1184)
五.动态规划
(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
4.ex_gcd(poj3101,poj1061)
(3)计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
5.拉格朗日乘数法(bzoj2876)
(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) 和 在线算法
(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)
改革V2.0
——Add 法则
记2012.11.21
较高级:
一.区间贪心.
二.逆向思维.
(1)向分支少的反向搜索(逆序Fibonacii)
三.可行解.
(1)一般模拟问题枚举时考虑的多出解(光标移动)
四.数学模型.
(2)Gauss消元(EXTENDED LIGHTS OUT,人偶师,球形空间产生器)
五.DP序.
(1)由当前向后(宿舍分享)
(2)a人表示状态(扫雷Mine)
六.计算几何.
(1)线段与直线相交(poj 3304)
(2.1)凸包(平面最远点对,卷包裹算法,QuickHull)
(2.2)凸包唯一性(稳定凸包)
(3)点集(TOYS,Toy Storage)
(4)三角形(近似直角三角形)
(5)Pick公式(Triangle)
(6)旋转卡壳(最小矩形覆盖)
(7)半平面交([HNOI2012]射箭)
七.组合数学.
(1)错排公式(不容易系列之一)
八.High图论.
(1)次小生成树与严格次小生成树(次小生成树,严格次小生成树)
(2)KM算法-(带权二分图匹配)(②第一天)
(3)缩点(The Bottom of a Graph)
九.HighDp优化.
(1)层次图
(2)状态压缩
(3)轮廓线
(4)斜率优化
(5)四边形不等式
十.积分.
(1)Simpson积分([NOI2005]月下柠檬树)
十一.解析几何.
(1)斜率排序(圈地,[HNOI2008]水平可见直线)
偏高级:
一.贪心策略泛讲.
(1)田忌赛马([ZJOI2008]泡泡堂BNB,勇者斗恶龙,打地鼠)
二.AC数论.
(1)欧拉函数(Longge的问题,[SDOI2008]仪仗队)
(2)取模
1.除法取模-乘法逆元([ZJOI2010]Perm 排列计数)
三.博弈论.
(1)对称博弈(A Funny Game)
四.搜索剪枝.
(1)相对顺序(Square)
五.概率学.
(1)Hash概率
1.生日攻击(Hash Killer II)
六.High哈希.
(1)反例
1.u64溢出(Hash Killer I)
2.%Mod(Hash Killer II)
七.2D数据结构.
(1)2D树状数组(上帝造题的七分钟)
八.High网络流.
(1)对偶图(狼抓兔子)
改革V3.0
——Contest 法则
记2013.1.1
很高级:
一.Codeforce比赛.
(1)#162 (Div. 2)(Colorful Stones (Simplified Edition),Roadside Trees (Simplified Edition),Escape from Stones,Good Sequences)
(3)Winter_2(凸四边形问题,两圆问题)
(3)Winter_3(磁盘碎片整理,虚拟水世界,麦田)
(5)Winter_5(树上路径问题,选边问题)
(6)男人八题(Tree)
(8)2013-3-2(关系,跳跃,骰子)
(11)2013-3-22(图书馆)
(13)#176 (Div. 2)(IQ Test,Pipeline,Lucky Permutation,Shifting,Main Sequence)
(14)CH 白色情人节欢乐赛 - Day1(Easy)(②第一天)
(16)2013-3-29(屋,电梯,矩形覆盖)
二.集训队论文.
(1)运用伸展树解决数列维护问题([NOI2005]维修数列)
改革V4.0
——专题法则
记2013.1.31
极高级-数据结构:
一.二叉搜索树-Treap.
(1)第k大数(Black box)
(2)MaxV(排队)
二.链表.
(1)链表优化Dfs([POI2007]办公楼biu)
(2)块状链表([NOI2003]Editor)
支线-《统计的力量》zkw线段树:
(1)单点更新(HDU 1166,POJ 2828,HDU 4302,POJ 3264,HDU 4288,HDU 4417,HDU 4366)
(2)区间更新(POJ 3468,HDU 4031,HDU 4027,HDU 4325,HDU 4267,HDU 3954,HDU 4358,CF 242E,RQNOJ 60)
(3)区间合并(POJ 3667,HDU 4339,HDU 4351
(4)扫描线(HDU 1542,POJ 1151,POJ 1389,POJ 3277,HDU 3265)
(5)二维线段树(HDU 1823,POJ 2155)
(6)线段树上的动态规划(POJ 1631,POJ 3298,POJ 2355,POJ 3171)
支线-《C++ Primer》STL库:
一.C的输入输出.
(2)小数保留位数(比赛)
二.STL中的容器.
(1)Map(Tyvj P2058)
(2)priority_queue(RQNOJ 658)
(3)vector
(4)list
(5)deque
支线-Python:
一.列表list.
(1)数组(PE 47-Distinct primes factors)
二.random*.
(1)
改革V5.0
——Block 法则
记2013.1.31
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
十.积分.
(1)Simpson
支线-《C++ Primer》STL库:
一.C的输入输出.
(1)占位
各种膜拜神犇