完全k叉樹

https://cometoj.com/contest/59/problem/A?problem_id=2712

題目描述

?

歡迎報考JWJU！這里有豐富的社團活動，比如為夢想奮斗的ACM集訓隊，經常組織飛行棋的桌游協會，喜歡“唱，跳，rap，籃球”的籃球協會，更奇特的是——讓人耳目一新的攀樹協會。顧名思義，攀樹協會會經常組織大家攀爬一些樹，比如李超樹，左偏樹，帶花樹，智慧樹等等。經過社團組織的一番培訓后，同學們已經學會了如何在樹上的相鄰結點中來回爬動。

不過上述的樹太沒意思了，RegenFallenRegenFallen同學向往更刺激的挑戰，今天他要挑戰的項目是一棵完全?kk?叉樹。

完全kk叉樹的定義：一個?mm?層的完全?kk?叉樹的前?m-1m?1?層均為滿?kk?叉樹，且第?mm?層的結點全部聚集在樹的左側。

因為RegenFallenRegenFallen是一個持久的男人，所以他希望一次能爬盡量長的路徑（不走重復的點），所以他想讓你告訴他，假如現在有一棵?nn?個點的完全?kk?叉樹，每條邊的長度均為?11，從樹上的某一點到另一點的最大距離是多少。

?

輸入描述

?

第一行給出一個?tt?(t≤10^{4}t≤104) 代表測試用例的組數。

接下來t行，每行包含兩個正整數?k, nk,n?(1 \le k \le 10^9, 2 \le n \le 10^91≤k≤109,2≤n≤109) 意義如題面所示。

?

輸出描述

?

對于每個測試用例，輸出一行一個正整數表示答案。

?

樣例輸入 1?

1 2 3

樣例輸出 1

2

提示

樣例給出了一個3個點的完全二叉樹，即第一層有一個點，第二層有兩個點。那么可以選擇第二層的兩個點來計算距離，其距離為2，即為樹上的最大距離。

?

模擬題，累加層數分類討論可AC

CODE;

#include<cstdio> #define ll long long using namespace std; int main() {int t;scanf("%d",&t);while(t--){ll k,n;scanf("%lld%lld",&k,&n);if(k==1){printf("%lld\n",n-1);continue;}ll temp=1,cnt=0;while(n){n-=temp;cnt++;temp*=k;if(n<temp)break;}if(n==0)printf("%lld\n",cnt*2-2);else if(n<=temp/k)printf("%lld\n",cnt*2-1);elseprintf("%lld\n",cnt*2);}return 0; }

?

轉載于:https://www.cnblogs.com/fusiwei/p/11262466.html

總結

以上是生活随笔為你收集整理的Comet OJ 夏季欢乐赛 完全k叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。