题解：P8046 [COCI2015-2016#4] CHEWBACCA

Malkin_Moonlight · 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;
}