完全二叉树
三个值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;
}