wxyww

未归档

精品(28) 题解(65)

/ 注册

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

[Treap][学习笔记]

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

2018-11-29

0 362

[luogu1552][派遣]

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

2018-11-27

0 348

[luogu1552][派遣]

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

2018-11-27

0 297

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

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

2018-11-27

0 447

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

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

2018-11-27

0 365

[左偏树][学习笔记]

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

2018-11-27

0 384

[左偏树][学习笔记]

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

2018-11-27

0 412

noip2018游记

Day0 路上紧张到不行。特别担心今年会挂掉。 Day1 一塌糊涂 T1似乎是积木大赛的原题。当时只用了个分治的做法在洛谷上水过去了。考场上发现能被卡成\(n^2\) T2看了很久只好写了个exgcd，最后10分钟发现是个完全背包。哎。写完过不了大样例啊啊啊。果断删掉，又不小心把iostrea...

2018-11-11

0 468

[20181107][模拟赛]

题面 T1 思路考虑一下每个数会与其他位置的哪些数字遇到。显然每隔gcd(n,m,k)个数都会遇到一次。所以只要看一下将给出的所有数字全部对gcd(n,m,k)取模是否能包含从0到gcd(n,m,k) - 1的所有数就行了。代码 #include<cstdio> #incl...

2018-11-07

0 344

[20181107][模拟赛]

题面 T1 思路考虑一下每个数会与其他位置的哪些数字遇到。显然每隔gcd(n,m,k)个数都会遇到一次。所以只要看一下将给出的所有数字全部对gcd(n,m,k)取模是否能包含从0到gcd(n,m,k) - 1的所有数就行了。代码 #include<cstdio> #incl...

2018-11-07

0 343