2015/2/5

leaf posted @ 2015年2月04日 21:38 in 未分类 , 771 阅读

今天终于将那道令人发指的题做掉了。。

题意是給定一棵树,在线询问编号L--R中距离点X最近的点是多少

 

首先,如果L--R固定,哪么我们检出L--R的虚树,然后询问。。那么对于L--R我们只要按1--N区间建立区间虚树,线段树查寻即可。。

 

问题看似解决了???但总感觉线结很多。。

首先怎么存区间的虚树? 我们可以对点开 vector 记录虚树dfs序即可。。。。怎么快速的在虚树上查寻?我一开始觉得很麻烦。。那些不是范围内的点怎么办?其实我们可以计算出每个不在范围内的点到在范围内的点的最短距离,这样就等价于在范围内的点了(有点想 codechef 的 BTREE)。然后怎么在dfs序中查寻距离最短的点?我们将每个点出与入记录到dfs序中,这样lower_bound待求点的dfs序号。。这样在左边的点与右边的点取min。。还有左边点的father(即自己的father)也可能成为答案。。这样就好了。。还有一种情况,就是待求点dfs序是max, 那么与虚树根节点求min即可。。

最后还被卡常数。。。时限3s 我跑了3s+。。怒开大时限。那么总的复杂度是 Nlog^2N

 

 

Avatar_small
HP Board 12th Import 说:
2022年8月17日 23:07

HPBOSE 12th New Question Paper 2023 Download, HPBOSE is popular knows as Himachal Pradesh Board Of School Education. HP Board 12th Important Question Paper 2023 PDF It is one of the large board in India. Himachal Pradesh Board is going to conduct Class 12th annual examination for those candidates who have successfully registered for 12th boards exams in 2023.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter