算法总结
蒟蒻学到的一些算法基础，本篇文章作为导航栏，将算法分为知识块记录，持续更新。。
导航
基础
时间复杂度对应数据范围
简单写题模板
常用容器
容易犯错的地方
好用的函数
数学
简单几何
各种数学公式
数论
线性代数
组合数学
博弈论
搜索
二分法
dfs、bfs
bfs扩展:双端队列、双向广搜、A*
dfs扩展:剪枝，迭代加深、双向dfs、IDA
DP
线性DP
背包问题
区间DP
状态压缩DP
数位DP
树形DP
单调队列优化DP
概率DP
数据结构
差分、前缀和
并查集
ST表
线段树、树状数组
平衡树、伸展树
数组分块、莫队
图论
拓扑排序
最小生成树
最短路
spfa求负环
差分约束
最近公共祖先
连通分量
二分图
欧拉回路和欧拉路径
字符串
字典树(Trie)
KMP
哈希字符串
AC自动机
Manacher
几何
各种配置
mybatis-plus配置
需要的依赖
12345678910111213141516171819<dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus-boot-starter</artifactId> <version>3.5.1</version></dependency><dependency> <groupId>com.baomidou</groupId> <artifactId>mybatis-plus-generator</artifactId> <version>3.5.1</version></dependency><dependency> <groupId>org.freemarker</groupId> & ...
仿百度云盘
前端部分
项目搭建
node.js版本选择16.20.0
执行npm init vite@latest front
配置如下，选择vue
安装需要的依赖
npm install @highlightjs/vue-plugin @moefe/vue-aplayer aplayer axios docx-preview dplayer element-plus highlight.js js-md5 sass sass-loader spark-md5 vue-clipboard3 vue-cookies vue-pdf-embed vue-router vue3-pdfjs xlsx --save
vite.config.js配置服务器参数
1234567891011121314151617181920212223242526272829import { fileURLToPath, URL } from 'node:url'import { defineConfig } from 'vite'impor ...
vue + springboot 图书管理系统demo
创建vue工程
安装/更新 vue
npm install -g @vue/cli
创建vue项目
vue create vue
然后选择Manually select features
用空格选择以下组件
后续配置
等vue安装完需要的依赖后执行以下命令启动vue
npm run serve
安装element-ui
npm i element-ui -S
在main.js中引入:
1234567891011import Vue from 'vue';import ElementUI from 'element-ui';import 'element-ui/lib/theme-chalk/index.css';import App from './App.vue';Vue.use(ElementUI);new Vue({ el: '#app', render: h => h(App)});
在assets文件夹中新建一个global.css用于全局设 ...
linux
常用文件管理命令
(1) ctrl c: 取消命令，并且换行
(2) ctrl u: 清空本行命令
(3) tab键：可以补全命令和文件名，如果补全不了快速按两下tab键，可以显示备选选项
(4) ls: 列出当前目录下所有文件，蓝色的是文件夹，白色的是普通文件，绿色的是可执行文件
(5) pwd: 显示当前路径
(6) cd XXX: 进入XXX目录下, cd … 返回上层目录
(7) cp XXX YYY: 将XXX文件复制成YYY，XXX和YYY可以是一个路径，比如…/dir_c/a.txt，表示上层目录下的dir_c文件夹下的文件a.txt
(8) mkdir XXX: 创建目录XXX
(9) rm XXX: 删除普通文件; rm XXX -r: 删除文件夹
(10) mv XXX YYY: 将XXX文件移动到YYY，和cp命令一样，XXX和YYY可以是一个路径；重命名也是用这个命令
(11) touch XXX: 创建一个文件
(12) cat XXX: 展示文件XXX中的内容
(13) 复制文本
windows/Linux下：Ctrl + insert，Mac下：com ...
最近公共祖先
最近公共祖先
最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 为了方便，我们记某点集S={v1,v2,.....,vn}S = \{v_1,v_2,.....,v_n\}S={v1,v2,.....,vn} 的最近公共祖先为LCA(S)。
性质
LCA(u)=u；LCA({u}) = u；LCA(u)=u；
uuu 是 vvv 的祖先，当且仅当 LCA(u,v)=u；LCA(u,v)=u；LCA(u,v)=u；
如果uuu不为vvv的祖先并且vvv不为uuu的祖先，那么u,vu,vu,v分别处于 LCA(u,v)LCA(u,v)LCA(u,v) 的两棵不同子树中；
前序遍历中， LCA(S)LCA(S)LCA(S)出现在所有SSS中元素之前，后序遍历中LCA(S)LCA(S)LCA(S)则出现在所有SSS中元素之后；
两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 LCA(A∪B)=LCA(LCA(A),LCA(B))；LCA(A\cup B) = LCA( ...
最小生成树
最小生成树
我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。
注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。
Kruskal算法
123456789101112131415161718192021222324252627282930313233343536373839404142434445struct Edge{ int a, b, w; bool operator< (const Edge &t) const { return w < t.w; }}e[N];int p[N], size[N];int find(int x){ if (p[x] != x) p[x] = find(p[x]); return p[x];}int main(){ cin >> n; for (int i = 0; i < n - 1; i ++ ) &# ...
最短路
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int>PII;const int N = 1e6 + 10;int n,m;int h[N],e[N],ne[N],w[N],idx;int dist[N];bool st[N];void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;}int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII,vector<PII>,greater&l ...