福建西南建设有限公司网站,大连建设信息网,编程入门教程,wordpress php环境ACM训练计划建议 From#xff1a;freecode# Date#xff1a;2015/5/20 前言#xff1a; 老师要我们整理一份训练计划给下一届的学弟学妹们#xff0c;整理出来了#xff0c;费了不少笔墨#xff0c;就也将它放到博客园上供大家参考。 菜鸟之作#xff0c;大牛勿喷…ACM训练计划建议 Fromfreecode# Date2015/5/20 前言 老师要我们整理一份训练计划给下一届的学弟学妹们整理出来了费了不少笔墨就也将它放到博客园上供大家参考。 菜鸟之作大牛勿喷如有不当或补充之处欢迎指出。 本建议书分为三个阶段大一、大二、大三。大四暂没整理一方面是大四要面临考验和找工作的问题坚持继续acm的很少另一方面本人还没大四…… 下面以个人经验分析一下这三个阶段建议学习的内容和具体的训练计划。 正文 大一第一阶段 大一是时间最充裕的一段时间也是可塑性最高的一个阶段。大一你有很多自由时间可以自己分配建议这段时间先打好c/c基础或者是任何一门语言的基础尽量做到“半精通”。因为像c这种语言几年内达到精通都是不可能的。而我这里所说的“半精通”实际上是将课本完全搞透的基础上再在课外拓展一些内容加深对语言本身的理解。 为什么我这里强调语言的重要性呢一方面是为了以后搞acm的需要语言通畅了可以保证你实现大部分算法没有障碍而比赛时时间是很重要的。另一方面也是你身为学计算机的学生的一个必须要学习的能力语言就是你手中的剑以后能披荆斩棘走多远剑有多锋利占很大因素。 另一方面建议打好数学的基础。学长身为过来人深受数学烂的苦。acm越到后期的时候其实用到的数学知识就越多。像有些题目赤裸裸的就是求积分还有一些题目将求期望嵌入到了DP的题目里…… 其实这些还好说都是显式的题目还有一种隐式的东西对acm帮助最大那就是数学思维。有数学思维和没有数学思维的区别就是一道题有N种思路和N*N种思路的区别。这越到后期越明显思路很重要比赛时面对一道题团队里首先要有多种思路可供分析然后大家讨论哪种思路是最可行的确定之后就是最擅长这个思路的人实现算法。如果分析一道题目的时候产生的思路很少那么无疑会降低这道题的AC命中率。 啰嗦了这么多其实我就想给大一的新生们强调两点语言和数学。 具体的实现策略数学的话好好上课把课本搞明白。 语言的话建议课本刷题 | 不会的问老师。 这个阶段刷题的话除了咱们学校的oj还可以到各大oj刷题poj上的水题比较多而且质量较高这里贴出一个poj水题的列表转。 poj1000AB problem poj1002电话上按键对应着数字。现在给n个电话求排序。相同的归一类 poj1003求最小的n让11/21/3...1/n大于给的一个实数 poj1004求一堆实数的平均数 poj1005由坐标 (0,0) 开始以半圆为形状每年侵蚀50m^2问(0,0)开始到(x,y)结束需要多长时间 poj1006三个周期是常数。现在给三个周期出现高峰的时候问下一次出现高峰是什么时候 poj1007求字符串排序 poj1008一种日历计算日期数量 poj1012Joseph问题 poj1013给3次称硬币的结果问哪个是假币且假币比真币轻还是重 poj1016一个数串这样变化它的后继是它含有几个1含有几个2...问循环情况 poj10171×12×23×34×45×56×6的产品放到6×6×h的盒子里。求h最小值。 poj1028模拟网页浏览 poj1031求一个点是否在凸包里面 poj1032把n分成若干个不同的数的和求最大乘积 【23...如果多出来就从最大一个数开始加1】 poj1045数学公式 poj1046给16个底色后给若干个颜色问与前面哪个距离最小 poj1051一个字符串每个字母都有一个代替。现在把那个代替又代了一些回去求原串。 poj1056给若干个字符串问是否有一个是另外一个的前缀 【其实可以用trie来做不过暴力可过】 poj1061给出两只青蛙的坐标一条经线上每个青蛙条一次的距离问跳多少次可以碰到 poj1065处理n个木棍每个木棍有两个参数。如果一个前面一个处理的不比它大就可以不用转换时间否则需要1个时间。问最少转换时间 poj1083一共400个房间南边200个北边200个。从一个房间搬东西到另外一个房间需要10min此期间其他人就不能通过这段路一个房间最多一次搬入或者搬出。 【统计每段路通过几次求max】 poj1118给若干个点求含最多点的直线含点数 poj1146求一个字符串后面一个字典序 【next_permutation函数】 poj1183arctan(1/a)arctan(1/b)arctan(1/c)给出a求bc最小的解 【数学推导】 poj1207每个数进行如下操作如果是偶数/2如果是奇数*31。问一个区间内可以操作操作次数最多的那个数的操作次数 【直接做就可以过】 poj1218求1-n之间有多少个平方数 poj1256求一个字符串的全排列 【next_permutation函数】 poj1298字母替换问题 poj1517求i0-9 e∑0in1/i!的数值 poj1657给棋盘上的起始点和终止点求王、后、车、象的最短距离 poj1833求后面一个字典序 【next_permutation函数】 poj1835模拟一个宇航员运动。三维左转右转上转下转前转后转 poj1936给两个s和t两个字符串。问t删去一些字符后是否可与s相同 poj2027比较两个数的大小 poj2159俩密码。问前面一个可不可能是后一个的原码。 【相同字母数相同】 poj2262对1000000内的偶数进行哥德巴赫猜想 poj2606给若干个点求含最多点的直线含点数 poj2656有n天如果一天的上课时间课外时间8就不开心。求最早一天不开心的时间。 poj26632×1的多米诺牌来覆盖3×n的长方形问方案数 poj2739求一个数可以表示成多少种连续素数的和。 poj2780给若干个点求含最多点的直线含点数 poj3006给一个数列首相公差求这个数列中第n个素数 poj3087不停洗牌问多少次后可以达到目标状态 poj3094把输入的再输出 poj3175给一个字符串求那个整数的开方的小数部分前n个有效数位即该字符串 poj3299有三个变量和推导公式任给两个求第三个。 poj3589猜数游戏判断两个数有多少A和B poj3618每次一个人到离原点最近的一个景点有正负求最多能经过多少个景点 poj3619每个人读书有速度读了一定时间会停下来。求每个人读完多少页需要多少时间 poj3620求最大的一个连通块 poj3627求最少的人让他们的高度超过一个数字 poj3663给n个数字。问有多少对数字和s poj3664两轮投票第一轮前m位进入第二轮第二轮最高票为冠军 poj3665每次取最大的一个数然后把它评分给剩下n-1个数不能平分就从1号数开始加。求取数顺序 poj3671n个1和2问至少修改多少个数可以让整个序列有序1在前2在后 poj3672上坡需要时间下坡需要时间平坡需要时间。现在给你去的路线求回去路线的需要时间 poj3673另类乘法两个数各个位上的数乘积的和 poj3749解密一个字符串。每个字符串都是原先字母后推5个字母 大二第二阶段 大二是一个很重要的时期一定要把握好特别是把握好学习的方向有目的的学习不要像学长一样跌跌撞撞学学这学学那荒废了很多时间。 所以在学期开始的时候要先给自己定一个学习计划。大二有两个学期分析好自己的优缺点擅长的和不擅长的感兴趣的方向然后综合起来明确自己这一年应该做哪些事情应该达到什么程度。 这里给出个人建议第一学期数据结构第二学期选几个方向专攻一下。 第一学期中建议的数据结构不仅是acm中很多方向的基础也是学习计算机的一个重要基础所以建议同学们打好数据结构的基础。时间上我只是给一个参考你可以根据自己的兴趣和课程来安排自己的时间。你可以在趁假期专攻一下也可以等着老师上课时学习。 关于第二学期建议的方向专攻这里要重点说明一下acm涉及的领域很广我们的时间又是有限的你不可能把所有方向都精通而acm又是团队配合的比赛所以你可以和队友每个人负责专攻几个方向这样比赛时不会出现一道题谁都没思路的情况。另外建议每个人专攻的方向要有一定的交集不然比赛时没有人和你讨论会降低这道题的正确率。事实上到了后期我们队仅仅是我们队没有依赖这种模式而是改成了两个人讨论思路一个人敲代码这是根据各队的特点安排的。当然我认为分方向还是有必要的因为这合理分配了团队中每个人的精力并在短时间内保证了团队的知识面没有漏洞。毕竟一口是吃不成胖子的。 下面给出我们划分的几大方向给大家做个参考排名不分先后。 1、数论 2、图论 3、动态规划 4、计算几何 5、搜索 6、博弈 7、组合数学 8、数据结构 9、模拟 个人对这九个方向的印象和推荐题目部分转载 各方向题集可以参见链接http://blog.csdn.net/liuqiyao_01/article/details/9079611 1、数论 大概有素数测试筛法扩展欧几里得算法同余模运算高斯消元中国剩余定理莫比乌斯反演等等。 我不擅长这方面数学烂还好后期团队里有两位数学大神不发表评论。 推荐题目 同余模运算poj2635, poj3292,poj1845,poj2115 素数测试与筛法poj2191poj1811 高斯消元poj1681poj1222 扩展欧几里得算法poj2891poj1061 中国剩余定理poj1006,zoj3538 莫比乌斯反演poj2154 2、图论 最短路最小生成树拓扑排序二分图最大团最大流强连通分量最近公共祖先次小生成树欧拉回路哈密顿回路等等。 图论理论深实现又麻烦不好啃。 推荐题目 最小费用最大流(poj2516,poj2516,poj2195) 双连通分量(poj2942) 强连通分支及其缩点.(poj2186) 图的割边和割点(poj3352) 最小割模型、网络流规约(poj3308, ) 3、动态规划 背包问题树形DP数位DP等等。 动态规划给我的感觉是比赛时一道题里面涉及了DP基本上就是难题了…… 不开玩笑动态规划很难需要时间的积累多做题需要锻炼的是用动归解题的思想这急不来。 推荐题目 背包问题hdu2602、poj3624、hdu2546、hdu2955、poj2184、hdu2639 树形DPpoj1155、hdu1011、poj1947、hdu1561、hdu4003、poj2486 概率DPzoj3383、zoj3460、hdu4405、hdu4336 数位DPhdu2089、hdu3555、hdu3652、poj3252 4、计算几何 点积和叉积、线段相交、多边形面积、凸包、半平面、圆与点的切线、圆与直线的交、圆与圆的交、圆与多边形的并和交、三维凸包、三维点和直线等等。 计算几何内容繁杂实现麻烦精度问题更是让人纠结本人负责的方向学习的时候各种泪啊两次省赛还都没考到……哭。 推荐题目 点积和叉积poj2318、poj2398 线段相交poj3304、poj1269、poj2653、poj1066、poj1039 凸包poj1113、poj3348、poj1318、poj1696、hdu1392、poj2187、hdu1348 半平面交poj3335、poj3130、poj1474、poj1278 曼哈顿距离hdu4666、poj2926 5、搜索 dfs、bfs、A*、IDA*、双向广搜等等。 前期搜索相对容易入门后期那些搜索的难题真是难啊。 这几年省赛好像没有单独的搜索题了。 推荐题目 dfspoj1724、hrbustoj1179、hdu1728、hdu1045、hdu1312、sdut2152、hdu1426、poj2386、hdu2553、hdu1022、hdu1241、hdu1016、hdu1010、hdu1175 bfs:poj3984、poj3278、hdu1242、hdu1240、hdu1195、hdu2717、hdu1253、hdu1026、hdu1180、hdu2612 6、博弈 巴什博弈、威佐夫博奕、Fibonacci博弈、尼姆博弈、公平组合博弈等等。 博弈不熟好像是找必胜态当然也可以找规律…… 博弈代码一般都很短只要分析出来公式或规律不难实现。 推荐题目 poj1067、poj1740、poj2234、poj1082、poj2348、poj2413、poj2419 7、组合数学 容斥原理、抽屉原理、置换群与Polya定理、母函数等等。 记得第五届省赛出了好多组合数学的题…… 推荐题目 置换群poj2369、poj1026、poj1721、poj3270、poj1879 Polya定理hdu1812、hdu1817、hdu2481、hdu1286 容斥原理hdu2204、hdu3208、hdu1796、hdu2841、hdu1695 8、数据结构 串处理、栈和队列、树、哈希、二分查找、并查集、线段树、二维线段树、哈夫曼树、后缀数组等等。 数据结构内容比较杂涉及的又都是基础的知识其中的很多思想都可以用在其他题目上一定要学好。 这里把它作为一个方向是为了它到了后期的一些高级的数据结构例如字典树、划分树、线段树、AC自动机等等。 推荐题目 查找二分、哈希poj3349、poj1002、hdu2141、hdu1025 串AC自动机、KMPhdu3695、hdu2203、sdut2411、poj2406、hdu1358、hdu3336 并查集poj2236、poj2524、poj1182、poj1611、hdu1232 字典树poj2503、poj2001、hdu1247、hdu1075、hdu1251 树状数组hdu1556、poj1195、poj3321、hdu1541/poj2352 线段树poj2155、poj1195、poj3468、poj3264、hdu1556、hdu1698、hdu1754、hdu1166 划分树poj2104、sdut2610 9、模拟 模拟就不举例了这里只作为一种题型出现没有什么固定的题目类型。 模拟主要实现麻烦思路往往不难。只要耐心点注意细节多斟酌斟酌就没问题。 推荐题目 hdu1030、hdu1033、hdu1035、hdu1057、hdu1063、hdu1002、hdu1004、hdu1013、hdu1015、hdu1017、hdu1020、hdu1022、hdu1029、hdu1031、hdu1033、hdu1034、hdu1035、hdu1036、hdu1037、hdu1039、hdu1042、hdu1047、hdu1048、hdu1049、hdu1050、hdu1057、hdu1062 最后加个10。 10、STL STLStandard Template Library标准模板库。 需要了解一下基本的set、map、vector、queue、algorithm要会用。 很多题目都需要用stl解决甚至是赤裸裸的考察stl。 Stl的好处在于方便而且由于它是动态开辟内存可以解决一些空间开辟不出来的问题。 例如hash空间太大一下子开辟不出来可以使用set解决。 大三第三阶段 大三要做的事只有两个字强化。 不要小看这个时期这可是能创造奇迹的一个重要的升华期。在经过前两个阶段的基础学习和方向延伸后你的算法底子已经有了并且有了一定的见识了解几个方向的算法知识。这个时候你可以沉下心巩固学过的知识以及慢慢学习其它领域的知识。这个过程很慢很艰难能让你感到成就感的回馈也少所以你会感到累感到辛苦甚至怀疑自己学得东西是不是没用的而且这个时期受到的外界诱惑比较多考研做项目……这些都会让你分心但是我想说一定不要放弃这是你的瓶颈期也是你的acm之路的一个考验度过去了你可能就会收获难以想象的回报。 这里强化的方式有两个一是刚才说的看书做题学习新知识二是打比赛。 现在已经后期你要经常学会经常打比赛自己打跟队友一起打一方面可以锻炼团队配合另一方面也可以很好的发现自己的漏洞。同时打比赛也是保持状态的一个良好途径懒惰没精神没状态拉到赛场上紧张地做几个小时题就清醒了。记得我们五一训练的时候一天一场训练赛早上睡眼惺忪的到实验室还没伸个懒腰就轰轰烈烈的投入到做题的行列中读题、分析、讨论、敲代码越来越清醒等到比赛结束之后才恍然发现已经到下午了…… 打比赛也有好多途径你可以自己找也可以听我的推荐下面举例 1、定期比赛网站 Bestcoder我们常打的比赛题目质量待考究不过用来每周练练手还是不错的。 Codeforces题目质量较高你的得分rating也是未来找工作的一个可信度很高的衡量标准。 Topcoder没打过听说很难。 2、不定期比赛 你可以关注杭电或者其他一些oj的Recent Contests可以查看其他oj最近举行的一些比赛。 3、Virtual Judge Virtual Judge可以抓取各大oj的题目制作成比赛如果近期没有比赛了你又感到寂寞难耐你可以用它自己给自己出题。 Virtual Judge网址http://acm.hust.edu.cn/vjudge/toIndex.action 注册个账号就能DIY比赛了。 另外给出一些推荐书目大家可以在训练或者学习的过程中参考这些书 刘汝佳系列 《算法竞赛入门经典》刘汝佳小白 这本书不厚题目很灵活拿来入门很好。 《算法竞赛入门经典第2版》刘汝佳紫皮书 小白的第二版没看这本书不知道多了什么内容只是变厚了好多…… 《算法竞赛入门经典——训练指南》刘汝佳大白 大白看了一部分语言通俗易懂计算几何就是靠它入门的。 《算法艺术与信息学竞赛》刘汝佳黑皮书 很难大三之前不推荐看。 刘汝佳的书习题很多在UVA上国内访问很慢好像还被墙了可以FQ过去刷题…… 《离散数学》 《组合数学》 《数据结构》 参考书 《挑战程序设计竞赛》 据说这本书不错拿来推荐一下。 《算法导论》 这本书放在这是用来膜拜的…… 把习题刷完你就是大神了。 后记 注意三个阶段都非常重要请不要荒废任何一个时期俗话说“什么时候做什么事”这个阶段做事情A下个阶段还有事情B要做所以请珍惜时间不要三心二意不要轻言放弃。转载于:https://www.cnblogs.com/Roni-i/p/7211628.html
