腾讯云开发者社区-腾讯云

开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

数据结构与算法

专栏作者

1812

文章

1329377

阅读量

135

订阅数

BZOJ3732: Network(Kruskal重构树)

编程算法二叉树

$n \leqslant 15000, m \leqslant 30000, k \leqslant 20000$

2018-07-27

3560

BZOj1261: [SCOI2006]zh_tree(dp)

Time Limit: 10 Sec Memory Limit: 162 MB Submit: 400 Solved: 272 [Submit][Status][Discuss] Description 张老师根据自己工作的需要，设计了一种特殊的二叉搜索树。他把这种二叉树起名为zh_tree，对于具有n个结点的zh_tree，其中序遍历恰好为(1，2，3，…，n)，其中数字1，2，3，…，n 是每个结点的编号。n个结点恰好对应于一组学术论文中出现的n个不同的单词。第j个单词在该组论文中出现的次数记为dj

2018-07-05

3720

2039. 树的统计

二叉树数据结构编程算法

输入文件：counttree.in 输出文件：counttree.out 简单对比时间限制：1 s 内存限制：128 MB 【题目描述】关于树的统计问题有多种多样的版本，这里你需要解决一个比较简单的问题：对于一棵包含N个节点的有根树，将所有点从1到N编号后，对于每一个节点v，统计出以v为根的子树中有多少个点的编号比v小。【输入格式】输入第一行包含一个整数N，以下N行每行包含一个整数，其中第i行的整数表示编号为i的节点的父亲节点的编号，根的父亲节点编号为0。【输出格式】

2018-04-13

5800

P2015 二叉苹果树

编程算法数据结构二叉树

题目描述有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。输入输出格式输入格式：第1行2个数，N和Q(1<=Q<= N,1<N<=100)。 N表示树的结点数，Q表示要

2018-04-13

8610

P1040 加分二叉树

编程算法二叉树

题目描述设一个n个节点的二叉树tree的中序遍历为（1,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二

2018-04-13

9170

codevs 1814 最长链

二叉树人工智能

1814 最长链时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出一棵N个结点二叉树，问这棵二叉树中最长链的长度为多少，保证了1号结点为二叉树的根。输入描述 Input Description 输入的第1行为包含了一个正整数N，为这棵二叉树的结点数，结点标号由1至N。接下来N行，这N行中的第i行包含两个正整数l[i], r[i]，表示了结点i的左儿子与右儿子编号。如果l[i]为0，表示结点i没有左儿子，同样地，

2018-04-12

7130

2977 二叉堆练习1

二叉树 ios 人工智能

2977 二叉堆练习1 时间限制: 10 s 空间限制: 32000 KB 题目等级 : 白银 Silver 题目描述 Description 已知一个二叉树，判断它是否为二叉堆(小根堆) 输入描述 Input Description 二叉树的节点数N和N个节点(按层输入) 输出描述 Output Description YES或NO 样例输入 Sample Input 样例输入1 3 1 4 9 样例输入2 3 6 4 9 样例输出 Sample Output 样例输出1 YES 样例输出2

2018-04-12

4740

2879 堆的判断

数据结构二叉树 ios 人工智能

2879 堆的判断时间限制: 1 s 空间限制: 32000 KB 题目等级 : 黄金 Gold 题目描述 Description 堆是一种常用的数据结构。二叉堆是一个特殊的二叉树，他的父亲节点比两个儿子节点要大，且他的左右子树也是二叉堆。现在输入一颗树(用二叉树的数组表示，即a[i]的左儿子与右儿子分别为a[2i],a[2i+1])，要求判断他是否是一个堆。输入描述 Input Description 一个整数N，表示结点数。第二行N个整数，表示每个结点代表的数字输出描述 Outpu

2018-04-12

5850

二叉树的遍历

二叉树数据结构编程算法人工智能

解决二叉树的很多问题的方案都是基于对二叉树的遍历。遍历二叉树的前序，中序，后序三大方法算是计算机科班学生必写代码了。其递归遍历是人人都能信手拈来，可是在手生时写出非递归遍历恐非易事。正因为并非易事，所以网上出现无数的介绍二叉树非递归遍历方法的文章。可是大家需要的真是那些非递归遍历代码和讲述吗？代码早在学数据结构时就看懂了，理解了，可为什么我们一而再再而三地忘记非递归遍历方法，却始终记住了递归遍历方法？三种递归遍历对遍历的描述，思路非常简洁，最重要的是三种方法完全统一，大大减轻了我们理解的负担。而我们常接触

2018-04-12

1.1K0

2010 求后序遍历

二叉树 ios 人工智能

2010 求后序遍历时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description 输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。输入描述 Input Description 共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。输出描述 Output Description 仅一行，表示树的后序遍历序列。样例输入 Sample Input abdehicfg dbheiafcg 样例输出 Sam

2018-04-12

5510

二叉树 ios 人工智能

1094 FBI树 2004年NOIP全国联赛普及组时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树[1]，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下： 1) T的根结点为R，其类型与串S的类型相同；

