hrbust-易琳凯

未归档

/ 注册

全部文章 / 未归档（共152篇）

易错点

如果出现输入数字后，后期没有修改却发生了改变，有可能发生越界在做LCA的时候preant数组第第二维度应该合适，不要造成越界

2019-08-09

0 301

E - Count on a tree 树上第K小

主席树的入门题目，这道题的题意其实就是说，给你一棵树，询问在两个节点之间的路径上的区间第K小我们如何把树上问题转换为区间问题呢？其实DFS就可以，我们按照DFS的顺序，对线段树进行建树，那么这个树上问题就可以转换为区间问题了，那么如何询问来表示两个节点之间的路径呢？其实也很简单，可以...

2019-08-09

0 440

Codeforces Round #577 (Div 2)

A. Important Exam 水题 #include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> using namespace ...

2019-08-06

0 378

2019牛客多校第一场A. Equivalent Prefixes

当然单调栈的解法这里就不提了。。。说一下笛卡尔树的解法其实这个题意一出来，只要学过笛卡尔树的人，都应该知道怎么解了。如果两个序列前K项，满足要求他们的子集合的最小值位置相同，那么他们数组的前K项构造出来的其实笛卡尔树其实是相同的。方法1.每次二分一个长度l...

2019-07-26

0 332

笛卡尔树

定义：笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列总的来说就是，二叉查找树+堆给定下列序列，那么构造出来的就是如图的东西。你可...

2019-07-26

0 497

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 408

Educational Codeforces Round 69

最近水平下降有点严重啊。。。还是多打CF熟悉手感 A. DIY Wooden Ladder 水题，给一个序列a，问最大K是多少？条件是序列中有两个值大于k+1，其他的有k个大于等于1的值直接排序即可，最多也就n-2条，枚举判断即可 #include<ios...

2019-07-23

0 345

[kuangbin带你飞]专题九连通图E POJ 3177 Redundant Paths

这个题最开始我想的是，直接缩点求双连通分量，连接这些双联通分量不就行了吗？但是其实是不对的，双连通内部双联通，我们如果任意的连接一条边在这些双联通分量之间，他们之间有没有桥其实并不知道。我应该是求缩点以后的叶子节点的个数，因为叶子节对于其本身来说，只有一条桥于其相连，我们可以连接两个叶子节点...

2019-07-23

0 345

[kuangbin带你飞]专题九连通图D - Network POJ - 3694

这道题其实也非常简单，只是在求割边及其个数的情况下，每次往里面加入新的边，并再次计算割边的个数。我们用tarjan可以求出原图的桥以及个数，当然我们不能暴力加边，然后求解，那么如何求呢？？？其实非常简单，我们可以LCA进行求解，我们在a和b点两个点之间加入新的边，那么相当于连通了a,b，那么...

2019-07-22

0 375

[kuangbin带你飞]专题九连通图C - Critical Links UVA - 796

这道题就是要求桥的个数。那么桥相应的也有判定的定理：在和u相邻的节点中，存在一个节点是最小的时间戳都比当前u的访问次序要大，也就是说这个点是只能通过果u到达，那么他们之间相邻的边就是的桥 #include<iostream> #include<string.h...

2019-07-22

0 298