2020-01-18 10:42 已编辑天津工业大学 C++

关注

2019清北学堂学习笔记

暴力求解法

迭代加深搜

适用于搜索树深度不确定的时候，可以使用迭代加深搜。

步骤：

1.枚举maxd表示最深枚举深度；
2.假设当前深度为g(n)，乐观估计至少要h(n)层才能到达叶子节点，那么g(n)+h(n)>maxd时，就应该剪枝。

在我理解看来，乐观估计的意思是说不去管所有的限制，然后去计算当前点到终点的距离或者所需要的操作数量，即还需要h(n)层，这时候的h(n)才是最好的，即最小（大）的，可以利用来剪枝。A*就是把状态乐观估计还要h(n)层才到达的想法使用到bfs上面。

双向搜索

对普通搜索的改进，使用的是BFS，大体流程就是从起点开始向终点搜，终点开始向起点搜，然后就直到第一个搜索碰到第二个或者是第二个碰到了第一个，然后答案就是两个搜索步数的和再减去1。比较典型的例题有魔板，然而那个题目一共3个变换方式，还可以不用双向搜索。

分治算法

数列上的分治

顾名思义，数列上的分治就是日常用的分治，最经典的例题就是求逆序对数量。使用的算法是归并排序，比较两个指针所对应的数字，如果左边的大于右边的，那么就说明，当前左边的指针到mid的所有数字都是大于右边指针所指的数字，那么答案就应该加上mid-l+1。

CDQ分治

可以代替数据结构的利器，可以解决的问题是区间加和单点修改。
\(\color{red}{流程：}\)
1. 按所有的按所有的操作等分分成前后两部分
2. 处理前面部分的、后面部分各自的修改和查询
3. 处理前面部分修改对后面部分查询的贡献（动态查询变成静态查询）
听老师说很好打，而且用处也很大，这个CDQ分治处理的问题需要满足离线操作和修改与修改之间互不影响。因为是把动态询问变成了静态询问，所以还可以通过分治把某些排序可以做好，更好地进行静态查询。

树分治

树的重心是指以该点为根时，最大子树节点数最小。子树节点数都<=n/2，层数也是有logn层，每一层都可以在O(n)的时间内处理问题。

贪心算法题目选讲

贪心，我的理解就是就当前状态来看，所选取的最优决策，但是不一定会是全局最优决策，所以很多题目看似是贪心，但是贪心并不正确，只能看直觉，毕竟证明很麻烦。典型例题是铺设道路（积木大赛），就是在当前点时，对比上一个点，如果比上一点大，那么加上多出的一部分，反之，就是continue，然后更新last为当前点的大小，last初值为0.

简单数学

欧几里得算法

可以求出变量a,b的最大公约数。

\(gcd\)代码：

int gcd(int a, int b){
return b == 0? a : gcd(b, a % b);
}

扩展欧几里得算法

可以求解类似于\(ax+by=c\)的不定方程，有整数解的条件是\(gcd(a,b)|c\)，即是在说\(gcd(a,b)\)必须是\(c\)的因子。

\(exgcd\)代码：

void gcd(int a, int b, int &g, int &x, int &y){
if (!b) {g = a; x = 1; y = 0;}
else{gcd(b, a % b, d, y, x); y -= x * (a / b);}
}

式子推导如下：
\(ax+by=gcd(a,b)\)
\(b \times x+(a- a/b \times b) \times y=gcd\)
\(y \times a+(x-y\times a/b)\times b = gcd\)

线性筛素数

学习过三种筛法，第一种，也是最耗费时间的就是，从2开始向n-1枚举，对其稍加优化就是枚举到，但是根本不会满足需求。于是就有了埃式筛，时间复杂度可以做到O(nlognlogn),可以说是很接近线性了，但是又不是真正的线性筛，所以还需要优化。欧拉筛成功的做到了线性筛的要求，在O(n)的时间内筛出素数。

埃式筛代码：

for(int i=2;i<=t;i++)
if(prime[i])
for(int j=2 * i;j<MAXN , j += i)
        prime[j]=false;

欧拉筛代码：

for(int i=2; i<=n; i++){
    if(!vis[i]) prime[cnt++]=i; 
    for(int j = 0; j < cnt && i * prime[j] <= n; j++){ 
        vis[i * prime[j]]=prime[j]; 
        if(i % prime[j] == 0) break;
    } 
}

