🗑️Doごみ箱2.1🐾
🐙 文章 🌠 系列 📂 分类 🏷︎ 标签 🧸 友链 🍅 关于 留言
🗑️Doごみ箱2.1🐾
/img/dodola.png

一只小菜鸡的Blog

图论基础||存储图||DFS、BFS(图论)

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 算法模板笔记

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

例图展示：

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)

阅读全文
 图论, 算法, 算法模板

拓扑排序

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里

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

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

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

阅读全文
 图论, 拓扑排序

字符串匹配问题||前缀函数+KMP+字符串哈希

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 算法模板笔记 字符串笔记

简称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)。

阅读全文
 KMP, 字符串, 算法, 哈希

最短路问题（Dijkstra + SPFA + Floyd）

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 算法模板笔记

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

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

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

阅读全文
 图论, 最短路

NENU2023学年算法2例题

DODOLA  发布于  更新于 ,  收录于  类别 在学算法的日子里 和 系列 题解记录

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

NENU OJ算法2例题

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

阅读全文
 算法, NENUOJ

【网站美化】点击特效2

DODOLA  发布于  更新于 ,  收录于  类别 关于Hugo的一些设置

增加了一个鼠标追尾的效果 QwQ

添加文件的方式参考上一篇~指路这篇

js文件：

pointerfollow.js

js 原文件来源：Canva’s Magic Mouse Effect (codepen.io)

（我有稍微改了一些样式 qwq，写在代码里了。

css文件：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

.star {
  position: fixed;
  z-index: 2;
  color: white;
  font-size: 1rem;
  animation-duration: 1500ms;
  animation-fill-mode: forwards;
  pointer-events: none;
}

@keyframes fall-1 {
  0% {
    transform: translate(0px, 0px) rotateX(45deg) rotateY(30deg) rotateZ(0deg)
      scale(0.25);
    opacity: 0;
  }

  5% {
    transform: translate(10px, -10px) rotateX(45deg) rotateY(30deg) rotateZ(
        0deg
      )
      scale(1);
    opacity: 1;
  }

  100% {
    transform: translate(25px, 200px) rotateX(180deg) rotateY(270deg) rotateZ(
        90deg
      )
      scale(1);
    opacity: 0;
  }
}

@keyframes fall-2 {
  0% {
    transform: translate(0px, 0px) rotateX(-20deg) rotateY(10deg) scale(0.25);
    opacity: 0;
  }

  10% {
    transform: translate(-10px, -5px) rotateX(-20deg) rotateY(10deg) scale(1);
    opacity: 1;
  }

  100% {
    transform: translate(-10px, 160px) rotateX(-90deg) rotateY(45deg) scale(
        0.25
      );
    opacity: 0;
  }
}

@keyframes fall-3 {
  0% {
    transform: translate(0px, 0px) rotateX(0deg) rotateY(45deg) scale(0.5);
    opacity: 0;
  }

  15% {
    transform: translate(7px, 5px) rotateX(0deg) rotateY(45deg) scale(1);
    opacity: 1;
  }

  100% {
    transform: translate(20px, 120px) rotateX(-180deg) rotateY(-90deg) scale(
        0.5
      );
    opacity: 0;
  }
}
阅读全文
 JavaScript, 美化, CSS, 光标