2022/7/11 exam summary

Time arrangement

8:00~8:40

First look at T1, I don't know what the best strategy is , But this form is the form of linear programming , So I directly rushed a simple type , At the beginning, I also turned to the dual problem , But I don't know why I can't pass the example , Later, it was found that direct simplicity was ok .

9:00~9:40

Yes T2 Of violence , The second gear is divided dinic The theoretical complexity of violence is $O(n^{2}mk)=5e17$, I'm shocked that this kind of thing can be too big

9:40~10:10

Write T3 Of 20 Fractional pressure , Then I guessed that the answer would not be very big , Therefore, direct memory explosion search , But it doesn't seem to work .

10:10~10:40

Think about how to use T2 The randomization of , Try to put dinic Change it to hlpp, But I can't write it out and give up .

A summary after the exam

T1

1. When I saw the question in the examination room, I fooled myself into a linear programming , After the example, I thought I could , Only later did I know , Linear programming solves an optimal real number solution , The problem requires an integer solution , Therefore, it must be adjusted to the integer solution after finding a solution , It seems very troublesome , Therefore, it is still necessary to write paragraphs , Hold the sure points first , The rest is in mang .
2. The first time I saw a backpack made of digital , Take advantage of the special nature of the topic , The state of the backpack can be written as $a\times 2^b$ In the form of , among a A very small , So you can only record a, To make a backpack , The complexity can be greatly reduced , Similar topics are [HNOI2007] The Pearl of Neverland . I feel that if I know this skill, this problem is not difficult , If you don't know, you can't think of it at all .
3. Using the drawer principle , The minimum upper bound can be deduced , hold dp The range of is minimized ,

T2

This is the fourth time in the recent exam to use the randomness of data , Summarize several functions of data randomness :
1: Make the data distribution very uniform , In this case, the probability of data conflict generated is small , Once there is a certain probability, the correct algorithm will become correct , Many different numbers will be generated , Using the drawer principle , You can think that some numbers will be generated .
2: The distance between the data is very close , In this case, violent enumeration , The number of enumerations expected is very small , You can do it directly .
3. Some seemingly complicated practices , Because I am not satisfied with the upper bound , So you can go through .
The practice of binary grouping in problem solving feels quite magical , By binary grouping , Can produce some magical properties , Or ensure certain correctness , I will encounter this again K The topic of three key points can be considered in this direction .

T3

The transformation in the solution of the problem is simply unexpected , Not to mention the greed and dp 了 .
I can only say that my thinking ability is not good , Although it is difficult to make these transformations and properties in the examination room , But still do more questions with high thinking content , It's still helpful to do this kind of problem .