2022 / 7 / 16 exam summary

Time arrangement

8:00~8:20

T2 None ？ You can O(n)dp once , Just write it .

8:20~8:50

The first gear seems to be pop search , But the number of States $O(9^{10})$, Limit to run 3min, And can't prune , Gave up .

8:50~9:30

T3 It seems that there are many points .
First, I wrote the first file of violence .

9:30~9:50

Intuition tells me to be ab At random, if the length of the string is greater than the root , Then the number of occurrences is less than the root , Radical Division , Complexity $O(n\sqrt{n}logn)$
It's too troublesome , Don't want to write .

9:50~10:30

For the third gear and the fourth gear, there is a muzzle $O(n\sqrt{n}logn)$ How to do it , It seems that it can be removed by tree segmentation or long chain dissection log, But it's disgusting .

10:30~12:00

I found that I thought too much just now , Only need SAM Of DAG You can walk without log, The fourth gear can roll back Mo team , So hurry , I do not know! 5e5 Can you pass .

12:00~13:00

Write T1 The first file of pop search , The result was not adjusted in the end .

A summary after the exam

T1

Classification of discussion , greedy , simulation .
Three knowledge points I hate most are mixed together , So there is no point in this question .
I think I should resist this kind of psychology in the examination room , Even if you don't want to write , so much trouble , But if you don't write, you won't get any points , If you write, you may get points , such as T1 The third gear of can be easily greedy .
If the solution is correct , There are probably three situations , Then they are greedy , Other situations can be about this situation .
Practice greedy questions and simulation questions properly , These two pieces are really too weak .

T2

wxq Search the valid status directly , Such words are very effective , You can pass the first gear .
Positive solution feels a little like pressure dp+dp set dp？
Don't know much about , I don't know how to build one DFA.

T3

I was reckless in the examination room 3 Hours , Yes 500 Line code , Fortunately, there are gains .
get One conclusion is that the character set is C when , If the string is random , So a length is L The expected number of occurrences of the string is $O(\frac{n}{C^L})$
Therefore, the length is greater than $lo{g}_C^n$ when , Look forward to 1 Times or not .
What does the positive solution seem to be DAG Segmentation and other black Technology , Wait until you get it right .