Preface
As a major competition that connects enterprises and universities, the Blue Bridge Cup is highly valued in major universities. During the university period, the awards of this competition are also very high in gold, which is a great affirmation of personal ability. The competition in the Blue Bridge Cup competition is also huge. To win a prize, you must not only have outstanding ability, but also use the correct methods to understand the knowledge points and difficult parts. These are the basic essentials for winning. Below the author analyzes the knowledge points and difficulty of the Blue Bridge Cup Group B questions in the past three years.
Difficulty analysis
We roughly divide these questions into three levels of difficulty, low, medium, and high. Low difficulty is a sub-question, and most of them are fill-in-the-blank questions. You only need to submit the answer when answering.
First of all, let's talk about low-level difficulty questions. This kind of questions generally only need to submit a number or a string to fill in the blanks. They are all about the examinee's general logical thinking ability and the application of general math and programming.
Moderate difficulty is the largest proportion. It consists of individual fill-in-the-blank questions and a large number of programming questions. Questions of this difficulty will consume a lot of test takers' time, and there will be obstacles in the corresponding programming questions, so that each question in the exam will have a score. gap. This obstacle is generally reflected in the optimization of time complexity. The lower the time complexity, the higher the score for this question. For example, take the fifth question of Group B in 19 years to illustrate the increasing triplet, the topic is as follows:
Given three integer arrays
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]，
Please count how many triples (i, j, k) satisfy:
1 <= i, j, k <= N
Ai < Bj < Ck
Seeing this question, three layers of for loops appeared in my mind to solve violently, but this will only get one-third of the score. If you want to get a full score, you need another cycle with lower time complexity. This question should Use two two-level for loops to get full points.
Finally, there are difficult questions. These questions are generally prepared for students who are in the national and international competitions. The characteristics of such questions are difficult. But it is not impossible to solve it. Comprehensive use of algorithms and comprehensive analysis of the problem still have the opportunity to complete the problem within a limited time. For example, the ninth question sequence count in the 2020 simulation contest requires proficiency in DFS and BFS, and on this basis, the use of memory search can pass 80% of the sample data.
Knowledge analysis
The author counted 18 years, 19 years B group and 20 years of simulation questions. It can basically be determined that the first two questions are simple sub-items, 5 and 6 questions are medium difficulty, and the last three questions are high difficulty questions.
The low-difficulty topics cover knowledge points, including various unit conversions, time conversions, statistical projections and other low-difficulty knowledge, so I won’t elaborate on them.
The medium difficulty covers many problems that require logical thinking, and the requirements for various algorithms are not high. Most of the problems of this difficulty can be solved by violent enumeration, but the for loop has more than three layers and must be optimized. Secondly, the two search algorithms, DFS and BFS, are also frequently tested, such as the maze of 19 years. Hash tables and double pointers are also common tests, as well as various sorting algorithms and greedy algorithms, which often appear in this part of the topic.
Among the difficult topics, the two major search algorithms, DFS and BFS, also appear frequently, in addition to dynamic programming, backtracking algorithms, etc. Some topics also involve divide and conquer strategies, and they are combined with other ways of thinking , It’s difficult to get a full score, so the focus should be on the first two difficult questions.
In summary, each difficulty knowledge point mainly involves the following;
(1) Low: general mathematical knowledge and logical thinking
(2) Medium: Enumeration, DFS, BFS, hash table, double pointer, greedy algorithm, major sorting algorithms
(3) High: DFS, BFS, dynamic programming, backtracking algorithm, divide and conquer strategy
to sum up
Ordinary students can participate in the Blue Bridge Cup and try their best to solve the problems of low and medium difficulty, so how to overcome the time complexity problem in medium difficulty? Just look for leetcode. The time complexity is not optimal and not submit. The above exercises are very effective.
END
Chief Editor | Wang Nanlan
Editor in charge | Liu Shihao