@ivorysi 2017-09-17T00:01:00.000000Z 字数 9900 阅读 697

松爷集训笔记

`笔记` `集训`

第一天

Sort（1）

选择排序，每次选择它最小的数放到最左边
插入排序，在一个有序的序列中找到某个数的位置
冒泡排序，每次比较并交换相邻两个元素，最大的元素会到最优
这三个都是 $O(n^2)$
归并排序是 $O(n \log n)$
基数排序，把int拆成一段一段，进行桶排序或计数排序

数据结构1

vector 插入删除，均摊 $O(1)$ 如果这个数组满了就乘2，小于 $\frac{1}{2}$ 就除2
link 双向链表，插入删除都是 $O(1)$ 的，链表不能按下标访问，访问会变成 $O(n)$
queue 先进先出FIFO，getmax维护一个单调递减的序列
stack 后进先出LIFO，插入后从栈顶一个一个删除，先进入不一定后出来，可以一个元素进栈然后马上出来，getmax维护每一个进入的数都和另一栈顶维护一个max
两个栈可以做一个deque

第二天

图论（1）

DFS

Depth-First Search
深度优先搜索
遍历一张图 fraversal(遍历)

dfs(u) {
    visited[u]=true;
    for each edge(u,v)
        if(!visited[v]) dfs(v);
}

最坏时间复杂度: $O(n+m)$ （假如有1个点和 $10^6$ 个自环）
空间复杂度 $O(n)$

树的深搜

可以求儿子，父亲，子树大小，结点深度

DFS序列

进入栈的时候记录
或者进栈和出栈都记录
可以记结点可以记边可以都记
长度为 $O(n)$

        a
     /    \
   b       f
/  |  \     \  
c  e  d      g
   |
   h

abcehdfg
每个子树都在一段连续序列里
证明：因为只有访问完这个结点所有后代才会回到父亲去遍历别的结点

BFS

Breadth-first search

        a
     /    \
   b       f
/  |  \     \  
c  e  d      g
   |
   h

进行BFS

BFS序列

abfcedgh
序列中每个结点的深度是严格单调的
实现需要一个队列
在入队的时候就标记它已经访问过
时间复杂度最坏 $O(n+m)$
空间复杂度: $O(n)$

树的宽搜

结点的深度，父亲，儿子

树的深搜和宽搜序列

在深搜宽搜序列中，儿子一定在父亲的后面出现

二叉树的DFS

先序遍历

根->左儿子->右儿子

dfs(u) {
    printf(u);
    dfs(lch[u]);
    dfs(rch[u]);
}

中序遍历

左儿子->根->右儿子

dfs(u) {
    dfs(lch[u]);
    printf(u);
    dfs(rch[u]);
}

后序遍历

左儿子->右儿子->根

dfs(u) {
    dfs(lch[u]);
    dfs(rch[u]);
    printf(u);
}

倒过来后就是左儿子右儿子交换后的前序遍历

已知三个序列还原二叉树

前序遍历&中序遍历和后序遍历&中序遍历都能还原唯一的一颗二叉树
前序遍历&后序遍历可以还原唯一个一棵真二叉树，还原二叉树的话会有多一些情况

二分图（Bipartite Graph）

定义

存在一种方案点分为两个集合V1 V2，两个集合包含所有的点
边都是V1连向V2

性质

1.不存在奇数条边构成的环

判断是否存在

染色，一个点染成一种颜色，与它相邻的点染成不同的颜色，如果有个点已经被染上色了，那么就不存在，如果都染完了，就存在
染色成功跟没有奇环等价

拓扑排序

i-j有边，则j依赖于i
i-j有路径，则j间接依赖于i
拓扑排序：输出一个序列，使排在前面的点不依赖于排在后面的点

q=new queue();
for(int i=0;i<n;++i) if(in-deg[i]==0)q.push(i);
ans=new vector();
while(!q.empty()) {
    u=q.pop();
    ans.push_back(u);
    for each edge(u,v) if(--in-deg[i]==0)q.push(v);
}
if(ans.size()==n) printf(ans);else printf("QAQ");

