补充知识点

• gcd
• 求逆元

深搜策略

1. 优化搜索顺序

   大部分情况下，优先搜索分支较少的节点

2. 排除等效冗余
3. 可行性剪枝
4. 最优剪枝

补充课程

• 离散数学
• 数学分析
• 数论
• 离散数学
  1. 集合、图论
  2. 代数结构、组合数学
  3. 数理逻辑
• 图论和集合论
• 代数空间和组合数学
• 数理逻辑

动态规划技巧

• 最后一步来进行状态转移

名词

• 最大独立集
• 可行流f，容量c

数学

1到n中包含因子p的个数

int cnt = 0;
while(n) cnt += n / p, n /= p;

$$

图论

二分图

最大独立集：选出尽可能多的点，这些点之间没有直接相连的边。
最大团：选出尽可能多的点，任意两点之间都存在边。
最小路径覆盖：在有向无环图中(匈牙利算法可用于无向图，即无向图也可以)，用最少的互不相交的路径，将所有点覆盖。
最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖(最小路径重复点覆盖)

最大独立集
    <=> 去掉最少的点，将所有边破坏掉
    <=> 最小点覆盖
    <=> 最大匹配数

最小路径覆盖(路径中每个点都是匹配点 <=> 路径终点的个数等于路径的个数 <=>左部非匹配点的个数)
    <=> 左侧非匹配点最少
    <=> 让左部匹配点最多
    <=> 找最大匹配

最小路径重复点覆盖(通过传递闭包转化为最小点覆盖)

最大流

1. 可行流f满足以下两个条件
   • 容量限制 $0\leq(f(u,v))\leq(c(u,v))$
   • 流量守恒 $\left(\forall x \right) \in v/\lbrace st \rbrace \sum_{(\forall x)\in E}f(v, x) = \sum_{(\forall x)\in E}f(v, x)$
2. 可行流流量
   $|f| = \sum_{(s, v)\in E}f(s, v) - \sum_{(v, s) \in E}f(v, s)$

3. 割的容量

4. 最小割
   $容量的最小值，将G(V, E)中的点分成两部分源点S和汇点T(S\cup T = V \&\& S\cap T = \phi)，$ $从源S到汇T的最小流量为最小割$

5. 模板
   $EK算法(O(nm^2) 1000 \leq m + n \leq 10000)、dinic算法(O(n^2m)$ $10000\leq m + n \leq 100000)、ISAP()、HLPP()$
6. 如果流量限制在点上就进行拆点
7. 费用流=》消圈法

规律

• 最长上升子序列的长度与最少需要下降子序列个数是对偶的

定义

1. 流的基本概念
    1.1 流网络，不考虑反向边
    1.2 可行流，不考虑反向边
        1.2.1 两个条件：容量限制、流量守恒
        1.2.2 可行流的流量指从源点流出的流量 - 流入源点的流量
        1.2.3 最大流是指最大可行流
    1.3 残留网络，考虑反向边，残留网络的可行流f’ + 原图的可行流f = 原题的另一个可行流
        (1) |f’ + f| = |f’| + |f|
        (2) |f’| 可能是负数
    1.4 增广路径
    1.5 割
        1.5.1 割的定义
        1.5.2 割的容量，不考虑反向边，“最小割”是指容量最小的割。
        1.5.3 割的流量，考虑反向边，f(S, T) <= c(S, T)
        1.5.4 对于任意可行流f，任意割[S, T]，|f| = f(S, T)
        1.5.5 对于任意可行流f，任意割[S, T]，|f| <= c(S, T)
        1.5.6 最大流最小割定理
            (1) 可以流f是最大流
            (2) 可行流f的残留网络中不存在增广路
            (3) 存在某个割[S, T]，|f| = c(S, T)
    1.6. 算法
        1.6.1 EK O(nm^2)
        1.6.2 Dinic O(n^2m)
    1.7 应用
        1.7.1 二分图
            (1) 二分图匹配
            (2) 二分图多重匹配
        1.7.2 上下界网络流
            (1) 无源汇上下界可行流
            (2) 有源汇上下界最大流
            (3) 有源汇上下界最小流
        1.7.3 多源汇最大流
