Phecda_

未归档

/ 注册

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

浅谈线段树

线段树一种初级数据结构(之前一度是高级),相信大多数学习数据结构的人都能熟练地掌握它. 线段树最初开发的意义是高效率地作用于区间操作(对数据的维护),但这个所谓的高效率也并不很高.但,相对于目前已经开发出来的一般性数据结构,线段树无疑是非常优秀且稳定的一个. \(\Theta ( n \times ...

线段树

2019-05-05

0 337

飞行员配对方案问题

飞行员配对方案问题传送门读完题,就知道这就是个裸的二分图皮配,然后,我还是不说匈牙利,(因为我真的不会啊!) 所以,我还是用了喜闻乐见的 Dinic 并且跑的也不慢.唯一难点就是输出方案了吧...输出方案用最后的连通性判断,这题就没了.... Code: #include <io...

网络流二分图最大匹配

2019-04-28

0 312

FhqTreap的区间翻转

学 Fhq 就是为了尽量不去写某毒瘤数据结构,所以自然要来杠一杠某数据结构的经典操作:区间反转听起来玄乎,但只需要一个小 trick 就行了:把原来的区间以下标作为权值建成 Treap , 这样整棵 Treap 的中序遍历就是原区间. 按照这种方法建树,是进行区间操作的第一步.接下来我们考虑如...

平衡树

2019-04-28

0 444

NOI2004郁闷的出纳员

传送门题目看起来玄乎,但其实只需要一点点小 trick 就可以了. 我们可以用一个全局的 delta 来维护工资的调整记录对于每一个新加入的员工,先判断是否低于最低工资下限,如果是,直接踢出,不做任何操作,否则,将其插入 Treap 中,不过这时为了不对以后的查询产生影响,我们要插入的值时 ...

平衡树全局懒标记

2019-04-28

0 436

二分图匹配

你以为我要讲匈牙利?不不不,我不会.我是要讲网络流哒! 呃,我直接说怎么搞吧你把二分图的两边节点搞出来,左边连一个超级源点,容量为 1 右边连一个超级汇点,容量为 1 然后跑从源到汇的最大流最大流就是最大匹配,至于为什么...这里借用一下大佬的证明: 首先假设，当前流网络有一个最大流，...

网络流二分图最大匹配

2019-04-28

0 385

营业额统计

传送门这个题...裸题啊,裸的不能再裸了按天数插入,每次插入之后,比较和前驱后继的差,取 min 统计入答案即可注意之前已经插入过的值就不需要插入了.然后这题就 A 了 Code: #include <iostream> #include <cstdlib> #...

平衡树

2019-04-28

0 497

USACO15DEC最大流MaxFlow

传送门这是个假的最大流,其实是一个用树剖+线段树就能解决的事情题目中的道路会对路径上的造成压力,最后询问最大的压力其实就等价于对每条路径上的点加上 1 的权值,并且最后询问整个树中的最大值然后树剖+最大值线段树裸题,完事,莫得别的问题了. \(Updated:\) 其实,可以树上差...

树链剖分线段树差分

2019-04-28

0 501

FHQ-Treap小结

\(Orz\) 范浩强大爷,竟然搞出了如此夺天地造化的数据结构. \(FHQ-Treap\),又名非旋\(Treap\),是范浩强大爷在某些奇特的灵感之下发明的一种平衡树,因其与\(Treap\)相似的性质和无旋转操作的特性被称为非旋\(Treap\).非旋\(Treap\)用\(Split\)和...

平衡树

2019-04-14

1 557

网络流小结

网络流小结联赛过后,虽然遗憾的没拿到一等,但这不是止步不前的时候,于是我就学了学网络流,学了这几天,也该总结总结了...... 网络流其实就是一种图论模型,在这种图中,边权变成了坑爹的流量,常见的最短路问题也变成了最大流-最小割问题网络图和普通图的最大区别也就是边权不再是一个***巴巴的数...

网络流

2019-03-31

0 298

NOIP2018Day1T2 货币系统

题目描述在网友的国度***有 \(n\) 种不同面额的货币，第 \(i\) 种货币的面额为 \(a[i]\)，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 \(n\)、面额数组为 \(a[1..n]\) 的货币系统记作 \((n,a)\)。在一个完善的货币系统中，每一个非负整...

背包

2018-12-05

0 395