题意
有T次询问,每次询问给出三个参数N,X,K,分别表示,有N个节点的二叉树,询问从X号节点出发走K条边能走到多少个不同的点。
思路
对于一颗二叉树上的点,我们可以分两种情况,一种是向上走,一种是向下走。
- 对于向下走,我们只需要不停的、分别的遍历当前节点的右儿子(对于二叉树就是序号乘2),直到向下走k层。如果中途存在当前的左儿子>N并且k没有走完,那么直接退出,因为不可能向下走k层。而走完k层时,我们要查看当前的有右儿子是否大于N,直接取min(r,N)即可。向下找的最后结果就是min(r,N)-l+1
- 对于向上走,我们每次到达一个父节点,都想进行一次向下的遍历(因为路程k可以通过折返的形式呈现),在这个过程中,必然会经过x节点并且通过x向下找,这样会导致重复,我们只需要每一次进行向下遍历是减去直接向下走的结果即可。具体的一些细节看代码吧,挺好调的。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dfs(int x,int n,int k)//计算x号点向下走k条边能走到的点数
{
if(k<0) return 0;
int l=x;
int r=x;
for(int i=0;i<k;i++)
{
l<<=1;
r=r<<1|1;
if(l>n) return 0;
}
return min(n,r)-l+1;
}
void solve()
{
int n,x,k;
cin>>n>>x>>k;
if(k==0)
{
cout<<1<<endl;
return ;
}
int ans=dfs(x,n,k);
while(x/2)
{
k--;
ans+=dfs(x/2,n,k)-dfs(x,n,k-1);
x>>=1;
}
cout<<ans<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
solve();
}
return 0;
}
标签:Binary,ABC,return,min,int,Tree,二叉树,向下,节点
From: https://www.cnblogs.com/lulu7/p/18246537