<>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