zcmimi's blog
avatar
zcmimi
2019-01-21 11:31:55

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义:

gcd(a,b)为整数ab的最大公约数

引理:

gcd(a,b)=gcd(b,a \bmod b)

证明:

设$r=a \b

avatar
zcmimi
2019-01-20 00:23:01

二维线段树一般用线段树套线段树写,当然也可以用四叉树

树套树,顾名思义,外层树的每个节点都是一棵树。

[题目地址:https://www.luogu.org/problemnew/

avatar
zcmimi
2019-01-20 00:22:39
avatar
zcmimi
2018-12-29 22:31:53

学习的原因:

之所以选择fhqtreap,不是因为可以可持久化,是因为:

1. 短

2. 好理解、好记

3. 应用范围广

不过学之前还是先对treap原理稍微有些了解比较好

其中有些细节还是要靠自己意会意会

原理:

概述:

f

avatar
zcmimi
2018-12-01 21:10:58

https://www.luogu.org/problemnew/show/P3369

最短(最简洁)代码:

解释:
turn(x,p):
    将x的左(p=0)/右(p=1)儿子旋转到x的头顶(变成x的父亲)

![](https://i.loli.net/2018/12/05/

avatar
zcmimi
2018-11-11 22:40:33

这应该是最后一次noip普及组吧。现在初三了,估计现在就AFO

前夕:

while(1)刷题,颓废,rp+=rand(),rp-=rand();

QwQ

Day0:

​ 早上坐了半天高铁,赶了半天路,都懒得打模板了,最后颓了一天slay,只打了3个模

avatar
zcmimi
2018-10-27

差分约束的具体概念:

如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。

例子:

假设有3个数a,b,c 我们知道:

a-b>=2
b-c>=3
a-c>=3

那么:a与c的差

avatar
zc
2020-10-29 16:00:01

查看原题

点击跳转

可以想到用并查集维护连通块(需要数字相同区域)个数

答案就是9*连通块个数

直接对每个点维护普通的并查集太慢了

由于并查集是可以合并的,我们可以使用倍增来合并

将一个点拆成\log n个点,分别代表从点i开始长度为2^k的子串

那么当我们处理两个区间相等的关系时,对区间做二进制拆分,拆成log个区间,分别并起来即可

最后再从上(大)往下(小)连边

avatar
zc
2020-10-29 10:15:24

查看原题

点击跳转

答案与位置没有关系,把序列当作集合来看

设大于等于s的数有cnt个,小于s的数和为sum

那么sum\ge s(c-cnt)

可以用 离散化+树状数组 / 平衡树 维护

avatar
zc
2020-10-29 09:11:32

查看原题

点击跳转

将草按生长速度排序,可以发现每次收割完草的高度仍为单调的

维护区间加,区间覆盖,区间和,区间最大值即可

8/74
Search
search