2018-04-12

5830

二叉树性质

•【性质1】在二叉树的第i层上最多有2i-1个结点（i>=1）。【性质2】深度为k的二叉树至多有2k –1个结点（k>=1）。 •【特别】一棵深度为k且有2k–1个结点的二叉树称为满二叉树。如下图A为深度为4的满二叉树，这种树的特点是每层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左到右，由此引出完全二叉树的定义，深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树 •【性质3】对任意

2018-04-12

5430

POJ 2104 K-th Number（主席树）

数据结构二叉树编程算法

Description You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segm

2018-04-12

5970

P3369 【模板】普通平衡树（Treap/SBT）

数据结构二叉树

题目描述您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：插入x数删除x数(若有多个相同的数，因只删除一个) 查询x数的排名(若有多个相同的数，因输出最小的排名) 查询排名为x的数求x的前驱(前驱定义为小于x，且最大的数) 求x的后继(后继定义为大于x，且最小的数) 输入输出格式输入格式：第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6) 输出格式：对于操作3,4,5,6每行输出一个数

2018-04-12

4420

3674: 可持久化并查集加强版

数据结构二叉树编程算法

Description Description：自从zkysb出了可持久化并查集后…… hzwer:乱写能AC，暴力踩标程 KuribohG：我不路径压缩就过了！ ndsf：暴力就可以轻松虐！ zky:…… n个集合 m个操作操作： 1 a b 合并a,b所在集合 2 k 回到第k次操作之后的状态(查询算作操作) 3 a b 询问a,b是否属于同一集合，是则输出1否则输出0 请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0

2018-04-12

6920

#106. 二逼平衡树（附带详细代码注释）

数据结构二叉树编程算法

内存限制：512 MiB时间限制：4000 ms标准输入输出题目类型：传统评测方式：文本比较上传者：匿名提交提交记录统计讨论测试数据题目描述这是一道模板题。您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：查询 x xx 在区间内的排名；查询区间内排名为 k kk 的值；修改某一位置上的数值；查询 x xx 在区间内的前趋（前趋定义为小于 x xx，且最大的数）；查询 x xx 在区间内的后继（后继定义为大于 x xx，且最小的数）。输入格式第一行

2018-04-12

9110

Day2平衡树笔记

数据结构二叉树

线段树不支持的操作：删除，插入 ---- 常见的平衡树 treap 慢||好写 sbt(大小平衡的树) 非常快比较好写 ||功能不全 rbt 红黑树特别快 || 非常难写以上操作支持插入删除O(NlogN) splay 特别慢。。≈O(sqrt(N)) 不太好写，功能强大 ---- 可持久化Treap 平衡树一定是二叉树左儿子里面的元素一定比他小右儿子一定比当前节点大中序遍历一定排好序每次递归的查询小——》左大——》右弊端：深度可能会非常深-->代价非

2018-04-11

6530

HDU 3078 Network

数据结构二叉树

Problem Description The ALPC company is now working on his own network system, which is connecting all N ALPC department. To economize on spending, the backbone network has only one router for each department, and N-1 optical fiber in total to connect

2018-04-11

6230

震惊！Vector两行代码求逆序对，六行代码过普通平衡树

数据结构二叉树

Vector两行代码求逆序对背景：济南集训Day7上午T2，出了一道逆序对的裸题，SB的我没看出是逆序对来，于是现场推了一个很刁钻的求逆序对的方法首先我们想一下冒泡排序的过程，我们不难发现，对于每一个元素，我们实际上是让他不停的和前面的元素比较，交换。也正是因为这个过程决定了在冒泡排序的过程中：一个位置的数的前面的数一定是递增的(从小到大排的话) 那么我们在交换的时候，直接二分找到一个合适的位置，插入即可这个很显然可以用平衡树Vector实现代码也非常短， 1 #include<cstdi

2018-04-11

7110

树上倍增求LCA及例题

数据结构二叉树编程算法

先瞎扯几句树上倍增的经典应用是求两个节点的LCA 当然它的作用不仅限于求LCA，还可以维护节点的很多信息求LCA的方法除了倍增之外，还有树链剖分、离线tarjan ，这两种日后再讲（众人：其实是你不会吧:unamused:。。。）思想树上倍增嘛，顾名思义就是倍增相信倍增大家都不默认，著名的rmq问题的的解法就是利用倍增实现的在树上倍增中，我们用表示第号节点，跳了步所能到达的节点表示号节点的深度然后用这两个数组瞎搞搞就能整出LCA来啦众人：:wrench: :

2018-04-11

1.2K0

点击加载更多

社区活动

腾讯技术创作狂欢月

“码”上创作 21 天，分 10000 元奖品池！

Python精品学习库

代码在线跑，知识轻松学

博客搬家 | 分享价值百万资源包

自行/邀约他人一键搬运博客，速成社区影响力并领取好礼

技术创作特训营·精选知识专栏

往期视频·千货材料·成员作品最新动态