首页 > 其他分享 >E - Complete Binary Tree

E - Complete Binary Tree

时间:2023-09-24 15:12:10浏览次数:37  
标签:Binary return Complete dep LL Tree ans

E - Complete Binary Tree

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

标签:Binary,return,Complete,dep,LL,Tree,ans
From: https://www.cnblogs.com/bu-fan/p/17725994.html

相关文章

  • pyqt5-QTreeWidgetItem
    QTreeWidgetItem树节点项。QTreeWidgetItem(strings:Iterable[str],type:int=QTreeWidgetItem.Type)创建节点时,必须是Iterable[str],表示一行中各列的文本 1、子节点child(self,index:int)->QTreeWidgetItem获取某节点的某子节点childCount(self)->int获......
  • pyqt5-QTreeWidget
    QTreeWidget树组件。1、顶级项addTopLevelItem(self,item:QTreeWidgetItem)末尾添加单个顶级项addTopLevelItems(self,items:Iterable[QTreeWidgetItem])末尾批量添加顶级项insertTopLevelItem(self,index:int,item:QTreeWidgetItem)指定索引插入单个顶级项......
  • Codeforces 1868D. Flower-like Pseudotree
    题目链接:D-Flower-likePseudotree题目大意:给定度数数组\({d_n}\),要求构造一个\(n\)个点\(n\)条边的连通图(也就是基环树),允许有重边,但不能有自环。需要满足第\(i\)个点的度数恰好为\(d_i\),并且将环上的边全部删去后,剩下的每棵树的高度(以原先在环上的点为根)相同。首先考......
  • Vscode Todo Tree
    管理注释,便于查找开发过的代码,提高工作效率。 使用: ......
  • 算法题——定义一个方法自己实现 toBinaryString 方法的效果,将一个十进制整数转成字符
    用除基取余法,不断地除以基数(几进制,基数就是几)得到余数,直到商为0,再将余数倒着拼起来即可。privatestaticStringtoBinaryString(intnumber){StringBuildersb=newStringBuilder();while(true){if(number==0)break;intyushu=num......
  • 【Java 基础篇】Java TreeSet 详解:红黑树实现的有序集合
    Java集合框架提供了多种数据结构,用于存储和操作数据。其中,TreeSet是一种特殊类型的集合,它通过红黑树(Red-BlackTree)数据结构实现了有序的、唯一元素存储。本篇博客将深入探讨TreeSet,包括其概念、特性、内部实现、使用方法以及示例代码。无论您是初学者还是有一定经验的Java开......
  • CF1842F Tenzing and Tree 题解
    TenzingandTree感觉很典型的题,就是树的重心+绝对值等式解法:以每个点\(i\)为根分别\(bfs\),得到一个距离数组\(dis\),取前\(k\)个值的权值为和,更新\(w[k]\)的值,\(n\)个点分别为根,更新\(n\)遍之后,得到\(w\)数组,则\((n-1)\timesi-w[i]\),即为\(i\)个点时候的......
  • Arrays.binarySearch 详解
    Arrays.binarySearch详解前提:非降序排序数组binarySearch(Object[]a,Objectkey)a:待搜索的数组key:要搜索的值逻辑条件可以找到:返回一个>=0的索引找不到:【从1开始计数】在数组范围内,返回-(key将要插入的位置)不在范围内:返回-1或者-(len+1)......
  • ClickHouse(15)ClickHouse合并树MergeTree家族表引擎之GraphiteMergeTree详细解析
    GraphiteMergeTree该引擎用来对Graphite数据(图数据)进行瘦身及汇总。对于想使用ClickHouse来存储Graphite数据的开发者来说可能有用。如果不需要对Graphite数据做汇总,那么可以使用任意的ClickHouse表引擎;但若需要,那就采用GraphiteMergeTree引擎。它能减少存储空间,同时能提高Grap......
  • CF1767C Count Binary Strings 题解
    CF1767CCountBinaryStrings题解Foreword感谢@樱雪喵、@swiftc两位大佬的耐心指导。Links洛谷CodeforcesDescription有一个长度为\(n\)的01串\(s\)(下标从\(1\)开始)和一些限制\(a_{i,j}(1\lei\lej\len)\)。\(a_{i,j}\)的含义如下:\(a_{i,j}=\)含义......