【学习笔记】倍增 + 二分

Smile House

倍增妙题 ！我好菜

写了一手 $O(n^4)$ 的搜索，T 了。

然后想 dp 。

朴素做法，设 dp[k][i][j] 表示 i 到 j 经过 <= k 条边的最长路径 。

如果 dp[k][i][i] > 0 则证明有环 。时间复杂度还是 $O(n^4)$ 。

显然倍增优化。设 dp[k][i][j] 表示 i 到 j 经过 <= 2^k 条边的最长路径 。

然后脑子一抽，把这个做法弃了 。

从高位到低位考虑 。如果没有出现环，就把 2^i 拼进去 。

答案是 ans+1 。

拓展：最小环问题（边权和最小的环）。 tips：floyd 算法，时间复杂度 O(n^3) 。同是环的问题，都借用了多源最短路的思路，但是解决方法略有不同 。

Boboniu and String

这道缝合题差点吓到我了

感谢Rabbit_Mua的帮助

和字符串没有半毛钱关系 。

考虑抽象成坐标系中点对 (a,b) 。

假设选定的字符串 t 坐标为 (x,y) 。

有 6 个方向可以移动 。差点又被吓到了

二分答案。要控制每个点都落到这个区域内。

现在问题转化的差不多了 。接下来要做的就是找到 (x,y) 的取值范围即可 。

首先肯定在矩形区域内 。

其次一定在两条斜线之间 。

最后得到 $x\in [L,R],y\in [L2,R2],y-x\in [L3,R3]$ 。

判断 $[L2-R,R2-L]\cap [L3,R3]$ 即可 。

tips：

1. 数形结合思维，对原问题进行抽象和转化 。
2. 利用不等式限制问题的解

The Hidden Pair

感谢xpx和题解的帮助

交互题要考虑的东西很杂，所以解决交互题不是一件简单的事

首先我们把 n 个点询问一遍，这样得到的点一定在两个标记点的路径上 。

假如我们知道了其中一个标记点，那么另一个标记点可以用 1 次询问求出，只需将除去这个标记点到根的路径后深度与另一个标记点相同的点都询问即可 （另一个标记点的深度可以用之前求到的两个标记点的距离减去其中一个标记点的深度）

事实上，我们只需要知道其中一个标记点的深度就能求出这个点 。

假设要求的标记点深度在 [l,r] 之间

我们可以二分查找 。

假设将深度为 [mid,r] 的点都询问，如果返回的长度 = 两个标记点之间的距离，就证明其中一个标记点的深度 >=mid 。

可能要注意一下二分的写法 。

这样总询问次数 $1+\lfloor \log 1000\rfloor +1=12$ 。

怎么优化呢 ？

注意到原来我们的二分范围是 [0,D] （D 表示树的深度）

实际上我们只需要找深度较大的那个标记点 。

所以真实的二分范围是 [(len+1)/2,min(D,len)]

这样询问次数会恰好少一次 。

tips：

1. 初涉交互题，要体会它的格式以及解题思路
2. 就本题而言，用到了最短路的性质，树上两点距离的性质 ，以及二分 。总的来说只有把问题想透，才能解决一道交互题 。