- 2020-11-16 19:49
*views 2*- algorithm
- Blue Bridge Cup
- The 11th
- 2020
- National Games
- Weekly notes

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

- Python146 blogs
- Java131 blogs
- Vue86 blogs
- Flow Chart79 blogs
- javascript42 blogs
- C++41 blogs
- programing language38 blogs
- MySQL37 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

The problem of string left rotation Interview essential ： Data structure time complexity and usage Remove outliers , use python to write matlab Of hampel(X) function BN layer pytorch realization Linux C Three methods of redirecting standard input and output to file [ Thesis reading ]HRNetV1,HRNetV2,HRNetV2p2021 World ranking of Computer Science Major ! This year's ranking reshuffle What certificates can big data test ? use Python and Pygame Implementation of code rain 2020 The 11th National Blue Bridge Cup B group C/C++