挑战程序设计竞赛POJ例题及练习题分类

{"likeCnt":14,"createTime":"Nov 8, 2018 10:09:47 PM","author":"zbx99","viewCnt":1827,"id":726,"title":"挑战程序设计竞赛POJ例题及练习题分类","trustable":false,"dislikeCnt":0,"content":"简单：\n1. 暴搜\n例题：[problem:POJ-2386]\n练习：[problem:POJ-1979]，[problem:POJ-3009]，[problem:POJ-3669]，[problem:POJ-2718]，[problem:POJ-3187]，[problem:POJ-3050]\n2. 贪心\n例题：[problem:POJ-3617]，[problem:POJ-3069]\n练习：[problem:POJ-2376]，[problem:POJ-1328]，[problem:POJ-3190]，[problem:POJ-2393]，[problem:POJ-1017]，[problem:POJ-3040]，[problem:POJ-1862]，[problem:POJ-3262]\n3. 基础动态规划\n练习：[problem:POJ-3176]，[problem:POJ-2229]，[problem:POJ-2385]，[problem:POJ-3616]，[problem:POJ-3280]（区间dp），[problem:POJ-1742]，[problem:POJ-3046]（优化递推式），[problem:POJ-3181]（高精度），[problem:POJ-1065]，[problem:POJ-1631]，[problem:POJ-3666]（[problem:Codeforces-13C]），[problem:POJ-2392]，[problem:POJ-2184]\n4. 基础数据结构\n（1）优先队列\n例题：[problem:POJ-2431]，[problem:POJ-3253]\n练习：[problem:POJ-3614]，[problem:POJ-2010]\n（2）并查集\n例题：[problem:POJ-1182]（种类并查集）\n练习：[problem:POJ-2236]，[problem:POJ-1703]（种类并查集）\n5. 基础图论\n（1）最短路\n例题：[problem:POJ-3255]（次短路），[problem:POJ-3169]（差分约束）\n练习：[problem:POJ-2139]，[problem:POJ-3259]（判负环），[problem:POJ-3268]，[problem:POJ-1201]（差分约束）\n（2）最小生成树\n例题：[problem:POJ-3723]\n练习：[problem:POJ-1258]，[problem:POJ-2377]，[problem:POJ-2395]\n6. 基础数学\n\n7. 二分搜索\n（1）最大化最小值（最小化最大值）\n例题：[problem:POJ-1064]，[problem:POJ-2456]\n练习：[problem:POJ-3258]，[problem:POJ-3273]，[problem:POJ-3104]，[problem:POJ-3045]（可以是结论题）\n（2）01分数规划\n练习：[problem:POJ-2976]，[problem:POJ-3111]\n（3）查找第k大的值\n练习：[problem:POJ-3579]，[problem:POJ-3685]\n（4）其他问题\n练习：[problem:POJ-3662]，[problem:POJ-1759]，[problem:POJ-3484]\n8. 尺取法\n例题：[problem:POJ-3061]，[problem:POJ-3320]\n练习：[problem:POJ-2566]（单调性转化），[problem:POJ-2739]，[problem:POJ-2100]\n9. 经典思维\n（1）相遇问题\n例题：[problem:POJ-1852]，[problem:POJ-3684]\n练习：[problem:POJ-2674]\n（2）反转问题\n例题：[problem:POJ-3276]，[problem:POJ-3279]\n练习：[problem:POJ-3185]，[problem:POJ-1222]\n（3）折半枚举\n例题：[problem:POJ-2785]\n练习：[problem:POJ-3977]，[problem:POJ-2549]\n10. 单调栈与单调队列\n（1）单调栈（最大矩形面积）\n例题：[problem:POJ-2559]\n练习：[problem:POJ-3250]，[problem:POJ-2082]，[problem:POJ-3494]\n（2）单调队列（滑窗问题）\n练习：[problem:POJ-2823]，[problem:POJ-3260]（完全背包+多重背包）\n\n中等：\n1. 数据结构进阶（线段树与树状数组）\n例题：[problem:POJ-2991]，[problem:POJ-3468]，[problem:POJ-2104]（归并树，数据加强后分块会超时）\n练习：[problem:POJ-1990]，[problem:POJ-3109]（扫描线），[problem:POJ-2155]（二维树状数组），[problem:POJ-2886]（反素数），[problem:POJ-3264]，[problem:POJ-3368]，[problem:POJ-3470]（扫描线）\n2. 动态规划进阶\n（1）状压dp\n例题：[problem:POJ-2686]\n练习：[problem:POJ-2441]，[problem:POJ-3254]，[problem:POJ-2836]，[problem:POJ-1795]，[problem:POJ-3411]\n（2）dp矩乘加速\n例题：[problem:POJ-3734]，[problem:POJ-3233]\n练习：[problem:POJ-3420]，[problem:POJ-3735]\n（3）dp优化\n例题：[problem:POJ-1769]（数据结构优化），[problem:POJ-3709]（斜率优化）\n练习：[problem:POJ-3171]（数据结构优化），[problem:POJ-1180]（斜率优化）\n3. 网络流\n（1）二分图匹配\n例题：[problem:POJ-3041]，[problem:POJ-3057]\n练习：[problem:POJ-1274]，[problem:POJ-2112]，[problem:POJ-1486]（关键边），[problem:POJ-1466]（最大独立集），[problem:POJ-3692]（最大团\u003d补图最大独立集），[problem:POJ-2724]，[problem:POJ-2226]（最小顶点覆盖）\n（2）最大流与最小割\n例题：[problem:POJ-3281]，[problem:POJ-3469]\n练习：[problem:POJ-2987]（最大权闭合图），[problem:POJ-2914]（无向图最小割），[problem:POJ-3155]（最大密度子图）\n（3）最小费用流\n例题：[problem:POJ-2135]，[problem:POJ-2175]（消圈算法），[problem:POJ-3686]（二分图最小权指派问题），[problem:POJ-3680]（负权边转化）\n练习：[problem:POJ-3068]，[problem:POJ-2195]（二分图最小权指派问题），[problem:POJ-3422]\n4. 图论进阶\n（1）强连通分量与缩点\n例题：[problem:POJ-2186]\n练习：[problem:POJ-3180]，[problem:POJ-1236]\n（2）2-SAT\n例题：[problem:POJ-3683]（输出一组可行解）\n练习：[problem:POJ-3678]，[problem:POJ-2723]（二分），[problem:POJ-2749]（二分）\n（3）LCA\n例题：[problem:POJ-2763]（RMQ）\n练习：[problem:POJ-1986]，[problem:POJ-3728]\n（4）其他问题\n练习：[problem:POJ-3713]（图的三连通）\n5. 基础计算几何\n暂未更新\n\n较难：\n1. 高级搜索\n暂未更新\n2. 字符串算法\n暂未更新\n3. 数学进阶\n暂未更新\n4. 博弈论\n暂未更新\n5. 分治\n暂未更新"}