ACM练习必读—How to prepare for ACM？

所有代码的学习都是为了训练我们的大脑，更高效更敏捷的去解答问题。为了让自己的大脑更加优秀，Bonnie决定从今天开始每周三个ACM题目，从解读问题，从思考方式到最终代码，从遇到错误到如何解答，从最初版代码到优化后的代码等问题入手，开始奇妙的编程之旅~今天首先介绍一下如何学习，学什么，怎么学...基础问题。本文聚焦于那些对于竞争性编程来说很重要并且特别值得研究的主题，以便为即将到来的ACM训练自己。

一个ICPC问题示例:一个常见的ICPC问题具有以下特征:

问题陈述:描述问题和将要生成的输出。

输入:确保你仔细阅读了这部分内容，因为任何小细节的遗漏都可能导致你的答案出现错误。

输出:和上面一样，这个也需要仔细阅读。

约束:这些约束可以包括对输入、时间、内存、代码大小等的约束。

时间限制:看看你的算法能否在这个范围内工作。如果没有，是时候改变了!

内存限制:如果你喜欢为每一件小事分配内存，那么是时候改变它了。

准备ACM-ICPC

最重要的一步:练习

对于所有这些OJ平台，从最大提交量的问题开始，检查其他解决方案，看看如何改进。一定要参加他们每月的竞赛，以保持达标。

目前我国也有很多不错的OJ平台，估计高校内部也有私有的平台在做，可以好好利用这一些资源，我们相信编程这件事情是可以通过训练让自己更上一层楼的。

学习什么？

仅仅了解编程的基础知识对ACM的有志向者来说不会有成效。我们需要对使用的高级算法有全面的了解。下面列出了必要的主题和算法，你一定要明确地知道如何改善并有机会在实际的竞争应用。

基本数据结构：要开始有竞争力的编程，必须掌握数据结构。以下是最常用的数据结构的列表：

Array

Stack

Queue

String

Heap

Hash

Extensive list of Data structures

高级数据结构：

Priority queues, union-find sets, (augmented) interval trees, (augmented) balanced BSTs and binary indexed trees

Binary Indexed Tree or Fenwick tree

Segment Tree (RMQ, Range Sum and Lazy Propagation)

K-D tree (See insert, minimum and delete)

Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)

Tries

Interval Tree

分类和搜索：集中精力学习基本概念，并且熟悉所有可用的库函数。

Binary Search

Quick Sort

Merge Sort

Order Statistics

字符串操作:字符串也使编程问题变得有趣和困难，这可能就是它们在此类竞赛中被广泛使用的原因。学习用于字符串的库函数实际上非常有用。

KMP algorithm

Rabin karp

Z’s algorithm

Aho Corasick String Matching

选择正确的语言：C++在编程竞赛中是最受欢迎的语言，其次是Java，但是你应该总是选择一种你喜欢的语言。对任何语言都有信心是最重要的。

标准模板库:一个典型的模板库，特别是对于那些使用c++作为编码语言的人

动态规划

Longest Common Subsequence

Longest Increasing Subsequence

Edit Distance

Minimum Partition

Ways to Cover a Distance

Longest Path In Matrix

Subset Sum Problem

Optimal Strategy for a Game

0-1 Knapsack Problem

Assembly Line Scheduling

Optimal Binary Search Tree

回溯法

Rat in a Maze

N Queen Problem

Subset Sum

m Coloring Problem

Hamiltonian Cycle

贪心算法

Activity Selection Problem

Kruskal’s Minimum Spanning Tree Algorithm

Huffman Coding

Efficient Huffman Coding for Sorted Input

Prim’s Minimum Spanning Tree Algorithm

图形算法

Breadth First Search (BFS)

Depth First Search (DFS)

Shortest Path from source to all vertices **Dijkstra**

Shortest Path from every vertex to every other vertex **Floyd Warshall**

Minimum Spanning tree **Prim**

Minimum Spanning tree **Kruskal**

Topological Sort

Johnson’s algorithm

Articulation Points (or Cut Vertices) in a Graph

Bridges in a graph

基础数学：程序员必须知道如何在内部表示整数和实数，并且应该能够编码高精度的数字。位操作技巧和了解数字基本算法的库函数将非常有帮助。

数论：在竞赛中编程，了解其中的一些概念将节省很多时间和精力。

Modular Exponentiation

Modular multiplicative inverse

Primality Test | Set 2 (Fermat Method)

Euler’s Totient Function

Sieve of Eratosthenes

Convex Hull

Basic and Extended Euclidean algorithms

Segmented Sieve

Chinese remainder theorem

Lucas Theorem

组合学：虽然直接接缝可能不重要，但组合学对估计算法的渐近复杂度很重要。

Analysis of Algorithms

Combinatorial Game Theory | Set 1 (Introduction)

几何算法

Convex Hull

Graham Scan

Line Intersection

Matrix Exponentiation

Online construction of 3-D convex hull

Bentley Ottmann algorithm to list all intersection points of n line segments

Rotating Calipers Technique

Area/Perimeter of Union of Rectangles

Closest pair of points

Area of Union of Circles

Delaunay Triangulation of n points

Voronoi Diagrams of n points using Fortune’s algorithm

Point in a polygon problem

网络流算法

Maxflow Ford Furkerson Algo and Edmond Karp Implementation

Min cut

Stable Marriage Problem

Dinic’s Algorithm for Maximum Flow and Wiki

Minimum Cost Flow Problem

Successive Shortest path Algorithm

Cycle Cancelling algorithm

Maximum weighted Bipartite Matching (Kuhn Munkres algorithm/Hungarian Method)

Hungarian Algorithm Wiki

Hungarian Algorithm for Assignment Problem

Maximum Bipartite Matching

Stoer Wagner min-cut algorithm

Maximum matching in general graph (Blossom Shrinking)

Gomory-Hu Trees

Chinese Postman problem(Please see this too)

Hopcroft–Karp Algorithm for Maximum Matching

好了，看起来还是十分多的内容，点击本文中的链接，需要科学上网。如果点击不进去也是没关系的，因为Bonnie会在每天发布一个，如果每天能够把当天的好好消化一下，Bonnie相信我们的进步通过日积月累是会给我们日后产生巨大益处的~