逆元

我理解的逆元就是一个数在模p的意义下的倒数。现在也有了多种求解逆元的方法，比如费马小定理，递推式求逆元，扩展欧几里得求逆元，当然用的最多的莫过于递推式，因为很快的就能求出。
组合数
有一个公式，然后是就是围绕着它进行推导，比如等等。

数据结构

堆

堆有两种，一个是大根堆，另一个是小根堆；一个是less，另一个是greater。
头文件是

#include <queue>
priority_queue<int>q;

支持的操作有：
插入，时间复杂度为O(logn);
查询，时间复杂度为O(1);
删除，时间复杂度为O(logn).
如果卡常数的话可以使用make_heap之类的。

二叉搜索树

树高期望 \(logn\)
操作：插入，删除，查询
例如STL中的set，map

线段树

线段树可以维护区间信息的数据结构，每一个节点都对应着一个序列的区间。
可以支持单点修改或者是查询。

动态开点

合并复杂度就是两颗线段树重合线段树重合节点个数

tree *merge(int l, int r, tree *A, tree *B){
if(A == NULL) return B; 
if(B == NULL) return A; 
if(l == r) return new tree(NULL, NULL, A -> data + B -> data); 
int mid = (l + r) >> 1; 
return new tree(merge(l, mid, A -> ls, B -> ls),merge(mid + 1, r, A -> rs, B -> rs), A -> data + B -> data); 
}

树状数组

一个十分好用的数据结构，其重点就是lowbit函数。只能维护满足可减性的量，例如和，异或和，而与，或不能用树状数组维护。线段树包括了树状数组，但是树状数组常数小。

二维树状数组

与一维树状数组类似，只是多了一层循环。令s[x][y]表示x-lowbit(x)+1<=i<=x, y-lowbit(y)+1<=j<=y的a[i][j]的和

并查集

按秩合并+路径压缩可以证明复杂度是对的，但是也可以只写路径压缩，是卡不掉的。

例题就是洛谷P1525关押罪犯。第一个做法是二分+二分图匹配，第二个做法是并查集。

Trie

代码：

//trie树，字母集
int rt=1,cnt=1;
int ch[N][26];
void insert(strint s) {
        int o=rt;
for(re int i = 0 ; i <s.size;++i) {
int k=s[i]-’a’;
if(ch[o][k]) o=ch[o][k];
else ++cnt,o=ch[o][k]=cnt;
}
sz[o]++;
}
int query(string s) {
int o=rt;
for(re int i = 0 ; i <s.size ; ++ i ) {
int k=s[i]-’a’;
if(ch[o][k]) o=ch[o][k];
else return 0;
}
return size[o];
}

Trie树还是蛮重要的，数也可以上trie树，但是需要变成二进制，这样的话在一个序列中寻求两个数的异或最大值就变得很容易求出来。比如说是异或最大值，我们让每一个数字都拆分为二进制，然后上trie树，总是选取1，如果没有1再去选取0，这样最后出来的数字就是最大的异或值。原理就是1000，总是会比0100好，更加优，所以一直选取1，没有1再取0.

Hash

19260817是一个常用的mod数，素数。

Hash碰撞

本来不相同的两个数可以在某一个数的时候会相同，被称为hash碰撞。为了避免可以使用map映射或者双模数。还有一个方法就是自然溢出，自然溢出加上双hash还会更好，不容易被卡。

RMQ问题

对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在[i,j]里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。
St表
令f[i][j]表示从i开始，2^j个数的最小值
f[i][j]总共有nlogn个状态
可以由j从小到大递推求出
静态查询最好使用ST表，这样的复杂度是最优的。
递推式为

f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);

求LCA

1.倍增求LCA

\(\color{red}{步骤：}\)

1.先使两个结点跳到同一深度。
2.如果两个结点相等了，那直接返回这个结点
3.否则两个结点一起跳到LCA的子结点位置
4.返回这个位置的父亲，即为LCA

2. 转换为RMQ问题

\(\color{red}{步骤：}\)

1.求出树的dfs序（每个结点进入和每次回溯到的时候都记录）
2.记录每个点第一次进入时在dfs序列中的位置pos[u]
3.两个点u，v的LCA即为dfs序中[pos[u],pos[v]]（不妨设pos[u]<=pos[v]）中dep最小的结点

