[learning notes] double + two points

Smile House

Double the wonderful question ！ I have good food

Wrote a hand $O(n^4)$ Search for ,T 了 .

And then think dp .

Simple approach , set up dp[k][i][j] Express i To j after <= k The longest path of an edge .

If dp[k][i][i] > 0 Then it is proved that there is a ring . Time complexity or $O(n^4)$ .

Obviously multiplier optimization . set up dp[k][i][j] Express i To j after <= 2^k The longest path of an edge .

And then a brain puff , Abandon this practice .

From high to low . If there is no ring , Just put 2^i Spell it in .

The answer is ans+1 .

expand ： The minimum ring problem （ Edge weight and the smallest ring ）. tips：floyd Algorithm , Time complexity O(n^3) . The same is the problem of rings , All borrowed the idea of multi-source shortest path , But the solution is slightly different .

Boboniu and String

This sewing problem almost scared me

thank Rabbit_Mua With the help of the

It has nothing to do with strings .

Consider abstracting into a pair of points in the coordinate system (a,b) .

Suppose the selected string t Coordinate for (x,y) .

Yes 6 You can move in two directions . Almost scared again

Two points answer . Control every point to fall into this area .

Now the problem is almost transformed . The next thing to do is to find (x,y) The value range of .

First of all, it must be in a rectangular area .

Secondly, it must be between two slashes .

Finally get $x\in [L,R],y\in [L2,R2],y-x\in [L3,R3]$ .

Judge $[L2-R,R2-L]\cap [L3,R3]$ that will do .

tips：

1. The combination of number and form , Abstract and transform the original problem .
2. Using inequality to limit the solution of the problem

The Hidden Pair

thank xpx And help with problem solving

Interactive questions have a lot to consider , So solving interactive problems is not a simple thing

First of all, we put n Ask one point , The point thus obtained must be on the path of the two marked points .

Suppose we know one of the marking points , Then another marking point can be used 1 Ask again to find , Just ask all the points with the same depth as the other marked point after removing the path from this marked point to the root （ The depth of the other mark point can be subtracted from the distance between the two mark points calculated before ）

in fact , We only need to know the depth of one of the marked points to find this point .

It is assumed that the required marking point depth is [l,r] Between

We can find in two .

Suppose the depth is [mid,r] Ask all the questions , If the returned length = The distance between two marked points , Prove the depth of one of the marked points >=mid .

Maybe we should pay attention to the writing of dichotomy .

So the total number of inquiries $1+\lfloor \log 1000\rfloor +1=12$ .

How to optimize ？

Notice that our original dichotomy range is [0,D] （D Represents the depth of the tree ）

In fact, we only need to find the deeper mark point .

So the real dichotomy range is [(len+1)/2,min(D,len)]

In this way, the number of inquiries will be exactly one less .

tips：

1. Beginning with interactive questions , To understand its format and problem-solving ideas
2. As far as the subject is concerned , The property of the shortest path is used , The nature of the distance between two points on a tree , And two points . In general, we can only think through the problem , To solve an interactive problem .