Detailed Explanation and Practice Questions for C++ GESP Level 7: Master These and You’re Set

1. Mathematical Library Functions

• Content: Trigonometric functions (sin, cos, tan), logarithmic functions (log, log10), exponential functions (exp, pow).

• Key Points: Radian calculations, differences in precision between double and float.

2. Complex Dynamic Programming

• Content: Two-dimensional dynamic programming (grid paths), interval dynamic programming (stone merging), longest subsequence (LIS/LCS), rolling array optimization.

• Difficult Points: Derivation of state transition equations and space optimization.

3. Graph Traversal and Algorithms

• Content: Adjacency matrix/list storage, DFS/BFS traversal, shortest path (unweighted graphs), Flood Fill algorithm.

• Applications: Maze problems, connected area filling.

4. Hash Tables

• Content: Hash function design, collision handling (chaining, open addressing), application of unordered_map.

5. High-Dimensional Dynamic Programming and State Compression

• Content: Multi-dimensional state design (e.g., three-dimensional knapsack), bit manipulation for space optimization.

GESP Level 7 Past Exam Questions Classification Table (https://www.luogu.com.cn/training/557#problems)

The following questions are from official mock exams and the 2024-2025 examination:

Knowledge Point Classification	Question Number	Question Name
Dynamic Programming	P10265	Two-Dimensional Knapsack Problem
Graph Traversal	P10370	Shortest Path in a Maze (BFS)
Hash Tables	P202409-5	Hash Collision Resolution (Open Addressing)
Mathematical Library Functions	P202403-11	Precision Issues in Exponential and Logarithmic Calculations
State Compression	P202412-7	High-Dimensional Dynamic Programming Optimization

Recommended problems of the same difficulty and knowledge points as Level 7 from Luogu

The following problems are categorized by knowledge points, covering core topics such as dynamic programming, graph theory, and mathematical library functions:

Dynamic Programming

Question Number	Question Name	Knowledge Point
P1216	Number Triangle	Basic Two-Dimensional DP
P1020	Missile Interception	Longest Decreasing Subsequence (LIS)
P1435	Palindrome String	Interval DP
P2758	Edit Distance	LCS Variation
P1048	Herb Gathering	Rolling Array Optimization
P1064	Jinming’s Budget Plan	Multi-Dimensional Knapsack Problem

Graph Theory and Traversal

Question Number	Question Name	Knowledge Point
P1605	Maze	Basic DFS/BFS
P1443	Horse Traversal	BFS Shortest Path
P1162	Color Filling	Flood Fill Algorithm
P1506	Rescue OIBH Headquarters	Connected Area Filling
P1037	Generate Numbers	Graph Connectivity Statistics
P2296	Find the Road	Graph Shortest Path Constraints

Mathematical Library Functions

Question Number	Question Name	Knowledge Point
P1888	Trigonometric Functions	Radian Calculations
P1024	Solving Cubic Equations	Comprehensive Application of Mathematical Functions
P5657	Gray Code	Bit Manipulation and Mathematical Derivation

Hash Tables

Question Number	Question Name	Knowledge Point
P3370	String Hashing	Hash Function Design
P1102	A-B Pairs	Fast Hash Lookup
P4305	Unique Numbers	Hash Deduplication

State Compression and High-Dimensional DP

Question Number	Question Name	Knowledge Point
P1896	No Overlap	State Compression DP
P2831	Angry Birds	Geometry + State Compression
P2622	Light Switch Problem II	Multi-Dimensional State Compression

Preparation Suggestions

1. Dynamic Programming and Graph Theory: Core difficulties at Level 7, focus on practicing state transitions and BFS/DFS templates.

2. Precision of Mathematical Functions: Pay attention to the differences between double and float to avoid calculation errors.

3. Mock Exam Practice: Familiarize yourself with question types through past exam questions, reinforcing knowledge points with Luogu problems.