2. 后缀自动机
    一、SAM的性质:

        SAM是个状态机。一个起点，若干终点。原串的所有子串和从SAM起点开始的所有路径一一对应，不重不漏。所以终点就是包含后缀的点。
        每个点包含若干子串，每个子串都一一对应一条从起点到该点的路径。且这些子串一定是里面最长子串的连续后缀。
        SAM问题中经常考虑两种边：
            (1) 普通边，类似于Trie。表示在某个状态所表示的所有子串的后面添加一个字符。
            (2) Link、Father。表示将某个状态所表示的最短子串的首字母删除。这类边构成一棵树。
    二、SAM的构造思路

        endpos(s)：子串s所有出现的位置（尾字母下标）集合。SAM中的每个状态都一一对应一个endpos的等价类。
        endpos的性质：
        (1) 令 s1,s2 为 S 的两个子串 ，不妨设 |s1|≤|s2| （我们用 |s| 表示 s 的长度 ，此处等价于 s1 不长于 s2 ）。则 s1 是 s2 的后缀当且仅当 endpos(s1)⊇endpos(s2) ，s1 不是 s2 的后缀当且仅当 endpos(s1) ∩ endpos(s2)=∅　。
        (2) 两个不同子串的endpos，要么有包含关系，要么没有交集。
        (3) 两个子串的endpos相同，那么短串为长串的后缀。
        (4) 对于一个状态 st ，以及任意的 longest(st) 的后缀 s ，如果 s 的长度满足：|shortest(st)|≤|s|≤|longsest(st)| ，那么 s∈substrings(st) 。
    三、SAM的构造过程
        分类讨论，具体看板书。
        证明较为复杂，略。

    四、SAM时间复杂度
        线性。
        证明较为复杂，略。
