2022/7/12 exam summary

Time arrangement

8:00~8:40

T1 It looks very friendly , Just write a tree backpack , On the way to writing, I suddenly realized that merging is k^2 Of , Can't get past .
So it's just 40pts

8:40~9:20

This question looks like 0/1 Fractional programming , Enumerating the median after two points can do $O(n^{2}logn)$
After writing, I found that I couldn't pass the example , After checking, I found that there was a wrong formula in the middle .

9:20~10:00

After modification, it is found that the median of enumeration is monotonic , So double pointer scan directly , Complexity $O(nlo{g}^{2}n)$
Measured the limit data and found that 2s, Think about it and find that it doesn't get stuck , So I handed it in first .

10:00~10:30

T1 The chain of can enumerate the endpoints of the interval to do $O(n^{3}k)$, You can go through this gear

10:30~10:50

Write T2 The violence of

10:50~11:40

analysis T2 The special properties of ,subtask4 It seems best to write , Every 1 The change of the situation is to walk to the right from a certain moment , Then go straight , Up to the right 1 end , That is to say, movement is an interval , At first, I wanted to use a balanced tree / Tree cover tree maintenance this thing , But I found that I couldn't write at all , Gave up .

A summary after the exam

T1
First , I didn't think I could divide and conquer / Chain divide and conquer
secondly , I've been thinking about how to reduce the complexity of backpack merging , In fact, I have seen this routine many times before , such as BZOJ4182 Shopping
, Is in the $O(nm)$ Solve the knapsack problem on the tree within the time complexity , The idea is that father and son share an array of backpacks , Then the father's knapsack value can be inherited directly from his son , After divide and conquer at the same time , When considering a subtree , The point that may be connected with it must be the ancestor on its divide and conquer tree , You can record whether each ancestor chose .
Next time you encounter a backpack on a tree, you must think about this .
T3
It may be this way to find the maximum average / The median question is too much , When I see this problem, I think 0/1 Fractional programming , There is no analysis of the nature of the original problem .
It can only be said that although the routine is too much, it can save a lot of thinking time , But it's also easy to cling to this routine , Deeper and deeper , Instead, the topic itself has a special nature , The complexity of doing it directly is better .
I feel more and more that my thinking ability is not enough , Or should we do more thinking questions .