DQS DQS

分类 数据结构 下的文章

【UER #1】DZY Loves Graph 带撤销并查集

in 算法,并查集,数据结构 read (190)
http://uoj.ac/problem/14 只是想来写一发带撤销的并查集,然而今天这题竟然不会做了… 只有前两个,显然每条边至多被加入和删除一次。直接用并查集做就行。注意按秩合并。 (然而删除时维护作为秩的高度很麻烦,所以用size当秩,正确性不知道,网上好多代码这...

[BZOJ1854][Scoi2010]游戏 并查集||匈牙利

Description lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极b...

线段树合并学习笔记

in 算法,线段树&&树状数组,数据结构 read (245)
被Splay的启发式合并的坑爹常数坑了无数次之后决定学习一下新姿势… 一些证明 正确性前提:对于同样值域的权值线段树,它们的结构是相同的。 所以可以同时递归处理,合并两子树可以直接把两子树根节点信息合并。 复杂度证明:两个线段树合并时,如果一个为空则返回另一个。否则递归合并...

[hdu6200]mustedge mustedge mustedge tarjan|树剖|并查集|树状数组|LCA

Problem Description Give an connected undirected graph with n nodes and m edges, (n,m≤105) which has no selfloops or multiple edges initi...

HIT Summer Training Contest2

辛苦打了一周的rating一天掉没了,非常伤心 智商不够,不会做构造题………… A : hdu - 5723 给一张图,求最小生成树,以及在最小生成树上任选两点的距离长度期望值。 每条边被计算的次数是左右两边点数之积。 死于少个强转longlong………… #includ...
雷姆
拉姆