Skip to content

Learning Path

Note

This article is currently being edited and discussed. Feel free to supplement further learning paths or share your thoughts in the comments!

This article will introduce the learning path for algorithm competitions.

This learning path serves both as a guide for beginners to learn algorithm competition knowledge and as a review checklist.

1 C++ Language Basics

Start by learning C++ syntax step by step.

1.1 Hello, World!

Begin your algorithm competition journey with a Hello, World! statement.

Also, get a rough idea of what the general structure of a C++ source program looks like.

1.2 Variables and Operations

The original purpose of computers was computation. Therefore, let's first learn how to complete some simple computational tasks.

1.3 Flow Control

1.3.1 Branching Structures

Sometimes, we need to execute different statements under different conditions. In such cases, we need to use branching statements.

Branching statements include the following:

  • if statement
  • if-else statement
  • if-elif-else statement
  • switch statement

1.3.2 Loop Structures

To execute a set of statements repeatedly multiple times, loop statements are needed.

Loop statements include the following:

  • for statement
  • while statement
  • do-while statement

1.4 Arrays and Structures

Arrays are used to store a large amount of data of the same type. Structures can bundle several variables together.

1.5 Functions and Recursion

Use functions to modularize your program and reduce implementation costs.

Recursion is a hurdle for beginners. "Calling itself" may not sound easy to understand at first, but upon closer examination, you'll find there is no fundamental difference between "calling itself" and "calling others."

2 CSP-J Beginner Level

2.1 Enumeration and Simulation

From now on, you can use the C++ language to complete some simple tasks, but this is far from enough.

To solve some simple problems correctly, you need to learn how to implement code by enumerating or simulating the logic in your mind. This may not seem very efficient, but it can be very useful sometimes.

2.2 Recursion and Divide and Conquer

Recursion refers to a method where a function continuously calls itself in its definition; divide and conquer involves repeatedly breaking down a problem into several subproblems, solving them, and then merging the results.

2.3 Strings

When solving informatics problems, you will frequently encounter the string data type. You need to learn some STL functions for manipulating strings. Of course, simulation is also a good method for solving string problems.

2.4 Sorting

When you obtain a set of data, how to transform it from unordered to ordered is also an important problem. When you run out of ideas, consider sorting the array. This is also the foundation for many subsequent algorithms.

There are many sorting methods, but understanding and remembering them is not difficult.

The NOI syllabus for the beginner level only requires learning three sorting algorithms: selection sort, bubble sort, and insertion sort. However, the others are not much more difficult and may appear in the preliminary round, so they are listed here as well.

2.5 Binary Search and Doubling

Binary search essentially uses the divide and conquer idea to continuously reduce the search range until the answer is found. However, note that this search method must be applied to ordered data structures.

Doubling, on the other hand, is different. It involves repeatedly doubling to transform linear processing into logarithmic processing, greatly optimizing time complexity. (This topic requires some mathematical foundation; skipping it for now is not a big problem.)

At the beginner level, search problems often appear in maze-like problems, typically involving map-like data. Additionally, search is commonly used for efficiently enumerating and constructing valid solutions and can also be used for partial scoring.

2.6.1 Depth-First Search (DFS)

Depth-first search refers to an algorithm that uses recursive functions to conveniently implement brute-force enumeration. It shares some similarities with the DFS algorithm in graph theory but is not exactly the same.

2.6.2 Breadth-First Search (BFS)

By designing each state as a point in a graph, you can perform a carpet-style search.

2.6.3 Search Optimization

Many problems can be solved using DFS, but the complexity of this algorithm is obviously unacceptable. Therefore, some optimizations are needed to make it run faster. Such optimizations can reduce impossible attempts and are called "pruning." Optimizations related to BFS are more flexible, but the basic idea is the same.

2.7 Introduction to Data Structures

2.7.1 Linear Data Structures

Arrays, linked lists, queues, and stacks are all linear structures. Clever use of these structures can facilitate many tasks.

2.7.2 Complex Data Structures

2.8 Introduction to Dynamic Programming

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems.

Since dynamic programming is not a specific algorithm but a method for solving particular problems, it appears in various data structures, and the types of related problems are more diverse.

2.8.1 Knapsack Problem

Given a knapsack with limited capacity, choose to place several items with capacity and value, and solve how to place them to maximize the total value. This is the first hurdle for many OIers. From here, algorithms become somewhat difficult to understand.

2.8.2 Linear Dynamic Programming

One of the most challenging parts of dynamic programming is designing states, which requires the use of construction-related techniques. Once you write the state and state transition equations, solving a dynamic programming problem is not difficult.

Memoization search is a search implementation method that records information about already traversed states to avoid repeatedly traversing the same state. Some problems can also use memoization search to reduce the difficulty of thinking.

Because memoization search ensures each state is visited only once, it is also a common implementation method for dynamic programming.

2.8.3 Complex Dynamic Programming

Interval dynamic programming is an extension of linear dynamic programming. When dividing the problem into stages, it is closely related to the order in which elements appear in the stage and which elements from the previous stage are merged.

2.9 Mathematics

2.9.1 High-Precision Algorithms

What if even long long (or int64) is not enough? Use high-precision algorithms. Essentially, they simulate the four arithmetic operations.

2.9.2 Base Conversion

In computers, besides binary, octal and hexadecimal are also commonly used. Sometimes, learning to use the correct base can greatly help in problem-solving.

2.9.3 Bitwise Operations

Bitwise operations are operations performed based on the binary representation of integers. Since computers store data internally in binary, bitwise operations are quite fast.

There are six basic bitwise operations: bitwise AND, bitwise OR, bitwise XOR, bitwise NOT, left shift, and right shift.

2.9.4 Number Theory

2.9.5 Combinatorial Counting

At this point, you have learned all the algorithms within the scope of the beginner level. However, to master them, you need to continue practicing with a sufficient number of problems to consolidate the knowledge points you have learned.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用