①代码能跑出来拓扑排序
②这张图存在一个拓扑排序的方案 ①->②
③它是DAG （有环必定互相依赖）②->③
③->① 考虑k个点DAG，找到第一个入度为0的点，剩下k-1个点都是DAG，一个点有拓扑排序
所以三种情况是等价的

有向无环图 Direct Acyclic Graph

在dfs树上如果有回边是不是有环
是这个显然的
在图上有环（非自环）是不是dfs树上一定有回边，为什么一定会搜到一个环
证明：搜到环上的第一个点，环上剩下的都在它的子树里，搜到最后一个点会产生一个回边

字符串

char[]
std::string

字符串函数

<cstdio>
<cstring>

$man 函数名
strlen(char *s)返回字符串长度
printf
scanf
sscanf(char *s,"%",&)
sprintf(char *s,"%",&)
strcmp(char *str1,char *str2) 若str1==str2，返回0，若str1< str2，则返回负数；
若str1>str2，则返回正数。
strcpy(char *dest,char *src) src复制到dest
strstr(char *str1,char *str2) 在str1中找str2并返回位置

C++

<string>

string.find()找子串
（1）size_t find (const string& str, size_t pos = 0) const; //查找对象--string类对象
（2）size_t find (const char* s, size_t pos = 0) const; //查找对象--字符串
（3）size_t find (const char* s, size_t pos, size_t n) const; //查找对象--字符串的前n个字符

（4）size_t find (char c, size_t pos = 0) const; //查找对象--字符

模式串匹配 string matching

单串匹配

在a串中找b，输出匹配上的位置

多串匹配

在a中找 $b_1,b_2...b_n$

单串匹配算法

暴力
最坏 $O(nm)$ ，最好 $O(n)$
设a的长度为n,b的长度为m

for(i=0;i<n-m;++i) {
    for(j=0;j<m;++j) 
        if(a[i+j]!==b[j])break;
    if(j==m) ans.push_back(i);
}

平均时间复杂度：
$O(n)$

忽然乱入的概率

买彩票p中奖，1-p不中奖
$p+(1-p)p+(1-p)^{2}p...$
$EX=p+(EX+1)(1-P)$

$EX=\frac {1}{p}$

哈希 hash

f:string->int [0,M)
独立并且随机的映射，得到两个字符串不相等单哈希值相等
A:a!=b
B:h(a)=h(b)
P(B|A)=1/m A发生了B的概率
P(B|A)=P(AB)/P(A)
P(A|B)=P(AB)/P(B)
设P(A)=x

      A     A'
B   x/m    1-x
B' x(1-1/m) 0

