题目要求:
对于每一行的数据表示n
个节点,完全m
叉树,求节点k
的子树有多少个,包括k
节点在内。
思路:
其实只要找出k
节点的左右孩子lc,rc
就好了,感觉这个需要不断的尝试,才能找到规律。
lc = (k - 1) * m + 2, rc = k * m + 1
.
- 有了这两个公式,便能求出对于任意一个节点的左右孩子,又因为他是完全m
叉树,
- 所以只有其左孩子和右孩子都小于等于节点n的话,就能计算出该层的节点个数是多少。
- 当发现左孩子大于n的时候,退出循环即可。
- 当发现右孩子大于等于n的时候,是rc = n, 进行最后一次操作就好了。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int T;
int n,m,k;
int Helper()
{
int res = 1;
LL lc = k, rc = k;
if (k > n) //节点不存在
return 0;
bool flag = true;
while (flag)
{
//计算左右孩子
lc = (lc - 1) * m + 2;
rc = rc * m + 1;
//左孩子大于总结点个数就说明该层啥也没有,不需要增加了,直接break就好了。
if (lc > n)
break;
//右孩子大于等于n的话,将右孩子变成n 执行最后一次节点增加操作即可。
if (rc >= n)
{
rc = n;
flag = false;
}
res += rc - lc + 1;
}
return res;
}
int main()
{
scanf("%d",&T);
while (T --)
{
scanf("%d%d%d",&n,&m,&k);
printf("%d\n",Helper());
}
return 0;
}