<>2020 Blue Bridge Cup results
In fact, the results came out yesterday , It's only today that I thought I could send such a blog .
My result in the National Blue Bridge Cup is the first in China （ I counted it for a while 100 How do you look ）
Actually, it was quite unexpected , Because many of my questions are not really right （ Or rather 4-5 It's national one ?）. There is also a major reason ： I only saved two last time awa
. Now let's talk about what I'm doing on the way to the game .
<> Preparation for National Games
According to the difficulty of this year's provincial competition , I don't think the National Games are difficult at all , I thought I could do seven or eight questions easily . But it wasn't until a few days before the National Games , I did 2019 After the real title of the National Games , You've made me an autistic person . I remember the penultimate question seemed to be the chairman tree , And then I spent it 2 I learned a lot in a few days
Chairman tree . Feeling about HKCEE , And then on Friday night I looked at it again KMP, Horses pull carts and so on . Even on Saturday morning 7 More and more dp can't , Look at the backpack and the bag LIS（
LIS I did , If I'm right ）.
<> Competition process
<> be careful
Make a statement , What is described below is based on my own memory , It doesn't mean the right question or the right answer , For reference only .
<> First question ： violence
It's like a request 1 - 2020 The number of contains a number 2 The number of the number of , Just look for it directly .
<> Second question ：BFS
There is a saying and a saying , That's called Dev What IDE It's not smart , I want to knock unordered_map Can't help me automatically complete , I'll take all the orders x+2020,y+2020, Then I opened one 6500
x 6500 Tag array for （ It's good it didn't blow up ）.
This problem is similar to cell proliferation , Just search for it directly .
<> The third question ： Basic number theory
Every number can be divided into the product of several prime numbers , for example 100 = 2 2 ∗ 5 2 100 = 2^2*5^2 100=22∗52（ among 2 and 5 It's a prime number ）
that 100 The number of divisors of is ( 2 + 1 ) ∗ ( 2 + 1 ) = 9 (2+1)*(2+1)=9 (2+1)∗(2+1)=9
a number x = a b c d . . y z Of about number individual number Just yes ( b + 1 ) ( d + 1 ) . . ( z + 1 )
x=a^bc^d...y^z The divisor of is (b+1)(d+1)...(z+1)x=abcd...yz The divisor of is (b+1)(d+1)...(z+1)
Let's record it first 1 - 100 The sum of the prime powers of each number of , And then it's done , If you remember correctly, the final answer d The order of magnitude is 1e16, Don't forget to drive long long.
<> The fourth question ：DP
It's like I'm driving a two-dimensional car dp It's written backwards ,dp[ i ][ j ] Last i Place in letters j The number of longest ascending subsequences at the beginning , The transfer equation is dp[ i ][ j ] = dp[ i
+ 1 ][ k ] ( k >= j )
For reference only , It could be wrong （ Or remember wrong ?）
<> The fifth question ：DFS
good heavens , I think this question is simpler than the previous one , The depth of each point is 0 16 You can search deeply .
<> Question 6 ： Divide and conquer + High precision simulation
It seems that I have passed the time when I do it 40 More than ten minutes , When I see this problem, I feel like divide and conquer , But I've been looking for the rules for a long time . I thought about it for about ten minutes and then I slipped away , Because I saw it 3100
, See high precision direct slide . Let's look at the problem again 2 More than an hour （ All that can be written in the back ）.
What I'm writing is to take the distance between these two points as | ( The distance from the first point to the upper right corner - Distance from the second point to the upper right corner ) |, It's like writing a function to find the distance from a point to the upper right corner .
We can divide this big picture into two parts every time 9 A small picture , Until his side length is 3 It can be evaluated directly .
9 There's a little picture in it 2 Tags affect evaluation ： Positive or negative , Up or down .
Consider these points .
<> Question 7 ： Monotone queue search LIS
This problem will be dealt with in a special way, and the names of all the people will be dealt with , At this time, we can think of the ordinary seeking LIS. It's just a comparison of numerical values , One is the minimum order of comparison dictionary .
Think about the solution of a monotonic queue , Go through the original array , If the current string is larger than the end of the queue , Then go straight to the team . Otherwise, I'll use it lower_bound Binary search for the first position greater than or equal to , Replace the original large value .【 If the large value replaced here is the element at the end of the team , So this may be the answer 】
The final answer is ： last hole Join the team or replace the trailing element That's the right one Ergodic point Queue for .
<> Question 8 ： greedy + sort
This problem depends on the basis of sorting, right , I gave it a push, as if by pressing a+b+c To sort , Small ones in front . The case of equality seems not to be dealt with ?
<> Question 9 ：???
The title is too long , After reading the title, I slipped away .
<> Question 10 ：DP Cheat points
One of the three dimensions DP, When the data is only 200 When I was young , You can be fooled 50% The score of .
To sum up ： The questions written during the competition are ： one , two , three , four , five , six （50%）, seven , eight , ten （50%）, It shouldn't be a lot wrong .
It doesn't matter , I'm very happy to get the first grade , come on. ~
Technology