一期基础训练计划.doc

这个训练计划 我也只是把我知道的知识点罗列出来而已. 其实acm还有很多方面的知识。 可能到acm生涯结束的时候 还是无法把所有的知识都吃透 所以acm的知识能学多少算多少，知识重要的不是你知道的多，重要的是你能否熟练的运用他们！ 题目注意事项： zoj： HYPERLINK / / grid： HYPERLINK / / hdu： HYPERLINK / / 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 1251 2.并查集 Hdu：1558 1811 1829 1198 3.图论专题： 简单的说下图怎么存储。 图通常分为邻接表和邻接矩阵两种方式储存。 请先移步到 数据结构书祥看这两种实现方式。 邻接表：我们知道要 动态分配内存。这种方式有时会导致效率低下。我们可以模拟一下动态分配内存，详见附件 静态分配。 这部分图论可参考 HYPERLINK /p-.html /p-.html 部分题目.这本书有讲解。 1.图的基本概念 poj：1659 2.图的遍历和活动问题 zoj：2110 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 2048 poj：1679 2421 1258 3026 4最短路径 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 3259 1192 3169 5可行遍性问题 zoj：1395 2016 2398 1130 1919 poj：2513 6.网络流问题 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 2470 poj:2942 3177 2762 2186 1236 3352 3694 3160 3592 9.平面图问题 zoj:2394 1084 2589 poj:1419 常用算法。 //可与数据结构的题目交叉做。 做以下题目时，请参考附件： Hdu课件 参考课本 李文新老师的《程序设计导引及在线实践》.pdf。 1.简单数学： 高中程度的数学能力基本能解决。所以速度秒杀下面几道题目： hdu：1049、1060、1061、1066 grid：2750 1657 2808 2801 2.递推题目： 考察的主要是数学的推理能力 hdu: 1290 1297 1438 1465 ~1466 1480 2013 2018 2041~2042 3.进制转换： grid：2972 2973 2734 2735 2798 2765 4.简单的字符串处理： grid：2742 2974 2744 2975 2743 2976 2818 2819 2820 2804 2797 2799 5.模拟题： 主要考察的是你的编码能力，题目做出来后，可以去网上找这道题目的相关代码，参考别人的做法简化自己的代码。 grid：2733 2712 2964 2965 2966 2723 2967 2746 2950 2745 6.大整数： 涉及知识点：大整数加法，乘法，除法，减法 除法的实现相对来说比较难，可以掠过。大整数运算其实可以使用java来实现比较方便，有兴趣的同学，可以去网上搜下 另外里面有一道题涉及 二进制快速幂，请参考附件 二进制快速幂.doc grid：2981 2980 2737 27