最小生成树
最小生成树最小生成包含两种算法
Prim O(n ^ 2)
Kruskal O(mlogm)
Prim主要分为两种朴素版Prim，堆优化版Prim
朴素版Prim时间复杂度是O(n ^ 2)
堆优化版代码过于复杂建议使用Kruskal
流程
初始化d数组为正无穷
d[1] = 0
for循环迭代n次，找到集合外距离集合最近的点t，然后用t来更新每一个点到起点的距离
最终将t放入到st集合中
int prim() { memset(d,0x3f,sizeof(d)); int res = 0; for(int i = 0;i < n;i++) { int t = -1; for(int j = 1;j <= n;j++) { if(!st[j] && (t == -1 || d[t] > d[j])) { t = j; } } //如果出现自 ...
最短路
最短路最短路
单元最短路
边权都是正数
朴素的Dijkstra -> O(n ^ 2)
heap + Dikstra -> O(m * logm)
边权都是负数
Bellman-Ford -> O(nm)
SPFA 一般O(m)，最坏的情况O(nm)
多元最短路
多源汇最短路 Floyed -> O(n ^ 3)
朴素Dijkstra思路
每一次去集合外查找距离当前点最短的点
初始化
首先我们应该初始化dis数组，使dis[1] = 0，其余的点都是正无穷
memset(dist, 0x3f, sizeof dist);dist[1] = 0;
接着我们去遍历s集合外还没有确定好最合适位置的点，判断谁是最小点
int t = -1;for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
接着对所有点点距离按照这一个点进行更新操作，将这个最小点放入到s集合当中
f ...
栈｜队列
模拟栈
栈的特性为先入后出，后入先出
如何进行模拟
根据栈的特性，我们会发现在栈弹出元素的时候弹出的都是后加入进来的
所以我们可以定义一个指针用来索引栈顶
操作流程
push元素，我们只需要将栈针向后进行移动
pop元素，只需要将指针前移
empty操作只需要判断栈针是否为0
query操作只需要打印栈针对应的元素
完整AC代码
#include <bits/stdc++.h>using namespace std;const int N = 100010;int st[N];int zz = 0;int main(){ int m,t;string op; cin >> m; while(m--) { cin >> op; if(op == "push") { cin >> t; st[++zz] = t; }else if(op == "pop ...
离散化
离散化什么事离散化？
离散化的本质是将已知序列建立新的下标索引，最终来缩小目标区间，并且可以结合二分，前缀和等算法进行额外的操作
离散化需要进行排序去重
排序：sort(alls.begin(),alls.end())
去重：alls.earse(unique(alls.begin(),alls.end()),alls.end());
unque函数实现
vector<int>::iterator unique(vector<int> &a) { int j = 0; for(int i = 0;i < a.size();i++) { if(!i || a[i] != a[i - 1]) { a[j++] = a[i]; } } return a.begin() + j;}
离散化常见题目给定一个无限长的数轴
输入一个n，执行n次操作即在x的位置上插入一个数c
输入一个m，执行m次操作，每一次操作给出两个数l和r，代表数轴的左右端点
最终打印 ...
链表
链表什么是链表?
链表是一种在存储单元上非连续、非顺序的存储结构，通过链式结构将一堆数据以链的形式进行串联，通过ne指针有效的对链表中的元素进行访问、
链表主要分为两大类
单链表
双链表
单链表
所谓单链表就是：单向链表，我们将链表中的每个元素称之为结点/节点，单链表中的每个节点是单向的，也就是说，我们无法直接获得某一结点的前面的第一个结点，即:前驱结点。
那么如何去模拟单链表呢？
在开始之前我们需要单链表需要什么？
为了方便遍历，单链表有head必不可少，其次每一个结点我们需要使用idx进行编号
接着设置数组，主要定义两个数组，一个用来存值e，另一个用来关联另一个结点ne
初始化
void init() { head = -1; idx = 0;}
主要实现的功能有以下几个
插入元素
头部插入
中间插入
删除元素
头部插入
void addHead(int x) { e[idx] = x; ne[idx] = head; head = idx++;}
在下标为k的位置插入
void add(in ...
高精度
高精度
主要是用来对超出int范围外的数字进行算数运算的一种算法
高精度 & 4
加法
减法
乘法
除法
高精度加法假如现在给两个高精度的数字A，B
首先我们需要将A的每一位存储到数组或者是集合当中，B也是同样的道理(当然这里需要反向存储，因为我们需要先去计算个位，然后判断下一位是否需要进位)
在进行加法运算的时候我们需要考虑这一位上是否有数，我们只需要加上A，B上这一位有数的值即可
第i位保留的结果为和取模操作，除以10判断下一位是否需要进位
循环结束我们需要判断t是否还有值，如果有值只需要再添加一个1代表进位操作。ex：90 + 10 当i = 2的是否t 等于1，我们需要在00的前面加上一即可
#include <bits/stdc++.h>using namespace std;vector<int> add(vector<int> &A,vector<int> &B) { vector<int> C; int i = 0,t = 0; while(i ...
一日为蒟蒻，来日方长
Coding more,Harvest more
Java基础
面向对象编程
区区C++基础
蒟蒻的第一道台阶
搭建VPS
在搭建节点的基础上，懂得各种协议的原理