A-DFS搜索

题意

给一个字符串，判断其中是否包含dfs子序列和DFS子序列。

数据范围

$T(1≤T≤100)$

$n(1≤n≤50)$

思路

直接搜。

参考代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void solve() {
    int n;cin >> n;
    string s;cin >> s;
    int f1 = 1, f2 = 1;
    int p = s.find('D');
    if (p != -1) {
        p = s.find('F', p);
        if (p != -1) {
            p = s.find('S', p);
            if (p == -1) { f1 = 0; }
        } else { f1 = 0; }
    }
    else { f1 = 0; }
    p = s.find('d');
    if (p != -1) {
        p = s.find('f', p);
        if (p != -1) {
            p = s.find('s', p);
            if (p == -1) { f2 = 0; }
        } else { f2 = 0; }
    }
    else { f2 = 0; }
    cout << f1 << " " << f2 << endl;
}

B-关鸡

题意

线段树(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最短，再去寻找中转点…而且每次取最小值最小的+最小的肯定得最小的（有一点贪心的感觉）。