Dist

本文主要是介绍Dist，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

有一棵 n 个点的 k 叉树，点的编号为 \(1…n\)，它的结构描述如下：

1 号点为根节点，如果一个点到 1 号点经过的最少边数为 i 则称它在第 i 层里。
第 i 层的第 j 个点的父亲是 第 i−1 层的第$ ⌊(j−1)/k⌋+1$ 个点。
第 i 层的第 j 个点的编号为 \(∑^{i−1}_{p=0}k^p+j\) 。
从 3 可以看出，除了最深的一层，其余层的点数都是满的(即第 \(i\) 层有 \(k^i\) 个点)
图中画了一个 k=3 的情形：

q 次询问每次询问树上点 x 到点 y 的距离（经过的最少边数）。

输入格式
第一行三个整数 \(n,k,q\) 。

接下来的$ q$ 行每行两个整数$ x,y $。

输出格式
对于每组询问，输出$ x,y$ 之间的距离。

样例
input

9 3 3
8 9
5 7
8 4

output

2
2
3

数据范围
时间限制: 2s
空间限制: 256MB
对于 20% 的数据，$ n,q≤10^3$ 。

对于 50% 的数据， \(n,q≤10^5\) 。

对于 100% 的数据， \(n≤10^{15},2≤k≤10^3,q≤10^5\) 。

发现这棵树的层数应该只有\(log n\)层。所以考虑直接暴力，就是先把两个点跳到同一层，然后再一起往上跳。

我们先研究一下一个点\(x\)的父亲是谁，很明显，\(x\)的父亲是\(⌊(x-2)/k⌋+1\).然后我们还要求出一个点的层数，可以暴力求，但我这里用了二分。然后往上跳就可以了。

#include<cstdio>
using namespace std;
long long n,x,y,pw[60];
int k,q,m,ax,ay,l,r,ans,md;
int askdep(long long x)
{
	l=0,r=m;
	while(l<=r)
	{
		md=l+r>>1;
		if(pw[md]<x)
			l=md+1;
		else
			r=md-1; 
	}
	return l;
}
int main()
{
	scanf("%lld%d%d",&n,&k,&q);
	pw[0]=1;
	for(m=1;pw[m-1]*k<=n;m++)
		pw[m]=pw[m-1]*k;
	--m;
	for(int i=1;i<=m;i++)
		pw[i]+=pw[i-1];
	while(q--)
	{
		scanf("%lld%lld",&x,&y);
		ax=askdep(x),ay=askdep(y),ans=0;
		while(ax>ay)
			ans++,x=(x-2)/k+1,--ax;
		while(ax<ay)
			ans++,y=(y-2)/k+1,--ay;
		while(x!=y)
			ans+=2,x=(x-2)/k+1,y=(y-2)/k+1;
		printf("%d\n",ans);
	}
} 

这篇关于Dist的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！