POJ题目分类-基础

Author Avatar
陈高勋 9月 09, 2016
  • 在其它设备中阅读本文章

题目分类转载自 cnblogs,截取部分基础练习题目,POJ传送门

经典

  • 1011(搜索好题)
  • 1012(学会打表)
  • 1013
  • 1019(它体现了很多此类问题的特点)
  • 1050(绝对经典的dp)
  • 1088(dp好题)
  • 1157(花店,经典的dp)
  • 1163(经典dp)
  • 1328(贪心)
  • 1458(最长公共子序列)
  • 1647(很好的真题,考临场分析准确和下手迅速)
  • 1654(学会多边形面积的三角形求法)
  • 1655(一类无根树的dp问题)
  • 1804(逆序对)
  • 2084(经典组合数学问题)
  • 2187(用凸包求最远点对,求出凸包后应该有O(N)的求法)
  • 2195(二分图的最佳匹配)
  • 2242(计算几何经典)
  • 2295(等式处理)
  • 2353(dp,但要记录最佳路径)
  • 2354(立体解析几何)
  • 2362(搜索好题)
  • 2410(读懂题是关键)
  • 2411(经典dp)

一.基本算法

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