hrbust-易琳凯
hrbust-易琳凯
全部文章
分类
未归档(152)
归档
标签
去牛客网
登录
/
注册
hrbust-易琳凯的博客
全部文章
(共152篇)
易错点
如果出现输入数字后,后期没有修改却发生了改变,有可能发生越界 在做LCA的时候preant数组第第二维度应该合适,不要造成越界
2019-08-09
0
296
E - Count on a tree 树上第K小
主席树的入门题目,这道题的题意其实就是说,给你一棵树,询问在两个节点之间的路径上的区间第K小 我们如何把树上问题转换为区间问题呢? 其实DFS就可以,我们按照DFS的顺序,对线段树进行建树,那么这个树上问题就可以转换为区间问题了, 那么如何询问来表示两个节点之间的路径呢? 其实也很简单,可以...
2019-08-09
0
432
Codeforces Round #577 (Div 2)
A. Important Exam 水题 #include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> using namespace ...
2019-08-06
0
369
2019牛客多校第一场A. Equivalent Prefixes
当然单调栈的解法这里就不提了。。。 说一下笛卡尔树的解法 其实这个题意一出来,只要学过笛卡尔树的人,都应该知道怎么解了。 如果两个序列前K项,满足要求他们的子集合的最小值位置相同,那么他们数组的前K项构造出来的其实笛卡尔树其实是相同的。 方法1.每次二分一个长度l...
2019-07-26
0
316
笛卡尔树
定义:笛卡尔树是一种特定的二叉树数据结构,可由数列构造,在范围最值查询、范围top k查询(range top k queries)等问题上有广泛应用。它具有堆的有序性,中序遍历可以输出原数列 总的来说就是,二叉查找树+堆 给定下列序列,那么构造出来的就是如图的东西。 你可...
2019-07-26
0
479
Codeforces Round #575 (Div. 3)
出题:A-B-D1-D2 补题:C-E-F 总结:B看错题,导致浪费非常多的时间,D2用前缀和分成三个写就超时,可能是我姿势不对。。。逃,心态炸了没读读懂C。。。还是太辣鸡了 A. Three Piles of Candies #include<i...
2019-07-25
0
396
Educational Codeforces Round 69
最近水平下降有点严重啊。。。还是多打CF熟悉手感 A. DIY Wooden Ladder 水题,给一个序列a,问最大K是多少? 条件是序列中有两个值大于k+1,其他的有k个大于等于1的值 直接排序即可,最多也就n-2条,枚举判断即可 #include<ios...
2019-07-23
0
332
[kuangbin带你飞]专题九 连通图E POJ 3177 Redundant Paths
这个题最开始我想的是,直接缩点求双连通分量,连接这些双联通分量不就行了吗? 但是其实是不对的,双连通内部双联通,我们如果任意的连接一条边在这些双联通分量之间,他们之间有没有桥其实并不知道。 我应该是求缩点以后的叶子节点的个数,因为叶子节对于其本身来说,只有一条桥于其相连,我们可以连接两个叶子节点...
2019-07-23
0
336
[kuangbin带你飞]专题九 连通图D - Network POJ - 3694
这道题其实也非常简单,只是在求割边及其个数的情况下,每次往里面加入新的边,并再次计算割边的个数。 我们用tarjan可以求出原图的桥以及个数,当然我们不能暴力加边,然后求解,那么如何求呢??? 其实非常简单,我们可以LCA进行求解,我们在a和b点两个点之间加入新的边,那么相当于连通了a,b,那么...
2019-07-22
0
372
[kuangbin带你飞]专题九 连通图C - Critical Links UVA - 796
这道题就是要求桥的个数。 那么桥相应的也有判定的定理: 在和u相邻的节点中,存在一个节点是最小的时间戳都比 当前u的访问次序要大,也就是说这个点是只能通过果u到达,那么 他们之间相邻的边就是的桥 #include<iostream> #include<string.h...
2019-07-22
0
291
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页