ACM一期基础训练计划

1、这个训练计划 我也只是把我知道的知识点罗列出来而已.其实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中的简

2、单实现.txt其它数据结构请自行简化。二 其他数据结构1.trie树请看附件 trie树的相关附件 或到网上搜索。注意自己写好和简化模版。Trie树最好使用静态分配实现！poj 3630 hdu 12512.并查集Hdu：1558 1811 1829 1198 3.图论专题：简单的说下图怎么存储。图通常分为邻接表和邻接矩阵两种方式储存。请先移步到 数据结构书祥看这两种实现方式。邻接表：我们知道要 动态分配内存。这种方式有时会导致效率低下。我们可以模拟一下动态分配内存，详见附件 静态分配。 这部分图论可参考部分题目.这本书有讲解。1.图的基本概念poj：16592.图的遍历和活动问题zoj：21

3、10 1709 1649 2913 1060 2193 2412 1008 2165 1136 1361 1091 1083 poj：2935 1270 3687 3.树与图的生成树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 1455 poj:3268

4、3259 1192 3169 5可行遍性问题zoj：1395 2016 2398 1130 1919 poj：25136.网络流问题zoj:1734 2874 2314 1994 1157 1992 2587 2788 2404 1553 poj:1149 1273 2112 3469 1815 3422 2391 3436 2516 7.支配集覆盖集独立集问题zoj：1654 1364 1140 2429 1516 1137 1059 1525 poj：3041 8.图的连通性问题zoj:1119 2182 2588 1979 1311 2532 2470poj:2942 3177 2762

5、 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 204120423.进制转换： grid：2972

6、 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来实现比较方便，有兴趣的同学，可以去网上搜下另外里面有一道题

7、涉及 二进制快速幂，请参考附件 二进制快速幂.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 2790 hdu:1010、1240、1241、124

8、2 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、1176 1058、1069、2059、208410.贪心算法入门：hdu：1045 1050 1051 1052 1053 1054

9、2037 1076 1203 1204 1239 1579 1730 228512.计算几何基础 请参考算法导论 计算几何里面的相关内容。一。点，线，面，形基本关系，点积叉积的理解POJ 2318 TOYS（推荐）POJ 2398 Toy Storage（推荐）一个矩形，有被若干直线分成N个格子，给出一个点的坐标，问你该点位于哪个点中。知识点：其实就是点在凸四边形内的判断，若利用叉积的性质，可以二分求解。POJ 3304 Segments知识点：线段与直线相交，注意枚举时重合点的处理POJ 1269 Intersecting Lines知识点：直线相交判断，求相交交点POJ 1556 The

10、Doors （推荐）知识点：简单图论简单计算几何，先求线段相交，然后再用Dij求最短路。POJ 2653 Pick-up sticks知识点：还是线段相交判断POJ 1066 Treasure Hunt知识点：线段相交判断，不过必须先理解“走最少的门”是怎么一回事。POJ 1410 Intersection知识点：线段与矩形相交。正确理解题意中相交的定义。详见：POJ 1696 Space Ant （推荐）德黑兰赛区的好题目。需要理解点积叉积的性质POJ 3347 Kadj Squares本人的方法极度猥琐。复杂的线段相交问题。这个题目是计算几何的扩大数据运算的典型应用，扩大根号2倍之后就避免

11、了小数。POJ 2826 An Easy Problem?! （推荐）问：两条直线组成一个图形，能容纳多少雨水。很不简单的Easy Problem，要考虑所有情况。你不看discuss看看能否AC。（本人基本不能）提示一下，水是从天空垂直落下的。POJ 1039 Pipe又是线段与直线相交的判断，再加上枚举的思想即可。POJ 3449 Geometric Shapes判断几何体是否相交，不过输入输出很恶心。此外，还有一个知识点，就是给出一个正方形（边不与轴平行）的两个对角线上的顶点，需要你求出另外两个点。必须掌握其方法。POJ 1584 A Round Peg in a Ground Hole

12、知识点：点到直线距离，圆与多边形相交，多边形是否为凸POJ 2074 Line of Sight （推荐）与视线问题的解法，关键是求过两点的直线方程，以及直线与线段的交点。数据有一个trick，要小心。二。凸包问题POJ 1113 Wall知识点：赤裸裸的凸包问题，凸包周长加上圆周。POJ 2007 Scrambled Polygon知识点：凸包，按极角序输出方案POJ 1873 The Fortified Forest （推荐）World Final的水题，先求凸包，然后再搜索。由于规模不大，可以使用位运算枚举。详见：POJ 1228 Grandpas Estate （推荐）求凸包顶点数目，很多人求凸包的模板是