完全二叉树
三个值N,X,K,分别表示点的个数,点的编号,求到X点的距离为K点的个数。
首先,我们对以X为根的子树进行分析,可以知道到X点距离为K的点的个数为2^k。这里需要特判,深度为K时最左边的编号不能大于N,点的个数就等于min(r,n)-l+1。
然后再对它的父亲进行记数,深度要减1,因为有部分重复计算了,因此要减去重复的部分。
一直跳到1,退出循环
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL dep(LL n,LL x, LL k) {//求距离
LL l = x, r = x;
if (k < 0) return 0;
for (int i = 1; i <= k; i++) {
l =l<<1;
r = r << 1 | 1;
if (l > n) return 0;
}
return min(r, n) - l + 1;
}
void solve() {
LL n, x, k;
cin >> n >> x >> k;
LL ans = 0;
ans += dep(n, x, k);//对自己计算
while (x / 2) {
k--;
ans += dep(n, x / 2, k) - dep(n, x, k - 1);//减去重复的部分
x >>= 1;//等价于x/=2
}
cout << ans << '\n';
}
int main() {
LL t;
cin >> t;
while (t--) {
solve();
}
return 0;
}