wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共395篇）

[luogu1503][鬼子进村]

题目链接思路将哪些村庄已经被摧毁了放到treap里。查询的时候如果当前村庄已经被毁了，那么就可以直接输出0.不然就输出这个村庄的后继-前驱-1。原因显然代码 #include<cstdio> #include<iostream> #include<cstd...

2018-11-29

0 377

[luogu3369][普通平衡树]

题目链接思路模板只是有几个容易出错的地方第45行容易忘记第54行里面的cnt--和siz--容易忘记第56行是根据id判断不是val 第60行siz--容易忘记第64行是siz+1不是siz+cnt 第77行和82行等于的情况容易忽略代码 #include<cstdio...

2018-11-29

0 433

[luogu3369][普通平衡树]

题目链接思路模板只是有几个容易出错的地方第45行容易忘记第54行里面的cnt--和siz--容易忘记第56行是根据id判断不是val 第60行siz--容易忘记第64行是siz+1不是siz+cnt 第77行和82行等于的情况容易忽略代码 #include<cstdio...

2018-11-29

0 0

[Treap][学习笔记]

平衡树平衡树就是一种可以在log的时间复杂度内完成数据的插入，删除，查找第k大，查询排名，查询前驱后继以及其他许多操作的数据结构。 Treap treap是一种比较好写，常数比较小，可以实现平衡树基本操作的一种平衡树。treap的平衡是基于随机化。是将堆与二叉查找树结合起来所得到的数据结构。...

2018-11-29

0 347

[luogu1552][派遣]

题目链接思路首先肯定要树形dp，一直没想到怎么用左偏树。如果不断弹出又不断地合并复杂度不就太高了。瞄了眼题解才知道可以直接用大根树。然后记录出当前这棵左偏树的大小(树里面所有点的薪水之和)以及点的个数。然后不断的删点。直到薪水满足条件为止。代码 #include<iostream...

2018-11-27

0 347

[luogu1552][派遣]

题目链接思路首先肯定要树形dp，一直没想到怎么用左偏树。如果不断弹出又不断地合并复杂度不就太高了。瞄了眼题解才知道可以直接用大根树。然后记录出当前这棵左偏树的大小(树里面所有点的薪水之和)以及点的个数。然后不断的删点。直到薪水满足条件为止。代码 #include<iostream...

2018-11-27

0 296

[luogu3377][左偏树(可并堆)]

题目链接思路左偏树的模板题，参考左偏树学习笔记对于这道题我是用一个并查集维护出了哪些点是在同一棵树上，也可以直接log的往上跳寻找根节点代码 #include<cstdio> #include<iostream> #include<cstdlib>...

2018-11-27

0 445

[luogu3377][左偏树(可并堆)]

题目链接思路左偏树的模板题，参考左偏树学习笔记对于这道题我是用一个并查集维护出了哪些点是在同一棵树上，也可以直接log的往上跳寻找根节点代码 #include<cstdio> #include<iostream> #include<cstdlib>...

2018-11-27

0 363

[左偏树][学习笔记]

主要应用首先要知道左偏树是用来干什么的。如果给我们两个优先序列，然后让我把这两个优先队列合并成一个优先队列。如果直接用堆，就是将一个队列里面的数不断弹出然后扔到另一个队列里。复杂度是\(O(n)\)n为队列中数的个数。但是用左偏树就可以做到\(log(n_1 + n_2)\)。 PS：为了便于讨...

2018-11-27

0 382

[左偏树][学习笔记]

主要应用首先要知道左偏树是用来干什么的。如果给我们两个优先序列，然后让我把这两个优先队列合并成一个优先队列。如果直接用堆，就是将一个队列里面的数不断弹出然后扔到另一个队列里。复杂度是\(O(n)\)n为队列中数的个数。但是用左偏树就可以做到\(log(n_1 + n_2)\)。 PS：为了便于讨...

2018-11-27

0 0