编程竞赛方法

Question

这是一个广泛的问题，但想知道专家的意见。我偶然看到了一个文档Suffix arrays – a contest approach，也发现了一些评论，参与者应该已经准备好了这样的数据结构。现在很多在线编程难题都是有时间限制的。所以我想知道其他的数据结构/算法是什么。

Answer 1

到目前为止，我已经参加了大约10年的比赛，我自己也创建了一个不错的库。大多数真正优秀的竞争对手都有自己的博客，例如传奇人物Petr Mitrichev，他们在那里解释他们在一些竞争问题上的想法。阅读这些可以帮助你-如果你看到一个很好的想法，实现它并将其存储起来。当我发现涉及算法的问题时，我会将算法添加到我的库中。这样我就可以验证我的实现是正确的--只有当我通过了至少一个问题的实现时，我才会添加一个算法。

下面是我的一些算法的列表：

• I有一个巨大的几何库，其中包含表示点、线、多边形、线段、圆以及与它们相关的一些操作的类(例如，点集的凸包等)强连接的components
• Dinitz流algorithm
• Bipartite匹配implementation
• Min的成本最大流implementation
• Aho-Corasic字符串搜索算法
• Knuth-morris-pratt字符串搜索算法
• Rabin-Karp字符串搜索算法使用algorithm
• Fast exponentiation
• Polynom implementation
• Big的algorithm
• Fast exponentiation
• Polynom implementation
• Big整数implementation
• Fractional数字implementation
• Matrix类implementation
• Prime的
• 线性时间后缀树factorization
• Eratosthenes Sieve
• Segment Tree
• Hungarian algorithm
• 2-Sat算法。为此，我使用了上面提到的塔尔扬算法。

你会注意到，一些最基本的算法(如BFS，DFS，Dijkstra)上面没有提到，这是因为我没有实现它们。这些算法不能很容易地推广到您只需简单地复制和粘贴它们，一切都会正常工作的方式。而且，我只需要不到5分钟的时间来编写它们--我通常只在我的库中放入那些很难实现或者在实现它们时容易出错的算法。

Answer 2

查看这些featured articles @ TopCoder。他们真的很酷。

在此期间，我建议您参加TopCoder的编程竞赛。因为提高的最好方法就是练习&不断参加这样的比赛。

此外，Project Euler也是非常容易上瘾的。

Answer 3

另外，在online评委的支持下，看看Programming Challenges的书，它是关于这个主题的很好的参考-它展示了在编程竞赛中取得成功所必需的主题。