「WC2018」即时战略

「WC2018」即时战略

考虑对于一条链:直接随便找点,然后不断问即可。

对于一个二叉树,树高logn,直接随便找点,然后不断问即可。

正解:

先随便找到一个点,问出到1的路径

然后找别的点,考虑问出来第一个从1过来的未知位置,就可以一口气问下去了。

怎么找?

logn询问次数

法一:

点分治

有点类似:CF772E Verifying Kingdom

可以直接确定走向

暴力插入点,替罪羊重构

O(nlog^2n)

法二:

LCT

直接在实链上不断二分,然后跳到下一个实链上

复杂度分析可以类比access操作,是logn的

最后再access一下

O(nlogn)

(zzt说复杂度不对?)

这个二分找位置的套路看来还是很普遍的。。

原文地址:https://www.cnblogs.com/Miracevin/p/10983602.html