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)

(2)最小费用最大流(poj2516,poj2195)

(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) 和 在线算法 

(RMQ+dfs)).(poj1330,bzoj1977) 

(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)区间覆盖(封印一击,引水入城).

二.逆向思维.

(1)向分支少的反向搜索(逆序Fibonacii)

三.可行解.

 

(1)一般模拟问题枚举时考虑的多出解(光标移动)

 

四.数学模型.

(1)矩阵(4a矩阵,最大子矩阵,矩阵的对角线)

(2)Gauss消元(EXTENDED LIGHTS OUT,人偶师,球形空间产生器)

(3)逆数组(区间修改,矩阵修改)

五.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)

(2)Winter_1(集合计数,无穷数,作业问题)

(3)Winter_2(凸四边形问题,两圆问题)

(3)Winter_3(磁盘碎片整理,虚拟水世界,麦田)

(4)Winter_4(盖楼,继任者,路径问题)

(5)Winter_5(树上路径问题,选边问题)

(6)男人八题(Tree)

(7)2013-2-23(子序列,稳定性,数位和乘积)

(8)2013-3-2(关系,跳跃,骰子)

(9)2013-3-9(两个子序列,人偶师,维护队列)

(10)2013-3-16(回文子串对,树,放球游戏)

(11)2013-3-22(图书馆)

(12)2013-3-23(溜冰,圈地,银河之星)

(13)#176 (Div. 2)(IQ Test,Pipeline,Lucky Permutation,Shifting,Main Sequence)

(14)CH 白色情人节欢乐赛 - Day1(Easy)(②第一天)

(15)2013-3-28(射箭,上学路线,分割)

(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的输入输出. 

(1)占位符(POJ 3748,开门人和关门人)

(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

 

 

Block of New Year 题目来源 题目名称 解法 POJ 1113 Wall Quickhull HDU 1234 开门人和关门人 scanf特殊占位符 BZOJ 1098 [POI2007]办公楼biu 链表优化Dfs BZOJ 1034 [ZJOI2008]泡泡堂BNB 加强版田忌赛马 BZOJ 1500 [NOI2005]维修数列 Splay解决数列维护问题 UVA 10209 Is This Integration ? 容斥原理求图形面积 BZOJ 1507 [NOI2003]Editor 块状链表 UVA 10905 Children’s Game qsort对字符串排序，字符串连接贪心 BZOJ 1076 [SCOI2008]奖励关 期望DP-从后向前规避不可能状态	Block of New Term 题目来源 题目名称 解法 FZU 1040 基因序列相似性问题 CLCS FZU 1922 非主流 预处理0,1的个数 POJ 3070 Fibonacci 矩阵幂 BZOJ 1977 [BeiJing2010组队]次小生成树 Tree 次小生成树,LCA的位运算 POJ 1330 Nearest Common Ancestors LCA加强.其实只要递归到根节点+标记就行了 POJ 1091 跳蚤 扩展欧几里德有解前提+容斥原理 UVA 11292 The Dragon of Loowater 勇者斗恶龙,经典贪心问题 HDU 1075 What Are You Talking About Tries的插入和查找 BZOJ 1502 [NOI2005]月下柠檬树 Simpson积分
Block of 3.15 题目来源 题目名称 解法 UVA 11729 Commando War 按执行时间从大到小排序贪心 RQNOJ 698 矩形计数 圆内接矩形对角线必过圆心 BZOJ 1084 [SCOI2005]最大子矩阵 Dp长矩阵 CH 白色情人节1 ②第一天 KM算法 POJ 2704 Pascal's Travels 裸DP FZU 2100 排队 Treap维护子树最大值 CH Adera 3 ZZB的数学作业 数列拆分构造 BZOJ 1007 水平可见直线 斜率排序+栈贪心 BZOJ 1185 [HNOI2007]最小矩形覆盖 旋转卡壳+点积逼近垂直直线	Block of 省选前 题目来源 题目名称 解法 CH 白色情人节2 ⑤我心永恒 字符串序列个数统计 BZOJ 2705 [SDOI2012]Longge的问题 欧拉函数 BZOJ 2732 [HNOI2012]射箭 方程转半平面交 POJ 2484 A Funny Game 对称博弈 POJ 2362 Square 相对顺序剪枝 POJ 2553 The Bottom of a Graph 缩点重构图 BZOJ 3098 Hash Killer II 生日攻击 UVA 11538 Chess Queen 矩形对角线计数 BZOJ 3097 Hash Killer I 弱等数论+构造法
Block of 半期考后 题目来源 题目名称 解法 BZOJ 2190 [SDOI2008]仪仗队 O(n)线性筛欧拉函数	Block of ?? 题目来源 题目名称 解法
Block of ?? 题目来源 题目名称 解法	Block of ?? 题目来源 题目名称 解法
Block of ?? 题目来源 题目名称 解法	Block of ?? 题目来源 题目名称 解法