ACM队训练建议戴维目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc335243210"ACM队训练建议PAGEREF_Toc335243210\h1HYPERLINK\l"_Toc335243211"训练方法PAGEREF_Toc335243211\h2HYPERLINK\l"_Toc335243212"其他题库PAGEREF_Toc335243212\h3HYPERLINK\l"_Toc335243213"必备知识点PAGEREF_Toc335243213\h3HYPERLINK\l"_Toc335243214"图论PAGEREF_Toc335243214\h3HYPERLINK\l"_Toc335243215"动态规划PAGEREF_Toc335243215\h4HYPERLINK\l"_Toc335243216"字符串PAGEREF_Toc335243216\h4HYPERLINK\l"_Toc335243217"数论PAGEREF_Toc335243217\h4HYPERLINK\l"_Toc335243218"组合数学PAGEREF_Toc335243218\h5HYPERLINK\l"_Toc335243219"数据结构PAGEREF_Toc335243219\h5HYPERLINK\l"_Toc335243220"计算几何PAGEREF_Toc335243220\h5HYPERLINK\l"_Toc335243221"搜索PAGEREF_Toc335243221\h6训练方法首先明确一点，在顶尖的ACMer中，很多人走的都不是在OJ猛刷题的路。OJ题目质量良莠不齐。对于大部分比赛套题来说，总会有防止人吃蛋的水题，也有故意刁难型的题目，有些赛区还流行论文题（结论题）、模板题，这些题目都不具备多少训练价值。以上提到的这些题目我们不太需要关心，大部分参赛者都会做（或者都不会做）。我们训练的目的主要是锻炼自己实实在在的解题能力，一来能在比赛中把握住那些有区分度的题目，二来确实使自己的综合素质有所提升。根据我长期的经验，强烈建议我们主要以参加TopCoder和CodeForces比赛的方式来提高自己的水平。原因如下：题目质量高，没有防吃蛋、防圆满的题有官方题解参赛者不乏来自世界各地的高手，你可以感受他们的节奏，学习他们不同的代码（编程技巧、思路、算法模板）可以打探国内各校ACMer的实力，甚至了解他们擅长的题型熟悉比赛的气氛，正式比赛则不慌不乱锻炼比赛的策略，知道在比赛该怎么调度自己，怎么安排做题的顺序和时间有challenge模式，通过cha别人的代码来锻炼自己读（队友）代码的能力数据赛后公开，了解数据该怎么出，了解什么地方容易有陷阱除此之外，我们可以通过看论文、看书、做OJ题目的方式来巩固一些其他方面的能力，比如学习STL的使用、深入经典算法等。对于ACM竞赛来说，我们不需要投入过多的精力在一些高难算法之中，虽然不排除有时候运气好刚好碰到一道，但概率很低，不如把时间投入在能力训练上性价比高。所以，如果真的有兴趣并且在时间盈余的时候可以深入研究一下，否则我个人不太推荐。其他题库POJ，题目杂而多，网上有很多题目分类和解题报告ZOJ，题目杂而多，每月必有月赛（ZJU队员原创题目，质量还可以，组队练习不容错过）SGU，都是原创题，难度偏大，题目数学味比较浓（尽管都是难题，但ACRush做完了）Timus，都是欧洲比赛的题目，质量还不错，但跟亚洲赛区风格不太一致SPOJ，都是网友加的题目，有些题目很有趣，但跟ACM比赛题目风格不太一致HDOJ，近几年引入了很多ACM亚洲地区赛的题目（好题），还有很多多校联赛的题目（垃圾题）必备知识点图论最短路Dijkstra（深刻理解，能作各种变形）最短路Bellman-Ford（支持负权，能判负环）最小生成树Prim（深刻理解，能作各种变形）最小生成树Kruskal（深刻理解，能作各种变形）树上经典问题（最小支配集，最大独立集，最小覆盖集，最长路等）最大流最小费用最大流二分图匹配（无权的匈牙利，带权的EK）（跟最小覆盖的对偶关系）拓扑排序强连通重连通2-SAT动态规划//要学会递推实现和记忆化搜索实现状态压缩背包斜率优化字符串AC自动机后缀数组PrefixfunctionZfunction（又叫extendedKMP）RK-hash数论扩展欧几里德（解方程，求逆元）