3. Tarjan求LCA

\(\color{red}{步骤：}\)

1.记录每个点的询问
2.dfs回溯时用并查集合并（将子结点集合并到父节点集合，以父节点为根）
3.查询lca(u,v)时假设此时u已访问，v刚访问到，那么u的并查集的根即为答案

最小生成树

Kruskal

贪心方法：将边按照边权排序，每一次都只是拿取边权最小的边，看它连接的两个点是否在一个连通块中，这里会用到并查集来维护，如果已经联通了，那么就说明会有更小的边已经连了；反之就加入，并且把两个点联通起来。

最短路径

Dijkstra算法

支持单源最短路，可以使用堆优化，复杂度为O(mlogm),但是不可以去判负环。

SPFA算法

该算法可以判负环，但是日常还是不要用，因为复杂度是错误的。

判负环的方法：

1.用len[u]表示源点到u的最短路中有几条边。
2.在更新最短路长度的时候顺便求出。
3.显然如果没有负环，len [u]<n
4.每一次顶点入队时都要进行check，如果len[u]>=n，则负环存在

Floyed算法

适用于多源最短路,直接三重循环枚举，利用中转站来使得两个点的距离变小。由于比较暴力而且复杂度是O(n^3)所以一般也不会用到。但是该算法也是一种思想，也会用到其他的题目。

建图技巧

通过添加虚拟点等手段将问题转化，从而达到减少边数等目的。

拓扑排序

给定一张有向图，要求输出一个序列，输出是要满足：如果图中u到v有一张有一条有向边，那么序列v在u的后面。如果该序列存在的话，那么就说明一定没有环，因为如果有环的话就不会有入度为0的边。

连通分量

在图中：顶点之间有路径一定互相到达。可以用并查集维护一个连通分量。
可以使用Tarjan算法在O(n+m)的时间内求出。

Tarjan算法

记录两个数组，一个表示没个点被访问的时间，另一个记录搜索树子树的点能访问的点DFN的最小值。

缩点

在图中，由于有强连通分量，并且在强连通分量中的点也都可以很容易的到达，所以我们可以把强连通分量看作为一个点，这样会比较好处理。

差分约束

直观的看，差分约束就是几个不等式，通过不断的相加来获得一个最终的形如x+y<=a的形式，a是一个常数，来获得最大值。我们想要求的最大值，可以通过图论跑最短路来求的。实际上就是x到y的最短路。
\(\color{red}{步骤：}\)
1.将形式转化为xi-xj<=ci的形式
2.对于每一个不等式都是从xj向xi来那一条长为ci的边
3.求出s到t的最短路
如果图中有负环，那么就不存在解；
S到t没有约束，即不能到达，所以是无限大。

环套树/基环树

其实就是树上加上了一条边。
步骤：
1.随意找一个点开始当成树进行dfs，并记录每个结点访问的时间戳dfn
2.dfs的过程中一定会有一个点往dfn比自己小的点连了边，那么这条边可以看成加上的那条。记录下这条边(u,v)
3.暴力让u和v往上爬到根，记录他们分别经过的点。
4.深度最大的他们都经过的点为他们的lca，u->lca之间的所有点+v->lca之间的所有点即构成环。

欧拉图

通过图中所有边一次且仅一次行遍所有顶点的通路称为欧拉通路。
通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路。
具有欧拉回路的图称为欧拉图。
具有欧拉通路的图称为半欧拉图。

圈套圈算法

dfs搜索，不能再往下走（不能重复使用一条边，但可以重复经过一个点）便回溯，回溯时记录路径，回溯时不清除对边的标记，最后求出来的路径就是欧拉回路。

DP

状态与记忆化搜索

状态的本质就是问题的子问题。不论是搜索还是DP都需要设计问题的状态，设计出了状态，就可以找出状态与状态之间的关系，然后再进行推导，状态之间的转移就是状态之间的联系，一般地DP是递推式的形式。状态需要保证无后效性和最优子结构。
动态规划和记忆化搜索都做到了每一个状态只会计算一遍，去掉了冗余计算。记忆化搜索也是搜索的一个有效的剪枝方法，复杂度多半是多项式级别的。记忆化搜索的代码比DP的代码更好理解，代码实现也容易。