3 计算几何
    1. 前置知识点
        (1) pi = acos(-1);
        (2) 余弦定理 c^2 = a^2 + b^2 - 2abcos(t)

    2. 浮点数的比较
    const double eps = 1e-8;
    int sign(double x)  // 符号函数
    {
        if (fabs(x) < eps) return 0;
        if (x < 0) return -1;
        return 1;
    }
    int cmp(double x, double y)  // 比较函数
    {
        if (fabs(x - y) < eps) return 0;
        if (x < y) return -1;
        return 1;
    }

    3. 向量
        3.1 向量的加减法和数乘运算
        3.2 内积（点积） A·B = |A||B|cos(C)
            (1) 几何意义：向量A在向量B上的投影与B的长度的乘积。
            (2) 代码实现
            double dot(Point a, Point b)
            {
                return a.x * b.x + a.y * b.y;
            }
        3.3 外积（叉积） AxB = |A||B|sin(C)
            (1) 几何意义：向量A与B张成的平行四边形的有向面积。B在A的逆时针方向为正。
            (2) 代码实现
            double cross(Point a, Point b)
            {
                return a.x * b.y - b.x * a.y;
            }
        3.4 常用函数
            3.4.1 取模
            double get_length(Point a)
            {
                return sqrt(dot(a, a));
            }
            3.4.2 计算向量夹角
            double get_angle(Point a, Point b)
            {
                return acos(dot(a, b) / get_length(a) / get_length(b));
            }
            3.4.3 计算两个向量构成的平行四边形有向面积
            double area(Point a, Point b, Point c)
            {
                return cross(b - a, c - a);
            }
            3.4.5 向量A顺时针旋转C的角度：
            Point rotate(Point a, double angle)
            {
                return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle));
            }
    4. 点与线
        4.1 直线定理
            (1) 一般式 ax + by + c = 0
            (2) 点向式 p0 + vt
            (3) 斜截式 y = kx + b
        4.2 常用操作
            (1) 判断点在直线上 A x B = 0
            (2) 两直线相交
            // cross(v, w) == 0则两直线平行或者重合
            Point get_line_intersection(Point p, Vector v, Point q, vector w)
            {
                vector u = p - q;
                double t = cross(w, u) / cross(v, w);
                return p + v * t;
            }
            (3) 点到直线的距离
            double distance_to_line(Point p, Point a, Point b)
            {
                vector v1 = b - a, v2 = p - a;
                return fabs(cross(v1, v2) / get_length(v1));
            }
            (4) 点到线段的距离
            double distance_to_segment(Point p, Point a, Point b)
            {
                if (a == b) return get_length(p - a);
                Vector v1 = b - a, v2 = p - a, v3 = p - b;
                if (sign(dot(v1, v2)) < 0) return get_length(v2);
                if (sign(dot(v1, v3)) > 0) return get_length(v3);
                return distance_to_line(p, a, b);
            }
            (5) 点在直线上的投影
            double get_line_projection(Point p, Point a, Point b)
            {
                Vector v = b - a;
                return a + v * (dot(v, p - a) / dot(v, v));
            }
            (6) 点是否在线段上
            bool on_segment(Point p, Point a, Point b)
            {
                return sign(cross(p - a, p - b)) == 0 && sign(dot(p - a, p - b)) <= 0;
            }
            (7) 判断两线段是否相交
            bool segment_intersection(Point a1, Point a2, Point b1, Point b2)
            {
                double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
                double c3 = cross(b2 - b1, a2 - b1), c4 = cross(b2 - b1, a1 - b1);
                return sign(c1) * sign(c2) <= 0 && sign(c3) * sign(c4) <= 0;
            }
    5. 多边形
        5.1 三角形
        5.1.1 面积
            (1) 叉积
            (2) 海伦公式
                p = (a + b + c) / 2;
                S = sqrt(p(p - a) * (p - b) * (p - c));
        5.1.2 三角形四心
            (1) 外心，外接圆圆心
                三边中垂线交点。到三角形三个顶点的距离相等
            (2) 内心，内切圆圆心
                角平分线交点，到三边距离相等
            (3) 垂心
                三条垂线交点
            (4) 重心
                三条中线交点（到三角形三顶点距离的平方和最小的点，三角形内到三边距离之积最大的点）
        5.2 普通多边形
            通常按逆时针存储所有点
            5.2.1 定义
            (1) 多边形
                由在同一平面且不再同一直线上的多条线段首尾顺次连接且不相交所组成的图形叫多边形
            (2) 简单多边形
                简单多边形是除相邻边外其它边不相交的多边形
            (3) 凸多边形
                过多边形的任意一边做一条直线，如果其他各个顶点都在这条直线的同侧，则把这个多边形叫做凸多边形
                任意凸多边形外角和均为360°
                任意凸多边形内角和为(n−2)180°
            5.2.2 常用函数
            (1) 求多边形面积（不一定是凸多边形）
            我们可以从第一个顶点除法把凸多边形分成n − 2个三角形，然后把面积加起来。
            double polygon_area(Point p[], int n)
            {
                double s = 0;
                for (int i = 1; i + 1 < n; i ++ )
                    s += cross(p[i] - p[0], p[i + 1] - p[i]);
                return s / 2;
            }
            (2) 判断点是否在多边形内（不一定是凸多边形）
            a. 射线法，从该点任意做一条和所有边都不平行的射线。交点个数为偶数，则在多边形外，为奇数，则在多边形内。
            b. 转角法
            (3) 判断点是否在凸多边形内
            只需判断点是否在所有边的左边（逆时针存储多边形）。
        5.3 皮克定理
            皮克定理是指一个计算点阵中顶点在格点上的多边形面积公式该公式可以表示为:
                S = a + b/2 - 1
            其中a表示多边形内部的点数，b表示多边形边界上的点数，S表示多边形的面积。
    6. 圆
        (1) 圆与直线交点
        (2) 两圆交点
        (3) 点到圆的切线
        (4) 两圆公切线
        (5) 两圆相交面积
4. 三维计算几何基础
    1. 三维向量表示(x, y, z)
    2. 向量加减法、数乘运算，与二维相同
    3. 模长 |A| = sqrt(x * x + y * y + z * z)
    4. 点积
        (1) 几何意义：A·B = |A| * |B| * cos(C)
        (2) 代数求解：(x1, y1, z1) · (x2, y2, z2) = (x1x2, y1y2, z1z2);
    5. 叉积
        (1) 几何意义：AxB = |A| * |B| * sin(C)，方向：右手定则
        (2) 代数求解：AxB = (y1z2 - z1y2, z1x2 - x1z2, x1y2 - x2y1)
    6. 如何求平面法向量
        任取平面上两个不共线的向量A、B：AxB
    7. 判断点D是否在平面里
        任取平面上两个不共线的向量A、B：先求法向量C = AxB，然后求平面上任意一点到D的向量E与C的点积，判断点积是否为0。
    8. 求点D到平面的距离
        任取平面上两个不共线的向量A、B：先求法向量C = AxB。然后求平面上任意一点到D的向量E在C上的投影长度即可。即：E·C / |C|
    9. 多面体欧拉定理
        顶点数 - 棱长数 + 表面数 = 2
    10. 三维凸包

数据结构

1. splay => fqh-treap
2. 后缀数组 => DC3

防止卡常代码

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")

英文