Hey
注意数据范围是否需要开longlong每日一算法备战蓝桥杯。
memset 只能设置0和-1
1. DFS(深度优先搜索算法)
深度优先搜索的步骤分为 1.递归下去 2.回溯上来。顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。这里称之为递归下去。
2024-03-16
在实际的操作中，我们一般对深度优先搜索问题进行分类：
- 定义的DFS：对图的连通性进行测试，典型的问题：迷宫连通性测试、图的条件搜索等
- 广义的DFS–DFS思路的应用：DFS搜索顺序+规则问题、穷举结果寻求最优解/符合条件解等等，由于其穷举答案的本质，又被称为爆搜
function dfs(当前状态, 一系列其他的状态量){
if(当前状态 == 目的状态){
···
}
for(···寻找新状态){
if(状态合法){
vis[访问该点]；
dfs(新状态);
?是否需要恢复现场->vis[恢复访问]
}
}
if(找不到新状态){
是否需要创建新规则？{
创建并对当前状态进行访问vis;
继续搜索;
恢复现场/恢复访问vis;
}
}
}
2. 回溯
「回溯是递归的副产品，只要有递归就会有回溯」，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。 回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。
2024-03-19
回溯算法能解决如下问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 棋盘问题：N皇后，解数独等等
3. BFS(广度优先搜索算法)
广度优先搜索较之深度优先搜索之不同在于，深度优先搜索旨在不管有多少条岔路，先一条路走到底，不成功就返回上一个路口然后就选择下一条岔路，而广度优先搜索旨在面临一个路口时，把所有的岔路口都记下来，然后选择其中一个进入，然后将它的分路情况记录下来，然后再返回来进入另外一个岔路，并重复这样的操作。
2024-03-20
广度优先搜索的优点：
-
可以寻找记录最短路径
-
不会爆栈
深度优先搜索的优点：
-
代码短
-
对于内存消耗小（不需要开队列）
struct Node
{
int x,y,d;
};
int w[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
bool st[N][N];
queue<Node> q;
void bfs()
{
q.push({0,0,0});
st[0][0]=true;
while(q.size())
{
auto t=q.front();
q.pop();
for(int i=0;i<4;i++)
{
int xx=dx[i]+t.x,yy=dy[i]+t.y;
if(xx<0||xx>=n||yy<0||yy>=m) continue;
if(st[xx][yy]) continue;
if(w[xx][yy]=='.') continue;
if(xx==n-1&&yy==m-1)
{
res=t.d+1;
return ;
}
st[xx][yy]=true;
q.push({xx,yy,t.d+1});
}
}
}
4. Flood Fill（洪水灌溉算法）
可以在线性的时间复杂内，找到某个点所在的连通块！ 从一个起始节点开始把附近与其连通的节点提取出或填充成不同颜色颜色，直到封闭区域内的所有节点都被处理过为止，是从一个区域中提取若干个连通的点与其他相邻区域区分开(或分别染成不同颜色)的经典算法。
2024-03-20
洪水填充算法实现最常见有四邻域填充法(不考虑对角线方向的节点)，八邻域填充法(考虑对角线方向的节点)，基于扫描线填充方法。
void dfs(int x,int y)
{
int t=g[x][y];
g[x][y]=-2;
//t有值的话就是灌溉到边界了
if(t) return ;
for(int i=x-1;i<=x+1;i++)
for(int j=y-1;j<=y+1;j++)
if(i>=0&&i<n&&j>=0&&j<n&&g[i][j]>=0)
dfs(i,j);
}
5. 并查集
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题（即所谓的并、查）。
时间复杂度：O(1)
2024-03-21
并查集是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：
- 合并（Union）：把两个不相交的集合合并为一个集合。
- 查询（Find）：查询两个元素是否在同一个集合中。
//同时实现并查操作
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
6. 哈希
简单来说就是把任意输入 通过特定方式（hash函数）处理后 生成一个值。这个值等同于存放数据的地址，这个地址里面再吧输入的数据进行存储。
这个hash函数又叫散列函数，会有一些常用的构造散列函数的方法，但是处理结果值可能相同，那就叫冲突，冲突也有常用的冲突常用的冲突解决方法。
时间复杂度：O(1)
2024-03-24
unordered_set(无序集合)
unordered_map(无序映射)
7. 单调队列&&单调栈
单调队列主要是为了求滑动窗口最大/最小值
单调队列是双端队列（首尾两边都可以append和pop）。具体而言，我们会在单调队列的队尾pop和append，会在队首pop 单调栈主要用来求每一个当前数左右最近的比他小/大的数
时间复杂度：O(n)
2024-03-24
//单调队列
//b数字为前k个数中最大的数
int q[N];
int hh=0,tt=-1;
for(int i=0;i<tot;i++)
{
if(hh<=tt&&q[hh]<=i-k) hh++;//队首元素出滑动窗口
while(hh<=tt&&a[q[tt]]<=a[i]) tt--;//从队尾去除比当前值小的数
q[++tt]=i;
b[i]=a[q[hh]];
}
//单调栈
//输出左边第一个比他小的数
int stk[N];
int top=0;
for(int i=1;i<=n;i++)
{
while(top&&stk[top]>=w[i]) top--;
if(top>0) cout<<stk[top]<<' ';
else cout<<"-1"<<' ';
stk[++top]=w[i];
}
8. 树状数组
树状数组也是很多最简洁优美的数据结构之一。最简单的树状数组支持两种操作
单点修改：更改数组中一个元素的值
区间查询：查询一个区间内所有元素的和
时间复杂度：O(logn)
2024-03-25
//找到二进制最后一个非1的位置
int lowbit(int x)
{
return x&-x;
}
//x位置加v，其父节点也加
void add(int x,int v)
{
for(int i=x;i<N;i+=lowbit(i))
tr[i]+=v;
}
//查询x处的值 (前缀和)
int query(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i))
res+=tr[i];
return res;
}
可以计算前缀和也可以计算当前值，只需在add时加入的是差分数组AcWing242.一个简单的整数https://www.acwing.com/problem/content/248/
9. 状态压缩DP
二进制表示状态：每一个数都应该对应集合的一种状态，并且每个数的状态都是不同的
时间复杂度：O(n(1«n)…)
2024-03-27
会遍历所有的状态（二进制表示的状态），所以n要较小的时候才可以用
- 旅行商问题
- NP问题
f[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int a=0;a<1<<n;a++)
{
//本行内不冲突
if(a&(a<<1)||a&(a>>1)) continue;
for(int b=0;b<1<<n;b++)
{
//与上一行不冲突
if(a&b||a&(b<<1)||a&(b>>1)) continue;
int t=get_count(a);
for(int j=t;j<=k;j++)
f[i][a][j]+=f[i-1][b][j-t];
}
}
9. 线性DP
线性DP是动态规划问题中的一类问题，指状态之间有线性关系的动态规划问题。
2024-03-30
//最长上升子序列长度
for(int i=0;i<n;i++)
{
f[i]=1;
for(int j=0;j<i;j++)
if(w[j]<w[i])
f[i]=max(f[i],f[j]+1);
res=max(res,f[i]);
}
10. 背包DP
背包问题是一种组合优化的NP完全问题（NP-Complete，NPC）。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。
NPC问题是没有多项式时间复杂度的解法的，但是利用动态规划，我们可以以伪多项式时间复杂度求解背包问题。
2024-03-31
一般来讲，背包问题有以下几种分类：
- 01背包问题
- 完全背包问题
- 多重背包问题
- 二维费用背包问题
// 01背包问题伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
for j = W,...,w[i] // 必须逆向枚举!!!
dp[j] = max(dp[j], dp[j−w[i]]+v[i])
// 完全背包问题伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
for j = w[i],...,W // 必须正向枚举!!!
dp[j] = max(dp[j], dp[j−w[i]]+v[i])
// 完全背包问题伪代码(空间优化版)
dp[0,...,W] = 0
for i = 1,...,N
for j = W,...,w[i] // 必须逆向枚举!!!
for k = [0, 1,..., min(n[i], j/w[i])]
dp[j] = max(dp[j], dp[j−k*w[i]]+k*v[i])
//二维费用的背包问题
for(int i=0;i<n;i++)
{
int v,m,w;
cin>>v>>m>>w;
for(int j=V;j>=v;j--)
for(int k=M;k>=m;k--)
f[j][k]=max(f[j][k],f[j-v][k-m]+w);
}
11. 区间DP
区间dp，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案。
2024-04-02
for(int len=2;len<n;len++)
for(int i=0;i+len-1<n;i++)
{
int j=i+len-1;
for(int k=i+1;k<=j-1;k++)
f[i][j]=max(f[i][j],f[i][k]+f[k][j]+w[i]*w[k]*w[j]);
}
12. 树形DP
树形DP准确的说是一种DP的思想，将DP建立在树状结构的基础上。整体的思路大致就是用树形的结构存储数据。
2024-04-03
树形DP的关键和实现方法是dfs。
先找到树根，从树根开始运用dfs递归，跟dfs一样先初始化，然后递归到叶子节点上为止，把最底层的f[i][j]更新完毕，再回来往上走，自底向上地根据题意更新上层的f数组，最后输出答案即可
//确定父子节点关系
void dfs(int u)
{
f[u][1]=w[u];
for(auto x:bian[u])
{
dfs(x);
f[u][0]+=max(f[x][1],f[x][0]);
f[u][1]+=f[x][0];
}
}
//未确定父子节点关系
int dfs(int u,int father)
{
f[u]=w[u];
for(auto x:bian[u])
{
if(x!=father)
{
dfs(x,u);
f[u]+=max((ll)0,f[x]);
}
}
}
