自动搬运

查看原文

来自洛谷，原作者为

	Malkin_Moonlight 不通过 1k 题目不改签名 || AFOed 不经常上谷

搬运于2025-08-24 22:35:28，当前版本为作者最后更新于2024-05-23 20:55:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意分析

给你 $n$ 个节点的完全 $k$ 叉树。然后又给你 $q$ 次查询。每次查询给你两个整数 $x$ 和 $y$ 让你求出这两个点在这个完全 $k$ 叉树中的距离。

思路

其实就是把编号大的那个点进行操作。每次让他变成自己的父亲并且步数加一。直到他与编号小的那个点变为完全 $k$ 叉树中一样的节点。

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
#define pb emplace_back
ll n,k,q,x,y,ans,i,j;
int main()
{
	//freopen("xxx.in","r",stdin);
	//freopen("xxx.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k>>q;
	for(i=1;i<=q;i++)
	{
		cin>>x>>y;
		if(k==1)
		{
			cout<<abs(x-y)<<endl;
			continue;
		}
		ans=0;
		while(x!=y)
		{
			if(y>x) swap(x,y);
			x=(x+k-2)/k;
			ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}