P(A|B)=x/m / (x/m+1-x） M变大hash会更靠谱，x变大（字符串比较增加）hash出错概率会变大

hash每个值上可以挂vector，防止冲突

KMP(Knuth-Morris-Pratt)

next[i]=
a的第i个前缀的最长的等于同长度后缀的真前缀的长度！！！

next[1]=0;
for(int i=2;i<=m;++i) {
    int t=next[i-1];
    while(t&&a[t]!=a[i-1]) t=next[t];
    next[i]=t+(a[t]==a[i-1]);
}

每次都是从t上次走到过的next[i-1]匹配，t每次至少-1，但是不会超过m，next每次加一，也不会超过m
复杂度 $O(m)$

int p=0;
for(i=0;i<n;++i) {
    while(p&&a[i]!=b[p]) p=next[p];
    if(a[i]==b[p] && ++p==m)
        ans.push_back(i-m+1),p=next[p];
}

p每次加1但不会超过n，然后p走回去每次至少减1但总次数也不会超过n

Trie树

自动机

有限状态自动机
Aho-Corasick AC自动机

第三天

数据结构2

堆 heap
维护数的集合的数据结构
insert 插入
getmin
deletemin
decreasekey 只能变小不能变大
小根堆，大根堆

二叉堆

二项堆

Fib堆（除了deletemin以外都是均摊O(1)）

二叉堆 binary heap

对于n个元素建堆
从底开始更新是 $O(n)$
一个简单的证明，对于每一个高度（从底计算），有多少大于等于这个高度的节点，等比数列求和，是不大于2n的

线段树

$O(\log n)$
包含某个节点的区间只有 $O(\log n)$
区间求和的复杂度证明：分开之后一个前缀一个后缀，前缀每层只会访问一个节点，后缀也一样，因为要么返回左儿子（右儿子）要么继续向下递归 $O(\log n)$
区间修改，打标记，不影响 $O(\log n)$ 的复杂度

什么情况下可以用线段树

a+(b+c)=(a+b)+c
为什么可以打标记m(A+B)=mA+mB
$m_1(m_2m_3)=(m_1m_2)m_3$

树状数组

while(x<=n) T[x]+=val,x+=x&-x;
while(x) ret+=T[x],x-=x&-x;

（忽然乱入）分块

把一个序列分成几块，然后对于能完全覆盖的线段是 $O(\frac {n}{T})$ 然后暴力是O(T)
$T=\sqrt{n}$ 是最小的 $O(\sqrt{n})$
可以询问很快，修改暴力
或者修改是单点的，询问时需要暴力

或者对询问分块

图论（2）

Robert E.tarjan

1、强连通分量

一个极大的强连通子图就是这个图的一个强连通分量
强连通分量可能会有多个，不会相交

dfn[x] 一个节点在dfs序列中的位置（时间戳）
low[x] 最小值

2、前向边

在dfs树上祖先指向后代

3、后向边

在dfs树上还带指向祖先

4、横叉边

由一个点走向dfs过的一个点（非自身所在的到根路径）

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

复杂度 $O(n+m)$
low只相当于yes,或no并不一定是能到达的最小时间，而是为了证明不是dfn

无向图有前向边和后向边没有横叉边

5、割点

删掉这个点之后这个图变得不连通了

6、桥

删掉这条边之后这个图变得不连通了

7、点双连通

任意两个节点间都存在两条路径，路径上的节点没有重合
没有割点和桥

8、边双连通

两个点之间的边是不相交，点的集合可以相交
有割点没有桥

dfs(u,fa) {
    dfn[u]=low[u]=++index;
    int n_ch=0;
    for each edge(u,v) {
        if(!dfn[v]) {
            dfs(v,u);
            low[u]=min(low[v],low[u]);
            if(low[v]==dfn[v]) bridges.push_back(u,v);
            if( fa!=NULL && low[v]>=dfn[u]) is_AP[u]=1;//松爷故意漏写了fa!=NULL
            ++ n_ch;
        }else if(v!=fa) {
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa==NULL && n_ch>1) is_AP[u]=1;
}

复杂度 $O(n+m)$

第四天

最短路

不存在负环的边一定不经过重复的点
因为经过重复点一定存在一个环删去环路径长度更优

Floyd

f[k][x][y] 1-k去更新x-y
f[n][x][y]即为x-y最短路
f[0][x][y]即为初始边权

f[k][x][y]=min(f[k-1][x][y],f[k-1][x][k]+f[k-1][k][y]);
空间 $O(n^3)$ 时间 $O(n^2)$

记录是从哪些点转移来的，然后递归，就可以找到一条最短路

最小环

我们更新最小环的时候只用了1-k的点，第k+1个点一定没用过
我们枚举1-k 1-k的两两点对，用i-j的最短路和i,k+1 k+1,j的边去更新这个环

Bellman-Ford

9.dist

dist[x]起点到x的长度

relax
dist[u]+w < dist[v]

while(1) {
    for each edge(u,v)
        relax(u,v);
    if(...) break;
}

时间复杂度 $O(nm)$

SPFA

q.push(S);
inq[S]=1;
while(!q.empty()) {
    u=q.pop();
    inq[u]=0;
    foreach edge(u,v)
        if(relax(u,v) && !inq[v])
            q.push(v),inq[v]=1;
}

最好是 $O(n+m)$ 上界是 $O(nm)$
一定要写inq

SLF

要是push的最短路比第一个点的最短路小，放在队列的最前

LLL

上网查

Dijkstra

暴力是 $O(n^2+m)$
二叉堆 $O((m+n)\log n)$
Fib堆 $O(m+n \log n)$

如果稠密图m很大还是用暴力比较快

H.insert(S,0);
dist[S]=0;
for(i=1;i<=n;++i) {
    u=H.delete_min();
    for each edge(u,v)
        if(relax(u,v)) 
            H.decreasekey(v,dist[v]);
}

10.最小生成树

边权和最小的生成树
对于连通的图一定存在，对于不连通的图一定不存在

kruskal

把所有边从小到大排序，如果这个两个点不连通，那么选择这条边，如果已经连通就构成了一个环，那么就不选择
证明，任何时候我们k算法选取的边集都属于这个图某一棵最小生成树，每次加一条边e，如果
e不在生成树的边集上，会产生一个环，另一条边是f，如果f>=e,f就不会在树上，如果e>=f，那么就不会被选取了，所以e==f

for edge(u,v,len) in sort(edges) {
    a=find_set(u);b=find_set(v);
    if(a!=b) merge(a,b);
}

merge可以启发式合并，每一个元素在合并时只有O(\log n)的复杂度了
那么整体复杂度就是 $O(n \log n+m \log m)$

Prim

任意选择一个点，选择一条最小的边，再在已生成的树上能到达的点选择一个最小的
因为如果不选择到达距离最小的点，那么必然有一条路径能到达那个点，那么另一个路径的点一定能比这个点更早到达，和prim算法不符

Boruvka

不要求掌握，可以了解

DP

Dynamic Programming

递推

Fib 1,1,2,3,5,8
a[i]=a[i-1]+a[i-2]
fac[i]=fac[i-1]*i
c[i][j]=c[i-1][j]+c[i][j-1]

递归

函数调用它本身或间接调用
递归要有边界条件
Fib(i)=Fib(i-1)+Fib(i)
Fib(0)=Fib(1)=1
h(1)=0;
h(x)=1+h(3x+1)/h(x/2)

状态

转移（从一个状态变成另外一个状态）

决策（在这个状态决定转移到哪一个状态）

后效性（前面的状态会对后面的状态有影响）

f[0]=a[0];f[i]=min(f[i-1],a[i]);

第五天

DP

search
找到起点和终点的一条路径

A

g(x) h(x)
f(x)=g(x)+h(x) 估值函数

A*

h<=h* 估计的距离小于等于实际的距离
满足最短路三角形不等式
八数码问题
定义h(x)为有多少个ai！=i
能比BFS更快找到最优解

记忆化搜索

处理有环的状态
1.检测一下栈中是否有这个点
2.不处理环……。。。

记忆化搜索处理dp，将出度为0的点全部指向一个点，然后从这个点开始进行记忆化搜索，然后输出栈里的东西

树上dp

求子树大小，节点权值最大值
简单路径条数（起点终点不同，同一个点也行） $size^2$
求直径（边权为1）dp（维护子树最深的点和次深的点了）
求最长路（边权为1）dp（维护子树最深的路和次深的路了）
求一个点使删掉后每个联通块点权值和最大

求一个点使删掉这个点后每个联通块最大权值的点得和最大（父亲的所在的联通块不能直接求，需要先dfs得到子树信息，需要再一遍dfs信息从上往下传）

DAG

求DAG的最短路和最长路（拓扑序）
求最短路的方案，dist[u]+w==dist[v]就累加方案
求s-t的必经点（s-x路径条数的x-t路径条数的乘积等于s-t路径条数）
求每个节点能到达多少个不同的节点（只能nm暴力，然后我们可以用int打包，这就有了一个很小的常数）

背包问题

01背包

每个物品要么装进这个背包，要么不装，使得到的V的总和最大
NPC问题
a[i]表示体积
f[1][j]=f[i-1][j] | f[i-1][j-a[i]] O(nV)
如果v不是整数那么这种做法行不通
b[i]表示价值
f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+b[i])

完全背包

for(int i=1;i<=n;++i) {
    for(int j=0;j+a[i]<V;++j) {
        f[i][j+a[i]]=max(f[i][j+a[i]],f[i][j]+b[i]);
    }
}

多重背包

把每个物品拆成 $2^1 2^2...2^{\log m_{i}}$
就是01背包乘一个log

剪枝

dfs(i,v1)
v1大于V就不是答案
全部放进去都比答案小，舍去
搜索之前排序先搜大的再搜小的
数独爆搜加剪枝

数位DP

每一位数的和加起来可以整除233
每一位数字的积大于x

第六天

数学

自然数

非负整数

整除

a|b
b=ka
b%a==0

prime number

0,1除外，只能被1和它本身整除

合数

0,1除外，不是质数的自然数

判断素数

$O(\sqrt{n})$

素数筛法

for(i=1;i<=tot;++i) {
    for(j=i;j<=n;++j) {
        f[j]=1;
    }
}

$O(n \log \log n)$
$n$ 以内质数个数 $O(\frac {n}{\log n})$
求[l,r]之内的质数 r-l<=1e6
l,r>=1e12

for(p<=1e6) {
    for(k=l/p;k<=r/p;++k) {
        f[k*p]=1;
    }
}

质因数分解

筛 $[1,\sqrt{n}]$ 的素数
$O(\frac{\sqrt {n}}{\log n})$
pollard-rho $O(n^{\frac {1}{4}})$

最大公约数

Greatest Common Divisor
$d|a$ $d|b$ 对于任何满足条件的 $d_{1}$ , $d_{1} < d$
int gcd(a,b) {return b==0?a:gcd(b,a%b);} a每次至少减少一半所以是 $O(\log n)$ 的
存在ua+vb=gcd(a,b) a-bq=r1 b-(a-bq)q2=r2
$ax= 1(\mod m)$
$a^m-1=1(\mod m)$ m是质数
$C^{m}_{n}= C^{m-1}_{n-1}+C^{m}_{n-1}$
$C^{m}_{n}= \frac {n!}{m!(n-m)!}$

图论和数据结构（3）

并查集

Disjoint-set union
Tarjan发明的，还有splay和link cut tree

make-set

find-set

merge

路径压缩，一棵树上所有的子树直接插在根上

int fa[]
int find(x) {return fa[x]==x ? x: fa[x]=find(fa[x]);}

按秩合并
小的rank往大的上合并

int rank[]
rank=max(x,y) x!=y
rank=x+1 x==y

rank实际上就是深度
只有按秩合并的复杂度是严格 $O(\log n)$
我们只要证明对于rank=i节点数一定大于等于 $2^i$

RMQ （Range Minimum Query）

查询区间最小值
暴力
线段树
分块分成根号n个，如果区间落在某个区间里我们就暴力处理
分块每次区间除二然后处理前缀后缀
如果一个区间整个落在根号n里，就再把这个小区间分成根号n个
Sparse Table 第i处开始走 $2^j$ 步， $2^j$ 大于区间一半，然后从另一端也走 $2^j$ 步。
缺点：需要 $O(n \log n)$ 的空间

LCA (Lowest Common Ancestor)

最近公共祖先
节点深度先调整一致
一个一个往上跳
f[i][j],i这个点往上跳 $2^j$ 步然后
Tarjan求lca是离线的（n+q）

LCA和RMQ

在dfs序列中找最小值可以用RMQ
dfs序列是+-1序列
然后我们可以用+-1RMQ
$O(n)$ 预处理 $O(1)$ 回答
将数组分为 $\frac{\log n}{2}$ 块
把一个序列建成笛卡尔树，变成lca问题可以+-1RMQ这样可以 $O(n)$ 预处理 $O(1)$ 回答

环套树（基环外向树）

一棵树加一条边
有n个东西，每一节点都向另外一个节点连边，如果是连通的就是环套树了
存图的方式存，存数组的方式存，
每个点向上连，根向环上另一个点

点x走y步能走到哪，把树建出来，然后除以环上的点
一个点能不能走到环（求一条非树边）
x走y步的点权值和（可重复）和第一题一样累加
x走y步的点权值和（不可重复）和第一题一样但是环走完后就不累加了

仙人掌

每条边最多属于一个简单环的简单无向连通图
最少n-1条边，最多2n-2条边（每条边都有两次）
它的一棵树被几条非树边覆盖，这些非树边覆盖的区域不相交

环

某些节点的集合

根

随便选一个点

父亲儿子

环上的所有节点到根距离最近的点就是环的父亲
环的儿子是除了父亲以外的结点
对于环的儿子父亲是这个环不是结点
每个结点只能是一个环的儿子
某个环的父亲的父亲是它到根的路径上第二个结点
结点的儿子可能是节点可能是环
环的父亲的儿子是环
在仙人掌上可以有n个结点和最多n-1个环

父亲结点

如果一个结点的父亲是环，它的父亲是从环的父亲数下来前面第一个儿子

母亲结点

如果一个结点的父亲是环，它的母亲结点是它除了父亲结点之外旁边的结点

子仙人掌

某一个结点的子仙人掌，根这个结点的所有简单路径上的边全部去掉，剩下的部分就是子仙人掌

dfs

dfs树上遇到一条非树边，就形成了一个环，然后处理环上的信息

第七天

Sort(2)

quick sort

随便找一个元素，把小于它的所有元素放到左边，大于它的所有元素放到右边，之后对左右分别处理
空间复杂度 $O(n)$
时间复杂度
最好 $O(n \log n)$
最坏 $O(n^2)$

void qsort(a,n) {
    int p=a[0];
    int l=0,r=n-1;
    while(l<r) {
        while(a[l]<p) ++l;
        while(a[r]>p) --r;
        if(l<=r) swap(a[l],a[r]),l++,r--;
    }
    if(0<r) qsort(a,r);
    if(l+1<n) qsort(a+l+1,n-l-1);
}

$T(n)=T(k)+T(n-k)+O(n)$
$T(n)=\frac {1}{n-1}\sum_{k=1}^{n-1}(T(k)+T(n-k)+O(n))$
$(n-1)T(n)=2(\sum_{k=1}^{n-1}T(k))+Cn^2+O(1)$
$nT(n+1)=2(\sum_{k=1}^{n}T(k))+C(n+1)^2+O(1)$
4-3得
$nT(n+1)-(n+1)T(n)=C(2n+1)+O(1)$
$\frac{T(n+1)}{n+1}-\frac{T(n)}{n}=O(\frac{1}{n})$
每次增加 $\frac {1}{n}$ , $n(1+\frac{1}{2}+\frac{1}{3}...)$ 是 $\log n$ 的
所以平均就是 $O(n \log n)$
快速排序不是很稳定

Heap sort

堆排序常数很大

第k大的数

用堆或线段树
还可以建一个k大的堆（k比较小）
quick select
按照快速排序那样左右分，如果k落在左边就递归左边，如果k落在右边就递归r
最坏 $O(n^2)$
最好 $O(n)$
$T(n)=T(k)+O(n)$
$T(n)=\frac {1}{n-1}\sum_{k=1}^{n-1}(T(k)+O(n))$
$(n-1)T(n)=(\sum_{k=1}^{n-1}T(k))+Cn^2+O(1)$
$nT(n+1)=(\sum_{k=1}^{n}T(k))+C(n+1)^2+O(1)$
4-3得
$nT(n+1)-nT(n)=O(n)$
$T(n+1)-T(n)=O(1)$
平均 $O(n)$
linear select
分成 $\frac {n}{Q}$ 个
把每个序列排个序
选择每个序列的中位数，再选择中位数的中位数
然后按照这个中位数进行左右划分
这个数不小于区间 $\frac {1}{4}$
$T(n·(1-\frac{Q+1}{4Q}))$
$Q=5$
$T(n)=5n+T(\frac {n}{5})+T(\frac{7}{10}n)$
$cn=5n+\frac {1}{5}cn+\frac {7}{10}cn$
$c=50$
$c=\frac{n}{Q}c+(\frac{Q+1}{4Q})c+Q$
$c(1-\frac{1}{Q}-1+\frac{Q+1}{4Q})$
$c=\frac{4Q^2}{Q-3}$ 最小的Q是6，可以取Q=5 c=50，Q=7 c=49
常数不一定有那么大