Exam summary on July 15, 2022

Time arrangement

8:00~8:30

The first two questions only seem to be violent , So look T3.
At a glance, we can see a cost flow , Because the flow is very small , So I feel I can pass 2000 Stalls .

8:30~9:00

w=0 The file of is to judge whether there are two 1 To x The path of , Then it is equivalent to asking 1 To x Is there an edge in all paths that must pass , Then break the edge into points , Build a dominant tree , Just judge whether there is an edge in the ancestor of each point , Combined with cost flow , Expected score 70

9:00~9:30

Write T1 The violence of

9:30~10:10

Write T2 Violence and chrysanthemum , Too many details , It took a long time .

10:10~10:25

The practice of muzzle chain , But there are too many details to write .

10:25~11:00

Feeling T1 You can put T and S Are built in reverse SAM Then count how many essentially different strings cross the midpoint .
Write a flower and find something wrong , This problem is not equivalent to the original problem , Then I gave up .

11:00~11:30

Feeling T3 It can simulate the cost flow , But not very good at maintenance .

A summary after the exam

T1

Shocked , What do you think it is SAM perhaps runs, The result is actually computational geometry ？
First, how to quickly find f I didn't expect this , I still don't feel very sensitive , When seeking problems with different essence , You can specify a feature point in each sample , Then find out all the samples with characteristic points for the first time for statistics .
secondly , Even if you can really push it out f, I can't think of associating this thing with vector dot product .
Then the problem becomes to find the maximum value of the dot product of one vector and other vectors , Then obviously only the points on the convex shell are possible , Then we can find that the answer is a unimodal function , It can be divided directly , Or double pointer according to monotonicity after offline .
I can't believe . But I also reviewed the knowledge of computational geometry .

T2

The transformation is very wonderful , Build the graph into a bipartite graph and dye it in black and white , This is really unexpected , Then it is transformed into tree isomorphism count by mapping , The key is not to count tree isomorphism . However, it is not sensitive to the modeling of bipartite graphs , Practice more .

T3

It turned out to be a tarjan The original title of the thesis , And it is to simulate the cost flow , But I haven't understood .