#搜索算法
搜索算法，即对当前的状态空间进行枚举，以找到对于某一问题的特殊解或最优解，这类算法被广泛应用在图遍历，寻路,算法竞赛等之中，在信息学竞赛中，搜索算法是十分重要的一类算法，通常涉及图论和组合数学等复杂问题的求解。对于大范围的枚举，又衍生出各种各样的优化算法，通过剪枝、压缩空间、双向搜索等
搜索寻路可视化
传送门1
传送门2
传送门3
网页嵌入如下
点击查看
文献
A*，Dijkstra，BFS算法性能比较及A*算法的应用
彻底理解Dijkstra算法
Dijkstra算法(一)之 C语言详解
路径规划之 A* 算法
常用距离算法详解
DFS
**DFS（Depth-First-Search）**即深度优先搜索。具体来说，DFS算法从起点开始遍历图，尽量沿着深度方向遍历下去，直到无法前进时回溯到上一个节点，继续遍历其它分支。DFS一般用于遍历或搜索一些树形结构或图结构的问题。在信息学竞赛中，DFS算法常用于解决排列、组合、路径搜索等一些组合问题，例如全排列、八皇后问题等。
BFS
BFS（Breadth-First-Search）即广度优先搜 ...
树状数组
树状数组(Binary Indexed Tree Fenwick Tree)是一种用于维护数列前缀和、区间和以及支持单点更新的数据结构。它能够在 O(logn)O(\log n)O(logn) 的时间复杂度内完成这些操作，比传统的前缀和算法更具有实用价值。树状数组也常常被用于解决数据结构中的某些问题，例如求逆序对、求数列中某一个数在排序后的排名等等。
基本思想
树状数组的核心思想是将原数列分解成若干个部分，对每一部分求出它们的和，并将这些和保存在一个数组中。数组中下标 iii 保存的是数列以第 iii 个元素结尾的、长度为 lowbit(i)lowbit(i)lowbit(i) 的区间和（其中 lowbit(i)lowbit(i)lowbit(i) 表示 iii 的最末尾的一个1所代表的数值）。这样，我们只需要利用这个数组就可以很方便地计算数列任意前缀和以及区间和了。
实现细节
初始化
构造树状数组需要两个步骤：
定义一个数组 treetreetree，用于保存树状数组的节点值。
将原始输入数组中的每个数加入到树状数组中。
123456789void init(int ...
背包问题
背包问题是一类经典的优化问题，在计算机科学中有广泛的应用。
简而言之，背包问题是在有限的背包容量内，如何最大化物品的价值和数量的问题。
具体来说，给定一组物品，每个物品有确定的重量和价值，需要选择一些物品放入背包中，使得它们的总重量不超过背包容量，同时总价值最大化。
背包问题有多种不同的变种，包括 0/1 背包、完全背包和多重背包等。
0/1背包问题
0/1背包问题是指在有限的容量下，选择某些物品放入背包，每个物品的体积和价值不尽相同，而目标是在不超过背包容量的情况下，让背包所装物品的总价值最大。其中，0/1表示每个物品只能选择装入一次或不装。
例题： 2. 01背包问题 - AcWing题库
二维解法
1234567891011121314151617181920212223242526272829#include <bits/stdc++.h>using namespace std;const int N = 10010;int n, m;int f[N][N];int v[N], w[N];int main(){ ios::s ...
最小生成树
最小生成树（Minimum Spanning Tree，简称 MST）是连接所有节点的边的集合中，权值最小的连通子图的边集合， 即一个加权连通图中，找到一棵生成树，使得所有边的权值之和最小。最小生成树的求解算法主要有两种：
Kruskal 算法
Kruskal 算法也是一种贪心算法，将所有边按照权值`从小到大排序，逐个加入到已有的边集合中，直到所有节点都被覆盖。具体步骤如下：
将所有边按照权值从小到大排序。
依次将每条边加入到已有的边集合中，如果加入该边后形成了环，则舍弃该边。
重复步骤（2），直到所有节点都被覆盖。
需要注意的是，无向图的最小生成树可能不唯一，但最小生成树的边数是固定的，即节点数减一。
时间复杂度分析
O(ElogE)或者O(ElogV)，其中E代表图中的边的数目，V代表图中的顶点数目。对图中的边按照非降序排列需要O(ElogE)的时间。排序后遍历所有的边并判断添加边是否构成环，判断添加一条边是否构成环最坏情况下需要O(logV)，关于这个复杂度等到景禹给你们谈并查集的时候再分析；因此，总的时间复杂度为O(ElogE + ElogV)，其中E ...
Cpp
未读RMQ问题与ST算法
RMQ(Range Minimum Query)问题是计算机科学中的一个经典问题，涉及到在给定数组的某个范围内查找最小值。ST(Segment Tree)算法是一种著名且高效的数据结构，可用于解决RMQ问题。
本文将介绍RMQ问题，描述ST算法，并在C++中实现它。
RMQ问题
给定一个大小为n的数组A以及两个整数i和j，使得1≤i≤j≤n，则RMQ问题是在子数组A[i，j]中查找最小元素。
暴力解决这个问题的方法是扫描给定范围内的所有元素以查找最小值。然而，这种方法需要O(n)时间复杂度。为了获得更好的时间复杂度，我们可以使用ST算法。
ST算法
ST算法是一种分治方法，它递归地将数组分成较小的段，并构建树来表示每个段的最小值。树的根节点表示整个数组的最小值，而每个叶节点表示单个元素。 ST算法的时间复杂度为O(n log n)。
预处理
首先，我们需要进行预处理。假设我们有一个大小为n的数组A，我们要构建ST树，使得每个节点表示从左到右的某个子段的最小值。以下是构建ST树的步骤：
创建一个数组tree，使它的大小为4*n。这个数组表示了ST树。
定义一个bu ...
并查集
并查集是一种用于处理集合合并和查询的数据结构，常用于连通性问题。它可以动态地添加和合并集合，并快速地查询两个元素是否在同一个集合中。 ————chatGPT
并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
合并（Union）：把两个不相交的集合合并为一个集合。
查询（Find）：查询两个元素是否在同一个集合中。
并查集的时间复杂度主要取决于查找的复杂度，因为合并的复杂度一般较小。一般而言，使用路径压缩和按秩合并的优化方法，可以使单次操作的时间复杂度达到 O(log n)。
基本代码
数据
1int fa[MAXN]; //代表节点的父节点
初始化
123456inline void init(int n){ for (int i = 1; i <= n; ++i) fa[i] = i; // 初始状态所有节点的父节点都是它自己}
关于inline函数， 看这里 （留个坑 ...
Hexo
未读Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.
Quick Start
Create a new post
1$ hexo new "My New Post"
More info: Writing
Run server
1$ hexo server
More info: Server
Generate static files
1$ hexo generate
More info: Generating
Deploy to remote sites
1$ hexo deploy
More info: Deployment
