1. 之前问题汇总
https://www.acwing.com/blog/content/39214/
2. 前缀和与差分
A. 前缀和
给定数组a[N] , S[N]。S[i]是a数组从第一个数组到第i个数字加起来的和(包括第i个)。
那么问下标为i到j(包括j,不包括i)中间所有数的和是多少，那就是S[j] - S[i]。包括j也包
括i: S[j] - S[i - 1]。不包括j不包括i: S[j - 1] - S[i]。不包括j包括i: S[j - 1] - S[i - 1]。
```
//代码：
for(int i = 1;i <= n;i ++)
S[i] = S[i - 1] + a[i];
// 不需要S数组版本:
for(int i = 1;i <= n;i ++)
a[i] += a[i - 1]; // 用a直接就可以实现求和数组
```
B. 差分
一般题目想让我们对一个区间内所有元素同时加减某一个数字，如果每次跑for循环就会时
间爆炸。我们一般自己开辟一个数组a, 如果在[l,r]这个区间内的所有元素同时加上x，我
们只需要让a[l]+x , a[r + 1] - x。然后我们对a数组进行前缀和就会发现，l前面的数字没有变化，
l到r中间的数字同时加上了x，r往后的数字也没有变化。假设前缀和数组为S，那么S就是符合题目
要求的数组和答案。如果题目给我们了原始数组，让我们对原始数组操作，那我们只需要把原始数
组元素也插入到a里就行了，这时候是比如在本来数组里x是第i个位置上的元素，我们只需要在差分数组里a[i] + x,
a[i + 1] - x就行。
```
代码:
const int N = 100;
int a[N] , arr[N]; // a是差分数组 arr是题目给的数据
int S[N]; // 差分数组的前缀和数组
void insert(int l , int r , int x) // 在l到r所有数字同时加x
{
a[l] += x , a[r + 1] -= x;
}
int main()
{
int m; // 假如有m次操作
cin >> m;
for(int i = 1;i <= n;i ++) // 先读入原始数组
cin >> arr[i];
// 将原数组数据同步到差分数组里
for(int i = 1;i <= n;i ++)
insert(i,i,arr[i]); // 在i到i区间同时加arr[i]
while(m -- )
{
int l , r , x; // 要求l到r所有元素加x
cin >> l >> r >> x;
insert(l,r,x);
}
// 最后对差分数组求和后 就是操做后的数组
for(int i = 1;i <= n;i ++)
S[i] = S[i - 1] + a[i];
return 0;
}
```
3. 并查集
并查集没什么好说的 直接上模板
int p[N];
int find(int x) // 找到x的祖宗
{
if(x != p[x]) p[x] = find(x);
return p[x];
}
初始化:
for(int i = 1;i <= n;i ++)
p[i] = i;
a和b不是一个祖宗节点的话 将b祖宗作为a祖宗:
int fa = find(a) , fb = find(b);
if(fa != fb)
p[a] = fb;
4. 哈希表
unordered_map<数据类型1,数据类型2> Mp; // 不能用int计数或者N太大了不能开数组时候用
bool st[N]; // 存在与否数组
int cnt[N]; // 一般记录某个数出现了多少次
----------------------------------------------------------------------------
unordered_map使用样例：问某个学号对应的名字叫啥
学号: int
名字: string
----------------------------------------------------------------------------
unordered_map<int,string> Map; // 第二个位置存你想知道的信息对应的数据类型
//哈希表存入
for(int i = 1;i <= n;i ++) // 假设给了n个名字和学号
{
string name;
int num;
cin >> name >> num;
Map[num] = name; // 要存的是学号对应的名字 所以下标是num
}
//哈希表查询
int num;
cin >> num;
string name = Map[num]; // num对应的名字 string类型
-------------------------------------------------------------------
5. dfs和bfs
使用dfs的几种情况:
一般使用dfs都是暴力枚举出所有可能情况 然后从中选择最优解或者题目要求解。
1. 比如有1到n个位置，1-n本书
问哪种排列方式是最符合题意的，一般都是用dfs枚举每个位置。
2. 一个有nxn的方格问从左上角走到左下角有多少个路径，可以走上下左右四个方向，不能重复走。那就是dfs每个格子。
3. 树的建立，树的输出
使用bfs的几种情况：
最短路，树的层次遍历。
最短路 从左上角走到右下角问最短路径，只需要bfs就行，第一次走到终点就是最短路。因为是一层递增走的所以第一次到终点就是最短路径
6. 双指针
快慢指针，头尾指针等等
7. 背包
8. Dijkstra
最重要最重要最重要的注意点： 一定要初始化 dist[] g[][]数组!!!!!!!!!
思路步骤：
1. 找到没有使用过距离起点最近的点
2. 将这个点标记使用过
3. 用这个点更新其他点 dist[j] = min(dist[j],dist[t] + g[t][j]);
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int g[N][N];//两点之间的权值
int dist[N];//1到点N的距离
int st[N];//这个点是否用过
int n,m;
int dijkstra()
{
memset(dist,0x3f,sizeof(dist));
dist[1]=0;
for(int i=1;i<=n-1;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if((t==-1||dist[t]>dist[j])&&!st[j])
t=j;
}
st[t]=1;
for(int j=1;j<=n;j++)
{
dist[j]=min(g[t][j]+dist[t],dist[j]);
}
}
return dist[n];
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof(g));
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
int ans=dijkstra();
if(ans==0x3f3f3f3f)
cout<<-1;
else
cout<<ans;
}
9. 链表
复习链表做过的题目 力扣做过的题目翻一翻！！！！
10. 二叉树
https://www.acwing.com/blog/content/39216/
