这个训练计划我也只是把我知道的知识点罗列出来而已.其实acm还有很多方面的知识。
可能到acm生涯结束的时候还是无法把所有的知识都吃透所以acm的知识能学多少算多少，知识重要的不是你知道的多，重要的是你能否熟练的运用他们！题目注意事项：zoj：/grid：/hdu：/zquoj：也就是我们的oj一．数据机构基础。
请自学完数据结构书：2，3，4，6，7，9.1，9.2.1 9.3 10 这几章，带*号可以暂时掠过，以后再看。
然后自行完成oj DS开头的题目。
注意栈队列这些数据结构一般不用像书本那样写得那么严谨。
在acm中，往往因为时间关系，一般写成简单的模式：请参考附件：栈与队列acm中的简单实现.txt 其它数据结构请自行简化。
二．其他数据结构1.trie树请看附件trie树的相关附件或到网上搜索。
注意自己写好和简化模版。
Trie树最好使用静态分配实现！poj 3630 hdu 12512.并查集Hdu：1558 1811 1829 11983.图论专题：简单的说下图怎么存储。
图通常分为邻接表和邻接矩阵两种方式储存。
请先移步到数据结构书祥看这两种实现方式。
邻接表：我们知道要动态分配内存。
这种方式有时会导致效率低下。
我们可以模拟一下动态分配内存，详见附件静态分配。
这部分图论可参考/p-251720691.html部分题目.这本书有讲解。
1.图的基本概念poj：16592.图的遍历和活动问题zoj：2110 1709 1649 2913 1060 2193 2412 1008 2165 1136 1361 1091 1083poj：2935 1270 36873.树与图的生成树zoj：1203 1542 1586 2158 1406 1372 1718 1914 2048poj：1679 2421 1258 30264最短路径zoj:1298 2750 1092 1721 1967 1952 2770 1508 1053 1655 1232 2008 1791 3088 3103 1942 2027 2797 1082 1221 1857 1260 1420 1455poj:3268 3259 1192 31695可行遍性问题zoj：1395 2016 2398 1130 1919poj：25136.网络流问题zoj:1734 2874 2314 1994 1157 1992 2587 2788 2404 1553poj:1149 1273 2112 3469 1815 3422 2391 3436 25167.支配集覆盖集独立集问题zoj：1654 1364 1140 2429 1516 1137 1059 1525poj：30418.图的连通性问题zoj:1119 2182 2588 1979 1311 2532 2470poj:2942 3177 2762 2186 1236 3352 3694 3160 35929.平面图问题zoj:2394 1084 2589poj:1419三．常用算法。
//可与数据结构的题目交叉做。
做以下题目时，请参考附件：Hdu课件参考课本李文新老师的《程序设计导引及在线实践》.pdf。
1.简单数学：高中程度的数学能力基本能解决。
所以速度秒杀下面几道题目：hdu：1049、1060、1061、1066grid：2750 1657 2808 28012.递推题目：考察的主要是数学的推理能力hdu:1290 1297 1438 1465 ~1466 1480 2013 2018 2041~20423.进制转换：grid：2972 2973 2734 2735 2798 27654.简单的字符串处理：grid：2742 2974 2744 2975 2743 2976 2818 2819 2820 2804 2797 27995.模拟题：主要考察的是你的编码能力，题目做出来后，可以去网上找这道题目的相关代码，参考别人的做法简化自己的代码。
grid：2733 2712 2964 2965 2966 2723 2967 2746 2950 27456.大整数：涉及知识点：大整数加法，乘法，除法，减法除法的实现相对来说比较难，可以掠过。
大整数运算其实可以使用java来实现比较方便，有兴趣的同学，可以去网上搜下另外里面有一道题涉及二进制快速幂，请参考附件二进制快速幂.docgrid：2981 2980 2737 2706 2809 2738 29517.枚举：简单点的枚举，就是用几个循环枚举每个数的每种情况，然后找出符合条件的，这种题目比赛时经常会出现，如果一心想着好的算法，而放弃这种暴力手段的话，有可能与水题失之交臂。
grid：2977 2692 2810 2811 2812 2739 2747 2813 11838.递归+搜索（二分搜索+ bfs+dfs）grid:2753 2756 2694 1664 2816 2754 2817 2815 2749 2790hdu:1010、1240、1241、1242 1072、1253 、1312、1372 (以上题目类似于1010)1238、1239、1015、1016 1401、1515、1548poj:1064 2507 2002 3685 2503 2413（高精度）1826（并查集或dfs或dfs+二分法最好用并查集)9.DP基础：grid：2757 1661 2806 2979 2809 2795 1088 2733 2786 2792 2766hdu：1003 、1466 、1087、1159、11761058、1069、2059、208410.贪心算法入门：hdu：1045 1050 1051 1052 1053 1054 2037 1076 1203 1204 1239 1579 1730 228512.计算几何基础请参考算法导论计算几何里面的相关内容。
一。
点，线，面，形基本关系，点积叉积的理解POJ 2318 TOYS（推荐）/JudgeOnline/problem?id=2318POJ 2398 Toy Storage（推荐）/JudgeOnline/problem?id=2398一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。
知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。
POJ 3304 Segments/JudgeOnline/problem?id=3304知识点：线段与直线相交，注意枚举时重合点的处理POJ 1269 Intersecting Lines/JudgeOnline/problem?id=1269知识点：直线相交判断，求相交交点POJ 1556 The Doors （推荐）/JudgeOnline/problem?id=1556知识点：简单图论＋简单计算几何，先求线段相交，然后再用Dij求最短路。
POJ 2653 Pick-up sticks/JudgeOnline/problem?id=2653知识点：还是线段相交判断POJ 1066 Treasure Hunt/JudgeOnline/problem?id=1066知识点：线段相交判断，不过必须先理解“走最少的门”是怎么一回事。
POJ 1410 Intersection/JudgeOnline/problem?id=1410知识点：线段与矩形相交。
正确理解题意中相交的定义。
详见：/novosbirsk/blog/item/68c682c67e8d1f1d9d163df0.htmlPOJ 1696 Space Ant （推荐）/JudgeOnline/problem?id=1696德黑兰赛区的好题目。
需要理解点积叉积的性质POJ 3347 Kadj Squares/JudgeOnline/problem?id=3347本人的方法极度猥琐。
复杂的线段相交问题。
这个题目是计算几何的扩大数据运算的典型应用，扩大根号2倍之后就避免了小数。
POJ 2826 An Easy Problem?! （推荐）/JudgeOnline/problem?id=2826问：两条直线组成一个图形，能容纳多少雨水。
很不简单的Easy Problem，要考虑所有情况。
你不看discuss看看能否AC。
（本人基本不能）提示一下，水是从天空垂直落下的。
POJ 1039 Pipe/JudgeOnline/problem?id=1039又是线段与直线相交的判断，再加上枚举的思想即可。
POJ 3449 Geometric Shapes/JudgeOnline/problem?id=3449判断几何体是否相交，不过输入输出很恶心。
此外，还有一个知识点，就是给出一个正方形（边不与轴平行）的两个对角线上的顶点，需要你求出另外两个点。
必须掌握其方法。
POJ 1584 A Round Peg in a Ground Hole/JudgeOnline/problem?id=1584知识点：点到直线距离，圆与多边形相交，多边形是否为凸POJ 2074 Line of Sight （推荐）/JudgeOnline/problem?id=2074与视线问题的解法，关键是求过两点的直线方程，以及直线与线段的交点。
数据有一个trick，要小心。
二。
凸包问题POJ 1113 Wall/JudgeOnline/problem?id=1113知识点：赤裸裸的凸包问题，凸包周长加上圆周。
POJ 2007 Scrambled Polygon/JudgeOnline/problem?id=2007知识点：凸包，按极角序输出方案POJ 1873 The Fortified Forest （推荐）/JudgeOnline/problem?id=1873World Final的水题，先求凸包，然后再搜索。
由于规模不大，可以使用位运算枚举。
详见：/novosbirsk/blog/item/333abd54c7f22c52574e0067.htmlPOJ 1228 Grandpa's Estate （推荐）/JudgeOnline/problem?id=1228求凸包顶点数目，很多人求凸包的模板是会多出点的，虽然求面积时能得到正确答案，但是在这个题目就会出问题。
此外，还要正确理解凸包的性质。
POJ 3348 Cows/JudgeOnline/problem?id=3348凸包面积计算三。
面积问题，公式问题POJ 1654 Area/JudgeOnline/problem?id=1654知识点：利用有向面积（叉积）计算多边形面积POJ 1265 Area/JudgeOnline/problem?id=1265POJ 2954 Triangle/JudgeOnline/problem?id=2954Pick公式的应用，多边形与整点的关系。