线段树(segment tree)

线段树主要用于维护区间信息，与传统的树状数组相比，可以实现O(log n)的区间修改，还可以同时支持多种操作(加、乘)，更具通用性。

1.1图的定义

上课讲过一大堆这里不再赘述，直接学习代码实现。

1.2图的存储

例图展示：

graph LR
v1((v1))--4-->v2((v2))
v1((v1))--9-->v6((v6))
v3((v3))--19-->v2((v2))
v3((v3))--22-->v1((v1))
v4((v4))--17-->v3((v3))
v5((v5))--29-->v8((v8))
v6((v6))--12-->v1((v1))
v6((v6))--9-->v5((v5))
v6((v6))--4-->v7((v7))
v7((v7))--25-->v4((v4))
v8((v8))--7-->v7((v7))
v8((v8))--11-->v3((v3))

设n个点，m条边

上图的数据（按照 起点-终点-权值）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

8 12
5 8 29
6 1 12
8 3 11
1 2 4
3 1 22
4 3 17
7 4 25
6 5 9
8 7 7
1 6 9
3 2 19
6 7 4

邻接矩阵

• 遍历效率低、不能存重边、初始化效率低初始化O(n^2)时间，建图O(m)时间、空间开销大O(n^2)
• 对于稀疏图来说大部分是INF，空间利用效率也不高

前向星

前向星涉及排序，所以其时间复杂度和排序算法有关，一般情况下时间复杂度为O(mlog m)，空间上需要两个数组（记录边的边数组、记录各点在边数组中起始位置的head数组），空间复杂度为O(m+n)

拓扑排序

前提：拓扑排序是对有向无环图来说的，无向图、有环图都不存在拓扑排序。

拓扑排序是将图G中的所有顶点排成一个线性序列，使得对于任意一堆有边顶点<u, v>，在线性序列中，u都出现在v之前。

拓扑排序可以反应某种方案是否是切实可行的。

字符串匹配算法

暴力做法(BF)

简称BF(Brute Force)算法。

没什么好说的，就是看到描述直接能想到的朴素做法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

vector<int> BF_match(string s, string p) {
    // s是主串，p是模式串
    int n = s.size(), m = p.size();
    vector<int> res;
    for (int i = 0; i <= n - m; i++) {
        int j = 0;
        for (; j < m; j++) {
            if (s[i + j] != p[j]) break;
        }
        if (j == m) res.push_back(i);
    }
    return res;
}

BF算法的时间复杂度不稳定。匹配成功时，最好为O(n)，最差为O(mn)；匹配失败时，最好为最好为O(n)，最差为O(mn)。平均时间复杂度为O(n)。

思维先行

我们要找某点到某点的最短路径(记为点u到点v)，这样的路径只能从两种路径中选择——

1. u和v之间有边连接时，存在边(u, v)，不存在的话可以视作这两点的距离无限大
2. u和v可以通过某些点中转相连，这个(最短的)中转路径

很明显，我们选最短路径肯定是在这两种路径当中选最短的来作为u和v的最短距离，而路径选择2又可以不断拆分，比如我们有u -> P -> v我们再去寻找这条路径的最短时，可以分为u -> P最短+P -> v最短，再去寻找中转点…而且每次取最小值最小的+最小的肯定得最小的（有一点贪心的感觉）。

有的题还没写完）咕咕咕））

NENU OJ算法2例题

这学期写算法2的思路并不都很详细，不过如果有想交流的也可以评论区或者私信，学校oj的题大多比较简单，这里的所有代码或许只保证通过学校的弱测试数据，因为其他地方OJ我还没有试过。