金牌
The topics below are not exhaustive for this division.
Contest problems may contain topics not covered in the guide, or topics listed under different divisions!
Modules Progress
Problems Progress
动态规划
大多数 Gold 和 Platinum 比赛都会出现动态规划题。
Introduction to DP
Very Frequent
Speeding up naive recursive solutions with memoization.
Knapsack DP
Rare
Problems that can be modeled as filling a limited-size container with items.
Paths on Grids
Not Frequent
Counting the number of "special" paths on a grid, and how some string problems can be solved using grids.
Longest Increasing Subsequence
Has Not Appeared
Finding and using the longest increasing subsequence of an array.
Bitmask DP
Not Frequent
DP problems that require iterating over subsets.
Range DP
Rare
Solving a DP problem on every contiguous subarray of the original array.
Digit DP
Rare
Finding the number of integers in a range that have a property.
图论
大多数 Silver 到 Platinum 比赛都会出现图论题。
Shortest Paths with Unweighted Edges
Somewhat Frequent
Introduces how BFS can be used to find shortest paths in unweighted graphs.
Disjoint Set Union
Somewhat Frequent
The Disjoint Set Union (DSU) data structure, which allows you to add edges to a graph and test whether two vertices of the graph are connected.
Topological Sort
Rare
Ordering the vertices of a directed acyclic graph such that each vertex is visited before its children.
Shortest Paths with Non-Negative Edge Weights
Not Frequent
Bellman-Ford, Floyd-Warshall, and Dijkstra.
Minimum Spanning Trees
Rare
Finding a subset of the edges of a connected, undirected, edge-weighted graph that connects all the vertices to each other of minimum total weight.
数据结构
More Operations on Sorted Sets
Not Frequent
Finding the next element smaller or larger than a specified key in a sorted set, and using iterators with sorted sets.
(Optional) Sorted Sets with Custom Comparators
Rare
Incorporating custom comparators into standard library containers.
Stacks
Not Frequent
A data structure that only allows insertion and deletion at one end.
Sliding Window
Somewhat Frequent
Maintaining data over consecutive subarrays.
Point Update Range Sum
Somewhat Frequent
Segment Tree, Binary Indexed Tree, and Order Statistic Tree (in C++).
树
DP on Trees - Introduction
Not Frequent
Using subtrees as subproblems.
DP on Trees - Solving For All Roots
Rare
Tree DP problems involving rerooting.
(Optional) Euler Tour Technique
Rare
Flattening a tree into an array to easily query and update subtrees.
(Optional) LCA with Euler Tour
Rare
Finding the lowest common ancestor by reducing it to a range minimum query over an Euler tour.
其他主题
较少要求掌握。
Optimizing Unimodal Functions
Rare
Using ternary or binary search to find the mode of unimodal functions.
Hashing
Rare
Quickly testing equality of substrings or sets with a small probability of failure.
(Optional) Hashmaps
Rare
Maintaining collections of distinct elements with hashing.
(Optional) Meet In The Middle
Rare
Problems involving dividing the search space into two.