计算几何——扫描线学习笔记 你会发现我的笔记的顺序和很多扫描线的讲解是反着来的。 其实是和我老师给的课件完全是逆序（谁帮我算一下逆序对啊喵）。 前言 一开始以为扫描线就是用来求二维几何图像的信息的。 但是其实这个并不准确。个人认为，扫描线其实是一个思想，就像动态规划一样。 具体的，其思想为，用一根（无形的）的线，去扫描一个空间。 在扫描的过程中记录下信息，然后加以处理、应用。如图： 当然你可以暂时忽略这个图片的内容。 引入——会议室问题 问题描述：一个饭店要接待\(n\)个顾客，每个顾客会在时间\([l_i,r_i]\)内就餐。求饭店里同时存在的最多的顾客数量。 非常基础的一道题了。我们举一...

线性代数——平面向量学习笔记 首发于洛谷。 定义及用语说明 无特殊说明，下文的向量均指自由向量且是平面向量。 向量，英文名为vector，目前没有准确而统一的中文翻译。 在物理学科，一般翻译成「矢量」，且与「标量」一词相对。 在数学学科，一般直接翻译成「向量」。对于向量的乘法： 物理 数学 直译 俗称 标量积 数量积 内积 点积 矢量积 向量积 外积 叉积 物理和数学上的用语采用了意译的方法，分别表示运算的结果为标量和矢量。 在数学学科，通常也可以翻译成「内积」和「外积」，是两个名词的直译。 而「点积」和「叉积」是根据运算符号得来的俗称，这种俗称也很常见。 本文采用「点...

