集训笔记

• N,NP,NPC,NP-Hard

排序：（sort）

//通过调整原数的顺序，使数列有序。
//稳定性：两个相同元素排序后的相对位置不发生位置交换则稳定，反之不稳定
//排序范围
* 快速排序
sort(a+1, a+n+1)

基于比较

• 选择排序【不稳定】$O(n^2)$
  {
  selection sort;
  for(......)
  {......
  判断稳定性循环
• 插入排序【稳定】
  insertion sort;
  {
  for(.......)
  {.......
• 冒泡排序【稳定】$O(n^2)$
  bubbie sort
  {.......

逆序对：ia[j]

• 归并排序O(nlogn)
  merge sort
  {.......

不基于比较

• 计数排序（数据量大，数据本身小）

• 基数排序
  radix sort
  ........

数据结构

向量，可以理解成一个数组。

     push-back()//末尾插入元素
     pop-back()//末尾弹出元素
     empty()//返回是否为空
     size()//返回大小

链表

图论（1）

• 有向图
• 无向图
• 自环
• 重边
• 简单图
• 度 degree（有多少条边连接了这个节点）
• 入度
• 出度
• 链式前向星==邻接表
• 路径 path：一个边的序列，且相邻两条边首尾相连
• 简单路径：同一条边只经过一次的路径（简单路径上可能有相同的节点）
• 环 cycle：一个起点和终点相同的路径
• 简单环：是简单路径，还是环
• 连通 connected：如果无向图中两个节点是连通的，则存在从a->b的路径
• 可达：有向图中
• 一个无向图是连通的，当无向图中任何两个节点都连通。
• 有向图没有连通的概念。
• 弱连通：把有向图所有边改成无向的，则该有向图弱连通。
• 强连通:有向图中任意两个节点可达
• 子图 subgraph：在一张图中选择一个边的子集和节点的子集，形成的一张新图，一个图本身是自己的子图。
• 生成子图：节点和原图相同，只删边的子图
• 导出子图：选出节点的子集，并将与该图中两端都有节点的边加入
• 边导出子图：选出边集，再选出相连的节点集合
• 连通子图：对于无向图来说的 连通的子图
• 连通分量 connected component：对于无向图来说，是一个无向图中的极大的连通子图。即再加入一个点，该图 不连通。
• 稀疏图：m=θ(n);
• 稠密图：m=θ(n^2);
• 完全图：任何两个节点之间都有边（对于无向图），m=n*(n-1)/2的简单图；
• 路径的长度：路径上边的长度和
• 最短路径：当不存在负环时存在。
• 树：有n个节点，n-1条边的连通无向图。
• 树：一个无向，无环的连通图。
• 树：任意两个节点之间有且只有一条简单路径的简单无向图。
• 森：每一个连通分量都是一棵树的图。每棵树都是森
• 生成树：是一个生成子图，也是一棵树。
• 有根树：在一棵树上选定一个节点作为根，则为有根树；
• 无根树：没根的树。
• 点的深度：当前节点到根节点的距离。根节点深度=0
• 树的深度：根节点儿子的深度的最大值
• 叶子节点：度为0或1的点
• 父亲：在有根树上，某结点到根的路径上的第二个节点即为父亲节点
• 祖先：到根路径上除了本身以外的所有节点
• 儿子/子节点/孩子/child/children：如果u是v的父亲，则v是u的儿子。
• 兄弟：同一个父亲的多个子节点之间为兄弟关系。
• 后代/子孙：儿子和儿子的后代们。
• 子树：删去该节点和该节点父亲之间的点之后该节点所在的连通分量。
• 一种树：一条链。
• 第二种树：菊花。
• 二叉树binary tree：每个节点最多有两个子节点的有根树。
• 左儿子：左边的儿子。
• 右儿子：右边的儿子。
• 真二叉树proper：每个点要么有2个儿子，要么有0个儿子。
• 满二叉树：对于每一层都有2^x个节点。
• 完全二叉树：除了最后一层以外都是满的，最后一排左对齐
• 树的存储方法：vector < int> childs[n]; int father[n];
• 或者使用邻接表。

字符串:

字符组成的序列

• 布鲁特·福斯算法的最坏时间复杂度为$O(nm)$。
• 哈希算法的最坏时间复杂度为$O(n+m)$。
• 克努斯-莫里斯-普拉特算法的最坏时间复杂度为$O(n+m)$
• 阿霍-科拉斯克算法可以用来解决多串匹配问题。

字符串匹配

单串匹配：

一个模式串a，一个待匹配串p，找到a的字串与p相等。
暴力算法：
取a每个位置比较
设a长度n，b长度m，平均复杂度o（n）
Best O (n) worst 0(n*m)
哈希：string->int
对应关系
n+m，有一定概率出错。
* KMP克努特.莫里斯.普拉特算法：a的第i个前缀等于最长的后缀的长度。*

Next [1] = 0;
…cpp
// O (n)
For (int I = 2; i<=m; i++)
{
   Int t = next [i-1];
   While (t && a[t]! = a [t-1]) t = next[t];
   Next [i] = t+ (a[t] == a [i-1]);
}

多串匹配：

一堆串a，一个串p。

AC自动机：种类：有限状态自动机：1.字符集2.状态集3.转移集

• 首先，建立一个trie树。在树上预处理出fail(即kmp中的fail)BFS,将第二层的节点的f-ail全部练到root上，假设当前点为x，数值是c ，往上寻找fail（x的父亲），若fail没有为c的儿子，那么再找fail【fail (x的父亲)】-直到为root

哈希值

哈希算法将任意长度的二进制值映射为固定长度的较小二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上来说基本上是不可能的。
消息身份验证代码 (MAC)哈希函数通常与数字签名一起用于对数据进行签名，而消息检测代码 (MDC) 哈希函数则用于数据完整性

哈希算法

哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。哈希值是一段数据唯一且极其紧凑的数值表示形式。如果散列一段明文而且哪怕只更改该段落的一个字母，随后的哈希都将产生不同的值。要找到散列为同一个值的两个不同的输入，在计算上是不可能的，所以数据的哈希值可以检验数据的完整性。一般用于快速查找和加密算法

数据结构

堆 heap

• 最小堆维护数的集合，通常支持插入元素、查询最小元素、删除最小元素、减小一个元素操作
• 功能：inser, getmin, delete, decreasekey
• 分类：二叉堆，二项堆， fib堆O（logn）
  fib堆 除了deletemin 都是O（1）
  二项堆merge 0(logn); fib 堆merge O(1)
  二叉堆：一个完全二叉树，满足堆的性质；每个节点的值不大于它的儿子的值。

• 最小堆最简单的实现是二叉堆，这种实现在上述各种操作的时间复杂度均为$O(\log n)。

• 对于$n$个数，建立二叉堆的时间复杂度为$O(n)$。

线段树

• 线段树维护一个序列，基本的线段树支持修改一个元素、区间求和操作，通过打标记，还可以支持区间修改操作，各操作的时间复杂度均为$O(\log n)$。

树状数组

• 树状数组维护一个序列，支持修改一个元素、求前缀和操作，各操作的时间复杂度均为$O(\log n)$。

while(x<=n)T[x]+=val, x+=x & -x//修改
while(x) ret+=t[x], x-=x&-x//求值

跑得比线段树还快。。。

分块思想：在各种范围都很好用

• 对询问分块

图论（2）

假定所有节点的编号都是1-n，边编号1-n；
tarjan

强连通分量：极大的强连通子图。

dfn[x]//一个节点在Dfs时访问到的程序
low[x]某种最小值
tarjan主要基于dfs

dfn[x]=low[x]=++index;
s.push(x);
instack[x]=ture;
for each edge(x,y)
   if[!dfn(y)];
{
   dfs(y);
   low(y)=min(low(x),low(y));
   {
       else if instack(y)
       low(x)=min(low(x),low(y));
    }
}
  if [dfn(x)]==[low)(x)];
{
    while (1)
    {
        t=s.pop(); instack(x)=false;
        if(t==x)break;
    }
}

• 割点：删掉该点后，图不连通
• 桥：一条边删去后图不连通
• 双连通分量：任意两点存在两条路径，且序列不相交。
• 点双连通：任意两点间存在两条路径，且节点序列不相交。
• 边双连通：边序列不相交

dfs(u,fa);
{
    dfn(u)=low(u)=++index;
    int n=ch=0
    dfn(v,u)
    low(u)=min(low[v],low[u])
    if(low[v]==dfn[v]) bridges.push_back(u,v);
    if(low[v]==dfn[u]) is_ap(u)=1;++_ch;
    elsse if(a!=NULL && v!=f[a])
    {
        low[u]=min(low[u]////)
    }
}

错误程序

最短路

简单最短路：不重复的边
无负权边：不可能出现重复的边

Dijkstra算法的特点是：图上不能含有负权边、适合在稠密图上运行

• 堆优化Dijkstra算法的特点是：图上不能含有负权边、适合在稀疏图上运行。

• Bellman-Ford算法的特点是：能够检测负权环。

  • Bellman-Ford求单源最短路 O(nm)
    详见：http://blog.csdn.net/niushuai666/article/details/6791765

• Floyd算法的特点是：能求出所有点对间最短路、代码简短且常数小、适合在稠密图上运行。

  • floyd:求多源最短路（最短路不存在或两点之间不可达：无法求得）
  • f[k][x][y]:通过1~k的点从x~y的最短路
    但在循环时我们只用到了k和k-1的值，所以三维数组是可以省略的。在循环k=n~1时，覆盖之前数据就可以了。
    时间O(n^3)；空间O(n^2)

• SPFA（实际上不存在）

• LLL，详见：http://www.doc88.com/p-09216406008.html
• Dijkstra:求单源最短路 m+nlsgn

最小生成树

边权最小的生成树

• Prim算法的特点是：适合在稠密图上运行。邻接矩阵:O(v2)
  邻接表:O(elog2v)
  详见：http://www.61mon.com/index.php/archives/199/
• Kruskal算法的特点是： 适合在稀疏图上运行。O（elog2e）
  算法详见：http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html
• 堆优化Prim算法的特点是：代码复杂、实际上不常用。
• 启发式合并：每一次把较小的集合往较大的集合里合并。
• 子图
• 有根树：没有儿子的节点
• 无根树

动态规划

状态（f的值） 转移 决策（决定） 后交叉性 搜索

递堆

递归：

多个函数互相调动

DP

search
DAG:youxiangwuhuan

背包问题

空间复杂度可以优化到O(V)。普通O(N*V)。

完全背包问题

物体有一个变为无限个。
* 详见：https://baike.so.com/doc/5989126-6202093.html

剪枝

数位DP

素数

0和1除外，只能被1和它本身整除的数叫素数

• log log n
• 埃氏筛法
• 质因数分解
• 最大公约数
• 费马小定理

数据结构 图论

并查集 log n

RMQ

LCA

仙人掌：一棵树，可加。。。边，不相交。

排序

• 快速排序 (稳定)
  一个序列中随便找一个数，大于它放右边，小于它放左边，自己放中间。
• 堆排序 （n log n 不一定）

这是一段经典的Pascal写的快速排序代码。

虽然这个语言已经快被我们遗忘了，但是经典就是经典。

    procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;