全部博文  (当前页5篇, 共208篇)

洛谷3379(LCA模板优化)

#problem ##题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 ##输入格式: 第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。 接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。 接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。 ##输...

最近公共祖先(LCA)之树上倍增法

#最近公共祖先 对于有根树T的两个结点u,v,最近公共祖先LCA(T,u,v)表示一个节点x,满足**x是u,v的祖先并且x的深度尽可能大**。 也可以把T理解为一个无向无环图,而**LCA(T,u,v)即u到v的最短路上森度最小的点** 所以,LCA主要就是求解**当两个点仅有唯一一条确定的最短路径时的路径信息**的问题。 #树上倍增 如果我们直接一个一个结点遍历去寻找这样的祖先,复杂...

TOJ 3515(堆_优先队列)

#problem There is a sequence of integers, we have two operations now 1 add a: means add an integer a to the end of the sequence, forms a N+1 long sequence. 2 mid : Output the current sequence's ...

_bitset_头文件简介

#**< bitset >头文件** bitset是用来存放bit位元素的,由于每个元素(0或1)只占1bit位,因而可以节约空间(相比于8bit位的bool型变量)。在c++ stl中,提供了操作位的容器,使用前包含< bitset >头文件即可。 #**相关操作** ###1.创建bitset对象 如bitset<100> b,它能容纳100位比特位,每位上的初始值为0 **注意:...

优先队列简介

#优先队列 STL中封装了**优先队列**(priority_queue)这种结构,它和普通队列的区别是:普通的队列是一种先进先出的数据结构,元素在队列尾部追加,从队列头删除。 而在优先队列中,元素被赋予优先级。当访问元素时,具有最高**优先级**的元素最先删除。优先队列具有**最高级先出**(first in,largest out)的行为特征。 #相关定义及操作 ###类的定义 ``...

当前第30页,共30页