图论——浅谈理论，DFS序、时间戳和欧拉序 提示：本文在树论基础上。 下文图例 DFS序：124579836.欧拉序：124457997885236631.回加欧拉序：124257975852123631. 下文举例均指此图。 DFS序 周所周知，DFS为深度优先遍历，其框架如： voiddfs(intu,intfa){ for(intv:g[u]) if(v!=fa)dfs(v,u); } 而DFS序就表示，DFS遍历节点的顺序。 比如第3个遍历到的节点为Q，则DFS序的第三个就是Q。 其框架表示为： voiddfs1(intu,intfa){ em.push_back(u);...

珂学家——珂朵莉树学习笔记 珂朵莉树（ChthollyTree），又名老司机树ODT（OldDriverTree）。 起源自lxl的CF896CWillem,ChthollyandSeniorious。 前置知识：std::set。 思想 将区间用set维护，每次对一个区间进行操作的时候，就将这个区间分离（split）出来。 复杂度的保证依靠推平操作，由于这个操作大幅减少了节点的数量，因此可以达到减少操作次数的目的；而对于每一个查询操作，暴力求解。 因此，我们可以得出卡死珂朵莉树的方法：避免推平操作，甚至没有推平操作，这样珂朵莉树就退化为暴力的\(\mathcalO(nm)\)了。（珂朵...

图论——最短路学习笔记 其实是复习性质的，主要是总结，证明什么的，等上大学再说。 定义 单源最短路：从一个点\(q\)出发，到其他所有点的最短路。 全源最短路：任意两点见最短路。 算法对比 算法 Floyd Johnson Bellman–Ford SPFA Dijkstra 类型 全源 全源 单源 单源 单源 作用于 任意图 任意图 任意图 任意图 非负权图 检测负环 能 能 能 能 不能 时间复杂度 \(\mathcal{O}(n^3)\) \(\mathcal{O}(nm\logm)\) \(\mathcal{O}(nm)\) \(\mathcal{O}(m...

C中<iterator><functional><numeric>库好用的函数 泰裤辣！ <iterator> 简述：迭代器省代码用的。 std::advance 记忆方法：advance－前进。 形如：advance(it,step)，表示it迭代器自增step步。 实现类似于： functionadvance(&it,n): whilen>0: --n it whilen<0: n --it 或 functionadvance(&it,n): it+=n std::next&std...

各种闲着没事的scanf奇葩用法 然而这些却很好用诶。 同理，scanf可以拓展到sscanf、fscanf 例题：P1580yyylovesEaster_EggI、P7911网络连接 未计入更加奇葩的C语言用法，比如%i%a这种明显等价的转换字符。 基础１：整数输入 十进制32位整数：%d十进制32位无符号整数：%u十进制64位整数：%lld十进制64位无符号整数：%ull 八进制32位整数：%o十六进制32位整数：%x 基础２：浮点数读入 单精度浮点数（float）：%f双精度浮点数（double）：%lf高精度浮点数（longdouble）：%LF 基础３：字符输入 输入一个字符：%c ...

动态规划——决策单调性优化DP学习笔记 决策单调性 对于最优性问题，常有状态转移方程：\(f_i=\min/\max\{f_j\dots\}\)， 形象的：如果\(i\)的最优转移点是\(j\)，\(i'\)的最优转移点是\(j'\)，当\(i<i'\)时，有\(j\lej'\)，则称该DP问题具有决策单调性。 即：\(i\)单增，其最优转移点单调不减。 如何发现一个转移方程具有决策单调性？打表。 使用 一、离线决策单调性 形如：\(f(i,j)=\min\limits_{k\lej}\{f(i-1,k)+\text{cost}(k,j)\}\)，转移分层. 形象的：\(f(i,j)\)...

基本技巧——分数规划学习笔记 引入 分数规划用来求一个分式的极值。 具体的，给定\(n\)个元素，每个元素有属性\(a_i,b_i\)，求一个集合\(P\in[1,n]\)，最大／最小化比率：$$\dfrac{\sum_{i\inP}a_i}{\sum_{i\inP}b_i}$$ 求解 二分法 假设我们要求最大值（求最小值的方法和求最大值的方法类似），二分一个\(\text{mid}\)，然后推式子（省略范围）： $\begin{array}{ll}&\suma_i/\sumb_i\ge\text{mid}\\\Longrightarrow&\suma_i\ge\sumb_i...

动态规划——树形DP学习笔记 引入 前置知识：树基础。 树形DP，即在树上进行的DP，最常见的状态表示为\(f_{u,\cdots}\)，表示以\(u\)为根的子树的某个东东。 本文将讲解一些经典题目（树的子树个数、树的最大独立集、树的最小点覆盖、树的最小支配集、树的直径、树的重心、树的中心），以及一些常见形式及思路（树上背包、换根DP）。 分类 树形DP问题的划分方法有多种方式。 按照「求解目的」进行划分 选择节点类：在树上进行选择，相邻节点不允许同时选； 树形背包类：在树上进行背包式的选择； 树的直径类：各种树上最近、最远、最长一类。 按照「阶段转移的方向」进行划分 自底向上：通过...

动态规划——带权二分优化DP学习笔记 引入 带权二分其实并不一定用于优化DP，也可能用于优化贪心等最优化的算法。 带权二分也叫WQS二分，最初由王钦石在他的2012年国家集训队论文中提出。 定义 使用情况 要解决一个最优化问题（求最大/最小值） 有一个限制，一般是某个参数要求一定恰好为\(k\) 而带权二分就可以很好的解决［恰好\(k\)个］的限制；以选物品取最大收益为例： 设\(f(k)\)为恰好选\(k\)个时的最大收益，将所有的\((k,f(k))\)画出来，图像必须组成一个凸包。 因此就可以打表看，是否组成了一个凸包，如果是，则可以考虑带权二分优化。 使用方法 例：求\(f(k...

搜索——进阶搜索算法 前情提要～ 双向广搜、双向深搜 堆优化的Dijkstra 一颗小小的A-STAR 不大聪明的IDDFS（IDS） 可爱的IDA-STAR 广搜、深搜 这是进阶搜索算法，不说了直接上例题： 以“P1514引水问题”为例： 点击查看代码 include<bits/stdc.h> usingnamespacestd; constintN=510; constintdx[4]={-1,0,0,1}; constintdy[4]={0,-1,1,0}; intn,m; inta[N][N]; boolvis[N][N][N]; vector<pa...

基本技巧——尺取法学习笔记 算法简介 尺取法，简单来说是一种利用［双指针法］遍历满足条件的［区间］的算法。 其算法思想为：对数组保存⼀对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。 尺取法不会去枚举到一定不满足条件的区间，所以是一种［⾼效的枚举区间的⽅法］。 朴素算法 先考虑朴素算法： 暴力\(O(n^2)\)：对于每一个\(l\)指针，枚举\(r\)指针。 二分\(O(n\logn)\)：对于每一个\(l\)指针，二分\(r\)指针。 其中\(1\)可以解决［无单调性的问题］；而\(2\)需要保证单调性，可以通过大部分的题目；但是对于部分\(n\le...

图论——Kruskal重构树 最大生成树将部分内容倒置即可 回顾：Kruskal 基本信息 求解最小生成树 时间复杂度：\(O(m\logm)\) 更适合稀疏图 算法思想 按照边权从小到大排序 依次枚举每一条边，如果这一条边两侧不连通，则加入这条边 代码 点击查看代码 include<bits/stdc.h> definerrread() usingnamespacestd; constintN=200010; inlineintread() { intnum=0,flag=1; charch=getchar(); for(;!isdigit(ch);ch=g...

线性代数——矩阵、矩阵乘法、广义矩阵乘法 引入 矩阵 一般用圆括号或方括号表示矩阵，形如： \(A=\begin{pmatrix}a_{11}&\cdots&a_{1n}\\\vdots&\ddots&\vdots\\a_{m1}&\cdots&a_{mn}\end{pmatrix}\) 矩阵表示线性方程组 例如，将线性方程组： \(\left\{\begin{matrix}7x_1+8x_2+9x_3=13\\4x_1+5x_2+6x_3=12\\x_1+2x_2+3x_3=11\end{matrix}\right.\) 写成矩阵乘法的形式（将...

线性代数——高斯消元 引入 消元法 消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其带入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。 矩阵表示线性方程组 例如，将线性方程组： \(\left\{\begin{matrix}7x_1+8x_2+9x_3=13\\4x_1+5x_2+6x_3=12\\x_1+2x_2+3x_3=11\end{matrix}\right.\) 写成矩阵乘法的形式（将系数抽出来）： \(\begin{pmatrix}7&8&...

数论——欧几里得算法、裴蜀定理、扩展欧几里得算法 引入 最大公约数 最大公约数即为GreatestCommonDivisor，常缩写为gcd。 一组整数的公约数，是指同时是这组数中每一个数的约数的数。\(\pm1\)是任意一组整数的公约数；一组整数的最大公约数，是指所有公约数里面最大的一个。 特殊的，我们定义\(\gcd(a,0)=a\)。 最小公倍数 最小公倍数即为LeastCommonMultiple，常缩写为lcm。 一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。\(0\)是任意一组整数的公倍数；一组整数的最小公倍数（LeastCommonMultiple,LCM），是指所有正...

数论——线性同余方程、乘法逆元 众所周知： 说明 如果爆int请自行开longlong或边读边模，或高精度处理。 同余 定义 若\(a\bmodm=b\bmodm\)，则称\(a\)与\(b\)关于模\(m\)同余，记为\(a\equivb\pmodm\). 同余的性质 反身性：\(a\equiva\pmodm\)； 对称性：若\(a\equivb\pmodm\)，则\(b\equiva\pmodm\)； 传递性：若\(a\equivb\pmodm\)、\(b\equivc\pmodm\)，则\(a\equivc\pmodm\)； 同余式相加：若\(a\equivb\pmodm\)、\...

数论——卢卡斯定理、求组合数 说明 温馨提示：组合数一般较大，下面的示范代码均无视数据范围，如果爆int请自行开longlong或高精度处理。 引入 从\(n\)个不同元素中，任取\(m\)个元素组成一个集合，叫做从\(n\)个不同元素中取出\(m\)个元素的一个组合；从\(n\)个不同元素中取出\(m\leqn\)个元素的所有组合的个数，叫做从\(n\)个不同元素中取出\(m\)个元素的组合数，也被称为「二项式系数」。 用符号\(\dbinom{n}{m}\)来表示，读作「\(n\)选\(m\)」；组合数计算公式：\(\dbinom{n}{m}=\dfrac{n!}{m!\,(nm)!}\)...

数论——欧拉函数、欧拉定理、费马小定理 欧拉函数 定义 欧拉函数（Euler'stotientfunction），记为\(\varphi(n)\)，表示\(1\simn\)中与\(n\)互质的数的个数。 也可以表示为：\(\varphi(n)=\sum\limits_{i=1}^n[\gcd(i,n)=1]\). 例如： \(\varphi(1)=1\)，即\(\gcd(1,1)=1\)；\(\varphi(2)=1\)，即\(\gcd(1,2)=1\)；\(\varphi(3)=2\)，即\(\gcd(1,3)=1\)，\(\gcd(2,3)=1\)；\(\dots\) 性质 欧拉函数是积...