I want to write too much , I don't know where to start .
<>Day -?
NOI More than a week ago , I went home . At the beginning, we played simulation games , After that, I didn't even play the simulation game . We made a plan to brush the questions , But the enthusiasm is very poor , One or two days to write a question , I've been dispiriting novels and comics . The whole person felt confused , Not so much nervous , It's better to forget NOI The existence of , Deliberately not to think about the end of not entering the team .
In fact, the mock up was OK , Most of the games can be ranked in the top , Many more times rk1. But the closer it gets NOI The worse you play , Behind the habitual explosion , Also often insomnia , So I climbed the mountain with my mother for several days , I feel more comfortable .
NOI the other day , I finally found out that it was coming NOI It's over , I'm still in a state of being hoodwinked , I feel desperate . I went out for a walk in the evening , With cjb I had a chat , Vomit a wave of bitter water , Relieved some of the pressure .
That's it. ,NOI2019 Here we are , It was held in my home Guangzhou No.2 Middle School . A year's season , It will end here .
<>Day 0
Day0 In fact, before the mentality is good , After reciting the written test, I went on the stage .AK Finish the written test , By the way, I have a look at the test questions , The third question is interaction , it seems NOI Actually joined the interaction ? The first question is good split , It's a suffix array , I've written about it before , So I decided to write it again .
The poor state before the exam is reflected , A short array of suffixes , I wrote fast 10 individual bug. So I spent a lot of time 1.5h The problem has been brought up , The students had already tried the machine and went back , I was the only one left to fight there .
I can't remember how it came out , It felt like it was over , There's only one thought left , Quickly write a big data structure problem in the computer room . So I chose lxl Write in big chunks , Yes 1h It's finished , And then I started fighting with him till night 7 spot , I can't get stuck . Mom came to see me , I let her go back , I just thought that the next day's game was hopeless , Want to give up and don't want to give up . Later, my mother told me that I was extremely ugly , It worried her a lot .
night cjb Gave me a call , We talked a lot , Just remember that he told me , It doesn't matter if the trial race explodes , Your performance tomorrow will not depend on what you do tonight . About half an hour , The whole person settled down a little bit , So I ordered a takeout , I took a bath and went to sleep .
<>Day 1
I had a good night's sleep .
In the morning, I went to the computer room to sit for a while and then went on the stage . I forgot to write down the game as usual at the beginning tips, Obsessive compulsive disorder or choose to make up in the middle of the test .
Look at it T1, Discovery is a simple slope optimization dp, So I jumped first .T2 It looks like a strange count ,T3 It's a strange greed , But it turns out that T2 yes 50 Naked violence ,T3 yes 40 Naked violence , I feel like I can take it , So I began to write questions .
Fast code over T1, For the sake of stability O ( n l o g n ) O(nlogn) O(nlogn) Convex hull trisection of , If it's too large, it's probably too big 9 spot .
stay T2 and T3 For a while , It feels better than greed , I'm obviously better at counting . So I began to think T2, According to 50 Cartesian tree of violence dp Think about it , The answer seems to be a piecewise polynomial , Is that right APIO The routine of rowing , Just use the lower power polynomial , So I cut it T2? to smell fishy , I went to the bathroom , It is found that a single merge is not
O ( L 2 ) O(L^2)O(L2), It is O ( L 3 ) O(L^3) O(L3)
The complexity of , Total complexity I don't know where to fly . I don't know what I think when I come back , It took a few minutes to write a memorized program for measuring complexity , A test found that the limit data complexity was only 4 ∗ 1 0 7
4*10^74∗107（ Only after the examination did I know that this practice was correct O ( n 3 ) O(n^3) O(n3) Of ）, Just calm down for a while and start writing .
I wrote one first 50 Divide violence , Then start rush Positive solution , Because it encapsulates polynomial operations , It's actually fast . Find infinite after writing RE, Start to tune the sample . Because I'm not used to output debugging , So combined gdb use . Compared with experience dev Next IDE The integrated environment experience is much worse , It took more than an hour to get one 180 The procedure of the line . In the middle, I wanted to give up several times , But before the simulation, it was the only one in the game AC The experience of data structure problem gives me a little confidence , Keep telling yourself it's coming out , So he insisted .
It's called out T2, It feels stable , Next, finish as scheduled T3 Of 40 branch , I began to take photos consciously .WC My experience tells me ,MLE It's the biggest enemy , So I specially measured the time and space , Make sure you don't make mistakes .
After checking the file name, the exam is over , After the next exam, I was too nervous to eat , With zyy and zjc They asked each other questions , It's time to score .
See the score , 100 + 100 + 40 = 240 100+100+40=240 100+100+40=240
, There is only feeling of happiness in my heart . hear au Line 190 branch , So I felt a little relieved .
<>Day 2
I had a bad sleep the night before , I woke up before five in the morning , I'm sleepy, but I can't sleep at all , So I made a cup of coffee in the morning , And a little bit of balm .
I've been worrying about interactive questions before the exam , So I took a look JOI Some classical binary interaction problems on trees .
Remember to write this opening tips It's over , I'll finish the same thing , I feel like I can't do any questions , It's going to be over ? Think of before cjb That's right , Calm down , Read the question quietly first .
It took a long time 10min Calm down , Finish T1, find 88 The two-dimensional line segment tree is very convenient , But it won't work out for a while . When you think of it, this question seems to be claris I've seen this on my blog , But it's a wonderful way , It may not be simple , So I jumped to the following question .
T2 Random by probability , It reminds me CTS
D2T3, The inscription is too expensive 2.5h Got it 20 branch , It doesn't feel good .T3 It seems to be normal interaction on the graph , There are many parts , But I don't want to push for a while , I'm still looking back T1.
I think so 10min, It is found that the contribution of rectangle is fixed , So it can be simulated Dijkstra, Using line segments to nest trees treap, Every time find out the point in the rectangle that has not been deleted, update it . This time it's fast , It's not a short tree , It only took a long time 30min It's over. It's over .
The state of mind has stabilized a little , As long as the following questions are well written ,T1 Do not write and hang , I'll be stable ?
feel T2 only 40 We can do it separately , So I think the discrimination is in the middle T3, Start playing interactively . Before the exam, the dichotomous interaction had an effect ,A and B All of the parts were quickly solved by XOR and .C and D It seems a bit difficult , But with the idea of XOR and , It can also be solved by deleting leaves . This part has 68 branch , It's a good score . There's more in the back
n ≤ 1004 n \leq 1004n≤1004 Part of , I feel like I can do it ?
I went to the bathroom and calmed down for a while , Come back and finish it A and B,C and D We're in some trouble , However, it has been solved quite smoothly , Not yet 11 spot .
I want to stop now , But think of last year was the team line card experience , Tell yourself you can't relax . So to n ≤ 1004 n\leq 1004 n≤1004
Part of the sub try for a while the idea of dichotomy , It turns out it's fake . Calm down for a while , The problem is that the number of edges connected by a point is even , It's not two points at this time . Think of a problem in the simulation game before , The problem is solved by a question about combinatorial numbers
m o d 3 mod\ 3mod 3
The nature of , Forced dichotomy , So can I construct a set , So that the number of sides connected to this point inside is odd , And then it's two ? Because the interaction library is given , So just random half of the points .
Finish writing this practice , There are already 80 The observable fraction of points . Think about it , It seems that the full score algorithm is modified on the basis of this practice , But it's empty , So I put it T2 Of 40 It's divided . In fact, there is still room left at this time 1h, But to be on the safe side , I didn't write the full score （ I feel like I can finish what I write ）.
Finally, fear T1 MLE, Specially measured the space for a while and then the test ended .
This time I gave up eating , Go back to the computer room and calm down . It seems that most of the students in the same school do not do well in the exam , however T2 I heard it was a sb topic , So I was very nervous .
See the score , 100 + 40 + 80 = 220 100+40+80=220 100+40+80=220
, The nervous heart finally relaxed . I talked with other players in the field , I'm surprised to find that I have the former 10 It's possible .
After that, go straight THU I changed my walk appointment （ It's not a fraction line yet ）, And then hang out .dcx D2 The exam blew up , Wandering on the edge of the line , Tried to help him see a wave of code , It can't be reevaluated .
night 6 More than a point finally announced the list , I'm in line rk7, It's a place I didn't even think of before ,yww and zjt They're all on the team .dcx It's a great pity , I got stuck in the line because of my mistake , I feel very sorry for him , Training with him for so long , He definitely has the strength of the training team , But I made a mistake in the final exam , It's a pity .
<> End ?
NOI2019 It's over , Entered the national training team , The dream has been realized . Some of the partners of the same trade join the team together , Keep going , Some regret to miss the training team . More people sign contracts with colleges and Universities , End up with an agreement OI distance .
When I saw this last year , I'm still a junior high school student , Busy every day orz Every way dalao. Follow Dong Dong every day , witness stdcall Regret retirement , I heard that hamsters missed the chance to join the team because of the suffix array . I was off the line 5 branch , I'm sorry , But because there is no direct interest , There was not much loss .
A year has passed , Experienced NOIP Play a stable role , Frustration of Peking University Training ,WC An unexpected crash , The freshness of training in No.80 Middle School , The unexpected joy of provincial election ,THUPC And CTS The joy of life , final , With one NOI My gold medal , It's a terminator .
Thank you, Mr. Lin , Thank your parents , Without their hard work , It is impossible to achieve such a result . I still remember the most lost days after Peking University training , It was you who enlightened me , Let me not give up , Can finally taste the taste of success .
Thanks, too cjb, Before the game , In the competition , Take care of me after the game , Enlighten me . For me , You've done your best , Regardless of the fatigue of boats and cars , I came to ask about my results at the first time after the competition , Anyway , After all, I can't reach it rk1, You don't have to invite me to dinner !
Thanks more dcx, Over the past year , We work together , hit cf and atcoder Late into the night , stay QQ Talk about the topic , Follow the blog to write questions together . Without you , I can't insist on doing this myself , Raise the level . This year , Because of your company , It was the happiest day of my training . It's a pity that you didn't join the training team this time , But then whatever choice you make , I will understand and support you . of course , I hope you can stay , Work with me for another year , Strive to enter the national training team , I believe next time , Luck will surely favor you who are diligent . after all , I don't want to go my own way .
Thank you all for helping me , I've been with you OIer. The seasons change , Peer OIer Come and go, too , Many people may never meet again , But with mayaohua2003 this ID My identity , I'm bound by you , I will probably not forget your names in the future , And the road we went through together , Friendship formed together . I hope you will go better and better on your respective paths .
therefore , Is this the end ? It could be , Maybe not . Now that we have come here , So the next few months , I will also be a student of Guangzhou No.2 Middle School , Try to challenge goals that were once out of reach , Maybe we can go further , Maybe it will stop soon . however , Now that we have this opportunity , that , Just try .
Technology
Daily Recommendation