• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • 北大ACM – POJ试题分类

    ACM-POJ EXP 5786阅读 2评论

     
    相关推荐文:
    旧版POJ分类目录: http://exp-blog.com/2018/06/10/pid-136/
    ACM绝版资源公开( 参考书、模板、讲义、指导): http://exp-blog.com/2018/07/11/pid-1777/
    ACM测试数据合集: http://exp-blog.com/2018/06/28/pid-1362/
    一位ACMer过来人的心得: http://exp-blog.com/2018/06/13/pid-113/

    POJ离线版题目POJ封面书《程序设计导引及在线实践》(密码:9ty5cx)


    1.入门水题

    可用于练手与增强自信
    POJ-1003 POJ-1004 POJ-1005 POJ-1207 POJ-3299 POJ-2159 POJ-1083 POJ-3094

    2.初级

    2.1. 基本算法
    枚举 POJ-1753 POJ-2965
    贪心 POJ-1328 POJ-2586
    递归和分治法
    递推
    构造法 POJ-3295 POJ-3239
    模拟法 POJ-1008 POJ-1068 POJ-2632 POJ-1573 POJ-2993 POJ-2996 POJ-3087
    高精度算法 POJ-1001 POJ-1503 POJ-2109 POJ-2389 POJ-2602 POJ-3982
    21位大数的水仙花数

    2.2. 图算法
    图遍历(前序序列、中序序列、后序序列) POJ-2255
    最短路径算法
    (dijkstra, bellman-ford,
    floyd, heap+dijkstra)
    POJ-1860 POJ-3259 POJ-1062
    POJ-2253 POJ-1125 POJ-2240
    最小生成树算法(prim, kruskal) POJ-1789 POJ-2485 POJ-1258 POJ-3026
    拓扑排序 POJ-1094
    二分图的最大匹配 (匈牙利算法) POJ-3041 POJ-3020
    最大流的增广路算法(压入重标法、KM算法) POJ-1459 POJ-3436

    2.3. 数据结构
    POJ-1016 POJ-1035 POJ-3080 POJ-1936
    排序(快排、归并排、堆排) POJ-1007 POJ-2388 POJ-1804 POJ-2299
    并查集
    高效查找法
    (数的Hash、串的Hash、二分查找)
    POJ-1002 POJ-3349 POJ-3274 POJ-1840 POJ-2002 POJ-3432 POJ-2503
    哈夫曼树、优先队列 POJ-3253
    trie树(静态建树、动态建树) POJ-2513

    2.4. 搜索
    深度优先搜索DFS POJ-2488 POJ-3083 POJ-3009 POJ-1321
    广度优先搜索BFS POJ-3278 POJ-1426 POJ-3126 POJ-3414 POJ-2251
    简单搜索技巧和剪枝 POJ-1010 POJ-2362 POJ-1011 POJ-1416 POJ-2676 POJ-1129

    2.5. 动态规划
    背包问题 POJ-1837 POJ-1276 POJ-1014
    DP(动态规划)
    可参考《刘汝佳:算法法艺术与信息学竞赛》
    (黑书一)page 149
    E[j] = opt{D+w(i,j)} POJ-1018 POJ-3267 POJ-1260
    最长公共子序列
    E[i,j] = opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij}
    POJ-1015 POJ-3176 POJ-1163 POJ-1080 POJ-1159 POJ-2533 POJ-1836
    最优二分检索树问题
    C[i,j] = w[i,j]+opt{C[i,k-1]+C[k,j]}

    2.6. 数学
    组合数学 加法原理和乘法原理
    排列组合 POJ-3252 POJ-1850 POJ-1496 POJ-1942
    递推关系 POJ-1012 POJ-1019
    逻辑推理 POJ-1013 POJ-1017
    数论 素数与整除问题 POJ-2739 POJ-2262 POJ-3006
    进制位
    同余模运算 POJ-2305 POJ-2635 POJ-3292 POJ-1845 POJ-2115
    中国余数定理
    (扩展欧几里德、辗转相除法)
    POJ-1006
    计算方法 二分法求解单调函数 POJ-3273 POJ-3258 POJ-1905 POJ-3122
    随机化算法 POJ-2531
    概率 POJ-2151

    2.7. 计算几何学
    几何公式 POJ-2031
    叉积和点积的运用
    (如线段相交的判定、点到线段的距离等)
    POJ-1039
    多边形的简单算法(求面积) 和
    相关判定(点在多边形内、多边形是否相交)
    POJ-1408 POJ-1584
    凸包 POJ-1696 POJ-2187 POJ-1113

    3.中级

    3.1. 基本算法
    C++的标准模版库的应用 POJ-3096 POJ-3007
    较为复杂的模拟题的训练 POJ-3393 POJ-1472 POJ-3371 POJ-1027 POJ-2706 POJ-1009

    3.2. 图算法
    差分约束系统的建立和求解 POJ-1716 POJ-1201 POJ-2983
    最小费用最大流 POJ-2516 POJ-2195
    双连通分量 POJ-2942
    强连通分支及其缩点 POJ-2186
    图的割边和割点 POJ-1523 POJ-3352 POJ-3177
    最小割模型、网络流规约 POJ-3308

    3.3. 数据结构
    线段树 POJ-2528 POJ-2828 POJ-2777 POJ-2886 POJ-2750
    静态二叉检索树 POJ-2482 POJ-2352
    树状树组 POJ-1195 POJ-3321
    RMQ POJ-3264 POJ-3368
    并查集 POJ-1703 POJ-2492
    KMP算法 POJ-1961 POJ-2406

    3.4. 搜索
    最优化剪枝和可行性剪枝
    搜索的技巧和优化 POJ-1020 POJ-3411 POJ-1724
    记忆化搜索 POJ-3373 POJ-1691
    搜索与状态压缩 POJ-1184

    3.5. 动态规划
    较复杂的动态规划
    (如特别的旅行商问题等)
    POJ-1191 POJ-1054 POJ-3280 POJ-2029 POJ-2948 POJ-1925 POJ-3034
    记录状态的动态规划 POJ-3254 POJ-2411 POJ-1185
    树型动态规划 POJ-2057 POJ-1947 POJ-2486 POJ-3140

    3.6. 数学
    组合数学 容斥原理
    抽屉原理
    置换群与Polya定理 POJ-1286 POJ-2409 POJ-3270 POJ-1026
    递推关系和母函数
    数论 高斯消元法 POJ-2947 POJ-1487 POJ-2065 POJ-1166 POJ-1222
    概率问题 POJ-3071 POJ-3440
    GCD(最大公约数)
    LCM(最小公倍数)
    POJ-3101
    中国余数定理
    (扩展欧几里德、辗转相除法)
    计算方法 0/1分数规划 POJ-2976
    三分法求解单峰/单谷的极值
    矩阵法 POJ-3150 POJ-3422 POJ-3070
    迭代逼近 POJ-3301
    随机化算法 POJ-3318 POJ-2454
    杂题 POJ-1870 POJ-3296 POJ-3286 POJ-1095

    3.7. 计算几何学
    坐标离散化
    扫描线算法
    (如求矩形的面积和周长,常和线段树或堆一起使用)
    POJ-1765 POJ-1177 POJ-1151 POJ-3277 POJ-2280 POJ-3004
    多边形的内核(半平面交) POJ-3130 POJ-3335
    几何工具的综合应用 POJ-1819 POJ-1066 POJ-2043 POJ-3227 POJ-2165 POJ-3429

    4.高级

    4.1. 基本算法
    代码快速写成(精简但不失风格) POJ-2525 POJ-1684 POJ-1421 POJ-1048 POJ-2050 POJ-3306
    保证正确性和高效性 POJ-3434

    4.2. 图算法
    度限制最小生成树 和 第K最短路 POJ-1639
    最短路、最小生成树、二分图、最大流问题的相关理论
    (主要是模型建立和求解)
    POJ-3155 POJ-2112 POJ-1966 POJ-3281 POJ-1087 POJ-2289 POJ-3216 POJ-2446
    最优比率生成树 POJ-2728
    最小树形图 POJ-3164
    次小生成树
    无向图、有向图的最小环

    4.3. 数据结构
    trie图的建立和应用 POJ-2778
    LCA和RMQ问题:
    LCA(最近公共祖先问题)
    离线算法(并查集+dfs)
    在线算法(RMQ+dfs)
    POJ-1330
    双端队列和应用
    (维护一个单调的队列,常在动态规划中起到优化状态转移的目的)
    POJ-2823
    左偏树(可合并堆)
    后缀树 POJ-3415 POJ-3294

    4.4. 搜索
    较麻烦的搜索题目训练 POJ-1069 POJ-3322 POJ-1475 POJ-1924 POJ-2049 POJ-3426
    广搜优化
    (利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法)(RMQ+dfs)
    POJ-1768 POJ-1184 POJ-1872 POJ-1324 POJ-2046 POJ-1482
    深搜优化
    (尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法)
    POJ-3131 POJ-2870 POJ-2286

    4.5. 动态规划
    需要用数据结构优化的动态规划 POJ-2754 POJ-3378 POJ-3017
    四边形不等式理论
    较难的状态DP POJ-3133

    4.6. 数学
    组合数学 MoBius反演 POJ-2888 POJ-2154
    偏序关系理论
    计算方法 极大极小过程 POJ-3317 POJ-1085
    Nim问题

    4.7. 计算几何学
    半平面求交 POJ-3384 POJ-2540
    可视图的建立 POJ-2966
    点集最小圆覆盖
    对踵点 POJ-2079

    4.8. 综合题
    POJ-3109 POJ-1478 POJ-1462 POJ-2729 POJ-2048 POJ-3336 POJ-3315 POJ-2148 POJ-1263

    转载请注明:EXP 技术分享博客 » 北大ACM – POJ试题分类

    喜欢 (25) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址
    (2)个小伙伴在吐槽
    1. 围观大神 :idea:
      喵星狗2018-07-13 17:41 回复
    2. :mrgreen: 以后就在这里安家咯~ POJ解题报告会更新到这边 :lol:
      EXP2018-07-01 21:36 回复