四糸智乃
四糸智乃
全部文章
算法
题解(25)
归档
标签
去牛客网
登录
/
注册
四糸智乃的兔子窝
四糸智乃DA☆ZE,小四喵~喵喵喵~
全部文章
/ 算法
(共11篇)
CDQ分治(基于归并排序的分治)
CDQ分治 预备知识 分治 与传统分治相同,CDQ分治的核心思想也是分而治之。 对于一个数组序列上的问题,分治的思想是总是考虑中的这一部分,而对于这一求解函数则使用递归表示。 式子中的加号并不一定是加法,只表示答案的合并。 这个说法有点过于抽象了。 ...
分治
CDQ分治
2020-10-10
25
4372
长链剖分
长链剖分可以视作是dsu on tree算法的一个特例,在学习之前,需要掌握树链剖分以及dsu on tree。 dsu on tree:https://blog.nowcoder.net/n/a84c24c37daf450d8bf9db81607c8f98 dsu on tree用于解...
长链剖分
dsu
启发式合并
2020-04-15
4
2260
dsu on tree(树上启发式合并)
dsu的意思是并查集,但是dsu on tree这个算法和并查集的关系也就剩一个启发式合并了。 学习这个算法的切入点还真不在启发式合并,关于启发式合并的问题实际上是最后再考虑它为什么叫启发式合并。 我们选什么作为切入点呢,选莫队算法,如果你不懂莫队也没关系,这里只是说这两个算法在应用的场...
dsu
启发式合并
2020-04-15
15
4848
树状数组
树状数组 树状数组常用于维护前缀信息,如前缀和、前缀乘积等等。 最常见的如给你一个长度为n的数组,单点修改,查询区间的和。 首先是想一下为什么不能用前缀和数组强行搞 先看一下前缀和 黄色和蓝色部分合起来表示前缀和覆盖的区间 黄色表示前缀和信息储存的位置 ...
树状数组
前缀和
2020-02-07
4
1648
高维前缀和(SOSDP)
高维前缀和(SOSDP) 高维前缀和,又叫SOSDP,Sum over Subsets dynamic programming,它一般是用来解决子集类的求和问题(虽然也可以解决高维空间的求和问题,但是时空往往不允许)。 高维度下求前缀和时,时间复杂度的瓶颈 先看一下前缀和的式子 一...
状态压缩
高维前缀和
前缀和
2020-02-07
27
10129
树状数组维护前缀和的前缀和
树状数组维护前缀和的前缀和 这个东西的用途其实不太大,复杂的区间信息还是靠线段树,而且这个操作线段树能直接干了。 主要应用在以下两个方面: 1、区间加数,区间求和问题。 2、区间加等差数列,单点求值问题。 ①可以用线段树直接干,②可以维护差分数组转化为①。 虽然在...
树状数组
差分
前缀和
2020-02-07
9
3303
二维前缀和与差分
二维前缀和与差分 对于一个二维数组a定义数组为数组a的前缀和数组,可以理解为一个左上矩阵的矩阵和 //为了避免数组越位,下标从1开始 for(int i=1;i<=n;++i) { for(int j=1;j<...
差分
前缀和
2020-02-07
0
1879
前缀和与差分
前缀和与差分 对于一个数组a定义数组为a数组的前缀和数组。 //为了避免数组越位,下标从1开始用 for(int i=1;i<=n;++i) { s[i]=s[i-1]+a[i]; } 定义数组...
差分
前缀和
2020-02-07
16
3470
数位DP
数位DP 所谓数位DP,就是把一个数按照k进制数的每一个位展开,在把每一位的信息作为状态来推出答案。 比如:12345这个数在十进制下可拆为1、2、3、4、5,个位可以推十位,十位可以推百位,以此类推。 推状态的方法有很多,一般来说第一反应就是像普通dp一样从前往后推,但是由于思维难度较高而...
记忆化搜索
数位DP
2020-02-06
7
3696
静态维护区间加等差数列的求和问题
静态维护区间加等差数列的求和问题 维护一个数组,先进行m次操作,然后查询每个位置的值,每个操作给定四个参数l,r,a,k表示从l到r依次加上一个首项为a,公差为k的等差数列。 维护数组,表示原数组的二阶差分。 修改操作 void add(int l,int&...
离线
前缀和
2020-02-06
3
2635
首页
上一页
1
2
下一页
末页