The first stage: practice the classic common algorithms. Type each of the following algorithms for me ten or twenty times, and simplify the code yourself. Because it is too common, practice writing without thinking. You can type the program in 10- 15 minutes, or even turn off the monitor.
1. Shortest track (Freud, Dijestra, Belmanford)
2. Minimum Spanning Tree (write a Prim first, Kruscal needs a union, which is not easy to write)
3. Addition, subtraction, multiplication and division of large numbers (high precision)
4. method of bisection. (The code can be within five lines)
5. Cross, judge the intersection of line segments, and then write a convex hull.
6.BFS, DFS, be familiar with hash tables (be familiar with them, be flexible, and keep the code simple)
7. Mathematically, there are: division by tossing and turning (within two lines), intersection of line segments, and polygon area formula.
8. There are many skills to call the qsort of the system, which can be mastered slowly.
9. Conversion between arbitrary systems
The second stage: practice a slightly more complicated but commonly used algorithm.
For example:
1. Binary matching (Hungary), minimum path coverage.
2. Network flow, minimum cost flow.
3. Line segment tree.
4. Check the scenery.
5. Familiar with typical dynamic programming: LCS, longest growth substring, triangulation and memory dp.
6. Game algorithm. Game tree, dichotomy, etc.
7. The largest faction, the largest independent group.
8. The judgment point is within the polygon.
9. Differential constraint system.
10. Bidirectional breadth search, A* algorithm, minimum dissipation first.
The third stage:
The first two stages are to lay the foundation, and the third stage is to exercise. In the competition, you can quickly build a model and think of new algorithms. This requires doing more comprehensive questions at ordinary times.
1. Read the papers on oibh (probably hundreds, I only read a little, hehe).
2. usually sweep away the problems on zoj, and don't always do those problems that you don't have to think about. (The moderator of CUHK acm often says that I choose the simple one: -P)
3. Participate in online competitions more, feel the competition atmosphere and evaluate your own strength.
If you don't pass a question, ask someone if there is a better algorithm to try.
5. Remember the questions you have done:-)
The following is transferred from:/wilworld/blog/item/88b1b844d37e4049500fe6a.html.
Algorithm book has a lot to refer to:
1, concrete mathematics-the basis of computer science
Ronald Graham, Donald Knut, Oren Patashnik
The book Concrete Mathematics is the textbook of Stanford Computer Department (1970 for graduate students). The content of this book is an extension of the first chapter of Knuth's masterpiece TAOCP, which covers almost all possible mathematical knowledge in the field of computer science. The answers to many classic questions in the book are easier to understand than those widely circulated at present. It is of great help to improve everyone's mathematics literacy.
2. Introduction of the algorithm
Thomas h Coleman, Charles e Laserson, Ronald L. Rivest, Clifford stein.
Introduction to Algorithms, a classic algorithm textbook of Computer Department of MIT. Author Rivest won the ACM Turing Award, Cow! This book is comprehensive in content and popular in language, which is very suitable for everyone to get started.
3. Practical algorithm analysis and program design.
Wu Wang Jian de
The famous "black book". The content includes all kinds of algorithms needed for the competition, which is suitable for readers at all levels.
Here is my own supplement: in fact, the so-called "black book" and a book, Algorithmic Art and Informatics Olympiad by Liu Rujia Huang Liang, are very classic and very popular.
4. Network algorithm and complexity theory.
Zheng Xie Li Jianping
Rich Graph Theory Textbooks
5. Algorithm+data structure = program
Noun (short for noun) Worth
Professor Wirth, the inventor of Pascal language, wrote a famous book, which profoundly expounded the relationship between algorithms and data structures, and provided detailed Pascal source programs for each algorithm, suitable for readers of all levels.
Finally, while learning algorithms to improve combat effectiveness, we should also do more problems, which is necessary in actual combat. In fact, not all questions are based on algorithms. Some topics can be optimized in many ways, and some topics are more engineering. There is still a big difference between getting started and doing a good job.
May every programming contest enthusiast challenge the limit!