Dydong
  文章分类
爬虫 2 前端 2 CVE 1 CTF&WEB 5 Docker 1 CTF&PWN 10 web 3 algorithm 40 Java 7 操作系统 4 database 2 php 1 底层原理 1
启发式合并&Manacher 启发式合并&Manacher
启发式合并&Manacher 启发式合并 概念：每一次合并利用贪心的思想把小的部分合并到大的部分之中，因为每一次合并后的区间大小一定会变为原来空间的两倍以上，所以时间复杂度为O(nlogn)。 2154. 梦幻布丁 - AcWin
2022-08-07 algorithm
algorithm
辛普森积分 辛普森积分
辛普森积分 定义 利用积分的定义对不规则面积求和，∫baf(x)dx代表从a到b的面积和，我们利用自适应的方式对面积进行二分，如果左边右边的面积和等于总的面积和那么就自适应((r-l)(f(l)+4f(mid)+f(r))/6)成
2022-06-30 algorithm
algorithm
扫描线 扫描线
扫描线 矩形面积并 离散+从左向右扫，这里的线段树是根据lazy来维护sum的。 #include<iostream> #include<cstring> #include<algorithm> #include<
2022-06-30 algorithm
algorithm
旋转卡壳 旋转卡壳
旋转卡壳 概述 寻找二维平面内距离最远的点，通过做垂线的方式可以证明，最远的点一定位于凸包上。所以先求凸包的轮廓，然后通过变换对锺点的来进行操作，用两条平行线来进行边界的取值，可以用当一条平行线经过凸包上两个点的时候来进行迭代更新，最远的距
2022-06-26 algorithm
algorithm
最小圆覆盖 最小圆覆盖
最小圆覆盖 定义 二维平面上有若干个点，找出一个最小半径的圆覆盖所有的点 最小覆盖圆是唯一的 若p不在s的最小覆盖圆内部，则p必在s的最小覆盖圆边上 随机化点，依次加入每一个点，如果在圆外那么找一个i在圆边上的圆，取最小值 for(i
2022-06-24 algorithm
algorithm
半平面交 半平面交
半平面交 定义 二维平面上有若干个直线，我们不断删除右侧的空间直到所有的直线全部迭代完剩下的就是所求半平面 先将所有的向量按角度排序（atan2(y,x)） 按顺序从左至右扫描所有的向量，用双端队列去维护 只要新的交点在前一个交点的左侧
2022-06-22 algorithm
algorithm
凸包 凸包
Andrew 1.将点按x为第一关键字，y为第二关键字排序 2.从左至右维护下半部分，从右至左维护上半部分 3.维护一个队列保证如果前一个向量在当前向量的左侧则直接推入，在右侧一直迭代至左侧为止 模板 给出二维平面内的所有点，求把这些
2022-06-21 algorithm
algorithm
计算几何（基础知识） 计算几何（基础知识）
计算几何（基础知识） 导论1. 前置知识点 (1) pi = acos(-1); (2) 余弦定理 c^2 = a^2 + b^2 - 2abcos(t) 2. 浮点数的比较 const double
2022-06-20 algorithm
algorithm
树链剖分 树链剖分
树链剖分 树链剖分的核心思想是把一棵树变为一个序列，树中的路径全部转化为logn段连续的区间，接下只要去用线段树或分块去维护即可。剖分有几个定义：轻重儿子：对子树的点数进行排序，最多点的即为重儿子，其它全为轻儿子；轻重边：父节点向轻重儿子
2022-05-27 algorithm
algorithm
莫队 莫队
莫队 分块简介 对序列进行根号n的拆分，接下来每一段做懒标记和单独处理，对于跨块的操作可以对整个大块进行操作，对于小块我们直接暴力修改，因此时间复杂度可以降低至m*根号n。 基本线段树改分块 #include<iostream> #
2022-05-27 algorithm
algorithm
树套树 树套树
树套树 概述树套树一般应用在当一棵树解决不了的时候，一般是利用树状数组或线段树套平衡树或线段树。 线段树套平衡树 1 l r x，查询整数 x 在区间 [l,r][l,r] 内的排名。 2 l r k，查询区间 [l,r][l,r] 内
2022-05-16 algorithm
algorithm
Splay Splay
Splay 概述 平衡树，尽量把时间复杂度压到nlogn，支持的方面有区间修改区间查询，区间翻转，区间删除，整段最大子序列，查询第K大的数，查询数是第几大。也可以运用在树套数中。 核心函数 核心思想通过判断节点的关系如果是直线则先右旋再
2022-05-15 algorithm
algorithm
1 / 4