- 题目描述
小红有一棵包含 n个节点的完全二叉树[1]，其中 1号节点为根，i号节点的左儿子编号是 2×i，右儿子编号是 2×i+1。
现在有 q次询问，每次查询一个 x，你需要回答与 x号节点深度[3]相同的节点有多少个（包含 x本身）。
- 【名词解释】
完全二叉树[1]：
满足以下全部条件的二叉树[2]：
若树的层数为 h，则除第 h层外，其他各层（1至 h−1层）的节点数均达到最大值（即第 i (1≤i<h)层节点数为 2 i−1 ）；
第 h层的所有节点都连续集中在左侧，即节点之间不存在任何空位。
二叉树[2]：
满足以下全部条件的树：
二叉树可以是空集；若不为空，则由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成；
每个节点要么没有父节点连接（此时该节点被称为根节点）、要么被 1个父节点连接（此时该节点被称为父节点的子节点）；
每个节点连接的子节点数量要么为 0（此时该节点被称为叶子节点），要么不超过 2，且此时每个子节点都有明确的“左”或“右”属性。
深度[3]：
从根节点到节点 u的唯一路径上的边数，称为节点 u的深度。根节点的深度为 0。
- 输入格式
每个测试文件均包含多组测试数据。第一行输入一个整数 T (1≤T≤10^4)代表数据组数。
每组测试数据描述如下：
第一行输入两个整数 n,q (1≤n≤10^18; 1≤q≤2×10^5)，表示二叉树的节点数、询问次数；此后 q行，第 i行输入一个整数 xi (1≤xi ≤n)，表示第 i次询问的节点编号。除此之外，保证单个测试文件的 q之和不超过 2×10^5。
- 输出格式
对于每一次询问，新起一行输出一个整数，代表与 xi号节点深度相同的节点数量。 样例如下：
- 题解如下
根据二叉树的性质我们可以先画出样例一的树图：
不难看出来可以和二进制的位数挂钩，每一行最左边的数转换成二进制，对应的二进制位数就是该行的行数，比如4转成二进制是110，是三位，他就在树中的第三行，再继续画图可以发现最前面的数就意味着该行有多少个节点，所以我们可以用到一个函数 "__lg()",这个函数用于快速计算一个整数的以 2 为底的对数的整数部分，也就是不大于 log₂(x) 的最大整数。对于完全二叉树的节点编号 x，深度 = __lg(x)，因此我们可以很轻易地解决这题了，代码及注释如下：
……省略头文件
//头文件有#define int long long 为了减少代码量没复制头文件
void solve() {
int n, q, i;
cin >> n >> q;
int highest = __lg(n);// 树的高度（最大深度）
while (q--) {
int x, ans;
cin >> x;
int high = __lg(x);
if (high < highest) // 在非最后一层
ans = 1ll << high;
else // 在非最后一层
ans = n - (1ll << highest) + 1; // 最后一层的起始节点编号 = 2^highest
cout << ans << endl;
}
}
signed main() {
//vector<vector<int>>a(n,vector<int>(m)); 二维构造
//cout << fixed << setprecision(10); 固定小数输出
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
cin >> T;
while (T--) solve();
return 0;
}
如有错误感谢指出和纠正！
京公网安备 11010502036488号